The Classical Vehicle Routing Problem

The first part of the paper introduces the classical Vehicle Routing Problem (i.e., the Capacitated VRP), the corresponding graph theory and mathematical programming models, and the main variants (Distance-Constrained VRP, VRP with Time Windows, VRP with Backhauls, and VRP with Pickup and Delivery). The second part of the paper considers in more details the Capacitated VRP (CVRP). In the CVRP, all the customers to be served correspond to deliveries and their demands are deterministic, known in advance, and may not be split. The available vehicles are identical and based at a single central depot, and only the capacity restrictions on the total demand loaded in the vehicles are imposed. The objective is to minimize the total cost (i.e., a weighted function of the number of routes and their length or travel time) to serve all the customers. The most effective exact (branch-and-bound, branch-and-cut) and approximate (classical heuristic and metaheuristic) algorithms are described. Computational results on a set of benchmark instances are also presented.

Paolo Toth is professor of Combinatorial Optimization at the Faculty of Engineering of the University of Bologna. His main research interests are the design and implementation of effective exact and approximate algorithms for optimization problems (TSP, VRP, Knapsack, Crew Management, Train Timetabling, Packing, ...). He is co-author of the book "Knapsack Problems: Algorithms and Computer Implementations" (J. Wiley, 1990), and co-Editor of the books "Combinatorial Optimization" ( J. Wiley, 1979), "FORTRAN Codes for Network Optimization" (Annals of OR, 1988), "Advanced Methods in Transportation Analysis" (Springer, 1996) and "The Vehicle Routing Problem" (SIAM Monographs, 2002). He is Editor of the Transportation Area of the journal "Operations Research", and Associate Editor of "Transportation Science", "Networks", "Journal of Heuristics", "European Journal of OR", "ITOR", "Discrete Applied Mathematics". He has also worked with AGIP, FS (the Italian Railway Company), Haworth and several Mass Transit Companies on real-world projects. From 1995 to 1996 he was President of EURO (Association of the European OR Societies). He is President of IFORS (International Federation of the OR Societies) for the years 2001-2003. In the year 1998, he was conferred the Harold Larnder Memorial Award (annual Award of the Canadian OR Society), and the EURO Gold Medal (the highest European OR award).