This paper seeks to investigate the performance of two different dynamic programming approaches for shortest path problem of transportation road network in different context, including the Bellman’s dynamic programming approach and the Dijkstra’s algorithm. The procedures to implement the two algorithms are discussed in detail in this study. The application of the Bellman’s approach shows that it is computationally expensive due to a lot of repetitive calculations. In comparison, the Dijkstra’s algorithm can effectively improve the computational efficiency of the backward dynamic programming approach. According to whether the shortest path from the node to the original node has been found, the Dijkstra’s algorithm marked the node with permanent label and temporal label. In each step, it simultaneously updates both the permanent label and temporal label to avoid the repetitive calculations in the backward dynamic programming approach. In addition, we also presented an algorithm using dynamic programming theory to solve the K shortest path problem. The K shortest path algorithm is particular useful to find the possible paths for travelers in real-world. The computational performance of the three approaches in large network is explored. This study will be useful for transportation engineers to choose the approaches to solve the shortest path problem for different needs.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application


    Weitere Titelangaben:

    Lect. Notes Electrical Eng.


    Beteiligte:
    Wang, Wuhong (Herausgeber:in) / Baumann, Martin (Herausgeber:in) / Jiang, Xiaobei (Herausgeber:in) / Li, Xuan (Autor:in) / Ye, Xiaofei (Autor:in) / Lu, Lili (Autor:in)


    Erscheinungsdatum :

    24.03.2020


    Format / Umfang :

    20 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application

    Li, Xuan / Ye, Xiaofei / Lu, Lili | British Library Conference Proceedings | 2020



    Solving Fuzzy Shortest Path Problem with Decision Maker’s Perspective

    Singh, Vishnu Pratap / Sharma, Kirti / Jain, Udit | Springer Verlag | 2021