Article ID: | iaor2007939 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 3 |
Start Page Number: | 255 |
End Page Number: | 273 |
Publication Date: | Sep 2006 |
Journal: | Discrete Optimization |
Authors: | Righini Giovanni, Salani Matteo |
Keywords: | networks: path |
When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.