A dynamic single-source single-destination shortest path problem on a directed graph is considered. The edge lengths are not constant, but they change as a function of time in a random way. The problem is modeled as a multi-stage decision process and solved by using a re-optimization method that solves the ι.th stage using the results of the solution of the (ι-1).th one. An algorithm, called the dynamical shortest path algorithm, is proposed for solving the global problem either finding a solution or detecting that the problem is infeasible and an upper bound on its running time is found. Numerical examples are reported in order to show the effectiveness of the method.
Shortest paths in randomly time varying networks / Festa, Paola; R., Cerulli; G., Raiconi. - In: IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS. - ISSN 1524-9050. - (2001), pp. 854-859. [10.1109/ITSC.2001.948772]
Shortest paths in randomly time varying networks
FESTA, PAOLA
;
2001
Abstract
A dynamic single-source single-destination shortest path problem on a directed graph is considered. The edge lengths are not constant, but they change as a function of time in a random way. The problem is modeled as a multi-stage decision process and solved by using a re-optimization method that solves the ι.th stage using the results of the solution of the (ι-1).th one. An algorithm, called the dynamical shortest path algorithm, is proposed for solving the global problem either finding a solution or detecting that the problem is infeasible and an upper bound on its running time is found. Numerical examples are reported in order to show the effectiveness of the method.File | Dimensione | Formato | |
---|---|---|---|
a2_IEEE_randomlyvaring.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Accesso privato/ristretto
Dimensione
232.04 kB
Formato
Adobe PDF
|
232.04 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.