Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zsfassung in engl. Sprache
-
dc.description.abstract
Das effiziente Senden von Daten über Netzwerke gewinnt zunehmend mehr an Relevanz - von Internettelefonie bis hin zu Event-basierten Nachrichtensystemen. Die konkrete Aufgabenstellung entstand aus dem Industrieprojekt SWIS im Bereich der sicherheitskritischen Kommunikation bei der Flughafensicherung. In dieser Arbeit wird das Design eines Netzwerkes, in welchem mehrere Nachrichten gleichzeitig übermittelt werden sollen, hinsichtlich Erstellungs- und Übertragungskosten optimiert. Die Verbindungen sind durch Kapazitäten beschränkt, die Nachrichten müssen Zeitvorgaben hinsichtlich der Übermittlungsdauer und Vorgaben bezüglich des Übertragungsprotokolls einhalten.<br />In dieser Arbeit werden verschiedene algorithmische Ansätze zur Lösung dieses NP-schweren Problems erörtert. Ein Verfahren ganzzahliger linearer Programmierung basierend auf einer Mehrgüterflussformulierung ermöglicht das exakte Lösen kleiner Probleminstanzen.<br />Um das Problem zu vereinfachen werden bei der Lagrange Relaxierung schwierige Nebenbedingungen als Lagrange-Multiplikatoren in die Zielfunktion aufgenommen. Dadurch ergibt sich für jeden Transport ein unabhängiges Teilproblem. Aufgrund dessen werden durch iterative Verfahren die Koeffizienten der Lagrange-Multiplikatoren angepasst und somit untere Schranken für das Ausgangsproblem gefunden. Durch Heuristiken wird versucht daraus gültige Lösungen zu erzeugen.<br />Basierend auf einer alternativen Problemformulierung, bei welcher jedem möglichen Pfad eine Variable entspricht, wird das Problem durch Spaltengenerierung gelöst. Ausgehend von einer gültigen Lösung werden in einem iterativen Prozess nur jene Variablen hinzugefügt, welche die Lösung weiter verbessern können. Die Bestimmung dieser Variablen erfolgt aufgrund der Lösung des selben Subproblems wie bei der Lagrange Relaxierung.<br />Mit den vorgestellten Verfahren können kleine Instanzen in wenigen Minuten beweisbar optimal gelöst werden, für größere Instanzen können gute heuristische Lösungen gefunden werden. Die scharfen unteren Schranken der Lagrange Relaxierung ermöglichen zuverlässige Aussagen über die Qualität heuristischer Lösungen. Umfangreiche experimentelle Tests belegen die Vor- und Nachteile der vorgestellten Verfahren.<br />
de
dc.description.abstract
Efficient network routing is becoming more and more important - examples are internet telephony or event-based message systems. The particular problem emerged from the industry cooperation SWIS in the context safety-critical communication of air traffic management. In this thesis the design of a network is optimized for design and protocol costs. The goal is to find a minimum cost network enabling the simultaneous routing of multiple messages. Capacity constraints for each edge, delay constraints for individual messages, as well as a global delay, and security constraints make the optimization difficult.<br />In this thesis several algorithmic approaches for solving this NP-hard problem are discussed. An Integer Linear Programming based approach using a multi-commodity flow formulation enables to solve small problem instances to provable optimality.<br />To simplify the problem constraints are brought into the objective function by attaching Lagrangean multipliers to them. This approach is called Lagrangean relaxation. This yields independent subproblems for each transport. In an iterative process the coefficients of the Lagrange multipliers are systematically adapted and lower bounds for the original problem are obtained. Heuristics can be used to derive valid solutions.<br />Based on an alternative formulation, which introduces a variable for each possible path, the problem is solved by Column Generation. Starting from a valid solution, further improving variables are iteratively added. These variables can be found by solving the same subproblem as for Lagrangean relaxation.<br />By the presented algorithms small instances can be solved within a few minutes to optimality. For larger instances good heuristic solutions can be found. Tight lower bounds obtained by Lagrangean relaxation enable to measure the quality of heuristic solutions. Based on extensive experimental tests, pros and cons of each approach are discussed in this thesis.
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Lagrange Relaxierung
de
dc.subject
Spaltengenerierung
de
dc.subject
Netzwerkdesign
de
dc.subject
Lagrangean Relaxation
en
dc.subject
Column Generation
en
dc.subject
network design
en
dc.subject
Constrained Shortest Path Problem
en
dc.title
Design eines sicherheits-, zeit- und kostenkritischen Kommunikationsnetzwerkes mittels Lagrange Relaxierung und Spaltengenerierung
de
dc.title.alternative
Design of a safety-, time- and cost-critical communication network by Lagrangean Relaxation and Column Generation
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Nina Musil
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Chwatal, Andreas
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen