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
In this thesis, we consider several generalized network design problems (NDPs) which belong to the family of NP-hard combinatorial optimization problems. In contrast to classical NDPs, the generalized versions are defined on graphs whose node sets are partitioned into clusters. The goal is to find a subgraph which spans exactly one node from each cluster and also meets further constraints respectively.<br />Applicable methodologies for solving combinatorial optimization problems can roughly be divided into two mainstreams. The first class consists of algorithms which aim to solve these problems to proven optimality - provided that they are given enough run-time and memory. This thesis starts with a brief introduction to linear and integer linear programming techniques since popular algorithms like branch-and-bound, branch-and-cut, etc. are based on them. The second class are metaheuristics which compute apparoximate solutions but usually require significantly less runtime. By combining these two classes, we are able to form collaboration approaches that benefit from advantages of both sides. We will examine various possibilities of such combinations and some of them will be used to solve the NDPs in this thesis.<br />The first considered NDP is the generalized minimum spanning tree problem. Given a graph whose nodes are partitioned into clusters, we seek a minimum spanning tree which connects exactly one node from each cluster. A variable neighborhood search (VNS) approach will be presented that uses three different neighborhood types. Two of them work in complementary ways in order to maximize search performance. Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms are used to identify best neighbors. For the third neighborhood type we apply integer programming to optimize local parts within candidate solution trees.<br />We then study the generalized traveling salesman problem (GTSP). Given a clustered graph, we seek the minimum-costs round trip visiting one node from each cluster. A VNS algorithm based on two complementary, large neighborhood structures is proposed. One of them is the already known generalized 2-opt neighborhood for which a new incremental evaluation technique is described, which speeds up the search significantly. The second structure is based on node exchanges and the application of the chained Lin-Kernighan heuristic.<br />As a related problem to the GTSP, we also consider the railway traveling salesman problem (RTSP). We are given a timetable and a salesman who has to visit a number of cities by train to carry out some business. He starts and ends at a specified home city, and the required time for the overall journey, including waiting times, shall be minimized. Two transformation schemes to reformulate the problem as either a classical asymmetric or symmetric traveling salesman problem (TSP) are presented.<br />Using these transformations, established algorithms for solving the TSP can be used to attack the RTSP as well. Finally, we consider the generalized minimum edge biconnected network problem. For a given clustered graph, we look for a minimum-costs subgraph connecting one node from each cluster in an edge biconnected way, i.e. at least two edge-disjoint paths must exist between each pair of nodes. Three VNS variants are considered that utilize different types of neighborhood structures, each of them addressing particular properties as spanned nodes and/or the edges between them. For the more complex neighborhood structures, efficient techniques - such as a graph reduction - are applied to essentially speed up the search process. For comparison purpose, a mixed integer linear programming formulation based on multi commodity flows is proposed to solve smaller instances of this problem to proven optimality.<br />Looking at the obtained results, we observe that the fundamental strategy of combining complementary neighborhood structures is very successful for solving generalized NDPs. In particular, all of them are shown to contribute significantly to the search process.<br />
