Algorithmische Lösungen für Last-Mile Netzwerke

Netzwerkdesignprobleme treten häufig in praktischen Bereichen wie dem Design von Kommunikationsnetzwerken, der Entwicklung elektronischer Schaltungen, dem Design von Glasfasernetzwerken oder der Entwicklung lokaler Wasser- und Wärmeversorgungssysteme auf. Das Hauptproblem auf das wir uns konzentrieren ist die sogenannte `Connected Facility Location in Multicommodity Networks`, das eine Verallgemeinerung der beiden bekannten Netzwerkdesignprobleme `Facility Location Problem` und `Steiner Tree Problem` repräsentiert. Gegeben ist dabei eine Menge von Knoten die Kunden und Infrastruktur darstellen, als auch deren benötigte Bandbreiten, mögliche Standorte der Anlagen und Verbindungen zu anderen Knoten. Das Hauptziel ist, eine Untermenge von Standorten mit Anlagen zu besetzen, jeden Kunden genau einer davon zuzuordnen und die Anlagen durch einen Steiner Tree zu verbinden. Die Kosten der Anlagen und ihren Verbindungen sollen dabei minimiert werden. In Multicommodity Networks hängen die Kosten der Kanten von zusätzlichen wirtschaftlichen Faktoren ihrer Kapazitäten ab, beispielsweise soll eine Rohrleitung größerer Kapazität billiger sein als eine Anzahl kleinerer Leitungen mit der gleichen Gesamtkapazität. Dieses kombinatorische Optimierungsproblem gehört zur Klasse der NP vollständigen Netzwerkdesignprobleme. Die verfügbaren Techniken für diese Probleme können grob in zwei Hauptkategorien eingeteilt werden: Exakte und heuristische Algorithmen. Exakte Algorithmen garantieren die beweisbar optimale Lösung für jede Probleminstanz. Hierbei sind exponentielle Laufzeiten oder großer Bedarf an Hauptspeicher möglich, sodaß mitunter die Garantie für optimale Lösungen aufgegeben wird, zugunsten guter Lösungen die von heuristischen Algorithmen gefunden werden. Um das oben beschriebene Problem und seine Varianten und Subprobleme für Kanten mit Kapazitäten zu lösen, planen wir die Entwicklung neuer Mixed-Integer Programming Formulierungen und das Design algorithmischer Frameworks um optimale Lösungen zu finden. Für große Instanzen sollen metaheuristische Methoden entwickelt werden, um suboptimale aber hochqualitative Lösungen zu erhalten und deren Abstand zum Optimum als Qualitätsmaß bereitzustellen. Unsere Forschung beruht auf Branch-And-Cut Methoden, Variable Neighbourhood Search und vielversprechenden Varianten ihrer Kombination.