Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3968
Main Title: Network flows and network design in theory and practice
Translated Title: Netzwerkflüsse und Netzwerk-Design in Theorie und Praxis
Author(s): Matuschke, Jannik
Advisor(s): Skutella, Martin
Peis, Britta
Referee(s): Skutella, Martin
Peis, Britta
McCormick, Thomas
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Die Dissertation "Network design and network flows in theory and practice" befasst sich mit Optimierungsproblemen aus den Bereichen Netzwerk-Design und Netwerk-Fluss-Theorie. Probleme dieser Art treten in verschiedensten Anwendungsbereichen der kombinatorischen Optimierung auf, insbesondere in der Planung von Logistik- und Telekommunikationsnetzwerken. Es werden vier verschiedene Problemklassen untersucht, wobei sowohl neue theoretische Grundlagen als auch unmittelbar in der Praxis anwendbare Modelle und Lösungsverfahren erarbeitet werden. Bei der ersten in der Dissertation untersuchten Problemklasse handelt es sich um dynamische abstrakte Flüsse. Abstrakte Flüsse stellen eine Verallgemeinerung klassischer Netzwerk-Flüsse, in der die Struktur des zugrundeliegenden Netzwerks durch ein abstraktes Mengensystem von "Pfaden" ersetzt wird, das als einziges Axiom eine bestimmte Eigenschaft sich kreuzender Pfade in Netzwerken nachbildet. Dieses allgemeine Modell wird um einen zeitlichen Aspekt erweitert und ein Max-Flow/Min-Cut-Theorem für das resultierende Modell dynamischer abstrakter Flüsse bewiesen. Im darauf folgenden Kapitel wird ein neues Modell für die taktische Transportplanung vorgestellt. Das Modell umfasst alle wichtigen Aspekte der taktischen Transportplanung: die Routen der Güter durch das Netzwerk, die Auswahl der zugehörigen Transporttarife sowie Lieferfrequenzen und Bestandsmengen. Die Integration dieser unterschiedlichen Aspekte gelingt mit Hilfe einer zyklischen Netzwerk-Expansion. Es werden auch heuristische Verfahren und gemischt-ganzzahlige Formulierungen entwickelt, um das aus dem Modell resultierende Optimierungsproblem zu lösen. Das Modell wurde in enger Zusammenarbeit mit Experten des Logistikberatungsunterenehmens 4flow AG entworfen. Ein breit angelegter Test der Verfahren auf Basis verschiedener Fallstudien aus aktuellen Kundenprojekten der 4flow AG zeigt, dass die berechneten Lösungen im Durchschnitt weniger als 10% von der Optimallösung abweichen. Bei der dritten untersuchten Problemklasse handelt es sich um integrierte Standort- und Netzwerk-Design-Probleme. Es wird eine allgemeine Methode zur Approximation solcher integrierter Probleme vorgestellt. Das Verfahren wird auf Location Routing, ein wichtiges Problem aus der Bereich der Transportlogistik, angewandt und der erste Approximationsalgorithmus mit konstantem Faktor für dieses Problem und mehrere seiner Varianten entwickelt. Eine Implementierung des Algorithmus wird auf verschiedenen Instanzen aus der Fachliteratur sowie deutlich größeren zufällig generierten Instanzen getestet. Es stellt sich heraus, dass der Optimalitätsabstand der berechneten Lösungen in der Praxis deutlich unter der bewiesenen theoretischen Worst-Case-Garantie bleibt. Im Weiteren wird das Problem der Standortplanung mit kapazitierten und längenbeschränkten Zugangsnetzen untersucht. Dieses tritt bei der Planung von Glasfasernetzwerken in der Telekommunikation auf. Es werden bikriterielle Approximationsalgorithmen vorgestellt, die die Längenschranke und die Kosten der Optimallösung mit unterschiedlichen Faktoren approximieren. Das letzte Kapitel der Dissertation beschäftigt sich mit der Orientierung von eingebetteten Graphen. Dabei handelt es sich um eine Variante von Netzwerk-Design, in der den Kanten eines ungerichteten Graphen Richtungen zugewiesen werden. Das untersuchte das primal-duale Orientierungsproblem besteht darin, eine Orientierung zu finden, die sowohl im primalen als auch im dualen Graphen der Einbettung vorgeschriebene Eingangsgrade für die Knoten erfüllt. Es wird gezeigt, dass es höchstens 4^g zulässige Orientierungen gibt, wobei g der Genus der Graph-Einbettung ist, und dass alle möglichen Orientierungen in einer Laufzeit von O(4^g|E|^2 + |E|^3) berechnet werden können. Das Problem wird jedoch NP-schwer, sobald die gewünschten Eingangsgrade der Knoten nur durch Intervalle anstelle exakter Werte spezifiziert sind.
This thesis investigates optimization problems from the areas of network design and network flow theory. Such problems occur in different application areas of combinatorial optimization, in particular in the design of logistics and telecommunication networks. We discuss four different classes of problems, providing both new theoretical insights as well as models and solution methods with immediate practical impact. The first problem class discussed in this thesis are abstract flows over time. Abstract flows generalize classical network flows by replacing the underlying network structure by a system of linearly ordered sets, called abstract paths. This set system fulfills a switching axiom that describes the behaviour of crossing paths in networks. We show that the presence of this axiom alone suffices to ensure max flow/min cut properties in the time expansion of the system. This yields the max flow/min cut theorem for abstract flows over time as well as a polynomial time algorithm to compute the maximum flow and the minimum cut in this setting. In the next chapter, we introduce a new model for tactical transportation planning, capturing all important aspects of the logistical task: the routes of commodities within the network, the corresponding tariff choices as well as delivery frequencies and inventory levels. These different aspects are integrated using a cyclic network expansion. We complement our model by providing various heuristic approaches and mixed integer programming formulations for solving the resulting optimization problem. The model has been developed in close collaboration with logistics experts at 4flow AG, a logistics consultancy company. We evaluate the model and our algorithms on a broad set of instances based on real-world logistics networks from ongoing and recent customer projects of 4flow AG. The computational study shows that most of our solutions are within 10% of optimality. The third problem class investigated in this thesis is comprised by combined location and network design problems. We discuss a general method of approximating such problems. We use this method to derive the first constant factor approximation algorithm for location routing, an important problem in transport logistics, and several of its variants. We also evaluate our algorithm in a computational study on instances from the literature and additional large-scale randomly generated instances. It turns out that the performance of our algorithm in practice exceeds the theoretical worst-case approximation guarantee by far. The second problem we study in this chapter is facility location with capacitated and length-bounded trees. It is motivated by the design of optical access networks in telecommunication. We derive bifactor approximation algorithms for the problem that provide different approximation factors for length bound and solution cost, with improved factors for two important special cases. The final chapter of the thesis deals with the problem of orienting the edges of an embedded graph in such a way that the resulting digraph fulfills given in-degree specifications both for the vertices and for the faces of the embedding. This primal-dual orientation problem was first proposed by Frank for the case of planar graphs, in conjunction with the question for a good characterization of the existence of such orientations. We answer this question by showing that a planar embedding, if it exists, can be constructed by combining certain parts of a primally feasible orientation and a dually feasible orientation. For the general case of arbitrary embeddings, we show that the number of feasible orientations is bounded by 4^g, where g is the genus of the embedding. Our proof also yields a fixed-parameter algorithm for determining all feasible orientations parameterized by the genus. In contrast to these positive results, however, we also show that the problem becomes NP-complete even for a fixed genus if only upper and lower bounds on the in-degrees are specified instead of exact values.
URI: urn:nbn:de:kobv:83-opus4-47852
http://depositonce.tu-berlin.de/handle/11303/4265
http://dx.doi.org/10.14279/depositonce-3968
Exam Date: 10-Dec-2013
Issue Date: 4-Mar-2014
Date Available: 4-Mar-2014
DDC Class: 510 Mathematik
Subject(s): Kombinatorische Optimierung
Netzwerk-Design
Netzwerkflüsse
Combinatorial optimization
Network design
Network flows
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
matuschke_jannik.pdf2.53 MBAdobe PDFThumbnail
View/Open


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