TU BRAUNSCHWEIG

Zeitkritische Ablaufbergoptimierung in Rangierbahnhöfen

Projektmitarbeiter: Ronny Hansmann
Projektleiter: Uwe Zimmermann
Laufzeit: 01.04.2004 - 31.08.2007
  

    Ablaufberg     Rangierbahnhof

 

Dieses Projekt mit der BASF AG als Projektpartner ist Teil des BMBF-Verbundprogrammes "Mathematik für Innovationen in Industrie und Dienstleistungen". Im Ludwigshafener Stamm­werk der BASF wird ein Großteil der internen Logistik auf der Schiene abgewickelt. Ein Nadelöhr stellt dabei der werkseigene, kostenintensive Rangierbahnhof mit Ablaufberg dar, in dem eingehende Züge zerlegt und die Wagen zu Ausgangszügen umsortiert werden. Das Projektziel, ein Optimierungstool als Entscheidungsunterstützung für die Disponenten zu entwickeln, das vollautomatisch optimale Pläne zur Sortierung der Wagen erzeugt, wurde innerhalb der Projektlaufzeit erfolgreich verwirklicht.
Im Rahmen des Projektes wurde eine umfassende theoretische Klassifizierung zahlreicher Varianten derartiger Sortierprobleme eingeführt. Für viele Varianten wurde deren Äquivalenz zu bestimmten Graphenfärbungs-, Scheduling- sowie Bin-Packing-Problemen gezeigt sowie eine komplexitätstheoretische Einordnung vorgenommen. Für mehrere als theoretisch schwer bewiesene Fälle wurden schnelle approximative Algorithmen erarbeitet, die Lösungen mit einer beweisbaren Güte liefern. Desweiteren wurden neben heuristischen Metho­den auch exakte Verfahren zur Bestimmung optimaler Lö­sungen entwickelt. Unter an­derem handelt es sich bei den exakten Ansätzen um LP- sowie Lagrangebasierte Branch-and-Bound-Verfahren, die auf verschiedenen binären Modellen beruhen.
Insbesondere für das reale Optimierungsproblem bei der BASF konnten mit den vorgeschla­genen Ansätzen innerhalb weniger Minuten optimale Sortierpläne für einen kompletten Tag bestimmt werden. Darüber hinaus wurde eine heuristische Lösungsmethode erarbeitet und prototypsich in Form einer Windows-Oberflächenanwendung umgesetzt, mit der sich Sor­tierpläne bestimmen lassen, die nur geringfügig vom Optimum abweichen. Aufgrund der Berechnungszeiten von unter einer Sekunde bietet dieser heuristische Ansatz die Möglichkeit zur schnellen Re-optimierung im Falle von Störungen oder Abweichungen vom ursprünglich angenommenen Wageneingang.
Es sei auf das Verwertungspotenzial der entwickelten Optimierungsverfahren innerhalb anderer Anwendungsbereiche, in denen Sortieren, Stapeln, Lagern oder Verstauen eine Rolle spielen, hingewiesen.

  

Projektpartner:
- BASF AG, Ludwigshafen

 

Relevante Publikationen:

Ronny Hansmann:
Optimal Sorting of Rolling Stock,
Dissertation, TU Braunschweig & Cuvillier Verlag Göttingen, 2011.
Druck oder PDF

Ronny Hansmann und Uwe Zimmermann:
Optimal Sorting of Rolling Stock at Hump Yards,
In MATHEMATICS - Key Technology for the Future: Joint Projects Between Universities and Industry 2004-2007, Springer Verlag Berlin, 2008.
Link

 


  aktualisiert am 17.10.2013
TU_Icon_E_Mail_1_17x17_RGB Zum Seitenanfang