Groupe d’études et de recherche en analyse des décisions

G-2007-59

What You Should Know about the Vehicle Routing Problem

In the Vehicle Routing Problem (VRP), the aim is to design a set of m minimum cost vehicle routes through n customer locations, so that each route starts and ends at a common location and some side constraints are satisfied. Common application arise in newspaper and food delivery, and in milk collection. This paper summarizes the main known results for the classical VRP in which only vehicle capacity constraints are present. The paper is structured around three main headings: exact algorithms, classical heuristics, and metaheuristics.

, 22 pages