## 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.

Author: | Arno Kühner |
---|---|

Document Type: | Master's Thesis |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |

CCS-Classification: | J. Computer Applications |

Granting Institution: | Freie Universität Berlin |

Advisor: | Ralf Borndörfer, Niels Lindner, Marco Blanco |

Year of first publication: | 2021 |