Umschlagpunkte im Lager verständlich erklärt

Ein Paket wechselt im Lager die Hände, weil jeder Wagen nur in seinem Bereich fährt. An jeder Übergabe kann es warten. Diese Seite zeigt, warum die schnellste Einzelentscheidung das Warten nicht immer senkt und was dagegen hilft.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Paket, drei Etagen

Stellen Sie sich ein Bürohaus mit drei Etagen vor. Auf jeder Etage arbeitet ein Bote. Er darf seine Etage nicht verlassen. Zwischen den Etagen fährt nur der Aufzugsbote.

Ein Paket soll von der ersten in die dritte Etage. Der Bote der ersten Etage bringt es zum Aufzug. Der Aufzugsbote fährt es nach oben. Der Bote der dritten Etage trägt es zum Schreibtisch. Das Paket wechselt also unterwegs die Boten. Jede Übergabe kostet Zeit. Ist der nächste Bote gerade beschäftigt, wartet das Paket zusätzlich.

Ein automatisches Lager mit hohen Regalen ist ähnlich gebaut. Die Etagen sind dort Regalgassen. Die Boten sind fahrerlose Wagen, hier Transporter genannt. Der Aufzug heißt Verteiler, ein Förderband oder Lift, das alle Gassen verbindet. Jede Gasse und der Verteiler bilden eine eigene Zone. Ein Transporter bleibt in seiner Zone. Die Stelle, an der ein Paket von einer Zone in die nächste wechselt, heißt Umschlagpunkt.

Nach einer Übergabe ist der Transporter leer. Er muss zur nächsten Abholung zurück, bevor er wieder etwas tragen kann. Diese Leerfahrt liefert nichts aus und kostet doch Zeit.

Jedes Paket hat eine Frist, bis wann es ankommen soll. Sie ergibt sich aus der kürzest möglichen Reise plus einer festen Zugabe. Diese Zugabe heißt Puffer: die Zeit, die ein Paket verlieren darf, ohne die Frist zu verpassen. Gemessen wird für jedes Paket die Zeit von dem Moment, in dem es abgeholt werden kann, bis zur Ankunft. Zählt man diese Zeiten aller Pakete zusammen, heißt die Summe Gesamtdurchlaufzeit. Sie soll klein sein.

Die Seite erklärt das an einem vereinfachten Rechenbild (Fachwort: Modell): einem erfundenen Lager mit festen Fahrzeiten. Alle Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht die Wirklichkeit.

Wer ist als Nächster dran?

Wird ein Transporter frei, können mehrere Pakete warten. Eine Regel muss entscheiden, welches er nimmt.

Die naheliegende Regel heißt: kürzeste Fahrt zuerst (Fachwort: SPT). Ein langes Paket vor einem kurzen hält das kurze lange auf. Ein kurzes vor einem langen hält das lange kaum auf. Fährt nur ein Transporter, liegen alle Pakete schon bereit und gibt es keine Leerfahrten, lässt sich die Regel deshalb nach einem bekannten Beweis nicht übertreffen.

Im Lager kommen zwei Dinge hinzu, die die Regel nicht sieht. Erstens sieht sie nur die nächste Fahrt, nicht die ganze Reise. Ein ausgedachtes Beispiel: Paket A hat schon eine Übergabe hinter sich. Ihm fehlt nur noch die letzte, kurze Fahrt, und sein Puffer ist fast aufgebraucht. Paket B ist neu und hat noch viel Puffer. Seine erste Fahrt ist etwas kürzer als die letzte von A. Die Regel nimmt B, weil sie die Vorgeschichte nicht kennt. A kann dann seine Frist verpassen.

Zweitens sieht die Regel nicht, wo der Transporter steht. Zwei Fahrten sind gleich lang. Die eine beginnt neben dem Transporter, die andere am anderen Ende der Gasse. Die Regel kann die weite Leerfahrt wählen. Der Transporter ist dann länger blockiert, und alle anderen warten länger auf ihn.

Fünf Wege, die Reihenfolge zu planen

Die Seite vergleicht fünf Verfahren, alle auf demselben erfundenen Lager:

