10. Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy, and Newspaper Industries

This paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal…. A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may be readily performed by hand or by an automatic digital computing machine. G.B. Dantzig and J.H. Ramser, The Truck Dispatching Problem, Management Science, October 1959 10.1 Introduction It has been nearly 40 years since Dantzig and Ramser first described and formulated the VRP and then solved a problem with 12 delivery points and one terminal. Theory, practice, and computer hardware and software have come a long way since then, so that today vehicle routing is considered one of the great success stories of operations research. In the last 40 years, there have been hundreds of successful applications in dozen of industries in numerous countries. The successful implementation of vehicle routing software has been aided by the exponential growth in computing power since 1950, the emergence of accurate and sophisticated geographic information systems (GIS) technology, and easy-to-use interface software that enables the customer to integrate routing with other key functions such as billing, inventory tracking, and forecasting (see Hall and Partyka [43]).