Rampen und Leercontainer: Zwei Forschungsarbeiten in unserem Planer

Ein klassisches Tourenplanungsmodell prüft jede Tour für sich. Jede Tour hat ihre eigene Kapazität, ihre eigenen Zeitfenster und ihren eigenen Fahrer, und die Touren begegnen sich nur in den Gesamtkosten. Das macht das Problem lösbar. Es ist aber auch der Grund, warum so viele optimierte Pläne auf dem Hof auseinanderfallen.

Zwei Dinge im Güterverkehr brechen diese Unabhängigkeit auf. Eine Rampe kann jeweils nur einen Lkw aufnehmen, egal zu welcher Tour er gehört. Ein Leercontainer, den eine Tour mitnimmt, steht für die nächste nicht mehr bereit. Wir haben uns angesehen, wie das Operations Research mit beidem umgeht, und die Ideen in den Planer eingebaut, der hinter dem Optimierer von Transportial und /vrp/solve steht.

Rampen: Bombelli und Fazi (2022)

A. Bombelli und S. Fazi untersuchten Lkw, die Luftfracht bei Spediteuren abholen und an Abfertiger (Ground Handler) an einem Flughafen liefern. Ein Ground Handler hält für sie nur ein oder zwei Rampen frei. Ihre Arbeit modelliert das als Pickup-and-Delivery-Problem mit Zeitfenstern, in dem an einer Abfertigungsstelle nicht mehr Lkw gleichzeitig bedient werden können, als sie Rampen hat.

Ihre Heuristik ist eine Adaptive Large Neighbourhood Search. Jede Route bleibt für sich zulässig, der Plan als Ganzes darf eine Rampe aber gegen einen Strafwert überbuchen. Nach jeder Einfügung geht ein Resolver die Rampenkonflikte in zeitlicher Reihenfolge durch. Bei jedem Konflikt verzögert er den Lkw, bei dem die Verschiebung am geringsten ausfällt; das kostet nichts, wenn dieser Lkw Puffer hat.

Ihre Ergebnisse sind für alle wissenswert, die mit Rampen planen:

• Ohne Koordination standen Lkw bis zu etwa drei Stunden in der Warteschlange, und manche Pläne wurden unzulässig.
• Die Koordination der Rampen senkte die Fahrzeit um 2 bis 19 %.
• Eine zweite Rampe war vor allem für die Zulässigkeit wichtig: Beide Rampen waren in weniger als 10 % der Zeit gleichzeitig belegt.

Was wir gebaut haben

Unser Planer führt für jeden Ort mit Kapazitätsgrenze eine Zeitleiste: für eine Rampe, ein Ladetor, einen Liegeplatz oder ein Ladegleis, für jeden Verkehrsträger gleich. Die Zeitleiste enthält die Aufenthalte aller Touren im Plan. Sie enthält auch, was von außerhalb des Plans belegt ist: andere Trips, die bereits an diesem Ort sind, und bereits gebuchte Rampen-Zeitslots.

Wenn der Planer eine Tour terminiert, fragt er an jedem begrenzten Stopp die Zeitleiste ab. Die Abfertigung beginnt, sobald eine Rampe für die gesamte Abfertigungsdauer frei ist, sofern die Zeitfenster das noch zulassen. Die Wartezeit zählt als echte Wartezeit, im Arbeitstag des Fahrers und in Zeit und Kosten der Tour. Jeder begrenzte Stopp kostet eine Abfrage, sodass das Prüfen eines Kandidaten günstig bleibt, und ein Plan ohne Rampengrenzen läuft genau wie bisher.

Hier sind wir bewusst von der Veröffentlichung abgewichen. Unsere Suche jongliert außerdem mit Lenkzeitkonten, Aufliegern, Kammern und Equipment-Bestand, und eine überbuchte Rampe würde jede dieser Zeiten unsicher machen. Deshalb halten wir jeden Plan innerhalb der Suche rampenzulässig:

• Platz machen. Kann eine Kandidatentour nicht rechtzeitig warten, werden die Touren, die ihr im Weg stehen, nach ihr terminiert, sofern sie dann noch passen. Das ist das Prinzip der Veröffentlichung: Der Lkw, der sich verschieben lässt, macht Platz. Die Kandidatentour trägt deren zusätzliche Zeit, und wenn keine Verschiebung funktioniert, wird die Einfügung abgelehnt.
• Der Resolver. Nach jedem angenommenen Schritt bekommt eine wartende Tour die Rampe zuerst, wenn die Tour, die sie belegt, mit geringeren Kosten warten könnte. Meist ist das eine Verschiebung innerhalb des Puffers, und der Tausch wird nur beibehalten, wenn beide Touren zusammen Zeit einsparen.
• Feste Reservierungen. Bestehende Trips und gebuchte Zeitslots werden nie verschoben.

Wenn Sie Überbuchungen lieber zulassen, stellen Sie die Regel dock_capacity auf Warnen. Eine Tour darf dann gegen Kosten pro Minute überbuchen, und das wird gemeldet, wie in der Veröffentlichung.

Leercontainer: Fazi, Choudhary und Dong (2023)

S. Fazi, S.K. Choudhary und J.X. Dong untersuchten Containertransporteure, die von einem Binnenterminal aus arbeiten. Ein Lkw macht mehrere Umläufe am Tag, jeweils mit einem Container.

