Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

0.00 Avg rating0 Votes
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: ,
Keywords: networks: path
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.