Mathematische Optimierung für Frachtschiffe

 (research.google)
1 Punkte von GN⁺ 2024-06-07 | 1 Kommentare | Auf WhatsApp teilen
  • Das Operations-Research-Team von Google Research hat die Shipping Network Design API veröffentlicht, die Netzwerkdesign, Fahrpläne und Container-Routen für Linien-Containerschiffe gemeinsam optimiert
  • Das Problem wird komplex, weil gleichzeitig die Reihenfolge der Hafenanläufe, Ankunfts- und Abfahrtszeiten sowie die Start-Ziel-Routen der Container festgelegt werden müssen – bis hin zu 500 Schiffen und 200 Häfen im WorldLarge-Maßstab
  • Der anfängliche Ansatz mit dualer Column Generation und CP-SAT fand für kleine und mittlere Instanzen nachweisbar optimale Lösungen, für große Probleme waren jedoch Heuristiken nötig, die Large Neighborhood Search mit Variable Neighborhood Search kombinieren
  • Im LINERLIB-Benchmark stieg der Containerdurchsatz in WorldSmall, EuropeAsia, Pacific und Mediterranean um 35 %, 14 %, 35 % bzw. 32 %, während die Zahl der eingesetzten Schiffe um 7 %, 15 %, 4 % bzw. 23 % sank
  • Google sieht die Methode als ersten Ansatz, der Netzwerkdesign- und Fahrplanprobleme im WorldLarge-Maßstab lösen kann, und stellt die Shipping Network Design API künftig als Teil der Operations Research APIs bereit

Das Problem, Container-Seefrachtnetzwerke gleichzeitig zu optimieren

  • 90 % der weltweit gehandelten Waren werden über See transportiert; große Frachtschiffe können 0,25 Meilen lang sein, 250.000 Tonnen wiegen und 12.000 Container mit Fracht im Gesamtwert von 1 Mrd. US-Dollar transportieren
  • Anders als Flugzeuge, Züge und Lkw sind Frachtschiffe nahezu dauerhaft unterwegs und bewegen sich auf dem Meer entlang zyklischer Routen
  • Ineffiziente Routen und Fahrpläne führen dazu, dass Container in Häfen liegen bleiben, Schiffe auf See warten und Logistikflüsse verzögert werden – was sich auch auf Produktpreise auswirkt
  • Googles Shipping Network Design API implementiert eine neue Lösung für dieses Problem
    • Sie ist schneller und skaliert besser als bisher bekannte Ansätze
    • Sie kann den Gewinn von Containerreedereien verdoppeln, 13 % mehr Container transportieren und den Betrieb mit 15 % weniger Schiffen ermöglichen

Drei Entscheidungen, die das LSNDSP gemeinsam lösen muss

  • Das Liner Shipping Network Design and Scheduling Problem, kurz LSNDSP, behandelt drei Entscheidungen gleichzeitig
    • Netzwerkdesign: Festlegen, in welcher Reihenfolge Schiffe Häfen anlaufen
    • Netzwerk-Fahrplan: Festlegen, wann Schiffe ankommen und abfahren
    • Container-Routing: Auswählen, welche Reise ein Container von seinem Start- zu seinem Zielort nimmt
  • Containerreedereien müssen alle drei Probleme lösen, behandeln sie aber üblicherweise nacheinander
  • Werden die drei Probleme gleichzeitig gelöst, steigt die Schwierigkeit, aber auch die Chance auf bessere Lösungen
  • Das Ergebnis des Netzwerkdesigns führt zu Servicelinien, denen einige Schiffe folgen
    • Zum Beispiel eine Route von Ostasien durch den Suezkanal nach Südeuropa
    • Servicelinien werden zusammen mit Daten veröffentlicht, damit Verlader wissen, wann und wo sie Container bereitstellen müssen

