2018/10/25 by Barrett W. Thomas, Tobia Calogiuri, Mike Hewitt · 1 citation
Engineering · Social Sciences · #Infrastructure Maintenance and Monitoring #Transportation Planning and Optimization #Vehicle Routing Optimization Methods
paper · doi:10.1002/net.21856
crossref issued 2018/10/25 · crossref published 2018/10/25 · crossref published-online 2018/10/25 · openalex publication_date 2018/10/25 · crossref created 2018/10/25 · crossref published-print 2019/03/01 · crossref deposited 2023/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21 · crossref indexed 2026/08/01
Bidirectional dynamic programming is an algorithm that searches for paths in a network from both the starting and the ending nodes that optimize a given objective function. In recent years, bidirectional dynamic programming has been shown to be an effective means for solving resource‐bounded shortest path problems. While many researchers have observed that bidirectional A ⋆ approaches perform poor computationally, we exploit the presence of resource constraints to overcome the source of these computational challenges. Our main contribution in this paper is an exact bidirectional A ⋆ algorithm for resource‐constrained shortest path problems (RCSPPs) that is capable of solving large‐sized instances that challenge the state‐of‐the‐art in the literature. We also analyze, both computationally and theoretically, the sensitivity of the algorithm's performance to its inputs.