Models and Algorithms for Extended Network Design

Abstract

The ubiquitous interest in networks per se stems from their natural appearance in countless situations - real world kind as well as theoretical. Network models can be used to describe infrastructure, processes, and relations in general. Furthermore, the cost-driven evaluation of networks leads to the question of how to effciently construct networks of high quality in regard to the expenses - either from scratch or by extending existing ones. The design of algorithms for effciently fnding optimal, or near optimal, structures is a field of research motivated by applications in various industries, such as telecommunications, transportation, manufacturing and mining, just to mention a few. The problems studied in this dissertation, all of them essentially combinatorial, ask for networks of minimal overall cost obtained from the synthesis of the fundamental graph classes of cycles, trees or stars. The resulting integrated decision-making under various capacity side constraints leads to computationally challenging models in discrete optimization. The contribution of the presented research is twofold. Firstly, new models of practical relevance are developed for which exact and heuristic state-of-the art algorithms are elaborated. Secondly, innovative matheuristic concepts of generic type are presented and studied on these models. These techniques are able to elegantly push the frontiers of computability to effciently approximate optimal solutions using mathematical programming.

In dieser Dissertation werden Modelle und Methoden für die Planung kostenoptimierter Netzwerke studiert. Es werden Strukturen aus der Klasse sogenannter erweiterter Netzwerke betrachtet. Diese zweistufigen zentralisierten Netzwerke vereinen zwei unterschiedliche Netzwerktopologien und ermöglichen somit integrierte Entscheidungsfindung. Zusammenfassend werden folgende Ergebnisse erarbeitet. Einerseits wird in dieser Doktorarbeit eine neuer Typ von Netzwerkplanungsmodellen entwickelt, sogenannte Ring-Baum-Probleme. Diese verallgemeinern grundlegend unterschiedliche Steinerbaum- und Tourenplanungsprobleme unter Berücksichtigung von Kapazitätsrestriktionen. Hierdurch lassen sich simultan zentrale Kreisstrukturen sowie angrenzende Baumstrukturen kostenoptimal planen. Zudem zeigt sich, dass diese Modelle ein hohes Potential für die Ableitung von Modellvarianten und deren Einsatz in diversen Anwendungsgebieten bergen. Die in der Arbeit entwickelten exakten und heuristischen Lösungsverfahren sind hochkompetitiv und entsprechen dem aktuellen Stand entsprechender Forschungsarbeit. Andererseits werden innovative Methoden auf Grundlage mathematischer Optimierung vorgestellt und es wird gezeigt, dass diese zum Lösen der betrachteten komplexen Modelle geeignet sind. Die konsequente Einbettung von Techniken der mathematischen Programmierung in metaheuristische Ansätze führt zu herausragenden Ergebissen im Vergleich zu den besten bekannten Methoden aus der Fachliteratur. Die vorgestellten Algorithmen vereinen exakte Schnittebenenverfahren mit iterativen lokalen Suchverfahren. Diese Methoden werden ausführlich für die betrachteten Modelle getestet, haben allerdings einen sehr allgemeinen Charakter, sodass die Anwendung auf weitere kombinatorische Optimierungsprobleme nahe liegt.