• Ohne Regel: Wer zuerst bereit ist, kommt zuerst dran.
• Dezentral: Jede Zone nimmt die kürzeste Fahrt zuerst, wie oben beschrieben.
• Koordiniert: Eine Regel aus der Ablaufplanung (ATCS). Sie wägt drei Dinge ab: die Länge der Fahrt, den Puffer des Pakets und den Abstand des nächsten freien Transporters.
• Zufallssuche: Sie spielt viele zufällig abgewandelte Pläne durch und behält den besten (GRASP). Die Abwandlungen gehen von der koordinierten Regel aus.
• Rechenprogramm: Es sucht den besten Gesamtplan (Google OR-Tools). Bei kleinen Fällen arbeitet es schnell. Bei großen stößt es an sein Zeitlimit und meldet die beste Lösung, die es bis dahin fand.

Ein Teil der Pakete ist als Express markiert und hat eine engere Frist. Die letzten drei Verfahren beachten das. Die ersten beiden ignorieren es mit Absicht, um zu zeigen, dass ein System ohne Blick auf Prioritäten sie schlicht übergeht.

Eine Besonderheit beim Vergleich: Die letzten beiden Verfahren planen so, dass Express-Pakete mehr zählen und jede Verspätung extra kostet. Verglichen werden aber alle an derselben Zahl, der Gesamtdurchlaufzeit. Die gründlichen Verfahren werden also nicht an ihrem eigenen Ziel gemessen.

Warum Warten manchmal klug ist

Die ersten drei Verfahren lassen einen freien Transporter nicht warten, sobald ein Paket bereitsteht. Der beste Gesamtplan tut es manchmal doch.

Ein Bild dazu: Der Aufzugsbote steht vor einem normalen Paket. In einer Minute kommt ein dringendes Paket am Aufzug an. Fährt er jetzt los, ist er fort, wenn das dringende eintrifft. Wartet er kurz, ist das dringende früher am Ziel. Das normale verliert etwas Zeit. Das dringende zählt in dieser Rechnung aber mehr.

Das Rechenprogramm fand solche Pläne. In einer Nachmessung an 37 kleinen Testfällen mit acht Aufträgen ließ ein bester Plan den Verteilertransporter in 10 Fällen bewusst stehen. Mit zehn Aufträgen waren es 15 von 37. Deshalb darf auch die Zufallssuche vor jeder Zuweisung kurz vorausblicken: Wird gleich ein dringenderes Paket bereit, bleibt der Transporter einen Moment stehen.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erzeugt ein erfundenes Lager und lässt die fünf Verfahren darauf planen. Der erste Knopf unten öffnet die Demo, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Häufige Missverständnisse

• „Die Gesamtdurchlaufzeit sagt, wann das Lager fertig ist.“ Nein. Sie zählt die Reisezeit jedes einzelnen Pakets zusammen. Ein Plan, der Pakete früh liefert, kann dieselbe Schlusszeit haben wie einer, der sie spät liefert.
• „Wer weiter vorausschaut, plant besser.“ Nicht automatisch. Beim Bau der Demo wurde zuerst eine Regel probiert, die das Paket mit der kürzesten Restreise zuerst nahm. Sie verlor gegen die einfache Regel, sobald Leerfahrten mitzählten.

Woran Sie das im Alltag erkennen

• Ihr Paket hängt in der Sendungsverfolgung lange „im Verteilzentrum“. Das kann an der Übergabe liegen: Es kann erst weiter, wenn ein passender Wagen frei ist.
• In einem vollen Café läuft die Bedienung, die gerade fertig ist, quer durch den Raum zum nächsten Tisch, obwohl direkt neben ihr jemand zahlen will. Der Weg zählt nirgends als Arbeit und kostet doch Zeit.

Wie ernst ist das Rechenbild zu nehmen?

Batterien, Kollisionen und mehrstöckige Verteiler fehlen. Die Zahlen gelten für erfundene Fälle und zeigen Tendenzen. Als Tendenz liegen Rechenprogramm und Zufallssuche vorn, die koordinierte Regel meist vor der dezentralen. Wie groß die Abstände sind, hängt vom Lager ab.

Was Sie mitnehmen:

• Fragen Sie bei jeder Regel, ob sie die ganze Reise sieht oder nur den nächsten Schritt.
• Zählen Sie Übergaben und Leerfahrten mit, wenn Sie Abläufe vergleichen.
• Trauen Sie einer plausiblen Regel erst, wenn sie an vielen Fällen geprüft ist und nicht an einem.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist ein synthetisches Lager im Hub-and-Spoke-Layout; alle Aussagen gelten nur dafür. Fachlich ist es ein Pickup-and-Delivery-Problem mit Transshipment (PDPT), hier als Ablaufplanung mit Vorrang zwischen Teilfahrten formuliert.

