Mathematische Optimierungstechnologie für Frachtschiffe

Optimierung von Transportnetzwerken für Frachtschiffe: Mathematische Optimierungsmethoden

Überblick

• Das Google-Forschungsteam hat eine neue Shipping Network Design API vorgestellt.
• Diese API hilft dabei, Probleme beim Netzwerkdesign und bei der Fahrplanerstellung von Frachtschiffen zu lösen.
• Diese Lösung ist schneller und effizienter als bestehende Methoden, verdoppelt die Erträge und ermöglicht den Transport von mehr Containern mit weniger Schiffen.

Hintergrund

• LSNDSP (Ship Network Design and Scheduling Problem) besteht aus drei Elementen: Netzwerkdesign, Netzfahrplanerstellung und Container-Routing.
• Bisher wurden diese Probleme einzeln gelöst, doch wenn man sie gleichzeitig löst, lassen sich bessere Lösungen finden.

Methodik

• Optimierungsprobleme bestehen aus Variablen, Nebenbedingungen und Zielfunktionen.
• Google löst das Problem mit zwei Ansätzen: Double Column Generation und CP-SAT.
• Diese Methoden liefern für kleine und mittlere Probleme optimale Lösungen, sind jedoch für große Probleme nicht geeignet.
• Zur Lösung großer Probleme werden Large Neighborhood Search und Variable Neighborhood Search eingesetzt.
• Diese Methoden verkleinern den Suchraum und steigern die Effizienz durch Parallelverarbeitung.

Ergebnisse

• Die Leistung wurde mit dem LINERLIB-Benchmark bewertet.
• Googles Lösung ermöglicht den Transport von mehr Containern mit weniger Schiffen.
• In jedem Szenario wird die Effizienz erhöht und der Ertrag deutlich gesteigert.

Fazit

• Googles Optimierungsmethoden sind der erste Ansatz, der große Probleme beim Design und der Fahrplanerstellung von Schiffsnetzwerken lösen kann.
• Es wird erwartet, dass diese Forschung zur Steigerung der Effizienz globaler Lieferketten beiträgt.

Meinung von GN⁺

• Technischer Hintergrund: LSNDSP ist ein komplexes Optimierungsproblem, bei dem Netzwerkdesign, Fahrplanmanagement und Routing gleichzeitig gelöst werden müssen.
• Industrielle Bedeutung: 90 % des globalen Handels sind auf den Seetransport angewiesen, daher hat die Lösung dieses Problems große wirtschaftliche Auswirkungen.
• Technische Herausforderung: Um große Probleme zu lösen, sind fortgeschrittene Methoden wie Parallelverarbeitung und die Verkleinerung des Suchraums erforderlich.
• Wettbewerbsprodukte: Andere Optimierungslösungen mit ähnlichen Funktionen sind unter anderem IBM CPLEX und Gurobi.
• Zu beachten: Bei der Einführung neuer Technologien können anfängliche Einrichtungskosten und eine Lernkurve anfallen. Langfristig können Effizienz und Rentabilität jedoch deutlich verbessert werden.

[GN⁺]

Hacker-News-Kommentare

• Meinung aus Terminal-Sicht: Die Optimierung von Terminals ist sehr komplex, und da jedes Terminal anders arbeitet, ist sie schwer skalierbar.
• Buchempfehlung „The Box“: Ein Buch über die Frühgeschichte der Containerisierung, eine interessante Lektüre, die Engineering, Design, Business und Geschichte verbindet.
• Problem der Containeroptimierung: Das Problem der Containeroptimierung für große Flotten ist noch nicht gelöst.
• Verbesserung durch Google OR: Google OR verbessert bestehende Lösungen um 10–20 %.
• Frage zur API-Nutzung: Es ist fraglich, ob sich ein Versuch lohnt, wenn demurrage (Liegegeld/Standgeld) nicht berücksichtigt wird.
• Neugier auf API-Endpunkte: Es ist interessant, ob die von Google angebotenen API-Endpunkte tatsächlich genutzt würden.
• Empfehlung des Omega-Tau-Podcasts: Es gibt dort eine hervorragende Folge über Containerschifffahrt und Optimierung.
• Ausführung im Docker-Container: Es funktioniert nur, wenn es in einem Docker-Container ausgeführt wird.
• Vorschlag zum Einsatz von Algorithmen: Vielleicht ließe sich die Einsatzplanung von Teilzeitkräften mit einem Algorithmus lösen.
• OR-Tools als Service: Offenbar werden OR-Tools nun als Service angeboten. Wenn eine bessere API verfügbar wäre, wäre man bereit, für GCP-Computing-Kosten zu zahlen.
• Frage zur Ladeplanung: Die Ladeplanung ist ein Problem, das nach der Routenplanung gelöst werden muss. Es wird eine grobe Berechnung zur Geschwindigkeit von Kranarbeiten sowie zum Be- und Entladeprozess vorgestellt.
• Komplexität der Ladeplanung: Zur Ladeplanung gehören Kriterien wie Gewicht, Balance, Stromversorgung und Werthaltigkeit der Ladung. Wegen dieser Komplexität wird ein einfacher Rechenansatz versucht.