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 :

    2020-03-24


    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



    An efficient dynamic model for solving the shortest path problem

    Nazemi, Alireza / Omidi, Farahnaz | Elsevier | 2012