Einschränkungen durch Hafenliegeplätze, Umschlag und Verzögerungen

  • Containerschiffe können nicht beliebig in einem Hafen anlegen, sondern müssen vorab festgelegte Liegeplatz-Slots nutzen
  • Nach der Annäherung an einen Hafen kann ein Schiff an einem Ankerplatz auf See warten, bis ein Liegeplatz verfügbar ist
    • Bei überlasteten Häfen kann es dort mehrere Stunden oder Tage bleiben
  • Ein genauer Netzwerk-Fahrplan umfasst nicht nur den Tag des Anlegens, sondern auch die genaue Uhrzeit
    • Um eine bestimmte Zeit einzuhalten, kann die Geschwindigkeit erhöht werden
    • Zur Kraftstoffeinsparung kann auch eine niedrigere Geschwindigkeit gewählt werden
  • Sobald ein Schiff angelegt hat, entladen Kräne Container und laden Container für die nächste Fahrt wieder auf das Schiff
  • Wenn sich der Fahrplan verzögert, kann es zu cut-and-run kommen: Das Schiff verlässt den Hafen, bevor alle geplanten Container geladen sind
    • Die verbleibenden Container werden dann von einem späteren Schiff mitgenommen
  • Wenn Container in einem Zwischenhafen Zeit verbringen, während sie vom Start- zum Zielort unterwegs sind, nennt man das Umladung
    • Umladung erhöht die Zahl möglicher Lösungen im LSNDSP weiter
    • Sie ist eine von mehreren Einschränkungen bei der Erzeugung von Container-Routen

Optimierungsmethoden: von Column Generation bis Neighborhood Search

  • Jedes Optimierungsproblem besteht aus Variablen, Einschränkungen für diese Variablen und einer zu minimierenden oder zu maximierenden Zielfunktion
    • Beispiel: Schiffe und Häfen sind Variablen
    • Beispiel: Die Zahl der Container, die ein Schiff aufnehmen kann, ist eine Einschränkung
    • Beispiel: Die Maximierung der Zahl transportierter Container ist eine Zielfunktion
  • Variablen und Einschränkungen werden meist als Matrix dargestellt; Spalten stehen für Variablen, Zeilen für Einschränkungen
  • Als gängige Technik zur Zerlegung großer Probleme wird Column Generation verwendet
    • Anfangs wird nur ein Teil der Variablen betrachtet
    • Anschließend werden neue Variablen – also neue Spalten – erzeugt, um das ursprüngliche Problem besser anzunähern
  • Google hat eine Softwarebibliothek entwickelt, die das Problem analysiert und vorhersagt, welche Spalten sinnvoll erzeugt werden sollten
    • Diese Bibliothek soll über MathOpt, ein Framework für mathematische Programmierung, als Open Source veröffentlicht werden

Grenzen zweier grundlegender Ansätze

  • Duale Column Generation betrachtet Netzwerkdesign und Container-Routing als zwei miteinander gekoppelte Probleme
    • Jedes Problem besteht aus einem Master-Problem, das die besten Optionen auswählt, und einem Hilfs-Generierungsproblem, das sinnvolle Optionen findet
    • Auf jedes Problempaar wird ein Kürzeste-Wege-Algorithmus angewendet, um sinnvolle Optionen zu erzeugen
    • Anschließend wählt der lineare Optimierungssolver Glop die jeweils besten Optionen aus
    • Column Generation wird gleichzeitig auf beide Probleme angewendet, wobei Zwischenergebnisse eines Problems den Fortschritt des anderen beeinflussen
    • Dieser Ansatz konnte nachweisbar optimale Lösungen finden, skalierte aber nur bis zu mittelgroßen Problemen gut
  • Auch eine Implementierung auf Basis von CP-SAT wurde ausprobiert
    • Sie verwendet Googles Constraint-Programming-Solver CP-SAT
    • Bis zu mittelgroßen Netzwerken funktionierte sie gut, skalierte aber nicht auf die Größe globaler Seefrachtprobleme
  • Beide Ansätze fanden bei kleinen und mittleren Problemen nachweisbar optimale Lösungen, boten jedoch keine ausreichende Skalierbarkeit für große Instanzen