• Woher Leercontainer kommen. Ein Export braucht einen Leercontainer: aus dem begrenzten Bestand des Terminals, aus einem gerade entladenen Import (ein Street-Turn: Der frei gewordene Container wird direkt für eine Exportladung weiterverwendet) oder aus einem entfernten Depot.
• Die harte Nebenbedingung. Der Leercontainerbestand des Terminals darf zu keinem Zeitpunkt unter null fallen. Das verknüpft die Umläufe verschiedener Lkw miteinander.
• Ihre Lösung. Sie lösen das Problem exakt, mit Branch-and-Price. Die Bestandsbedingung wird nur zu „kritischen Zeitpunkten“ geprüft: in den Momenten, in denen ein Umlauf einen Leercontainer entnimmt, denn knapp werden kann der Bestand nur bei einer Entnahme. Ein Umweg zum Depot wird in die Kante eingepreist, statt ein zusätzlicher Stopp zu werden.

In realen Fällen bei Tilburg und 's-Hertogenbosch waren ihre Pläne 25 bis 43 % günstiger als die der Disponenten, mit weniger Umläufen. Sie testeten auch, was bei engeren Bedingungen passiert. Weniger Gelegenheiten für Street-Turns erhöhten die Kosten in den realen Fällen um 2 bis 12 %, und ein Tagesstart ohne Leercontainer im Bestand um bis zu 27 %.

Was wir gebaut haben

Eine Sendung kann jetzt angeben, dass sie bei der Abholung eine Einheit braucht, nach der Zustellung eine freigibt, oder beides. Eine Einheit kann ein Leercontainer, eine Wechselbrücke oder ein Pool-Auflieger sein.

Wenn der Planer eine Tour aufbaut, sucht er für jede benötigte Einheit eine Quelle in dieser Reihenfolge:

1. Eine früher auf derselben Tour frei gewordene Einheit, wenn beide Sendungen einen Street-Turn zulassen und der Lkw sie dazwischen mitführen kann.
2. Der Bestand oder das Depot mit dem geringsten Umweg, angefahren auf dem Weg zur Abholung.

Eine frei gewordene Einheit, die nicht wiederverwendet wird, geht nach der Zustellung unterwegs an einen Bestand zurück. Wie die Depotkanten in der Veröffentlichung werden diese Besuche als Zeit, Distanz und Kosten in den Abschnitt eingepreist, statt zu Stopps zu werden.

Über alle Touren hinweg führt ein gemeinsames Buch jeden verfolgten Bestand: seinen Anfangsbestand, bekannte Zu- und Abgänge sowie die Entnahmen und Rückgaben jeder Tour. Wie in der Veröffentlichung wird ein Bestand nur geprüft, wenn eine Einheit entnommen wird. Eine Entnahme, die einen Bestand unter null drücken würde, weicht auf ihre nächste Quelle aus, und wenn keine mehr übrig ist, entscheidet die Regel equipment_stock. Bereits bestehende Trips zählen mit ihren offenen Entnahmen und Rückgaben.

Wir setzen kein Branch-and-Price ein. Eine Large Neighbourhood Search reißt Pläne auseinander und baut sie neu auf, und das Entfernen einer Tour kann einer anderen Tour den Leercontainer entziehen, mit dem sie gerechnet hat. Deshalb bewertet die Suche jede fehlende Einheit wie eine nicht eingeplante Sendung, und der letzte Durchgang beschafft alles, was dann noch fehlt, neu oder entfernt es. Der Plan, den Sie bekommen, schickt nie zwei Lkw zum letzten Leercontainer auf dem Hof.

Wo sich beides trifft

Spannend wird es dort, wo sich die beiden Mechanismen berühren. Wenn der Planer eine Tour wegen einer Rampe neu terminiert, verschiebt sich auch der Moment, in dem diese Tour einen Container entnimmt oder zurückgibt. Rutscht eine Rückgabe hinter die Entnahme einer anderen Tour, kann ein Bestand, der in Ordnung aussah, plötzlich knapp werden. In unserem Planer nimmt eine neu terminierte Tour ihren Equipment-Plan mit, sodass das Bestandsbuch immer die tatsächlichen Zeiten der Tour abbildet.

Genau deshalb gehört alles in eine einzige Suche. In getrennten Werkzeugen würde das niemand bemerken. Die Rampenbuchung würde einen Lkw nach hinten schieben, die Leercontainer-Disposition läge mit dem Morgenbestand richtig, und der Plan würde trotzdem scheitern.

Was wir weggelassen haben

• Getrennte Lade- und Entladerampen sowie Rampen, die bestimmten Fahrzeugtypen vorbehalten sind. Alle betriebsbereiten Rampen eines Standorts zählen gemeinsam.
• Chassis-Pools. Die Herkunft des Containers wird geplant, ein zwischen Lkw geteilter Chassis-Pool nicht.
• Gleichwertige Containertypen (ISO-Größen- und Typgruppen) und Hofkapazität. Typen müssen exakt übereinstimmen, und Rückgaben werden nie wegen eines vollen Hofs abgelehnt.
• Equipment-Bestand und Linienverbindungen per Bahn oder Binnenschiff in einer Anfrage. Planen Sie die Straßenabschnitte vorerst als Sendungen.

Die Veröffentlichungen

• A. Bombelli und S. Fazi (2022). The ground handler dock capacitated pickup and delivery problem with time windows: a collaborative framework for air cargo operations. Transportation Research Part E 159, 102603.
• S. Fazi, S.K. Choudhary und J.X. Dong (2023). The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research 310(1), 343–359.

Wir haben auf den veröffentlichten Arbeiten aufgebaut. Die Autoren waren nicht beteiligt, und etwaige Schwächen unserer Umsetzung gehen auf uns. Was der Planer in derselben Suche sonst noch entscheidet, lesen Sie in Eine Suche, der ganze Frachtplan. Welche Felder Sie nutzen, steht im Leitfaden zum multimodalen VRP.