Exact and heuristic algorithms for uncertain and time-dependent hub location problems based on quadratic optimization
Final Report Abstract
Hub-Location-Probleme behandeln die strategische Planung von Transportnetzen: Für eine Anzahl an Depots sollen untereinander Sendungen ausgetauscht werden. Da die Etablierung einer Direktverbindung von jedem Depot zu jedem anderen Depot zu kostenintensiv ist, wird stattdessen eine Reihe von Standorten als Hubs ausgewählt; jede Sendung wird vom Start- zum Zieldepot über ein oder zwei Hubs geroutet. Diese Vorgehensweise lohnt sich, sofern die Einsparungen durch Transportbündelung die zusätzlichen Kosten der Hubs überschreiten. Mehr als drei Jahrzehnte nach Beginn der Hub-Location-Forschung stellt die strategische Planung von Transportnetzwerken immer noch eine Herausforderung dar. Für die stark vereinfachten Modelle der Achtziger Jahre stehen mittlerweile ausgereifte Algorithmen zur Verfügung. Hier wird jedoch mit einem Transportkostensatz pro Tonnenkilometer gerechnet, der auf Hub-Hub-Verbindungen mit einem festen Faktor diskontiert wird. Dies führt mitunter zur Einplanung schlecht ausgelasteter Fahrzeuge. Weiterhin werden alle Daten als bekannt vorausgesetzt und mögliche Schwankungen oder Störungen ignoriert. Für anwendungsnahe Modelle besteht noch großer Forschungsbedarf. In der ersten Projektphase wurden wesentliche Fortschritte bezüglich der Modellintegration komplexer Transportkostenfunktionen erzielt. In enger Zusammenarbeit der Projektpartner erfolgte die Entwicklung heuristischer und exakter Optimierungsverfahren, welche gute Lösungen auch bei großen, realistischen Problemgrößen berechnen. Gerade bei Single-Allocation-Problemen, in denen die Sendungen ohne Sortierung zu dem gewählten Hub transportiert werden (wie etwa in Postnetzen), haben sich die entwickelten quadratischen Optimierungsmethoden bewährt. Wesentlich für die Einsetzbarkeit der diskutierten Modelle ist es, den Schritt von deterministischen zu stochastischen Daten zu gehen. In der Realität sind Transportmengen und -zeiten nicht vorher bekannt und Hubausfälle können ein schlecht geplantes Netzwerk empfindlich stören. Daher haben wir in der zweiten Projektphase die stochastischen Einflüsse in mathematischen Problemformulierungen integriert und hierfür effiziente Dekompositionsverfahren entwickelt. Mit unserem Projekt haben wir nicht nur einen Beitrag zur Lösung anwendungsnaher Transportplanungsprobleme geleistet, sondern konnten auch algorithmisch und mathematisch in neue Bereiche vorstoßen, besonders in der Kombination von quadratischen Optimierungstechniken mit stochastischen Einflüssen.
Publications
- (2013): Strategic planning in LTL logistics - increasing the capacity utilization of trucks. In: Electronic Notes in Discrete Mathematics (41), S. 37–44
Clausen, Uwe; Meier, J. Fabian
(See online at https://dx.doi.org/10.1016/j.endm.2013.05.073) - (2014): Heuristic Strategies for a Multi-Allocation Problem in LTL Logistics. In: Stefan Helber (Hg.): Operations Research Proceedings 2012. Selected papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz Universität Hannover, Germany, September 5 - 7, 2012. Cham: Springer, S. 521–526
Clausen, Uwe; Meier, J. Fabian
(See online at https://doi.org/10.1007/978-3-319-00795-3_78) - (2015): Some Numerical Studies for a Complicated Hub Location Problem. In: Hans-Jürgen Sebastian, Phil Kaminsky und Thomas Müller (Hg.): Quantitative Approaches in Logistics and Supply Chain Management. Proceedings of the 8th Workshop on Logistics and Supply Chain Management, Berkeley, California, October 3rd and 4th, 2013. Cham: Springer (Lecture Notes in Logistics), S. 33–43
Meier, J. Fabian; Clausen, Uwe
(See online at https://doi.org/10.1007/978-3-319-12856-6_2) - (2016): A Compact Linearisation of Euclidean Single Allocation Hub Location Problems. In: Electronic Notes in Discrete Mathematics 52, S. 37–44
Meier, J. Fabian; Clausen, Uwe; Rostami, Borzou; Buchheim, Christoph
(See online at https://doi.org/10.1016/j.endm.2016.03.006) - (2016): Lower Bounding Procedures for the Single Allocation Hub Location Problem. In: Electronic Notes in Discrete Mathematics 52, S. 69–76
Rostami, Borzou; Buchheim, Christoph; Meier, J. Fabian; Clausen, Uwe
(See online at https://doi.org/10.1016/j.endm.2016.03.010) - (2017). The uncapacitated single allocation phub median problem with stepwise cost function. Optimization Online
Rostami, Borzou; Buchheim, Christoph
- (2018): Reliable single allocation hub location problem under hub breakdowns. In: Computers & Operations Research (96), S. 15–29
Rostami, Borzou; Kämmerling, Nicolas; Buchheim, Christoph; Clausen, Uwe
(See online at https://doi.org/10.1016/j.cor.2018.04.002) - (2018): Solving Single Allocation Hub Location Problems on Euclidean Data. In: Transportation Science 52 (5), S. 1141–1155
Meier, J. Fabian; Clausen, Uwe
(See online at https://doi.org/10.1287/trsc.2017.0751) - (2020): Oracle-based algorithms for binary twostage robust optimization. In: Computational Optimization and Applications 77 (2), S. 539–569
Kämmerling, Nicolas; Kurtz, Jannis
(See online at https://doi.org/10.1007/s10589-020-00207-w) - (2020): Stochastic single-allocation hub location. In: European Journal of Operational Research
Rostami, Borzou; Kämmerling, Nicolas; Naoum-Sawaya, Joe; Buchheim, Christoph; Clausen, Uwe
(See online at https://doi.org/10.1016/j.ejor.2020.07.051) - (2021): Dekompositionsverfahren zur strategischen Planung von Hub-and-Spoke-Netzen unter Nachfrageschwankungen. Dissertation, Fakultät Maschinenbau, Technische Universität Dortmund
Kämmerling, Nicolas
