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.