RighSala07 10.1002/net.20212 doi New dynamic programming algorithms for the resource constrained shortest path problem. 2008 The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch-and-price algorithms for vehicle-routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method is a well-known exact dynamic-programming algorithm improved by new ideas, such as bidirectional search with resource-based bounding. The second method consists in a branch-and-bound algorithm, where lower bounds are computed by dynamic-programming with state-space relaxation; we show how bounded bidirectional search can be adapted to state-space relaxation and we present different branching strategies and their hybridization. The third method, called decremental state-space relaxation, is a new one; exact dynamic-programming and state-space relaxation are two special cases of this new method. The experimental comparison of the three methods is definitely favorable to decrement state-space relaxation. Computational results are given for different kinds of resources, arising from the capacitated vehicle-routing problem, the vehicle-routing problem with distribution and collection, and the vehicle-routing problem with capacities and time windows. Righini, G. Salani, Matteo 155-170 Networks 0028-3045 51 3 2008 http://www3.interscience.wiley.com/cgi-bin/jhome/32046 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