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 /spl iota/.th stage using the results of the solution of the (/spl iota/-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
2001-01-01
624743 byte
Conference paper
Electronic Resource
English
Shortest Paths in Randomly Time Varying Networks
British Library Conference Proceedings | 2001
|Shortest paths in traffic-light networks
Online Contents | 2000
|British Library Conference Proceedings | 2011
|Fuzzy Dissimilar Shortest Paths in Urban Traffic Networks
British Library Conference Proceedings | 2006
|Shortest Paths in Stochastic Time-Dependent Networks with Link Travel Time Correlation
Online Contents | 2013
|