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.
|Titolo:||New dynamic programming algorithms for the resource constrained elementary shortest path problem|
RIGHINI, GIOVANNI (Primo)
|Parole Chiave:||Shortest path ; Vehicle routing ; Column generation ; Dynamic programming ; Branch-and-bound.|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||2008|
|Digital Object Identifier (DOI):||10.1002/net.20212|
|Appare nelle tipologie:||01 - Articolo su periodico|