An Improved Shortest Path Algorithm for Aircraft Routing

Abstract

Thousands of commercial flights are scheduled each day, and the need for flight routes to be as efficient as possible is very important. The cost for the flights has to be as low as possible while still fulfilling and complying with all regulations in safety and other requirements. Aircraft routing is the problem of creating routes for aircraft to operate, subject to constraints. The shortest path problem with resource constraints is commonly used as a subproblem in solution methodologies in order to solve the aircraft routing problem. The aim of this thesis is to implement and evaluate an algorithm called a multidirectional dynamic programming algorithm (MDDPA) in order to solve the shortest path problem with resource constraints. The results from the implementation of MDDPA is compared to the results of another dynamic programming algorithm. The results show that MDDPA in most test cases finds a solution with a cost that is at least as good as the solution found by the other dynamic programming algorithm. However, this usually comes at the expense of longer execution times, where our implementation of MDDPA in most cases takes longer time at finding a solution. In order to gain better results in terms of computing times, we suggest implementing multithreading in MDDPA and analyse how the choice of parameters used in MDDPA could affect the results.