Milk Collection: How to Route and Assign Milk Collection Lorries to Farms

Problem Statement

A small milk processing company is committed to collecting milk from 20 farms and taking it back to the depot for processing.^[24] The company has one tanker lorry with a capacity for carrying 80,000 litres of milk. Eleven of the farms are small and need a collection only every other day. The other nine farms need a collection every day. The positions of the farms in relation to the depot (numbered 1) are given in Table 23.1 together with their collection requirements.

Find the optimal route for the tanker lorry on each day, bearing in mind that it has to (i) visit all the ‘every day’ farms, (ii) visit some of the ‘every other day’ farms, and (iii) work within its capacity. On alternate days it must again visit the ‘every day’ farms but also visit the ‘every other day’ farms not visited on the previous day.

For convenience a map of the area considered is given in Figure 23.1.

Table 23.1:

	Position 10 miles:
				Collection requirement
Farm	East	North	Collection frequency	(1000 litres)
1 (Depot)	0	0	—	—
2	$-3$	3	Every day	5
3	1	11	Every day	4
4	4	7	Every day	3
5	$-5$	9	Every day	6
6	$-5$	$-2$	Every day	7
7	$-4$	$-7$	Every day	3
8	6	0	Every day	4
9	3	$-6$	Every day	6
10	$-1$	$-3$	Every day	5
11	0	$-6$	Every other day	4
12	6	4	Every other day	7
13	2	5	Every other day	3
14	$-2$	8	Every other day	4
15	6	10	Every other day	5
16	1	8	Every other day	6
17	$-3$	1	Every other day	8
18	$-6$	5	Every other day	5
19	2	9	Every other day	7
20	$-6$	$-5$	Every other day	6
21	5	$-4$	Every other day	6

Figure 23.1:

^[24]Reproduced with permission of John Wiley & Sons Ltd. (Williams 1999, pp. 255–256).