Algorithms for Shortest Path Tour Problem

Carpooling route planning becomes an important problem with the growth of low-carbon traffic systems. When each passenger has multiple potential pick-up/drop-off locations, the problem will be more challenging. In the paper, we discussed a simplified carpooling route planning problem, namely the Shortest Path Tour Problem (SPTP), whose aim is to find a single-origin single-destination shortest path through an ordered sequence of disjoint node subsets. We propose Stage Dijkstra and Global Dijkstra algorithms to find the optimal shortest path, with the time complexity of O ( l ( n + m ) log ⁡ n ) and O ( l ( n + m ) log ⁡ ( l n ) ) respectively, where l represents the number of node subsets. To the best of our knowledge, O ( l ( n + m ) log ⁡ n ) is the best time complexity of the exact algorithms for SPTP. Besides, the Stage Dijkstra and Global Dijkstra algorithms both have the linear space complexity, which is highly suitable for resource-constrained environments. Experiments conducted on large-scale road networks and synthetic datasets demonstrate the effectiveness and efficiency of our proposed algorithms in terms of running time and memory consumption.

Authors

• Yucen Gao Shanghai Key Laboratory of Scalable Computing and Systems, School of Computer Science, Shanghai Jiao Tong University, China
• Zhuoran Li IIIS, Tsinghua University
• Jingyu He
• Jun Fang
• Hui Gao Tianjin University
• Xiaofeng Gao Shanghai Jiao Tong University
• Guihai Chen Nanjing University

Keywords

• Carpooling route planning
• Shortest path tour problem
• Large-scale road network
• Stage & global Dijkstra