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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Algorithms to find shortest and alternative paths in free flow and congested traffic regimes


    Beteiligte:
    Faro, Alberto (Autor:in) / Giordano, Daniela (Autor:in)


    Erscheinungsdatum :

    2016-09-22


    Format / Umfang :

    29 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Shortest paths in traffic-light networks

    Chen, Yen-Liang | Online Contents | 2000


    Application of Discrete Fourier Transform to Find Reliable Shortest Paths

    Wu, Xing / Nie, Yu (Marco) | Transportation Research Record | 2011



    Congested Traffic Flow: Observations and Theory

    Kerner, B. S. / National Research Council | British Library Conference Proceedings | 1999