• Zonen und Transporter: Zwei bis fünf Gassen-Zonen hängen an einer zentralen Verteiler-Zone. Jede Zone ist ein Pfad aus Knoten: Gassen haben drei bis acht Knoten einschließlich ihres Anschlussknotens, der Verteiler einen bis sechs. Zone \(z\) hat \(c_z\) zonengebundene Transporter (je Gasse einen bis vier, im Verteiler einen bis sechs), die ihre Zone nicht verlassen. Fahrgeschwindigkeit: ein Knoten je Minute in der Gasse, zwei im Verteiler. Jeder Transporter wird einzeln mit Position und Verfügbarkeitszeit (ab wann er frei ist) geführt und startet am ersten Knoten seiner Zone, in Gassen am Anschluss zum Verteiler.
• Anschluss: Gasse \(i\) hängt am Verteilerknoten mit dem Index \(i\) modulo der Knotenzahl des Verteilers. Folgerung (Rechnung dieser Seite aus dieser Konstruktion): Hat der Verteiler nur einen Knoten, hängen alle Gassen am selben Knoten, die Teilfahrt im Verteiler dauert null Minuten, und der Verteilertransporter blockiert nichts. Die Umstiegszeiten bleiben. Dasselbe gilt für Aufträge zwischen Gassen, die am selben Verteilerknoten hängen, auch bei mehreren Verteilerknoten, solange es mehr Gassen als Verteilerknoten gibt.
• Aufträge und Routen: Auftrag \(o\) hat Ursprung, Ziel und Freigabezeit \(r_o\), gleichverteilt über einen einstellbaren Zeithorizont. Ein einstellbarer Anteil der Aufträge hat sein Ziel in einer anderen Gasse. Die Zonenfolge ist festgelegt: eine Teilfahrt in der eigenen Gasse (\(L_o = 1\)) oder drei, nämlich Gasse, Verteiler, Zielgasse (\(L_o = 3\)). \(d_{o,\ell}\) ist die feste Dauer der Teilfahrt \(\ell\), der Weg im Zonenpfad geteilt durch die Geschwindigkeit.
• Umstieg: Zwischen zwei Teilfahrten desselben Auftrags liegt die feste Umstiegszeit \(h\) (null bis fünf Minuten einstellbar). Die nächste Teilfahrt darf erst danach beginnen.
• Leerfahrt: Vor einer neuen Teilfahrt fährt der Transporter vom Ausstiegsknoten seiner letzten Teilfahrt zum Einstiegsknoten der neuen. Die Dauer \(\rho\) ist die reale Distanz im Zonenpfad geteilt durch die Geschwindigkeit, keine Pauschale. Der Transporter ist vom Moment der Zuweisung an belegt.
• Frist und Express: \(\delta_o\) ist die Freigabezeit plus Mindestreisezeit (Summe der Fahrzeiten und Umstiegszeiten) plus ein fester Puffer. Der Puffer beträgt für normale Aufträge zwanzig Minuten, für Express-Aufträge acht. Express-Aufträge haben das Gewicht \(w_o = 3\), die übrigen \(w_o = 1\).
• Kennzahl: Die Gesamtdurchlaufzeit ist die Summe der Durchlaufzeiten \(C_o - r_o\), wobei \(C_o\) die Ankunftszeit von Auftrag \(o\) ist, also das Ende seiner letzten Teilfahrt. Die Verfahren GRASP und CP-SAT optimieren dagegen den gewichteten Zielwert aus dem nächsten Abschnitt.
• Voreinstellung: drei Gassen mit fünf Knoten, ein Verteiler mit zwei Knoten, ein Transporter je Zone, zwanzig Aufträge über sechzig Minuten, sieben Zehntel davon zonenübergreifend, ein Fünftel Express, eine Minute Umstiegszeit.

Die Formeln

