Symmetry helps : bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
Articolo
Data di Pubblicazione:
2006
Citazione:
Symmetry helps : bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints / G. RIGHINI, M. SALANI. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - 3:3(2006), pp. 255-273.
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Column generation; Dynamic programming; Shortest path; Vehicle routing
Elenco autori:
G. RIGHINI, M. SALANI
Link alla scheda completa: