Journal article
An exact bidirectional A⋆ approach for solving resource‐constrained shortest path problems
Networks, Vol.73(2), pp.187-205
03/2019
DOI: 10.1002/net.21856
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.
Details
- Title: Subtitle
- An exact bidirectional A⋆ approach for solving resource‐constrained shortest path problems
- Creators
- Barrett W. Thomas - University of IowaTobia Calogiuri - University of SalentoMike Hewitt - University of Chicago
- Resource Type
- Journal article
- Publication Details
- Networks, Vol.73(2), pp.187-205
- Publisher
- John Wiley & Sons, Inc
- DOI
- 10.1002/net.21856
- ISSN
- 0028-3045
- eISSN
- 1097-0037
- Number of pages
- 19
- Language
- English
- Date published
- 03/2019
- Academic Unit
- Bus Admin College; Business Analytics
- Record Identifier
- 9984380454402771
Metrics
3 Record Views