Reliable lifelong planning A*: Technique for re-optimizing reliable shortest paths when travel time distribution updating

Wenxin Teng and Bi Yu Chen

Transportation Research Part E: Logistics and Transportation Review, 2024, vol. 188, issue C

Abstract: Re-optimization technique is an efficient approach for solving the shortest path problem in dynamic deterministic networks, where link travel times are updated in real-time. However, existing re-optimization techniques, built on the assumption that link travel times are deterministic, cannot be used to solve reliable shortest path problems in real road networks with noticeable levels of travel time uncertainties. This study proposes a novel re-optimization technique, named reliable lifelong planning A* (RLPA*), for re-optimizing reliable shortest path finding results in dynamic stochastic networks, where link travel time distributions are updated in real-time. The proposed RLPA* technique can efficiently determine the optimal solution in dynamic stochastic networks by reusing path search results produced in the previous time instance. The proposed RLPA* technique is further utilized to solve the K reliable shortest paths problem, which is regarded as a series of reliable shortest path searches in a dynamic stochastic network. To validate the proposed algorithms, a comprehensive case study using real traffic data is conducted. The case study results demonstrated that the proposed algorithms significantly outperform the corresponding state-of-the-art algorithms on all testing networks.

Keywords: Re-optimization technique; Reliable path finding problems; K reliable shortest paths problem; Transport informatics; Travel time uncertainty (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554524002266
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:188:y:2024:i:c:s1366554524002266

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2024.103635

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().