Ziel. Gesucht sind Startzeiten \(s_{o,\ell} \ge 0\) für jede Teilfahrt. Sie minimieren die gewichtete Durchlaufzeit plus eine Verspätungsstrafe mit dem Gewicht \(\lambda\) (in der Demo ein halb): \(\sum_o w_o \,(s_{o,L_o} + d_{o,L_o} - r_o) + \lambda \sum_o \max(0,\, s_{o,L_o} + d_{o,L_o} - \delta_o)\). Das CP-SAT-Modell lässt den festen Term \(r_o\) weg; das ändert das Optimum nicht (Rechnung dieser Seite).

Vorrang. Eine Teilfahrtenkette beginnt nicht vor der Freigabe, und jede weitere Teilfahrt beginnt erst nach dem Ende der vorigen plus Umstiegszeit (für alle Teilfahrten \(\ell\) eines Auftrags außer der letzten):

\[s_{o,1} \geq r_o \qquad \forall o\]

\[s_{o,\ell+1} \geq s_{o,\ell} + d_{o,\ell} + h\]

Transporter. Jede Teilfahrt \((o,\ell)\) in Zone \(z\) bekommt eine Maschinenvariable \(m_{o,\ell} \in \{0, \ldots, c_z - 1\}\), die angibt, welcher der \(c_z\) Transporter sie fährt. Liegen zwei Teilfahrten derselben Zone auf demselben Transporter, muss eine die andere samt Leerfahrt abschließen: \(s_{o',\ell'} \ge s_{o,\ell} + d_{o,\ell} + \rho(x_{o,\ell}, e_{o',\ell'})\) oder umgekehrt, mit dem Ausstiegsknoten \(x_{o,\ell}\) und dem Einstiegsknoten \(e_{o',\ell'}\). Auf verschiedenen Transportern gibt es keine Bedingung; so entsteht Parallelität. Das ist das Standardmuster paralleler Maschinen mit reihenfolgeabhängigen Rüstzeiten. Eine einfache Kapazitätsbedingung je Zone genügt nicht, weil die Transporter wegen ihrer Positionen nicht austauschbar sind.

Disposition der drei einfachen Regeln. Sie arbeiten ereignisgesteuert: Wird ein Transporter frei und wartet eine Teilfahrt, geht die Teilfahrt mit dem niedrigsten Prioritätswert an den freien Transporter derselben Zone mit der kürzesten Leerfahrt zu ihr. Bei Gleichstand der Priorität entscheidet die frühere Bereitzeit. Ohne Regel ist der Wert konstant, es zählt also nur die Bereitzeit. Dezentral ist der Wert die Dauer \(d_{o,\ell}\) der aktuellen Teilfahrt (SPT, Shortest Processing Time first). Für die koordinierte Regel ist der Wert \(-I\) mit dem Index \(I\) unten.

Koordiniert (ATCS). Die Regel Apparent Tardiness Cost with Setups (ATCS, in der Fassung der Demo) bedient die Teilfahrt mit dem höchsten Index \(I(o,\ell) = \dfrac{w_o}{d_{o,\ell}} \cdot F_{\sigma} \cdot F_{\rho}\). Der erste Faktor ist gewichtetes SPT. Die beiden Exponentialfaktoren sind der Frist-Faktor und der Weg-Faktor:

\[\exp\!\left(-\frac{\max(\sigma_{o,\ell},\,0)}{K_1 \, \bar d}\right)\]

\[\exp\!\left(-\frac{\min_{\text{frei } t} \rho(t, e_{o,\ell})}{K_2 \, \bar d}\right)\]

Dabei ist \(\sigma_{o,\ell} = \delta_o - (\tau + d_{o,\ell} + \sum_{k>\ell}(d_{o,k} + h))\) der Puffer bis zur Frist, gerechnet ab dem Entscheidungszeitpunkt \(\tau\) mit der restlichen Reise ohne weitere Wartezeit, und \(t\) läuft über die gerade freien Transporter der Zone. \(\bar d\) ist die mittlere Dauer aller Teilfahrten des Szenarios, einmal berechnet. \(K_1 = 1\) (Frist) und \(K_2\) = 0,15 (Weg) sind abgestimmt. \(F_\sigma\) bezeichnet den ersten, \(F_\rho\) den zweiten Exponentialfaktor. \(F_\sigma = 1\), wenn der Puffer aufgebraucht ist, und fällt mit wachsendem Puffer. \(F_\rho = 1\), wenn ein freier Transporter am Einstiegsknoten steht, und fällt mit wachsender Leerfahrt. Express-Aufträge gehen über das Gewicht \(w_o\) und über die kürzere Frist ein, also über ein kleineres \(\sigma\). Hat eine Teilfahrt die Dauer null, steht im Nenner eine Untergrenze von einem Millionstel Minute; ihr Index ist dann sehr groß. Gegenüber der Literatur ist die Fassung angepasst: Der Puffer rechnet die ganze Restreise ein statt nur der aktuellen Teilfahrt, und beide Exponenten werden durch \(\bar d\) geteilt statt, wie in der Literatur üblich (aus dem Gedächtnis, nicht geprüft), durch eine mittlere Rüstzeit.

GRASP. Die Zufallssuche (Greedy Randomized Adaptive Search Procedure) benutzt \(I\) als Konstruktionsregel. Statt strikt dem höchsten Index zu folgen, zieht sie bei jeder Entscheidung gleichverteilt aus den vier besten bereiten Teilfahrten (Kandidatenliste) und wiederholt das in 150 unabhängigen Läufen. Danach folgen bis zu 400 zufällige Störungen: Zum Prioritätswert \(-I\) einer einzelnen Teilfahrt wird ein Aufschlag addiert, gezogen zwischen minus und plus einem halben \(\bar d\). Die Simulation wird wiederholt, der Aufschlag nur bei Verbesserung behalten. Er wird ohne Umrechnung addiert (Minuten zu einem Wert der Einheit eins durch Minute, Rechnung dieser Seite aus dem Aufbau); seine Wirkung hängt deshalb von der Größenordnung von \(I\) ab. Bewertet wird am gewichteten Zielwert von oben. Zusätzlich blickt die Simulation um ein Fenster von 0,75 Minuten voraus (das Vorausblick-Fenster): Wird innerhalb des Fensters in derselben Zone eine Teilfahrt bereit, die zu ihrer eigenen Bereitzeit besser bewertet wird als die beste bereite, bleibt der Transporter stehen und wird beim nächsten Ereignis neu entschieden.

CP-SAT. Das Rechenprogramm löst das Modell mit den Maschinenvariablen exakt, soweit das Zeitlimit reicht, und meldet sonst die beste gefundene Lösung.

Herleitungen und durchgerechnete Fälle

Die folgenden Rechnungen sind Rechnungen dieser Seite an konstruierten Fällen, keine Messungen der Demo.

Warum die lokale Regel in der Kette nichts verspricht.

• Schritt 1: SPT minimiert die Summe der Fertigstellungszeiten auf einer Maschine, wenn alle Aufträge zu Beginn bereitliegen, nichts umgerüstet werden muss und keine Vorrangbeziehungen bestehen (Tauschargument: ein langer Auftrag direkt vor einem kürzeren lässt sich vertauschen, ohne dass sich für die übrigen etwas ändert).
• Schritt 2: Im Modell sind alle drei Voraussetzungen verletzt. Aufträge treten über die Zeit ein, die Teilfahrten eines Auftrags liegen in Reihe auf verschiedenen Zonen, und die Dauer einer Leerfahrt hängt vom Vorgänger auf demselben Transporter ab.
• Schritt 3: Für das Gesamtsystem folgt daraus keine Optimalitätsaussage für die dezentrale Regel. Ob sie dort gut oder schlecht abschneidet, ist eine Frage der Messung.

Der Frist-Faktor kehrt die Rangfolge um. Zwei Teilfahrten A und B warten in derselben Zone, beide mit Gewicht eins. Ein freier Transporter steht an beiden Einstiegsknoten, \(F_\rho\) ist also bei beiden eins. A dauert drei Minuten und hat keinen Puffer mehr (\(F_\sigma = 1\)). B dauert zwei Minuten und hat den Puffer \(S \ge 0\). Angenommen sei \(\bar d = 2\) und \(K_1 = 1\). Dezentral wird B gewählt, weil zwei kleiner als drei ist. Koordiniert gilt \(I_A = 1/3\) und \(I_B = \tfrac{1}{2}\, e^{-S/2}\). A gewinnt genau dann, wenn \(e^{-S/2} < 2/3\) gilt, also für \(S > 2 \ln(3/2)\). Das sind etwa vier Fünftel einer Minute. Hat B mehr als etwa vier Fünftel einer Minute Puffer, nimmt die koordinierte Regel A, obwohl B kürzer ist.

Der Weg-Faktor dominiert schon bei kleinen Abständen. Zwei Teilfahrten sind gleich lang (zwei Minuten) und haben denselben Puffer. Der freie Transporter steht an der einen; die andere beginnt vier Knoten weiter in derselben Gasse, also vier Minuten Leerfahrt. Mit \(\bar d = 2\) und \(K_2\) = 0,15 ist \(F_\rho\) für die entfernte Teilfahrt \(e^{-4/(K_2 \bar d)}\), das ist \(e\) hoch minus gut dreizehn und liegt in der Größenordnung eines Millionstels. Die dezentrale Regel sieht zwei gleiche Dauern und entscheidet nach der Bereitzeit, nicht nach der Lage. Allgemein überstimmt der Weg-Faktor einen SPT-Vorteil vom Faktor zwei, sobald sich die Leerfahrten um mehr als \(K_2 \bar d \ln 2\) unterscheiden, bei gleichem Frist-Faktor. Das ist gut ein Zehntel von \(\bar d\). Mit dem kleinen \(K_2\) wirkt die koordinierte Regel in diesem Bereich also fast wie „nächster Transporter zuerst, bei Gleichstand SPT“.

Warum Warten sich lohnen kann. Eine Zone, ein Transporter, Umstiegs- und Leerfahrtzeiten vernachlässigt. Teilfahrt X (Gewicht eins, Dauer vier) ist ab Minute null bereit, Teilfahrt Y (Express, Gewicht drei, Dauer drei) ab Minute eins. Ohne Warten endet X nach vier und Y nach sieben Minuten: gewichtete Summe der Fertigstellungszeiten \(4 + 3 \cdot 7\), das sind fünfundzwanzig, ungewichtet elf. Wartet der Transporter bis Minute eins, endet Y nach vier und X nach acht Minuten: gewichtet \(3 \cdot 4 + 8\), das sind zwanzig, ungewichtet zwölf. Das Warten senkt die gewichtete Summe und erhöht die ungewichtete. Eine Regel, die nie wartet, kann diesen Plan nicht erzeugen. Die Ursache sind die verschiedenen Freigabezeiten; die Gewichte verstärken den Effekt. Schon ohne Gewichte lohnt Warten: X dauert vier Minuten und ist ab null bereit, Y dauert eine Minute und ist ab eins bereit. Ohne Warten ist die Summe der Fertigstellungszeiten \(4 + 5 = 9\), mit Warten \(2 + 6 = 8\). Bei Freigabezeiten ist also nicht immer ein Plan ohne Leerzeit optimal.

Befunde

Die Zahlen stammen aus Vergleichsläufen der Entwicklung auf erfundenen Lagern. Es gab vier Szenariofamilien (Standard, Hub-Engpass, express-lastig, groß); ihre Einstellungen sind nicht dokumentiert. Die Lücke zu CP-SAT bezieht sich auf den gewichteten Zielwert aus dem Abschnitt „Die Formeln“, nicht auf die Gesamtdurchlaufzeit. Die Quelle spricht vom Anteil der verbleibenden Lücke zu OR-Tools ohne Formel. Gemeint ist vermutlich der Anteil der Differenz zwischen koordinierter Regel und CP-SAT, den GRASP schließt; das ist nicht belegt.

