A graph algorithm for the time constrained shortest path

Abstract

Highly efficient algorithms for solving the time constrained shortest path problem have been highlighted over the past decades to reduce the cost of vehicle travel in the road network. The paper presents a novel graph algorithm comprising three stages to acquire a time constrained shortest path between any two nodes on the map. In the first stage, the undirected graph is transformed into a directed graph (DT graph) by deleting edges that must not be included in any of the time constrained shortest paths. A variant DT tree with the destination as the root and the source as the leaf is then constructed from the DT graph in the second stage. By finding the minimal difference value between leaves and the root of the variant DT tree, we can eventually obtain a time constrained shortest path from the variant DT tree in the third stage. Experimental results show that our algorithm not only requires less running time than some classical graph algorithms but also can work immediately in the first stage without knowing the information of both the destination and a specific time constraint.

KEYWORDS:

• Time constrained shortest path
• graph algorithm
• DT graph
• variant DT tree

Subject classification codes:

• Computer science
• theory & methods

Acknowledgments

The authors would like to thank the anonymous reviewers for their constructive and insightful comments on this paper.

Author contribution

Conceptualization Ideas: Pan Liu and Wulan Huang; Methodology: Pan Liu and Wulan Huang; Software: Pan Liu; Validation: Pan Liu and Wulan Huang; Formal Analysis: Pan Liu and Wulan Huang; Investigation: Pan Liu; Writing – Original Draft: Pan Liu and Wulan Huang; Writing – Review & Editing: Wulan Huang and Pan Liu; Supervision: Pan Liu.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 A Java class of our algorithm is developed for this experiment and the download link with the password PAN1 is https://pan.baidu.com/s/1kFlM4g4XZnzgwJVD1Uc9pw.

Additional information

Funding

This work was supported in part by National Social Science Fund General Project of China under [grant number 18BTQ058] and the Science and Technology Key Project of Jiangxi Province under [grant number 20142BBE50015].