G-2009-81
Enhanced Branch-and-Price-and-Cut for Vehicle Routing with Split Deliveries and Time Windows
Claudia Archetti, Mathieu Bouchard et Guy Desaulniers
In this paper, we study the split delivery vehicle routing problem with time windows SDVRPTW that is a variant of the well-known vehicle routing problem with time windows VRPTW where each customer can be served by more than one vehicle. We propose enhancement procedures for the exact branch-and-price-and-cut algorithm recently developed by Desaulniers (2009) for the SDVRPTW. In particular, we introduce a tabu search algorithm to solve the column generation subproblem, new classes of valid inequalities, and a new separation algorithm for the k-path inequalities. Computational results show the effectiveness of the proposed enhancements.
Paru en décembre 2009 , 26 pages