Datum
03.08.2012
Dieser Beitrag wurde verfasst von:
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.
Optimierung eines Schienennetzes
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.
Vorteile von CPLEX
Entwickelt wurde das Modell mit der ILOG-eigenen Sprache OPL (Optimization Programming Language). Diese ist syntaktisch sehr nah an der üblichen mathematischen Notation, sodass jeder Mathematiker ein OPL-Modell ohne Schwierigkeiten lesen und verstehen kann.
CPLEX ermöglicht einem, verschiedene Modelle und Datensätze zu eigenen Ausführungskonfigurationen zusammenzustellen. So kann beispielsweise dasselbe Modell mit unterschiedlichen Daten getestet werden, oder es können verschiedene Modelle mit gleichem Datensatz auf Laufzeit, Speicherverbrauch, Solververhalten etc. untersucht werden.
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.
Erstellung verschiedener OPL-Modelle
So waren wir dafür verantwortlich, ein Modell zu entwickeln, das im Idealfall die optimale Route der einzelnen Züge berechnet. Dabei musste berücksichtigt werden, dass Züge mit unterschiedlichen Lieferungen in einem bestimmten Schema an den einzelnen Standorten ankommen. Außerdem mussten die Anzahl der Züge und die parallele Nutzbarkeit der Gleise beachtet werden. Ziel war es, die Frequenz der Züge zu erhöhen, sodass eine höhere Produktivität an den Zielorten möglich war.
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
Lösungsansatz: Netzwerkflussmodell
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.
Fazit
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.
Autor
Marc Arnoldussen
X-INTEGRATE Software & Consulting GmbHKontakt