ODEA

Minimum cost disjoint paths under arc dependences. Algorithms for practice. In this thesis, we develop a unified algorithmic framework for Minimum Cost Disjoint Paths Problems. These problems arise in a variety of applied contexts, in particular telecommunication networks and automated vehicle routing. The main motivation typically is the desire to plan a structure which is safe in a certain way. In telecommunications, survivability of networks is a paramount issue. In guiding of cargo vehicles, it is prevention of collisions. We have taken the initial impulse for our research from a project with T-Systems Darmstadt. Planners needed a tool to support the pricing of so-called Virtual Private Networks. We developed a software called ODEA to aid their processes. It was also applied to realistic instances from a logistics project with Containerterminal Altenwerder at Hamburg harbour. Disjoint Paths Problems are posed in the form of a directed or undirected graph with nonnegative arc/edge costs and a set of node pairs in it. A feasible solution is a set of connecting paths, one for each node pair, such that two conditions are satisfied: 1. all paths are pairwise nonintersecting in a given sense, 2. the total cost of the solution is a minimum among all solutions. This problem is known to be NP-hard even in very restricted cases. Literature reports about special cases allowing polynomial time algorithms as well as heuristic approximation schemes. There is an apparent lack on exact approaches suitable for deployment in broad purpose software. Our work addresses this gap. We present an integer programming model flexible enough to accommodate several disjointness modes, yet practical enough to allow for efficient algorithmic treatment of real-world instances. We introduce a new modelling technique called arc dependences. It generalizes the traditional notion of disjointness which differentiates between arc-, edge- or node disjointness only. With its help, planners can restrict their work to specially constructed abstractions of the input graph, comprising significantly less data without losing the essence needed for safety. While the main focus of this model lies on paths in the graph, we also investigate an alternative featuring so-called star flows. The main part of this book describes in detail the methods developed for encoding in our software. We devise a Branch-and-Bound scheme and fill in the contents for its functional ingredients: branching strategies, structural pruning, upper and lower cost bounds. This includes two novel ideas for strengthening the latter. Behind all these tasks, the combinatorial core engine of the solver is an assortment of specially adapted cheapest paths routines. We set up a representative testbed and perform extensive testing of our algorithms throughout all development stages. We conclude with a competition between ODEA and the commercial general purpose CPLEX MIP solver.