Heuristiken für Skalierung auf große Instanzen

  • Um die Skalierbarkeit zu erhöhen, wurden zwei Varianten lokaler Suche eingesetzt, die Nachbarschaften bestehender Lösungen untersuchen, um Verbesserungsmöglichkeiten zu finden
  • Large Neighborhood Search fixiert einen Teil der Lösung und wendet dann die oben genannten Methoden an
    • Beispiel: Bedingungen wie „Dieses Schiff läuft jeden zweiten Dienstag Los Angeles an“ werden festgelegt
    • Das reduziert den Suchraum und erhöht die Skalierbarkeit
  • Variable Neighborhood Search durchsucht Nachbarschaften sowohl des Netzwerks als auch des Fahrplans
    • Die Suche wird parallelisiert und auf mehrere Maschinen verteilt, um viele Nachbarschaften gleichzeitig auszuwerten
    • So lässt sich der Suchraum begrenzen und zugleich Wissen aus Operations Research und der Schifffahrtsbranche einbeziehen
  • Beide Ansätze sperren Teile vielversprechender Lösungen und verwenden ein inkrementelles Verfahren, das von bereits guten Lösungen ausgeht und sie weiter verbessert
  • Frühere Versuche berücksichtigten Transportzeiten nicht, weil das Problem dadurch deutlich schwerer zu lösen wird; Google stellte jedoch fest, dass die Einbeziehung der Transportzeit die Lösungsqualität deutlich verbessert

Ergebnisse im LINERLIB-Benchmark

  • Die Leistungsbewertung nutzt LINERLIB, einen Branchen-Benchmark für Probleme des Seefracht-Netzwerkdesigns
    • Der Benchmark enthält Flotten, Häfen und Containernachfrage für Containerfracht-Szenarien
  • Die Testszenarien umfassen WorldSmall, EuropeAsia und WorldLarge
    • WorldLarge umfasst 500 Schiffe, 200 Häfen und rund 140.000 Container
  • Das Optimierungsziel besteht nicht einfach darin, die Zahl der Container zu maximieren oder die Zahl der Schiffe zu minimieren
    • Würde nur die Containerzahl maximiert, könnten mehr Schiffe eingesetzt werden, was die Betriebskosten erhöht
    • Würde nur die Schiffszahl minimiert, könnten unrealistisch lange Lieferzeiten entstehen, etwa wenn ein einziges Schiff alle Container transportiert
  • LINERLIB balanciert dies über den geschätzten Gewinn, also pünktliche Liefererlöse abzüglich Fahrtkosten und Kosten für die Containerabfertigung in Häfen
  • Im Vergleich zur Baseline routet Googles Methode mehr Container mit weniger Schiffen
    • WorldSmall: 35 % mehr Containerdurchsatz, 7 % weniger Schiffe
    • EuropeAsia: 14 % mehr Containerdurchsatz, 15 % weniger Schiffe
    • Pacific: 35 % mehr Containerdurchsatz, 4 % weniger Schiffe
    • Mediterranean: 32 % mehr Containerdurchsatz, 23 % weniger Schiffe
  • Auf Basis der wirtschaftlichen Annahmen von LINERLIB verbessert sich auch die erwartete Gewinnmarge deutlich

