Open Access

Michael Brückner

• This thesis investigates the shortest path problem with pair constraints or the pair constraint problem (PCP) for short. We consider two types of pair constraints, namely forbidden pairs and binding pairs consisting of two distinct vertices each. A path respects a forbidden pair if it uses at most one of the two vertices and it respects a binding pair (x,y) if it uses also y, if x is used. Within this thesis, we bring together and compare several formulations and variants of the pair constraint problem and their complexities. We also collect existing recursive algorithms and present their running times. Most of the presented contributions only consider forbidden pairs. We introduce a new recursive algorithm also handling binding pairs and prove its theoretical complexity of O(n^4). We implemented the algorithm and tested it on real-world instances provided by Lufthansa Systems AG. Therefore we needed to develop a heuristic translating the real-world data into an instance of the shortest path problem with pair constraints. This heuristic is presented as well as all computational results. In Chapter 4, we start investigating the associated polytope of an integer program formulation of the shortest path problem with pair constraints. For the case of one forbidden or binding pair, we find a complete linear description of the associated polytope. We prove that the number of facets grows exponentially in |V| even in these simple cases. However, separation is still possible in polynomial time. The complete linear description can be extended to the case of contiguously disjoint pairs.