Solve the Constrained Shortest Path Problem Using an Improved A* Algorithm
Nan Xu, Xiang Wu, Miaomiao Zhang, Xianying Chang · 2024
Motivated by the practical aircraft routing problem of civil flight planning, we proposed an improved A* algorithm to address the shortest path problem with exclusionary or inclusionary constraints take the forms of node Y is forbidden or compulsory if node X has been passed through. The improved A* algorithm prioritizes expanding the partial paths with the shorter total distance after passing through all known compulsory nodes through the current node, which effectively guides the search directions and greatly improves the search efficiency.