Frage	Befund
Warum wurde ATCS gewählt?	Eine reine Restroutenregel (kürzeste Restreise zuerst) verlor gegen die dezentrale Regel, sobald Leerfahrten im Modell waren. Eine danach gebaute Linearkombination aus unabhängig abgestimmten Gewichten funktionierte, aber nicht durchgängig. ATCS schlägt sie bei der Gesamtverspätung (Summe von \(\max(0, C_o - \delta_o)\)) in jeder getesteten Szenariofamilie.
Wie wichtig ist die Dämpfung des Weg-Faktors?	Mit schwacher Dämpfung (großes \(K_2\)) verlor die koordinierte Regel in bis zu 33 von 40 Szenarien gegen die dezentrale. Gewählt wurde \(K_2\) = 0,15.
Wie viel der Lücke zu CP-SAT schließt GRASP?	Ohne Vorausblick grob 15 bis 30 %, mit Vorausblick von 0,75 Minuten grob 25 bis 35 % (Sweep über 4 Szenariofamilien mit je 15 Zufallsszenarien; 150 Läufe, Kandidatenliste 4, 400 Störungen). Nachmessung auf 4 Familien mit je 6 Zufallsszenarien und fünf Sekunden Zeitlimit für CP-SAT: Familienmittel 23 bis 36 % mit und 18 bis 27 % ohne Vorausblick, mit Vorausblick in drei von vier Familien besser, in einer leicht schlechter. Der ursprüngliche Sweep ist nicht reproduziert.
Wie viel Rechenzeit braucht GRASP?	An den Obergrenzen der Regler grob 2 bis 3 Sekunden ohne und 3 bis 4 Sekunden mit Vorausblick (rechnerabhängig). Ein doppeltes Budget (300 Läufe, 800 Störungen) brachte nur marginal mehr bei etwa doppelter Laufzeit. Eine Lokalsuche mit Tauschzügen statt Störungen brachte keine verlässliche Verbesserung bei fast doppelter Laufzeit und wurde verworfen.
Wie oft wartet ein bester Plan bewusst?	In einer Nachmessung an 37 kleinen Szenarien mit Engpass am Verteiler ließ ein Teil der als optimal erkannten CP-SAT-Lösungen den einzigen Verteilertransporter stehen, obwohl eine Teilfahrt bereitlag: bei 8 Aufträgen in 10 der 37 Szenarien, bei 10 Aufträgen in 15 der 37. Die frühere Zählung 6 von 37 ist nicht reproduziert.
Wie breit darf das Vorausblick-Fenster sein?	Das Fenster ist die Zeitspanne, über die der Simulator nach einer gleich bereit werdenden dringenderen Teilfahrt schaut. Im Sweep von 0 bis 2 Minuten brachte 0,75 Minuten den größten Gewinn in den Läufen. Fenster ab etwa dem Doppelten der Voreinstellung gaben einen Teil davon wieder her.
Verliert die koordinierte Regel gegen die dezentrale?	Messstand der Entwicklung, nicht in der Quelle als Tabelle: Über 40 Zufallsszenarien der Voreinstellung ohne Express verlor sie bei der Gesamtdurchlaufzeit zuletzt in vier Szenarien; in der Summe der Unterschiede lag sie vorn. Bei Express-Pünktlichkeit in einem Szenario mit dichtem Verkehr (drei Gassen, ein Verteilerknoten, ein Transporter je Zone, ein Express-Anteil von drei Zehnteln) war sie in zwanzig Zufallsszenarien in vierzehn besser, in zwei schlechter, in vier gleich.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Eine Rangfolge als Tendenz (mit dem Vorbehalt zur Abstimmung der Parameter unten): Zufallssuche und CP-SAT liegen im gewichteten Zielwert vor der koordinierten Regel, diese in den Läufen meist vor der dezentralen. GRASP schlägt die koordinierte Regel in den Sweeps fast immer.
• Der Mechanismus der bewussten Leerzeit ist an echten CP-SAT-Lösungen nachgeprüft und nicht nur postuliert. Die Rechnung oben zeigt zudem, dass er bei gewichteten Zielen auftreten kann.
• Die Wirkung der beiden Exponentialfaktoren folgt aus der Formel und ist in den konstruierten Fällen nachrechenbar.

Was sie nicht belegt:

