We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.
Shortest Paths in Piecewise Continuous Time-Dependent Networks / Dell'Amico, Mauro; Iori, Manuel; Pretolani, Daniele. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 36:6(2008), pp. 688-691. [10.1016/j.orl.2008.07.002]
Shortest Paths in Piecewise Continuous Time-Dependent Networks
DELL'AMICO, Mauro;IORI, MANUEL;PRETOLANI, Daniele
2008
Abstract
We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.File | Dimensione | Formato | |
---|---|---|---|
OPERES5180.pdf
Accesso riservato
Tipologia:
Versione pubblicata dall'editore
Dimensione
585.68 kB
Formato
Adobe PDF
|
585.68 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris