Netzwerk-Design für zweistufige Transportsysteme und ein Branch-and Price-Verfahren für das gemischte Direkt- und Hubflugproblem

Transportnetzwerk-Design ist eines der bedeutenden Anwendungsfelder des Operations Research und der mathematischen Optimierung. Es birgt große Potentiale zur Kostenreduktion und zur Verbesserung der Service-Qualität. Insbesondere gilt dies für die Planung von großen Regelnetzen, bei denen bereits aus Einsparungen von wenigen Prozent wegen der regelmäßigen Wiederholung der Abläufe hohe Gesamtbeträge resultieren. Die vorliegende Dissertation beschäftigt sich mit der Modellierung und Lösung speziell strukturierter Service-Netzwerk-Design-Probleme für zweistufige Transportsysteme, bei denen Services des inneren Netzwerks entweder direkte Transporte oder Transporte zwischen Umladeterminals und einem zentralen Hub sind. Wesentliche taktische Planungsaufgaben sind die Auswahl und die zeitliche Festlegung (das Scheduling) der Services, insbesondere die Wahl der Umladeterminals und Umladezeitpunkte, sowie die eindeutige Zuordnung von Aufträgen zu Services. In den neu entwickelten Modellen sind viele praktisch relevante Anforderungen abgebildet, wie individuelle Zeitfenster von Transportaufträgen, Öffnungszeiten von Terminals, Be- und Entladezeiten für Transportmittel sowie komplexe Abhängigkeiten zwischen Services, wie die Repositionierung und die Beschränkung bestimmter Gruppen von Transporten. Exemplarisch wird mit dem Direktflugproblem (DFP) und dem gemischten Direkt- und Hubflugproblem (MFP) zum Flugnetz-Design des Nachtluftpostnetzes für den Brieftransport der Deutschen Post AG eine praktische Anwendung vorgestellt. Die eingesetzte Lösungungsmethodik zur Bearbeitung dieser im mathematischen Sinne schwierigen (NP-schweren) Probleme basiert auf der Linearen Programmierung. Die zur Lösung benutzten Modelle besitzen eine riesige Zahl von ganzzahligen Variablen. Daher werden Dantzig-Wolfe-Dekomposition und Techniken des Column-Generation zum dynamischen Erzeugen von Entscheidungsvariablen innerhalb eines Branch-and-Price-Verfahrens zur ganzzahligen Lösung benutzt. Optional wird das Branch-and-Price durch neu hergeleitete Schnittebenen zu einem Branch-and-Price-and-Cut-Ansatz ergänzt. Der umfangreiche methodische Teil der Arbeit beinhaltet einerseits eine in sich geschlossene Darstellung der allgemeinen Methodik. Andererseits erfordert die konkrete Ausgestaltung eines beschleunigten Branch-and-Price-and-Cut-Verfahrens die Lösung der LP-Relaxation des Master-Programms mit sog. Cliquen-Rucksack-Problemen als Teilproblemen, die Angabe von damit kompatiblen Verzweigungsregeln, die Herleitung von Schnittebenen mit der Entwicklung eines zugehörigen Separationsverfahrens sowie allgemeine Techniken zur Beschleunigung. Dieselben Methoden können sowohl zur exakten Lösung innerhalb eines Optimierungsalgorithmus als auch zur Entwicklung eines heuristischen Verfahrens für die approximative Lösung größerer Problem-Instanzen dienen. Im Rahmen dieser Arbeit wurde erfolgreich ein Prototyp des Verfahrens implementiert. Die detailliert analysierten Testrechnungen basieren auf Daten des Decisions Support Systems ISBT-Netzplanung der Deutschen Post AG: DFP mit bis zu 400 Aufträgen können gut mit der in der Arbeit entwickelten Lösungsmethodik untersucht werden. Das ebenfalls neu entwickelte Verfahren zur Clusterung der Transportaufträge macht es möglich, auch für sehr viel größere DFP ganzzahlige Lösungen mit einem Fehler im einstelligen Prozentbereich zu bestimmen. Für Instanzen des DFP mit bis zu 200 Aufträgen kann sogar meist eine optimale Lösung errechnet werden. Beim MFP lassen sich Instanzen mit bis zu ca. 200 Aufträgen auf ganzzahlige Lösungen hin untersuchen. Geclusterte DFP- und MFP-Instanzen dieser Größe umfassen praxisrelevante Fragestellungen der Deutschen Post AG, so daß verschiedenste Szenarios zur künftigen Entwicklung des Nachtluftpostnetzes untersucht und optimiert werden können. Ein für die Praxis interessantes Ergebnis der Arbeit ist sicherlich, daß im Nachtluftpostnetz die Benutzung eines Flug-Hubs bei ausschließlicher Orientierung an den Kosten wenig sinnvoll erscheint. Ein reines Direktflugnetz ist dem gemischten Transportnetz vorzuziehen.