Weight Constrained Path Finding with Bidirectional A*

Abstract

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i.e., the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.