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

Column Generation Algorithms for Vehicle Routing Problems

Claudio Contardo

In this talk, I will provide a comprehensive literature review of column generation-based algorithms applied to vehicle routing problems. I will focus on some particular variants of this problem, namely the capacitated vehicle routing problem (CVRP), the multiple-depot vehicle routing problem (MDVRP), the capacitated location-routing problem (CLRP) as well as some othe classic variants of the problem. I will discuss mainly exact algorithms, but I will also describe some successful applications of column generation in metaheuristics. Finally, I will discuss some current and future avenues of research.