89302 RighSala06 10.1016/j.disopt.2006.05.007 doi TRANSP-OR-ARTICLE-2006-021 Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints 2006 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. Righini, G. Salani, Matteo 255-273 Discrete Optimization 1572-5286 3 3 2006 http://www.elsevier.com/locate/disopt TRANSP-OR EPFL
Fatal error: Uncaught Error: Call to undefined function ereg() in E:\Inetpub\transp-or.epfl.ch\web\oneMarcXML.php:230 Stack trace: #0 {main} thrown in E:\Inetpub\transp-or.epfl.ch\web\oneMarcXML.php on line 230