Institutskolloquium

Gilbert Laporte: "Metaheuristics for the Vehicle Routing Problem"

Dienstag, 19. Mai 2009 16.15 Uhr
Gebäude 368, Raum 432

The Vehicle Routing Problem (VRP) consists of designing optimal delivery or collection routes through a set of geographically scattered customers. In the classical version, a fleet of identical vehicles is based at a depot and the routes must satisfy side constraints, typically on their total demand and on their length. The VRP was introduced by Dantzig and Ramser in 1959. It is NP-hard and exact algorithms can only solve relatively small instances. Heuristics are by far the preferred solution methodology in practice. Among these, several metaheuristics developed over the past fifteen years, such as tabu search, memetic algorithms, GRASP, etc., have been highly successful in solving large instances of the VRP. In this talk I will provide an overview of the best heuristics and metaheuristics for the VRP.


Gilbert Laporte is Professor of Operations Research at HEC Montréal, Director of the Canada Research Chair in Distribution Management, and adjunct Professor at Molde University College, the University of Bilkent, the University of Alberta and Université Laval.
He has authored or coauthored 15 books, as well as more than 300 scientific articles in combinatorial optimization, mostly in the areas of vehicle routing, location and timetabling.