Individuelle Fahrplanoptimierung mit IBM ILOG CPLEX

Bei Supply Chain-Fragestellungen kann es vorkommen, dass einem die ILOG Supply Chain-Produkte wie LogicNet Plus XE und Transportation Analyst für die eigenen Bedürfnisse unpassend erscheinen. Für diesen Fall (und selbstverständlich für weitere Fälle) bietet ILOG CPLEX die Möglichkeit, ein eigenes mathematisches Modell zu entwickeln und darauf basierend Problemstellungen zu optimieren.

Dies war bei einem Kunden der Fall, der seine Güter über ein Schienennetz verteilt. Aufgrund verschiedenster Restriktionen, die bei sonst üblichen Supply Chains keine Anwendung finden, war die Nutzung von ILOG CPLEX die sinnvollste Alternative.

Unsere Aufgabe war es nun, zusammen mit einem weiteren CPLEX-Experten ein Modell zu entwickeln, das sämtliche gewünschte Restriktionen berücksichtigt und dabei performant bleibt.

Außerdem ist es möglich, innerhalb eines Modells weitere Modelldateien einzubinden, sodass die Zusammenarbeit hierüber sichergestellt werden konnte. Während unsere Aufgabe darin bestand, das Grundgerüst für das Modell zu entwerfen und Testmodelle zu entwickeln, konnten weitere spezifische Restriktionen parallel extern entwickelt werden.

Im Parallelmodell wurden außerdem Restriktionen eingebaut, die es ermöglichten, eine Gleissperrung und andere Störungen im Ablauf zu simulieren, um auch für diesen Fall in kürzester Zeit einen neuen Fahrplan erstellen zu können.

Im Endeffekt bestand das Projekt aus fünf verschiedenen Modellen mit den Funktionen

• Datengenerator zur Erstellung von Testdaten
• Automatische Datenbereinigung zur Nutzung externer Daten
• Grundmodell ohne Störungen im Ablauf
• Erweiterung des Modells
• Aufbereitung der Daten zur Lösungsausgabe

Die Problemstellung wurde durch ein Netzwerkflussmodell realisiert. Dies beruht darauf, dass jeder Ort zu jedem möglichen Zeitpunkt einen Knoten darstellt, jede Verbindung zwischen diesen Knoten wird Kante genannt. Die Nutzung der Kanten wird über Entscheidungsvariablen definiert: Der Wert einer Kante repräsentiert die Anzahl der Züge, die diese Kante nutzen. Der Fluss wird dadurch sichergestellt, dass die Anzahl der eingehenden Züge an einem Knoten mit der Anzahl der ausgehenden Züge übereinstimmen muss. Dabei zählen auch Züge, die am Standort bleiben, zu den ausgehenden Zügen, da in diesem Fall die Kante von Ort O und Zeitpunkt t zu Ort O und Zeitpunkt t+1 genutzt wird.

Auf diese Art entsteht ein lineares Modell, das lediglich durch die Ganzzahligkeitsbedingung in der Performanz eingeschränkt werden kann. Durch die vorliegende Modellgröße war dies allerdings kein Problem, eine optimale Lösung konnte in wenigen Sekunden errechnet werden.

Somit ist CPLEX für diese Art von Optimierungsanforderungen ideal geeignet, nicht zuletzt aufgrund der Möglichkeit, vielfältigste Restriktionen einbauen und das Modell damit Schritt für Schritt an die eigenen Bedürfnisse anpassen zu können.