CIRRELT, Canada
August 09, 2012, 11:00, Room GC B3 424 (click here for the map)
The multi-trip vehicle routing problem with time windows is a variant of the classical vehicle routing problem with time windows, where a vehicle can perform several trips during the planing time horizon. Multiple trips are beneficial to the carrier by limiting the number of vehicles and drivers necessary to the deliveries, especially in the cases where vehicle capacities, distances or time constraints naturally imply short distribution routes. However, this feature generate many combinatorial issues due to the mutual exclusion constraints that appear between two trip performed by the same vehicle. We propose a set covering formulation, where variables represent trips, and an exact method based on Branch and Price scheme to solve it. Computational results on Solomon's benchmarks evaluate the method on small to middle-sized instances.
Florent Hernandez is a Postdoctoral reseacher in Operation Research and transportation science at Ecole polytechnique de Monr�al and CIRRELT, Canada, since october 2011. He recieved his Ph.D thesis in Computer science from the Universit� Montpellier 2, France, in november 2010. Between these dates, he was teaching assistant at the Universit� Montpellier 2. Even if his PhD research topic was focused on designing a Branch and Price algorithm to solve a spraying agricultural problem, his main research topic is more generally expanded to the combinatorial optimization methods used in transportation science.