The article is based on a talk given by Professor Paul Williams of Southampton University to the Mathematical Programming Study Group. Collecting Milk from Farms Professor Williams described the work which he had been doing with Martin Butler and Leslie-Ann Yarrow to determine routes for tankers collecting milk from farms in an area to the north of Dublin. Large farms have their milk collected every day while smaller ones only need collections every other day. The problem is to find the shortest two routes for the tanker drivers, one for "red" days in a 2-week cycle (Monday, Wednesday, Friday, ...) and one for "blue" days (Tuesday, Thursday, Saturday, ...) such that the large farms are visited on both the red and the blue days while the small ones are visited on either the red or the blue days. Vehicle Routing Problems The problem is clearly related to the standard Vehicle Routing Problem (otherwise known as the Travelling Salesman Problem, TSP), but it has the additional ingredient that each of the small farms must be allocated either to the red days or the blue days. This makes it considerably more difficult than the standard problem. There were 42 farms which means that whereas there are 1.67 x 10^{49} possible routes for the standard TSP there are 4.27 x 10^{62} possibilities in this case. Despite this, the problem was solved to proven optimality! Heuristic Solutions When Professor Williams gave the problem to his MSc class to solve using heuristics, they came up with a variety of solutions, ranging from 250 miles to 175 miles. In retrospect, the 175 mile solution was amazingly good, being better than could be obtained using many adaptations to this problem of well-known vehicle routing heuristics. There also proved to be a strong correlation between the distances which the students found and their results at the end of the course. The 175-mile solution is shown in Figure 1. The farms marked with a '+' must be visited every day while those with a '*' must be visited every other day. One day's routes is shown in plain lines while the other is shown in dotted lines. Figure 1: Initial 175-mile Route If the problem had been a commercial one, it is likely that the 175-mile solution would have been accepted. However, this was for a PhD thesis and the aim was to establish, if possible, what the optimum solution was. In so doing, one obtains information about the quality of the heuristics which are typically used in solving such problems. For some problems (such as the standard TSP), it is now possible to use advanced integer programming techniques to find solutions which are either the proven optimum or which are substantially better than could be obtained using heuristics. In this way, such research feeds through into commercial practice. Solving the Problem as an LP The first stage in solving the problem was to pose it as a Linear Programming problem and find the continuous solution. The problem is formulated as follows: Minimise total distance travelled subject to "every day" farms must be visited twice on both red and blue tours; "every other day" farms must be visited once on red and blue tours; tanker movements into a farm must equal tanker movements out of the farm. This took 2 seconds to solve and produced a solution with a distance of 157 miles. As is typical with such a formulation, the solution is not really a solution at all. What happens is that the model recommends many disconnected subtours and some of these involve fractional movements, i.e. a farm is visited half on red days and half on blue days. First Integer "Solutions" An attempt was made to find an integer feasible solution at this point by just using the standard integer programming algorithm in the package (XPRESS). It was not expected that this would be any good (because the optimum solution to the model as posed to the package would be to have many disconnected subtours). It was, nonetheless, surprising that the package should spend 3 weeks without finding a single integer feasible solution before being put out of its misery. This should really serve as a warning against naive use of integer programming. Tightening the Formulation The next stage was to tighten the mathematical formulation so that there was less "cheating" possible in the solutions found. This involved adding constraints of the form: tanker movements into or out of an "every other day" farm can only occur to the extent that that farm is being visited on that day. There were 1189 such constraints, which it would have been quite practicable to add directly to the LP matrix. However, the XPRESS package permits classes of constraints to be defined which are not used initially but which are tested after the initial LP solution has been found to see if any are violated, in which case they are added to the problem and the matrix is re-solved. It turned out that 61 of these variable upper bound (VUB) constraints were needed, resulting in a revised LP solution of 169.65 miles. The solution still contained disconnected subtours and fractional visits, but it was getting much closer to the known feasible solution length of 175 miles. If the problem was passed over to the integer programming code, it took 40 minutes to find an integer feasible solution (no fractional visits) but this of course contained disconnected subtours. Reaching Optimality At this point human intervention was used to identify disconnected subtours and manually add "subtour elimination constraints" to the formulation. These, and the related "comb constraints" are well-known but variants were required for the two-day aspects of this problem. Where TSPs are being solved routinely, software is used to identify the subtours and combs automatically, but this was not done here. Fifteen subtour elimination constraints and 3 comb constraints were added and the problem re-solved, with more VUB constraints being added. This yielded an LP solution of 171.15 miles. A further 3 subtours and 2 combs were identified and their constraints added, which with further VUB constraints produced an LP solution of 172.08 miles. The integer programming algorithm was invoked and found an integer feasible solution with a value of 172.5 miles which it proved to be the global optimum in 13 seconds. On inspection it was found not to contain any subtours or other defects. It is therefore known to be an optimum solution. It is shown at Figure 2. Figure 2: Optimal 172.5-mile Route The end result, therefore, was to improve on the best heuristic solution by 2.5 miles. Not much, you might think, for all that effort; and possibly (probably) irrelevant to the real tanker driver who has his own reasons for selecting his route. However, the principal researcher, Martin Butler, is now using the knowledge gained to tackle the real problems of milk tanker drivers around the U.K. and Ireland. And in the audience at the Study Group meeting was the man from the Milk Marketing Board who has been using a commercial vehicle routing package to solve very similar problems. Related articles include Farm Management by MP and What can Integer Programming Do?. To find other articles, refer to the MP in Action page. |
MP in Action > Software >