Diskrete Optimierungsmodelle und Algorithmen zur strategischen Planung von Transportnetzen im Einzelwagenverkehr
Final Report Abstract
Im Rahmen des Forschungsprojekts wurde eine Analyse der Produktionsstruktur des Einzelwagenverkehrs durchgeführt und darauf basierend eine geeignete Systembeschreibung entwickelt, welche sowohl die praktischen als auch die mathematischen Anforderungen berücksichtigt. Diese Systembeschreibung wurde in eine geeignete Darstellung der Graphentheorie überführt. Zu unterscheiden waren dabei die unterschiedlichen Knoten und deren verschiedenen Aufgaben sowie die Kanten, die zum einem das Schienennetz selber und zum anderen Zugfahrten auf dem Schienennetz repräsentieren. Die Transportkosten im Einzelwagenverkehr sind größtenteils durch Fixkosten, wie Trassengebühren oder den Personaleinsatz pro Zugfahrt, geprägt. Um die Transportkosten realistischer abzubilden, wurde eine gestufte (stückweise-lineare) Kostenfunktion entwickelt. Des Weiteren wurden handhabbare Definitionen für die mathematische Modellierung entwickelt. Basierend auf der Systembeschreibung wurde ein neuartiges, mathematisches Hub-Location-Modell zur strategischen Netzplanung und -optimierung entwickelt, welches grundlegend von bisherigen Modellen zur Hub-Location-Planung abweicht. Dieses Modell integriert sowohl Kapazitäten und Kosten in den Hubs (Zugbildungsanlagen) als auch auf den Verbindungsstrecken. Um den strategischen Aspekt der Dimensionierung von Hubeinrichtungen gerecht zu werden, wurden für jeden potentiellen Hubstandort mehrere Kapazitätslevel mit unterschiedlichen Fixkosten integriert. Da die Streckenkosten größtenteils durch die Trassengebühren sowie den Einsatz eines Zuges geprägt sind, wurde für die Streckenkosten eine gestufte Kostenfunktion integriert. Das Modell betrachtet darüber hinaus zwei verschiedene Hub-Typen, für welche verschiedene (Allokations-) Restriktionen gelten. Des Weiteren setzt das Modell nicht voraus, dass die Kosten der Dreiecksungleichung genügen und das Hubnetz vollständig verknüpft ist. Insbesondere die Integration von mehreren Hub-Typen sowie die Abbildung von praxisnahen, gestuften Kosten erhöhte die Komplexität des Modells und führte zu einem erhöhten Schwierigkeitsgrad bei der Lösung des Problems. Um eine allgemeine Anwendbarkeit und eine Übertragbarkeit des Modells auf andere Bereiche zu ermöglichen, wurde ein Submodell entwickelt, welches nur einen Hub-Typ integriert, jedoch die Kapazitätslevel sowie die gestufte Transportkostenfunktion beinhaltet. Basierend auf der entwickelten Modellierung wurden mehrere Ansätze zur Komplexitätsreduktion entwickelt. Dazu zählen u.a. die Entwicklung von geeigneten Preprocessing-Techniken, die Analyse und Identifikation von redundanten Nebenbedingungen und Variablen sowie straffenden Nebenbedingungen, welche insbesondere die LP- Relaxierung stärken. Des Weiteren wurden zwei verschiedene Dekompositionsansätze entwickelt. Zum einen wurde aufgrund der hierarchischen Netzstruktur ein Dekompositionsansatz entwickelt, der das Modell in zwei Subprobleme unterteilt, welche nacheinander gelöst werden. Zum anderen wurde im Rahmen eines Column-Generation-Ansatzes ein Dekompositionsansatz entwickelt, der das ursprüngliche Problem in unabhängige Subprobleme zerlegt, welche separat lösbar sind. In einem übergeordneten Problem, welches die schwierigen Kapazitätsrestriktionen enthält, werden die Ergebnisse dieser Subprobleme zusammengeführt und optimiert. Folglich weichen die entwickelten mathematischen Modelle und Lösungsansätze von den bisherigen Ansätzen der Hub-Location-Literatur ab. Aufgrund der Komplexität und der Neuartigkeit des entwickelten Hub-Location-Problems besteht weiterer Forschungsbedarf. Dieser betrifft vor allem folgende Punkte: Aufgrund der Komplexität des speziellen Hub-Location-Problems, aber auch allgemeiner, grundlegender Probleme, ergeben sich Forschungsfragen bei der Untersuchung der polyedrischen Eigenschaften sowie zur Untersuchung der Komplexität selbst. Insbesondere polyedrische Eigenschaften wurden in bisherigen Arbeiten stark vernachlässigt. Auch die Weiterentwicklung von Techniken zur Reduktion der Komplexität, wie Preprocessing-Techniken oder neue Modellierungsansätze, stellen einen zukünftigen Forschungsschwerpunkt da. Auf diese Weise kann nicht nur die Komplexitätsreduktion der Probleme erzielt werden, sondern auch ermöglicht werden, dass die Probleme immer praxisnäher entwickelt werden können. Des Weiteren sollte in zukünftigen Arbeiten die hier entwickelten Lösungsansätze weiterentwickelt werden. Der Column-Generation-Ansatz kann bspw. in einen Branch-and-Bound-Ansatz integriert werden, um so einen exakten Algorithmus zu entwickeln. Auch kann ein Schwerpunkt auf die Entwicklung von weiteren Lösungsansätzen basierend auf Heuristiken, wie der Tabu Suche, gelegt werden. Aufbauend auf den grundlegenden, theoretischen Erkenntnissen des Forschungsvorhabens und der allgemeinen Modellierung ist eine Ausweitung des Ansatzes auf weitere logistische Systeme, wie bspw. den Straßengüterverkehr, möglich. Dabei ermöglicht insbesondere die flussabhängige Kostenstruktur eine praxisnahe Abbildung vieler logistischer Systeme.
Publications
- Strategic network design for wagonload traffic in German railway logistics. In: Sumalee, A., Lam, W.H.K., Ho, H.W., Siu, B. (Hrsg.): Proceedings of the 15th International Conference of Hong Kong Society for Transportation Studies (HKSTS). Hong Kong (China), 2010, S.255-262
Sender, J., Clausen, U.
- A flow-based hub location model with capacity levels. Proceedings der 4th International Conference on Experiments/Process/System Modeling/Simulation/Optimization (4th IC-EpsMsO). Athen (Griechenland), 2011, S. 21-28
Sender, J, Clausen, U.
- A new hub location model for network design of wagonload traffic. In: Żak, J. (Hrsg.): The State of the Art in the European Quantitative Oriented Transportation and Logistics Research – 14th Euro Working Group on Transportation & 26th Mini Euro Conference & 1st European Scientific Conference on Air Transport. Procedia - Social and Behavioral Sciences. (2011) Nr. 20, S. 90-99
Sender, J., Clausen, U.
- Einzelwagennetz muss flexibler werden. Internationales Verkehrswesen, (2011) Nr. 4, S. 23-26
Schaumann, H.
- Hub-Location-Problems with choice of different hub capacities and vehicle types. Lecture Notes in Computer Science. (2011) Nr. 6701, S. 535-546
Sender, J., Clausen, U.
- Neuausrichtung des Einzelwagenverkehrs – Herausforderung für den Schienengüterverkehr. Eisenbahntechnische Rundschau (ETR). (2011) Nr. 4, S. 2-5
Schaumann, H.
