Dynamic programming algorithms for the elementary shortest path problem with resource constraints
Articolo
Data di Pubblicazione:
2004
Citazione:
Dynamic programming algorithms for the elementary shortest path problem with resource constraints / G. Righini, M. Salani. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - 17:(2004), pp. 247-249. [10.1016/j.endm.2004.03.047]
Abstract:
When vehicle routing problems with additional constraints (e.g. capacities or time windows) are solved via column generation and branch-and-price, it is common that the pricing problem requires
the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the nodes. The pricing problem is usually solved via dynamic programming in two possible ways: requiring elementary paths or allowing paths with cycles. We experimentally compare these two strategies and we evaluate the effectiveness of some algorithmic ideas to improve their performance.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Shortest path ; vehicle routing ; dynamic programming ; column generation
Elenco autori:
G. Righini, M. Salani
Link alla scheda completa: