Premium
An exact bidirectional A ⋆ approach for solving resource‐constrained shortest path problems
Author(s) -
Thomas Barrett W.,
Calogiuri Tobia,
Hewitt Mike
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21856
Subject(s) - shortest path problem , computer science , mathematical optimization , path (computing) , exploit , k shortest path routing , constrained shortest path first , dynamic programming , bounded function , resource (disambiguation) , longest path problem , dijkstra's algorithm , algorithm , theoretical computer science , mathematics , graph , mathematical analysis , computer network , computer security , programming language
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.