A Heuristic Algorithm to Solve the Shortest Path Problem with Constraints

In this paper, we proposed a heuristic algorithm to solve the shortest path problem with additional exclusionary or inclusionary restrictions inspired by the practical flight planning problem. The optimal path without considering the additional restrictions is found and a repairing algorithm is applied on it to repair the path to meet the restrictions if necessary and then an iterative heuristic algorithm is applied to optimize the solutions until the preset termination criteria is met. The computational results show that the proposed heuristic algorithm has good performance in both efficiency and quality.