Algorithms to find shortest and alternative paths in free flow and congested traffic regimes. (December 2016)

• Record Type: Journal Article
• Authors: Faro, Alberto; Giordano, Daniela
• Is Part Of: Transportation research. Volume 73(2016)
• Page Start: 1
• Page End: 29
• Publication Date: 2016-12
• Subjects: All Pair Shortest Paths (APSP) -- Single Source Shortest Paths (SSSP) -- Ubiquitous information systems -- Traffic emergency assistance; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2016.09.009
• Languages: English
• ISSNs: 0968-090X

Abstract

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.