An exact bidirectional A⋆ approach for solving resource‐constrained shortest path problems. Issue 2 (25th October 2018)

• Record Type: Journal Article
• Authors: Thomas, Barrett W.; Calogiuri, Tobia; Hewitt, Mike
• Is Part Of: Networks. Volume 73:Issue 2(2019)
• Page Start: 187
• Page End: 205
• Publication Date: 2018-10-25
• Subjects: bidirectional -- Dijkstra -- dynamic programming -- heuristic search -- resource constraints -- shortest paths; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21856
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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.