• Die Lücke zu CP-SAT: Sie ist auf den gewichteten Zielwert bezogen. Wo CP-SAT sein Zeitlimit erreicht, ist die Vergleichslösung nicht bewiesen optimal, und die Lücke zum wahren Optimum kann größer sein. Zudem verlangt das CP-SAT-Modell zwischen zwei Teilfahrten desselben Transporters nur, dass die nächste nicht vor dem Ende der vorigen plus Leerfahrt beginnt. Der Transporter darf also schon vor der Bereitzeit der nächsten Teilfahrt zu ihrem Einstiegsknoten fahren, während die einfachen Regeln und GRASP erst bei der Zuweisung losfahren. Die erste Leerfahrt aus der Ausgangsposition berechnet das Modell gar nicht. Beides verschafft CP-SAT einen Vorsprung, der nicht auf diese erste Fahrt beschränkt ist (Rechnung dieser Seite aus dem Aufbau). Seine Größe ist nicht gemessen.
• Die Prozentzahlen: Die Nachmessungen haben wenige Zufallsszenarien je Familie und keine Streuungsangaben. Die ursprünglichen Sweeps sind nicht reproduziert, und die Familien sind nicht definiert. Die Parameter \(K_1\), \(K_2\) und das Fenster wurden über dieselben Szenariofamilien abgestimmt, an denen die Überlegenheit gemessen wird. Eine Überanpassung ist deshalb nicht ausgeschlossen.
• Die Zahlen 10 und 15 von 37: Die Quelle nennt nur die Auftragszahl (8 bzw. 10), nicht die Zahl der Verteilerknoten und die übrigen Einstellungen. Alle Szenarien, die die Demo als Engpass am Verteiler bezeichnet, haben einen einzigen Verteilerknoten. Ob das auch für diese 37 galt, steht nirgends. Dann dauert die Verteilerfahrt null Minuten (siehe Modell), und Warten des Verteilertransporters bliebe ohne Wirkung. Außerdem beweist ein Leerlauf in einer gefundenen optimalen Lösung nicht, dass jede optimale Lösung warten muss. Ein Test mit verbotenem Warten fehlt.
• Wenig Verkehr: Die Demo beschreibt Ohne Regel, Dezentral und Koordiniert bei wenig Verkehr als nah beieinander liegend, Zufallssuche und CP-SAT auch dort als deutlich besser. Eine Messreihe dazu steht nicht in der Quelle.
• Die Vergleichsregel: Die dezentrale Regel ist bewusst einfach und blind für Frist, Express-Markierung und Leerfahrt. Andere übliche Regeln, etwa nach der frühesten Frist, werden nicht verglichen.
• Das Modell: Feste Fahrzeiten, keine Kollisionen innerhalb einer Gasse, keine Lade- oder Batteriezyklen, ein einziger Verteilerpfad. Die Befunde gelten nur für dieses Layout.
• Die dezentrale Regel zur Optimalität: Dass SPT lokal optimal ist, gilt nur unter den Voraussetzungen aus der Herleitung. Im Modell mit Freigabezeiten und Leerfahrten gilt der Beweis nicht.

Erweiterungen und Verweise

• Die einfache Regel einzeln: Die Seite SPT-Regel verständlich erklärt zeigt den Tauschbeweis für eine Maschine und was reihenfolgeabhängige Rüstzeiten daran ändern.
• Nicht umgesetzt: Lade- und Batteriezyklen, mehrstöckige Verteiler und Kollisionsvermeidung in der Gasse. Eine Vorab-Messreihe (Stand 2026-09-23) zu einer verwandten Kommissionier-Aufgabe mit mehreren Kommissionierern ergab, dass Blockieren in schmalen Gängen bis zu 57 % des Vorteils der Regel „früheste Frist zuerst“ gegenüber „Ankunftsreihenfolge“ aufzehren kann. Sie ist vorläufig und betrifft nicht diese Demo.

Quellen

• Vepsäläinen, Morton (1987): Priority rules for job shops with weighted tardiness costs. Management Science 33 (Ausgangsform der ATC-Regel).
• Lee, Bhaskaran, Pinedo (1997): A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions 29 (Erweiterung auf Rüstzeiten, eine Maschine). Lee, Pinedo (1997): Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research 100 (parallele Maschinen).
• Feo, Resende (1995): Greedy randomized adaptive search procedures. Journal of Global Optimization 6 (GRASP; die Quelle nennt 1989/1995).
• Drexl (2012): Synchronization in vehicle routing: a survey of VRPs with multiple synchronization constraints. Transportation Science 46. Cuda, Guastaroba, Speranza (2015): A survey on two-echelon routing problems. Computers & Operations Research 55.
• Quelltext und Tests der Demo: github.com/sebastian-hanisch/warehouse-transfer-demo.

Autoren und Jahre stammen aus der Beschreibung der Demo; die Titel und Zeitschriften wurden für diese Seite nicht nachgeschlagen, sie stammen aus dem Gedächtnis und sind nicht geprüft. Die Befundtabelle gibt Vergleichsläufe der Entwicklung wieder. Die durchgerechneten Fälle und die Folgerung zum Verteiler mit einem Knoten sind Rechnungen dieser Seite.