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

You are here: Homepage > Search

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

Li, Xuan / Ye, Xiaofei / Lu, Lili

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.