dc.description.abstract
Diese Dissertation behandelt verschiedene generalisierte Netzwerkdesignprobleme (NDPs), die zu den NP-harten kombinatorischen Optimierungsproblemen gehören. Im Gegensatz zu klassischen NDPs sind die generalisierten Versionen auf Graphen definiert, deren Knotenmengen in Clustern aufgeteilt sind. Das Ziel besteht darin, jeweils einen Subgraphen zu finden, der genau einen Knoten pro Cluster enthält und weitere Nebenbedingungen erfüllt.<br />Methoden, die zum Lösen von kombinatorischen Optimierungsproblemen eingesetzt werden, können grob in zwei Hauptrichtungen eingeteilt werden. Die erste Klasse besteht aus Algorithmen, die diese Probleme beweisbar optimal lösen können, sofern ihnen ausreichend viel Zeit und Speicher zur Verfügung gestellt werden. Diese Arbeit beginnt mit einer kurzen Einführung in die Techniken der linearen und ganzzahlig linearen Programmierung. Sie bilden die Basis für populäre Algorithmen wie Branch-and-Bound, Branch-and-Cut und viele weitere. Die zweite Klasse besteht aus Metaheuristiken, die zwar Näherungslösungen erzeugen, aber wesentlich weniger Zeit benötigen. Wenn beide Klassen miteinander kombiniert werden, entstehen hybride Algorithmen, die von den Vorteilen beider Richtungen profitieren können. Einige der vielfältigen Kombinationsmöglichkeiten werden untersucht und auf NDPs in dieser Arbeit angewandt.<br />Das erste Problem, das betrachtet wird, ist das generalisierte minimale Spannbaumproblem. Gegeben ist ein Graph, dessen Knoten in Clustern partitioniert sind. Wir suchen nach einem minimalen Spannbaum, der genau einen Knoten pro Cluster verbindet. Ein Ansatz basierend auf variabler Nachbarschaftssuche (VNS) wird vorgestellt, der drei verschiedene Nachbarschaftstypen verwendet. Zwei davon arbeiten komplementär, um die Effizienz bei der Suche zu erhöhen. Beide enthalten exponentiell viele Lösungen, aber effektive Algorithmen werden eingesetzt, die die jeweils besten Nachbarlösungen in polynomieller Zeit finden. Für die dritte Nachbarschaft wird ganzzahlige lineare Programmierung verwendet, um Teilbereiche einer Lösung zu optimieren.<br />Als nächstes betrachten wir das generalisierte Handlungsreisendenproblem (GTSP). Ausgehend von einem geclusteten Graphen suchen wir eine Rundreise minimaler Länge, die von jedem Cluster einen Knoten besucht.<br />Ein VNS Algorithmus basierend auf zwei Nachbarschaftsstrukturen wird vorgestellt. Eine davon ist die bereits bekannte generalisierte 2-opt Nachbarschaft, für die eine neue inkrementelle Auswertungstechnik entworfen wird, die den Suchvorgang wesentlich beschleunigt. Die zweite Nachbarschaft basiert auf dem Austauschen von den in der Lösung vorkommenden Knoten, auf die anschließend die verkettete Lin-Kernighan Heuristik angewendet wird.<br />Als ein zum GTSP verwandtes Problem untersuchen wir das Eisenbahn-Handlungsreisendenproblem (RTSP). Gegeben ist ein Fahrplan und ein Geschäftsmann, der eine Anzahl von Städten per Bahn besuchen muss, um Aufträge zu erledigen. Die Reise startet und endet an einem bestimmten Ort und die dafür benötigte Gesamtzeit, inklusive den Wartezeiten, soll minimiert werden. Es werden zwei Transformationen präsentiert, die das Problem als asymmetrisches oder symmetrisches Handlungsreisendenproblem (TSP) umformulieren. Damit können für das RTSP bewährte Techniken eingesetzt werden, die für das klassische TSP konzipiert sind.<br />Schließlich wird das Problem des generalisierten minimalen kantenzweizusammenhängenden Netzwerks betrachtet. Ausgehend von einem geclusteten Graphen wird ein Subgraph gesucht, der genau einen Knoten pro Cluster kantenzweizusammenhängend verbindet, d.h. zwischen je zwei Knoten müssen mindestens zwei kantendisjunkte Wege existieren. Wir betrachten drei VNS Varianten, die mit unterschiedlichen Nachbarschaftsstrukturen arbeiten. Jede adressiert bestimmte Teilaspekte wie die verbundenen Knoten und/oder die Kanten zwischen ihnen. Für komplexere Nachbarschaften werden effiziente Techniken wie Graphreduktion eingesetzt, die den Optimierungsvorgang wesentlich beschleunigen. Für Vergleichszwecke wird eine Formulierung als ganzzahliges lineares Programm entworfen, mit der kleine Instanzen beweisbar optimal gelöst werden können.<br />Experimentelle Ergebnisse zeigen, dass die grundlegende Strategie, komplementäre Nachbarschaftsstrukturen zu kombinieren, beim Lösen von generalisierten NDPs sehr erfolgreich ist. Insbesondere wird festgehalten, dass jede Nachbarschaftsstruktur signifikante Beiträge zum Optimierungsvorgang leistet.<br />
de