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.
|Titolo:||Dynamic programming algorithms for the elementary shortest path problem with resource constraints|
|Parole Chiave:||Shortest path ; vehicle routing ; dynamic programming ; column generation|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||10.1016/j.endm.2004.03.047|
|Appare nelle tipologie:||01 - Articolo su periodico|