HISTORY LESSON

50 years of the savings method for vehicle routing problems

By Graham K. Randg.rand@lancaster.ac.uk

The vehicle routing software survey elsewhere in this issue of OR/MS Today (see page 40) surveys packages supplied by vendors, many of which will have used in their algorithms, to a greater or lesser extent, the savings method, which was first published 50 years ago in Operations Research (then an Operations Research Society of America journal but now an INFORMS journal).

The vehicle routing problem (VRP) is easy to state: a set of customers with known location and demand are to be supplied from a depot by delivery vehicles of known capacity subject to all customer demand being met, vehicle capacity not being exceeded and total trip length not exceeding some specified level. The routes begin and end at the depot. A customer’s demand is satisfied by a single vehicle in a single delivery.

The constraints arise because: (i) it is assumed all demand must be met that day, although this is not always the case, (ii) there is a limit on how much product the vehicle can carry, though it is very difficult to define this precisely, and (iii) there may be a legal restriction on the length of the trip in hours. If times of delivery at customers’ locations are also specified, then it is often described as the “vehicle scheduling” problem. An amusing but salutary story of why this may not be a sufficient description of the VRP, in the context of applying the savings method, is provided by Woolsey [1]. Although it can be stated easily, the VRP is known to be NP-hard and therefore it is unlikely that a polynomial-time algorithm will be found for this problem.

The vehicle routing problem was first described by Dantzig & Ramser in 1959 [2], who provided a solution method based, not surprisingly, on linear programming. Five years later, Clarke & Wright [3] developed the heuristic solution method that became known as the savings method. It is also called the Clarke-Wright algorithm, after the authors, but in the early years it was also described as the Wright-Fletcher-Clarke algorithm or the Fletcher-Clarke-Wright algorithm.

Fletcher and Clarke had given a paper at the 1963 conference of the Operational Research Society held in Nottingham, England [4]. Surprisingly, their heuristic obtained a better result than Dantzig and Ramser for the illustrative example that they used [3]. Dantzig and Ramser’s approach looked at linking pairs of customers into a route that were close together, just considering the distance between them, but Clarke and Wright extended this to take into account the reduction in distance obtained by linking two customers into a route, rather than serving them on separate routes. It is interesting to note that this follow-up paper to Dantzig and Ramser’s, published in Management Science, was published in Operations Research. Even more intriguing is why a British practitioner published in an American journal. Of the 600 or so papers published in Operations Research before theirs, only 15 were written by authors with a U.K. address.

Clarke was employed by the Cooperative Wholesale Society in Manchester, England (as was Fletcher), though by the time the paper was published he had moved to work at ICI in Hyde. Wright was at the University of Manchester, then the Manchester College of Science and Technology. It was he who had pointed out Dantzig and Ramser’s paper to Clarke and Fletcher. Fletcher and Clarke gave credit to Wright for developing “almost the same method as the one described in this paper.” The original programs were written in FORTRAN for an IBM 7090 and in AUTOMATH for a Honeywell 800 [4].

The motivation was to improve the distribution of deliveries of Cooperative Wholesale Society vehicles in the English Midlands; 400 customers were served from Manchester [4]. The specific example given in the paper by Clarke and Wright involved 30 customers being served from a depot in Newton Heath, a suburb of Manchester and the original name of the soccer team Manchester United! For a single instance, the current practice used 10 routes and a total of 1,766 miles, which the savings method improved to eight routes and 1,427 miles.

The Clarke-Wright paper concludes with the tantalizing comment that “details of some of these restrictions together with computational methods for a digital computer will be found in a case study which will be published shortly.” There is no evidence of such a paper being published.

Alan Fletcher died in 2010. His daughter gave me an address in Florida for Geoff Clarke, who had moved to the United States many years previously, but no response was received to a letter. Any further information about Clarke or about J.W. (John?) Wright, would be appreciated.

This essay has sought to give insight into the origins of the savings method for the vehicle routing problem 50 years ago. I provide elsewhere [5] details of the subsequent proposed variations to the basic savings formula and other published improvements, mainly to improve the speed of computation. I also chart the role the savings method has played in the investigation of vehicle routing problems with additional constraints. I report some interesting examples of practical applications of the savings method and comment on the use of the savings method in commercial routing packages.

The savings method has had a long and rich life, and it is apparent that this assessment is of a history that is unfinished, with the savings method continuing to make contributions to vehicle routing, and indeed other applications, as it passes its half-century.

Graham K. Rand (g.rand@lancaster.ac.uk) is a senior lecturer in the Department of Management Science, Lancaster University Management School, Lancaster, U.K.

Reverences

  1. Woolsey, R.E.D., 1991, “Being wrong with Clarke and Wright,” Computers & Operations Research, Vol. 18, No. 7, pp. 607-609.
  2. Dantzig, G.B., and Ramser, J.H., 1959, “The truck dispatching problem,” Management Science, Vol. 6, No. 1, pp. 80-91.
  3. Clarke, G., and Wright, J.W., 1964, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, No. 4, pp. 568-581.
  4. Fletcher, A., and Clarke, G., 1963, “A case study in transportation,” paper presented at the Operational Research Society Annual Conference, Nottingham.
  5. Rand, G.K, 2009, “The Life and Times of the Savings Method for Vehicle Routing Problems,” ORiON, Vol. 25, No. 2, pp. 125-145.