An Improved Shortest Path Algorithm for Aircraft Routing
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2022
Författare
Thorén, Samuel
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Multidirectional dynamic programming algorithm (MDDPA), Dynamic programming, Shortest path problem with resource constraints, Aircraft routing, Column generation