Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE: A General Heuristic for Vehicle Routing Problems

CONFÉRENCIER: Stefan Ropke, Computer Science Department, University of Copenhagen, Denmark

DATE et ENDROIT: Jeudi 30 septembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE: Jean-François Cordeau (340-6278)

RÉSUMÉ: This talk presents a metaheuristic for the Pickup and Delivery Problem with Time Windows (PDPTW). The metaheuristic employed is an extension of the Large Neighborhood Search (LNS) method proposed by Shaw (1998). We denote this extension the Adaptive Large Neighborhood Search (ALNS). In the talk it is shown how a number of well known variants of the vehicle routing problem can be modeled and solved as PDPTWs. This allows us to solve many types of vehicle routing problems using the proposed heuristic. The list of problems solved by the heuristic includes the Capacitated Vehicle Routing Problem, the Vehicle Routing Problem with Time Windows, the Vehicle Routing Problem with Backhauls, the Multi Depot Vehicle Routing Problem, the Vehicle Routing Problem with Simultaneous Pickup and Delivery. In total 12 variants of the Vehicle Routing Problem from the literature have been considered. For most of these problems the approach yields a heuristic that is able to match or improve upon the solution quality reported in the literature without any problem-specific tuning. Finally it is explained how the ALNS metaheuristic can be used to solve problems outside the Vehicle Routing domain, and we outline the problem types it would be well suited for. The talk is based on joint work with David Pisinger.