Key Visual - Manage Your Business Integration
 

Aug

03

Individuelle Fahrplanoptimierung mit IBM ILOG CPLEX

By Marc Arnoldussen on Fr, Aug/03/2012

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.


Margin
Blog-Autor
Marc Arnoldussen
Marc Arnoldussen
Optimization & SCM Engineer
+49 221 97343-0
Margin
Informationen
7.0.1  7.0.2  8.0  Absatzmarkt  Active MQ  Active  Administration  Agile Lösungen  Agility  AMS  Analyst  Analytics  Anbindung  Anforderungen  Anwenderkonfernz  Apache  Application Server  API Management  API  AS2  ASP  Automatisierung  b2b  B2B Integration  Basic  Big Data  Blogreihe  Bluemix  Blueworks  BPM  Broker  BRMS  Bus  Business Process Management  Business Rules  Buzzword  Camel  Cast Iron  Cloud API  Cloud Computing  Cloud Integration  Cloud  Commerce  Compliance  Conference  Connect:Direct  CPLEX  CXF  DataPower  Decision Server Insights  Deployer  Deployment  Development  DFDL  Digitalisierte Prozesse  Digitalisierung  Domino  DSI  e-Fachverfahren  ersteinrichtung  Edi  Edition  Einführung  Einsatz  Entscheidung  Entwicklung  ESB  Excel  Fahrplanoptimierung  Features  Federated Connectivity  File Transfer  Filetransfer  Finance  FTE  gentran  gis  Geschäftsprozesse  Go Live  Google  Governance  Hardware ESB  Hosting  Hybrid-Cloud  Hybrid Cloud  Hybrid  IBM Blueworks  IBM BPM  IBM Integration Bus  IBM InterConnect  IBM  ILOG DOC  ILOG LNP  ILOG Transportation Analyst  ILOG  Impact  Infrastruktur  Installation  Integration as a Service  Integration Bus  Integration  Integrator  Interoperabilität  IT-Business-Alignment  Konfiguration  Linear  LNP  Logistik  monitoring  M2M  Manage File Transfer  Management  Marktplatz  Mathematik  Mediation  Message Broker  Messages  Messagesight  Messaging  MFT  Migration  Modellierung  MQ  MQTT  Multicast  Muster  Nachlese  Neuerungen in V7.0.1  Neuerungen  off-premise  on-premise  ODM  ODME  Öffentliche Verwaltung  Open Source  Operational Decision Management  Optimierung  OPL  OSGi  Outsourcing  PaaS  Pattern Integration  Pattern  Patterns  Performance  Portfolio  Praxis  Private  Process Server  Produktionsplanung  Prozessautomatisierung  Prozessintegration  Prozessmodelierung  Prozessoptimierung  PureSystem  Qualität  Real Time  Regelmanagement  Rollen  Routenplanung  Routing  ROI  SaaS API  SaaS Integration  SaaS  Salesforce  Schwerpunktanalyse  Script  SCM  Security  Service Federation Management  Servicemix  SFM  SI  Slotting  SoapUI  SOA Cloud Symposium  SOA  SPSS  Standard  Standardplattform  Standardtool  Standortoptimierung  Sterling Integrator  Sterling  SugarCRM  Symposium  Template  TIP  TM1  TOSCA  Transportation  Transportoptimierung  Übersicht  Umstieg  Unix  Update  vergleich  Vorteile  worklight  workload  wtc  Wartung  Websphere  Websphere: Rollen  WebService Security  WebSphere Enterprise Service Bus  WebSphere ESB  WebSphere MessageBroker  WebSphere Technical Conference  WebSphere  WESB  Workloads  WODM  XAR