Quicklinks:
What can O.R. do for you?
O.R. IN EVERYDAY LIFE

O.R. Inside Your Pint of Milk

A dairy company has a milk tanker which collects milk from 46 farms. The bigger farms have to be visited every day, whilst the smaller ones are visited every other day. Alternate days are designated as either A or B days, half the smaller farms having a collection on A days and the other half on B days. On any day, the tanker starts from the dairy, pays one visit to each of the farms due for a collection that day, and finishes up back at the dairy. The problem is to find the shortest route for the tanker to take, both on an A day and on a B day, given that the dairy company can choose which farms to allocate to A days and which to B days.

Take away the complication of the A and B days, and this would be an example of a famous and frequently encountered problem known as the travelling salesman problem (TSP). The trouble with the TSP is that, except for very small problems, there are an enormous number of possible routes to check through in order to find the best one. With 46 collection points, as in this case, the number of possible routes is, in fact, 16 700 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000, which is quite a lot. Add in the complication of the A and B days, and the number of routes rises to 42 700 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000, which is quite a lot more. Because of the complexity of the problem, trial and error or common sense are not powerful enough to give an efficient solution - it's all too easy to come up with what looks like a sensible route that is, in fact, twice as long as it need be. Clearly, we need some O.R. inside!

Because the problem is mathematically troublesome, O.R. tends to use heuristics to solve problems like the TSP. Heuristics are procedures, often based on real-life analogies such as mimicking the way an ant colony finds the 'best' route to a food source, which have been found to give good solutions in many situations, but which do not necessarily deliver what is strictly 'the best' solution. In this case a number of heuristics were tried, giving total travelling distances of between 250 and 175 miles, showing that even with the aid of a sophisticated heuristic you may not get very close to the best solution. But without the aid of a heuristic, you would be likely to come up with an answer well in excess of 300 miles.

In this case, though, we know that the best heuristic did very well indeed, because a university researcher spent rather a lot of time working out what the best possible solution was, and discovered that it was 172.5 miles. So, thanks to the O.R. inside, the dairy had a solution as near to the best as made no practical difference.

Banner Watch our 'What is O.R. movie' Download our Guide to O.R.