Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1857
Main Title: Minimum Cost Disjoint Paths under Arc Dependences. Algorithms for Practice
Translated Title: Disjunkte Wege zu minimalen Kosten unter Bogenabhängigkeiten. Algorithmen für die Praxis
Author(s): Oellrich, Martin
Advisor(s): Möhring, Rolf H.
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In der vorliegenden Dissertation entwickeln wir einen einheitlichen algorithmischen Rahmen für Disjunkte Pfadprobleme mit minimalen Kosten. Diese Probleme treten in vielfältigen angewandten Kontexten auf, insbesondere in der Telekommunikation und der automatischen Fahrzeugführung. Die Hauptmotivation ist typischerweise das Erfordernis, eine Struktur zu planen, die in einem bestimmten Sinne sicher ist. In der Telekommunikaton ist Verfügbarkeit ein Thema von höchster Bedeutung, bei Fahrzeugen ist es Kollisionsfreiheit. Wir bekamen den Startimpuls für unsere Arbeit durch ein Projekt mit T-Systems Darmstadt. Dort brauchten Planer ein Werkzeug zur Unterstützung der Bepreisung so genannter Virtueller Privater Netze. Wir entwickelten zu diesem Zweck eine Software namens ODEA, die später auch auf realistische Instanzen eines Logistikprojektes mit dem Containerterminal Altenwerder am Hamburger Hafen angewandt wurde. Disjunkte Pfadprobleme sind gegeben in der Form eines gerichteten oder ungerichteten Graphen mit nichtnegativen Bogen-/Kantenkosten und einer Menge von Knotenpaaren. Eine zulässige Lösung ist eine Menge mit je einem verbindenden Pfad pro Knotenpaar, die zwei Bedingungen erfüllt: 1. alle Pfade sind paarweise überschneidungsfrei in einem gegebenen Sinne, 2. die Gesamtkosten der Lösung sind minimal unter allen Lösungen. Dieses Problem ist bekanntermaßen NP-schwer schon in stark eingeschränkten Fällen. Die Literatur berichtet über polynomial lösbare Spezialfälle und heuristische Approximationsmöglichkeiten. Exakte Ansätze fehlen, die zum Einsatz in Software für allgemeine Zwecke geeignet wären. Unsere Arbeit befasst sich mit dieser Lücke. Wir stellen ein ganzzahliges Modell auf, das zum einen flexibel genug ist, um mehrere Disjunktheitsmodi abzubilden, zum anderen eine effiziente algorithmische Bearbeitung anwendungsnaher Instanzen ermöglicht. Wir führen eine neue Modellierungstechnik namens Bogenabhängigkeiten ein. Sie erlaubt eine Verallgemeinerung des klassischen Disjunktheitsbegiffs, der nur bogen-, kanten- und knotenbezogene Disjunktheit unterscheidet. Mit ihrer Hilfe können Planer ihre Arbeit auf speziell konstruierte Abstraktionen des Eingabegraphen beschränken, der erheblich weniger Daten enthält ohne die für die Sicherheit benötigten Informationen zu verlieren. Im Mittelpunkt dieses Modells stehen Pfade im Graphen. Wir untersuchen auch eine alternative Formulierung mittels so genannter Sternflüsse. Der Hauptteil dieses Buches beschreibt im Detail die Methoden, die wir für unsere Software entwickelt haben. Wir entwerfen ein Branch-and-Bound-Schema und geben die Inhalte für seine funktionalen Teile an: Verzweigungsstrategien, strukturelle Ausschlüsse, obere und untere Kostenschranken. Darunter sind zwei neuartige Ideen zur Verbesserung der unteren Schranken. Unterhalb all dieser Teilaufgaben stellen speziell angepasste kombinatorische Kernroutinen zur Berechnung billigster Pfade die Basis des Programms dar. Wir stellen ein repräsentatives Testbett zusammen und testen unsere Algorithmen durch alle Entwicklungsschritte hindurch. Wir schließen ab mit Vergleichen zwischen ODEA und dem ganzzahligen Solver des kommerziellen Tools CPLEX.
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.
URI: urn:nbn:de:kobv:83-opus-18656
http://depositonce.tu-berlin.de/handle/11303/2154
http://dx.doi.org/10.14279/depositonce-1857
Exam Date: 26-Mar-2008
Issue Date: 21-May-2008
Date Available: 21-May-2008
DDC Class: 510 Mathematik
Subject(s): Ausfallsichere Netzplanung
Disjunkte Pfade
Kombinatorische Optimierung
Combinatorial Optimization
Disjoint Paths
Survivable Network Design
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_28.pdf3.22 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.