Chapter 1 Vehicle routing

This chapter presents the most important algorithms that have been developed for model of the vehicle routing problem. However, before plunging into the mathematical development, it will be helpful to consider some examples of vehicle routing problems and various practical issues that arise in the use of vehicle routing models. Vehicle routing problems are all around us in the sense that many consumer products such as soft drinks, beer, bread, snack foods, gasoline and pharmaceuticals are delivered to retail outlets by fleets of trucks whose operation fits the vehicle routing model. Other examples of vehicle routing problems include the delivery of liquefied industrial gases and the collection of milk from farms for transportation to a processing center. Many companies have reported successful implementation of mathematical algorithms to optimize trucking operations including Air Products and Chemicals, Chevron, DuPont, Edward Don and Company etc. Two approaches have been taken to providing geographic information. The first approach is easy to implement and thus preferred if it is accurate enough. It consists of assigning coordinates to each customer and assuming that the travel distance between customers is the Euclidean distance between their coordinate pairs. Cost is taken to be proportional to distance. The distance is often scaled up by a factor to compensate for roads that deviate from a straight-line path between customers. The second approach obtains travel distances by applying a shortest route algorithm to a computerized network model of the road system.