Hybrid Discrete Optimization for Route Planning and Scheduling

Abstract

Combinatorial optimization is intimately related to various scientific disciplines that originated from different historical roots, such as constraint programming and satisfiability. Despite their differences in origin, the methods developed within these fields exhibit many similarities while simultaneously offering complementary strengths and weaknesses, which suggests their integration for solving difficult optimization problems. This thesis addresses three real-world applications by integrating combinatorial optimization techniques with methods from adjacent disciplines, specifically constraint programming, satisfiability, and automata theory.

First, the logic-constrained shortest path problem (LCSPP) is studied. In this variant of the shortest path problem, only paths satisfying general logical constraints, expressed as propositional formulae on arcs, are admissible. A branch-and-bound method for the LCSPP is developed that incorporates domain reduction techniques from the satisfiability community. The practical relevance of the algorithm is demonstrated by solving a flight planning problem that takes traffic flow restrictions imposed by air traffic control into account. Compared to a mixed-integer programming solver, the hybrid approach achieves a run-time improvement of over two orders of magnitude.

Second, the first exact solver for price-optimal routing in public transit that is able to represent intricate real-world fare structures is presented. The solver is based on the notion of conditional fare networks, which are hybrids of language and resource constraints. Based on this model, the multi-objective RAPTOR algorithm is adapted for price-optimal route planning. This result is further generalized to a class of shortest path problems, in which paths are evaluated based on a general partial order.

Finally, this thesis examines a scheduling problem arising in cargo handling in hub airports. Here, logic-based Benders decomposition is employed to integrate mixed-integer programming and constraint programming, achieving computation times that are less than half of those required by a mixed-integer programming approach.