Highlights Two novel algorithms speed up the solution of the All Pair Shortest Paths problem. These algorithms can be parallelized. A fast recalculation of the shortest paths is done if travel times change suddenly. Alternative routes to avoid remaining trapped in the traffic jams are computed.
Abstract Location-based systems can be very helpful to mobile users if they are able to suggest shortest paths to destination taking into account the actual traffic conditions. This would allow to inform the drivers not only about the current shortest paths to destination but also about alternative, timely computed paths to avoid being trapped in the traffic jams signaled by cyber-physical-social systems. To this aim, the paper proposes a set of algorithms that solve very fast the All Pair Shortest Paths problem in both the free flow and congested traffic regimes, for road networks of medium-large size, thus enabling location-based systems to deal with emergencies and critical traffic conditions in city and metropolitan areas, whose transport networks typically range from some hundreds to many thousands of nodes, respectively. The paths to avoid being trapped in the traffic jams are computed by using a simulation of the shockwave propagation, instead of historical data. A parallel version of the algorithms is also proposed to solve the All Pair Shortest Paths problem for metropolitan areas with very large road networks. A time performance analysis of the proposed algorithms for transport networks of various size is carried out.
Algorithms to find shortest and alternative paths in free flow and congested traffic regimes
2016-09-22
29 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Algorithms to find shortest and alternative paths in free flow and congested traffic regimes
Online Contents | 2016
|Shortest paths in traffic-light networks
Online Contents | 2000
|Application of Discrete Fourier Transform to Find Reliable Shortest Paths
Transportation Research Record | 2011
|Application of Discrete Fourier Transform to Find Reliable Shortest Paths
Online Contents | 2011
|Congested Traffic Flow: Observations and Theory
British Library Conference Proceedings | 1999
|