API und weitere Veröffentlichungen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-06-07
Hacker-News-Kommentare

  • Ich bin auf der Terminal-Seite dieser Branche tätig; interessant, wirkt aber sehr akademisch.
    Ich frage mich, ob das tatsächlich in Zusammenarbeit mit Reedereien entstanden ist. Auf Terminal-Seite stecken wir gerade tief in der Containeroptimierung, und es ist wirklich fast ein Albtraum. Selbst Terminals, die demselben Unternehmen gehören, arbeiten sehr unterschiedlich, und sogar die Terminologie unterscheidet sich oft innerhalb des Unternehmens. Optimiert man für ein Terminal, muss man beim nächsten 80 % neu bauen, sodass jede Lösung sehr schwer zu skalieren ist.

    • Bei Problemen der industriellen Optimierung sieht es immer so aus, als läge unglaublich viel Geld ungenutzt herum, aber in der Praxis machen nicht dokumentierte, menschenzentrierte Einschränkungen die Sache erheblich komplizierter.
      Deutsche Ingenieure wehrten sich zum Beispiel dagegen, Funktionen von Vorserienfahrzeugen zu sperren, weil sie sie dann nicht in der Freizeit nutzen konnten. Im Gesundheitswesen flossen Milliarden in Überstunden, sodass bessere Dienstpläne leicht machbar wirkten, aber es gab viele gewerkschaftliche Einschränkungen und zu wenig Personal am Markt. Ich frage mich, wie realistisch Googles Lösung ist. Fließen auch Einschränkungen wie Huthi-Raketen ein? Nach meiner Erfahrung sind Lösungen, die sich leicht an unerwartete Änderungen anpassen lassen, oft wertvoller als nachweisbar optimale Lösungen.
    • Die für die Leistungsbewertung verwendeten Benchmark-Daten stammen von Maersk: https://github.com/blof/LINERLIB
    • Ich komme nicht aus der Schifffahrt, habe aber 15 Jahre in der Fertigungsindustrie gearbeitet, hauptsächlich in Test Engineering und Automatisierung, außerdem in Lager-/Materialverwaltung sowie Transport/Logistik. Mein Master war in Operations Research für die Fertigung.
      Ich stimme zu, dass objektive Optimierung meist akademisch ist. Es gibt immer Gründe, warum man der effizientesten Version eines standardisierten Prozesses nicht einfach folgen kann oder warum das unmöglich ist. Manchmal sind es „dumme“ Gründe, die durch Menschen entstehen, häufig aber auch rationale Gründe, die Externalitäten widerspiegeln, etwa Wetter, Ausfallzeiten, Lieferkettenunterbrechungen oder holprige Nachfragesignale und Prognosen aufgrund von Saisonalität. Trotzdem halte ich es fast immer für besser, vom effizientesten Prozess auszugehen und dann Ausnahmen einzubauen, statt einen Standardprozess auf Basis bekannter Ausnahmen zu definieren. Wenn man Ausnahmen zur Regel werden lässt, arbeitet man immer weniger effizient als optimal.
    • Ich arbeite ebenfalls mit Terminals und Unternehmen im Hinterlandtransport. Es gibt viele Leute, die „cool aussehende“ akademische Probleme wie Stauplanoptimierung, Liegeplatzzuweisung oder Kranaufteilung lösen wollen, aber nur sehr wenig davon wird tatsächlich implementiert.
      Diese Branche ist schwierig, und weil Hafenarbeitergewerkschaften traditionell stark sind, ist das politische Umfeld noch schwieriger. Probleme, die man sauber abgrenzen und benennen kann, sind in der Realität miteinander verflochten, und wenn man erwartet, dass ein Algorithmus sie für die Nutzer „magisch“ löst, scheitert man fast immer. Diese Branche verschlingt Software-Schwergewichte, die mit der Haltung hineinspringen: „Ist doch nur ein Traveling-Salesman-Problem / Constraint Solver / einfach den gewünschten Ansatz laufen lassen?“ Kluge Leute werden definitiv gebraucht, aber man sollte demütig anfangen und zuerst mit den echten Nutzern sprechen. In deinem Profil scheint keine Kontaktmöglichkeit zu stehen; wenn du dich mit anderen Unternehmen in dieser Branche austauschen möchtest, schick mir gern eine Mail. Wir arbeiten an interessanten Dingen, besonders im Segment der Terminals unter 1 Mio. TEU pro Jahr mit hohem Anteil intermodaler Transporte.
    • Könntest du für Leute außerhalb dieses Bereichs etwas genauer erklären, woran du gerade arbeitest?

  • Ich lese gerade The Box über die Frühgeschichte der Containerisierung, und es ist wirklich faszinierend.
    Sehr empfehlenswert für alle, die eine unterhaltsame Mischung aus Ingenieurwesen, Design, Business und Geschichte suchen. Es lässt meine kleinen Coding-Probleme ziemlich lächerlich wirken.

    • Hervorragendes Buch, und ich stimme der Empfehlung zu.
      Das wird vermutlich viel Widerspruch hervorrufen, aber ganz ernsthaft: Ich glaube, der Einfluss des 20-Fuß-Seecontainers auf die Welt war größer als der Einfluss, den große Sprachmodelle in Zukunft möglicherweise erreichen werden. Lies zuerst das Buch und sag mir dann, warum ich falschliege. Natürlich liege ich nicht falsch.
    • Wikipedia-Artikel zu „The Box“: https://en.m.wikipedia.org/wiki/The_Box_(Levinson_book)
    • Bei Flexport wurde dieses Buch an Neueinsteiger verteilt. Zumindest war das vor ein paar Jahren so.

  • Bei sehr großen Flotten scheint Containeroptimierung offenbar noch ein ungelöstes Problem gewesen zu sein. Wusste ich nicht.
    Wenn Googles Operations Research die Auslastung gegenüber bestehenden Lösungen um 10–20 % verbessert hat, ist das beeindruckend.

  • Ich bin sehr gespannt, ob irgendjemand diesen veröffentlichten API-Endpunkt tatsächlich nutzt: https://developers.google.com/optimization/service/shipping/...
    Trotzdem ziemlich cool.

    • Aus meiner beruflichen Erfahrung bei Google Cloud von 2015 bis 2023 sind solche Operations-Research-APIs 1) akademisch geprägt und 2) kommerziell vor allem dafür gedacht, dass Google-Cloud-Solutions-Architects und -Engineers kundenspezifische Business-Lösungen bauen, die auf GCP laufen.
      Ein typisches Beispiel ist die Route Optimization API, die ein Operations-Research-Team für Unternehmen auf diese Weise veröffentlicht hat; später wurde auf Basis des Inputs einiger Alpha-Kunden darauf die Fleet-Engine-Lösung aufgebaut. Solange eine Operations-Research-API nicht über Google Cloud bereitgestellt wird, gibt es keine SLA- oder Zuverlässigkeitsgarantie; daher würde ich sie außer für akademische Zwecke nicht verwenden. Nur meine zwei Cent.
      https://developers.google.com/maps/documentation/transportat...
    • Es könnte sogar unverantwortlich sein, es nicht auszuprobieren. Ich frage mich, ob das die vollständige Form der Probleme und Einschränkungen ist, mit denen Planer konfrontiert sind. Flexport ist in diesem Bereich ein in SF ansässiges Unternehmen mit 3,3 Mrd. US-Dollar Umsatz.
    • Googles Friedhof[1] wächst schnell, daher bin ich bei neuen Google-Ankündigungen vorsichtig. Solche APIs dürften besonders problematisch sein, wenn man sie in Zukunft ersetzen muss.
      [1]: https://killedbygoogle.com/

  • Wenn Liegegeld nicht berücksichtigt wird, weiß ich nicht, ob es sich wirklich lohnt, das auszuprobieren
    https://developers.google.com/optimization/service/reference...

  • Der Omega Tau Podcast hat eine sehr gute Folge[0] über Container-Verschiffung gemacht, in der auch die Optimierung der Containerplatzierung und Routenplanung behandelt werden. Sehr empfehlenswert
    [0]: https://omegataupodcast.net/146-container-shipping/

  • Die Formulierung „anders als Flugzeuge sind Frachtschiffe fast ununterbrochen im Einsatz“ kann man durchaus etwas hinterfragen
    Frachtschiffe werden zwar während der Fahrt viel gewartet, aber ansonsten ist der Unterschied meiner Ansicht nach deutlich kleiner. Im Hafen werden sie über mehrere Tage hinweg entladen und beladen und abgefertigt, und sie warten auch Stunden oder Tage auf einen Liegeplatz. Wenn man sich den Fall der Delta A350 ansieht, ist sie abgesehen von 3 Stunden Turnaround am Flughafen praktisch rund um die Uhr in Bewegung: https://www.flightradar24.com/data/aircraft/n513dz

    • Ich denke, man kann sie auch beim Entladen als „in Betrieb“ bezeichnen

  • Das erinnert mich daran, wie Inhaber oder Manager von Läden wie Restaurants in der Nachbarschaft sagen, dass es ihnen Kopfzerbrechen bereitet, Schichten für Aushilfen zu planen, und sogar behaupten, das sei der Grund, warum sie so gut bezahlt werden
    Ich dachte, das müsste sich doch algorithmisch lösen lassen

    • Viele Menschen mögen es nicht, wenn sich ihre Arbeitszeiten stark ändern
      Man kann vielleicht die Nacht abdecken, in der die Hälfte der Belegschaft zu Taylor Swift geht, aber wenn man dafür Leute hereinholt, muss deren nächste Schicht wiederum von jemand anderem abgedeckt werden, und wenn sich das fortsetzt, entsteht ein völlig anderer Dienstplan mit Leuten, die noch nie miteinander gearbeitet haben. Mit mehr Constraints lässt sich das beheben, aber allein sie alle aufzuschreiben und zu priorisieren ist nicht einfach. Menschen sind keine Legosteine
    • Das ist genau das Problem, das ich lösen möchte. Ich höre dieselbe Geschichte von fast allen, die Dienstpläne erstellen
      Mit meinem Hintergrund in Operations Research kam mir das immer seltsam vor. Die Probleme wirken einfach genug, um sie mit allgemeinen Solvern zu modellieren und zu lösen, und der potenzielle Nutzen scheint auch ohne fortgeschrittene Methoden groß zu sein. Das Problem ist, dass Operations Research insgesamt schwer zugänglich ist. Die meisten gut unterstützten Solver lassen einen Probleme in einem mathematischen Paradigma definieren, was „normale Menschen“ auf den ersten Blick überwältigt. Es gibt auch fertige Lösungen für typische Planungsprobleme, aber wenn man nicht von Anfang an damit gearbeitet hat, hat jeder Betrieb seine eigenen Varianten, was eine vollständige Einführung schwierig macht. Entweder unterstützen sie diese Varianten nicht, oder man weiß nicht, wie man sie in das Tool hineinbekommen soll. Selbst wenn der Wille da ist, Dienstpläne besser zu lösen, setzen die Kurse, die man findet, meist erhebliche Programmier- oder Mathematikvorkenntnisse voraus. Ich denke, man müsste für Dienstplanungsprobleme eine No-Code-Modellierungsumgebung bauen können, die auch „normale Menschen“ nutzen können, für die Excel nicht ausreicht, die sich aber keinen Operations-Research-Experten leisten können
    • Das ist ein wirklich wichtiges Problem, und viele Softwareprodukte befassen sich bereits damit
      Fast jedes größere HR-/Workforce-Management-System enthält entsprechende Optionen. Zum Beispiel https://www.workday.com/en-us/products/workforce-management/... und https://www.oracle.com/human-capital-management/workforce-ma... gibt es, und es gibt auch viele spezialisierte Anbieter. Allerdings waren solche Systeme, wie andere gesagt haben, auch umstritten. Manche werden nämlich so eingesetzt, dass sie normale menschliche Bedürfnisse nicht berücksichtigen. Zum Beispiel indem sie aufeinanderfolgende Schichten zuweisen, Dienstpläne kurzfristig ändern oder reale Umstände wie Kinderbetreuung nicht berücksichtigen können, die ein menschlicher Manager einbeziehen würde
    • In derselben Operations-Research-Gruppe gibt es ein Beispiel für Dienstplanung in Restaurants: https://developers.google.com/optimization/service/schedulin...
    • Ich habe etwas Hintergrund in kombinatorischer Optimierung und habe schon darüber nachgedacht, Software für dieses Feld oder etwa für Stundenplanung an Schulen auszuprobieren
      Das Problem ist aber, dass jeder Betrieb andere Constraints hat. Etwa dass in jeder Schicht mindestens eine Person mit Erste-Hilfe-Kenntnissen sein muss, dass Alice und Bob nicht miteinander auskommen, dass man nicht an zwei Samstagen hintereinander arbeiten darf, dass Schichten alle zwei Wochen wechseln oder dass zwischen Schichten mindestens 12 Stunden liegen müssen. Ein Tool, das flexibel genug ist, damit viele Organisationen es nutzen können, würde am Ende vermutlich so komplex werden, dass es schwer zu bedienen ist

  • Ich frage mich immer noch, wie die Stauplanung für solche Schiffe aussieht
    Das dürfte ein Problem sein, das im nächsten Schritt nach der Routenplanung für jeden Container näherungsweise gelöst werden muss. Die Stauplanung kommt später ins Spiel und hat Einschränkungen, die viel stärker von der jeweiligen Situation abhängen als von einer globalen Systemsicht. Selbst grob optimistisch gerechnet schafft ein Kai-Kran 30 bis 50 Bewegungen pro Stunde; pro Schiff sind 2 oder 4, manchmal sogar 6 Krane im Einsatz, und das Ganze muss schichtweise wie eine Schale abgearbeitet werden. Ein Ultra Large Container Vessel hat mindestens 14.501 TEU, New Panamax 10.000 bis 14.500 TEU, Post-Panamax 5.101 bis 10.000 TEU, Panamax 3.001 bis 5.100 TEU. Wenn man 24.000 TEU als 12.000 40-Fuß-Container annimmt, ergibt das 4 Krane × 50 Container pro Stunde und Kran × 24 Stunden pro Tag = etwa 1.200 Container pro Tag.
    https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
    Bei der Stauplanung eines Schiffs gibt es neben der Verfügbarkeit im Hafen auch Kriterien für Gewicht, Balance, Stromversorgung und den zulässigen Wert der Ladung. Weil im Artikel die frühere Abfahrt aus dem Hafen erwähnt wurde, habe ich mich für diesen Overhead interessiert und eine grobe Rechnung angestellt.

    • Es gibt einen online veröffentlichten Vortrag eines Forschers der Technical University of Denmark (DTU), der als Einführung in das Stauproblem ziemlich gut ist: https://www.youtube.com/watch?v=9ltz4G-lPdg
      Aus Sicht von jemandem, der tatsächlich in diesem Bereich arbeitet, gibt es viele Möglichkeiten, sich die Arbeit zu erleichtern. Es ist grundlegend, nach Blöcken pro Lukendeckel zu planen und Container nach Ziel, Größe und Gewicht zu gruppieren und als austauschbar zu behandeln. Wenn man den Plan dann vor Arbeitsbeginn vom Schiff an das Terminal schickt, kann auch das Terminal optimieren und umstauen, weil es die Positionen der Container im Yard kennt. Wenn man sich entscheidet, die Details einzelner Container zu ignorieren und sich nur auf Gruppen zu konzentrieren, wird die Stauplanung deutlich einfacher. Mit viel weniger Aufwand erhält man sehr ähnliche Ergebnisse, und das Terminal hat mehr Flexibilität, seinen Betrieb zu optimieren.