8414
2021
eng
masterthesis
0
--
--
--
Shortest Paths with Boolean Constraints
For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.
publish
Ralf Borndörfer
Arno Kühner
Niels Lindner
Niels Lindner
Marco Blanco
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
MODAL-Gesamt
Network Optimization
MODAL-MobilityLab
Freie Universität Berlin