New dynamic programming algorithms for the resource constrained elementary shortest path problem

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‐kn...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2008-05, Vol.51 (3), p.155-170
Main Authors: Righini, Giovanni, Salani, Matteo
Format: Article
Language:English
Subjects:
Applied sciences
branch-and-bound
column generation
dynamic-programming
Exact sciences and technology
Logistics
Operational research and scientific management
Operational research. Management science
shortest path
vehicle-routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008
ISSN:0028-3045
1097-0037
DOI:10.1002/net.20212