Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4579
Main Title: Network design with facility location
Subtitle: Approximation and exact techniques
Translated Title: Netzwerkdesignprobleme mit Standortplanung
Translated Subtitle: exakte und approximative Methoden
Author(s): Rezapour, Mohsen
Advisor(s): Bley, Andreas
Referee(s): Skutella, Martin
Salavatipour, Mohammad R.
Bley, Andreas
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In dieser Arbeit betrachten wir Optimierungsprobleme, welche Fragestellungen aus dem Netzwerkdesign und aus der Standortplanung miteinander kombinieren. Solche Probleme treten unter Anderem bei der Planung und Optimierung von Netzen für die Telekommunikation, im Bereich Transport und Logistik oder für die Energieversorgung auf. Bei der Standortplanung, dem sogenannten Facility Location, ist typischerweise zu entscheiden, welche Standorte (Facilities) eingerichtet werden sollen und von welchem Standort jeder Kunde versorgt werden soll. Ziel dabei ist es, die Gesamtkosten für die Einrichtung der gewählten Standorte und die Anbindung der Kunden zu minimieren. In der Regel wird jeder Kunden dabei einzeln und direkt von einem einzigen Standort versorgt, so dass neben der Wahl der Standorte lediglich die Zuordnung der Kunden zu den Standorten zu entscheiden ist. Einsparungen durch eine mögliche gemeinsame Nutzung der Versorgungsinfrastruktur durch mehrere Kunden können somit nicht berücksichtigt werden. Dies ist typischerweise Inhalt von Netzwerkdesign-Problemen. In diesen ist ein Netzwerk so zu entwerfen und zu dimensionieren, dass verschiedene Transport- oder Kommunikationsbedarfe zu möglichst minimalen Kosten gleichzeitig erfüllt werden können. Dafür müssen neben den Entscheidungen zur Topologie und Dimensionierung der Netze oft auch auch Entscheidungen zu den Routen getroffen werden, entlang denen die jeweiligen Bedarfe gesendet werden sollen. Im Gegensatz zur Standortplanung, bei der diese erst durch die Zuordnung der Kunden an die Facilities festgelegt werden, sind die Quellen und Ziele der jeweiligen Transportbedarfe beim Netzdesign in der Regel fest vorgegeben. In vielen praktischen Anwendungen sind die Entscheidungen über Routen und Standorte aber stark voneinander abhängig und sollten gleichzeitig getroffen werden. Ein naiver Ansatz, der zuerst die Standorte festlegt und anschließend die Routen plant, kann somit zu insgesamt sehr schlechten Ergebnissen führen. Ziel dieser Arbeit ist es, diese beiden Problemaspekte zusammen zu führen und verschiedene, praktisch relevante kombinierte Netzwerkdesign Facility Location Probleme zu untersuchen. Aufbauend auf bekannten Techniken für Netzwerkdesign und Standortplanung entwickeln wir dabei neue algorithmische Techniken und praktische Lösungsansätze für diese Probleme. Zunächst befassen wir uns mit einer Kombination aus Buy-at-bulk Network Design mit dem klassischen Facility Location Problem. Genauer gesagt betrachten wir Verallgemeinerungen des Facility Location Problems, in welcher mehrere Kunden über einen gemeinsam genutzten Baum anstelle individueller Direktverbindungen an einen Standort angebunden werden können. Die Kanten des Baumes sind dabei durch die Wahl geeigneter Kabeltypen (oder Transportsysteme) so zu dimensionieren, dass die resultierenden Kapazitäten für die aggregierten Bedarfe der darüber verlaufenden Verbindungen ausreichen. Die Aufgabe besteht darin, die zu eröffnenden Standorte und die auf den Netzkanten zu installierenden Kapazitäten so zu wählen, dass alle Kunden mittels besagter Bäume an die gewählten Standorten angebunden und die Gesamtkosten minimal sind. Diese Verallgemeinerung erlaubt es, die oben erwähnten Einsparungensmöglichkeiten durch die gemeinsame Nutzung der Versorgungsinfrastruktur durch mehrere Kunden sinnvoll abzubilden. Wir präsentieren den ersten LP-basierten Approximationsalgorithmus für dieses Problem und beweisen eine obere Schranke von O(K) für die Ganzzahligkeitslücke des zugrundeliegenden LPs. Außerdem entwickeln wir verschiedene kompakte und exponentielle ILP-Formulierungen des Problems und entwickeln einen darauf basierenden Branch-und-Cut-und-Price Algorithmus, der es uns erlaubt, sehr große praktische Instanzen zu lösen. In vielen Anwendungsszenarien, insbesondere in der Telekommunikation, müssen die gewählten Facilities zusätzlich in einem Kernnetz untereinander verbunden werden, um überregionale Funktionen realisieren zu können. Im einfachsten Fall führt dies zu Problemen, in denen die Facilities mit einem baumartigen Netzwerk aus Verbindungen eines speziellen Kabeltyps (oder Transportsystems) verbunden werden. Wir betrachten zwei Versionen dieses Problems: In der Buy-at-Bulk Version hat jeder Kabeltyp eine feste Kapazität und feste Installationskosten. In der Deep-Discount Version hat jeder Kabeltyp eine unbegrenzte Kapazität, dafür aber neben den festen Installationskosten zusätzliche nutzungsabhängige Kosten. Die erste Version tritt typischerweise bei der Planung von Kommunikationsnetzwerken auf, die zweite in Transport und Logistik. Wir entwickeln in dieser Arbeit die ersten Approximationsalgorithmen mit konstanter Gütegarantie und zeigen, dass es eine LP Formulierung mit einer konstanten Ganzzahligkeitslücke gibt. Insbesondere in der Telekommunikation spielt das Kernnetzwerk, welches die gewählten Standorte verbindet, eine wichtige Rolle für die Qualität und die Verfügbarkeit der Netzdienste. Daher sollen diese Teilnetze überlicherweise so geplant werden, dass sie sowohl fehlertolerant sind als auch kurze Verbindungswege ermöglichen, damit für jede Kommunikationsverbindung auch im Falle eines Knoten- oder Kantenausfalls Alternativrouten zur Verfügung stehen und Verzögerungen durch zu viele Netzknoten auf den Kommunikationswegen vermieden werden. Im letzten Abschnitt der Arbeit beschäftigen wir uns mit einer aus diesen Anforderungen entstandenen Erweiterung des Facility Location Problems, in der zwischen den gewählten Facilities ein Kernnetz zu planen ist, welches eine vorgegebenen Anzahl von disjunkten längenbeschränkten Wegen zwischen den Knoten besitzt. Im Allgemeinen ist jedoch bereits das approximative Lösen dieses Problems NP-schwer. Daher beschäftigen wir uns in dieser Arbeit mit IP basieren Techniken. Wir entwerfen und diskutieren zunächst zwei starke erweiterte Formulierungen und entwickeln anschließend einen auf einer Benders Dekomposition dieser Formulierungen basierenden und praktisch sehr effizienten Branch-und-Cut Algorithmus zur Lösung dieses Problems.
In this thesis, we consider a family of problems that combine network design and facility location. Such problems arise in many practical applications in different fields such as telecommunications, transportation networks, logistic, and energy supply networks. In facility location problems, we want to decide which facilities to open and how to assign clients to the open facilities so as to minimize the sum of the facility opening costs and client connection costs. These problems typically do not involve decisions concerning the routing of the clients’ demands to the open facilities; once we decided on the set of open facilities, each client is served by the closest open facility. In network design problems, on the other hand, we generally want to design and dimension a minimum-cost routing network providing sufficient capacities to route all clients’ demands to their destinations. These problems involve deciding on the routing of each client’s demand. But, in contrast to facility location problems, demands’ destinations are predetermined. In many modern day applications, however, all these decisions are interdependent and affect each other. Hence, they should be taken simultaneously. A naive strategy that first decides which facilities to open, and then builds routing networks connecting clients to the open facilities, may lead to very poor solutions. This has motivated several new combined network design facility location problems which are studied in this thesis. We develop new algorithmic techniques and solution approaches for these problems, building on the known techniques for facility location and network design. In a first line of work, we study problems that integrate buy-at-bulk network design into the classical facility location problem. More precisely, we consider generalizations of the facility location problem where multiple clients may share capacitated trees to connect to the open facilities instead of requiring direct links. The task is to open facilities (sinks) and route all client demands to the open facilities via a capacitated access network that is constructed installing access cables of different costs and capacities. On the theoretical side, we present the first LP-based approximation algorithm for this problem and prove an upper bound of O(K) on the Integrality gap of the underlying LP. We also undertake the first computational study for this problem. To this end, we provide compact and exponential-sized formulations for the problem and develop a branch-cut-and-price algorithm allowing us to solve very large real-world instances of the problem. In many real-world applications, particularly in telecommunications, there is the additional requirement to connect the open facilities via high bandwidth core cables. In the simplest case, this leads to variants of the problem in which open facilities are connected via a tree-like core network that consists of infinite capacity cables. We analyze two fundamental versions of this problem: In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. The Buy-at-Bulk version arises in the planing of telecommunication networks, while the Deep-Discount problem version is motivated by applications in logistic and transportation networks. We develop the first constant-factor approximation algorithms for these connected versions. Using sampling techniques, we then improved the approximation factors. We were even able to prove a tighter bound of O(1) on the the Integrality gap of an LP formulation of the problem similar to one for the unconnected version. The core network plays a primary role for the service availability and the service quality in telecommunications networks. Therefore it is common to require that the core networks are fault-tolerant and have short routing paths. In the final part of this thesis we focus on the core network design. To take these requirements into account, we introduce and study another network design facility location problem where the core network has to fulfill simultaneous survivability and hop-length restrictions between the chosen facilities. It is easy to see that it is already NP-hard to compute a constant-factor approximation for the problem. Hence, we focus our research on IP based techniques. We propose two strong extended formulations for the problem and devise a practically efficient branch-and-cut algorithm based on Benders decomposition for its solution.
URI: urn:nbn:de:kobv:83-opus4-69339
http://depositonce.tu-berlin.de/handle/11303/4876
http://dx.doi.org/10.14279/depositonce-4579
Exam Date: 16-Mar-2015
Issue Date: 21-Aug-2015
Date Available: 21-Aug-2015
DDC Class: 000 Informatik, Informationswissenschaft, allgemeine Werke
Subject(s): Approximationsalgorithmus
Ganzzahlige Programmierung
Netzwerkdesign
Standortplanung
Telekommunikation
Approximation algorithm
Facility location
Integer programming
Network design
Telecommunications
Creative Commons License: https://creativecommons.org/licenses/by/3.0/de/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
rezapour_mohsen.pdf2,18 MBAdobe PDFThumbnail
View/Open


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