Warten oder fahren verständlich erklärt
Ein Wagen steht beladen bereit, und vielleicht kommt gleich noch ein Auftrag in der Nähe. Sofort losfahren oder warten? Und was ist mit einem Auftrag, der einen großen Umweg kostet? Diese Seite zeigt, was Warten bringt und wann ein Auftrag den Umweg nicht wert ist.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Ein Wagen, der warten kann
Ein Lieferdienst bekommt über den Tag verteilt Aufträge. Jeder Auftrag hat eine Frist, bis zu der die Ware beim Kunden sein muss. Ein Wagen steht beladen bereit. Er könnte sofort losfahren. Er könnte auch noch warten, ob in der Nähe ein weiterer Auftrag eintrifft, den er auf derselben Fahrt mitnimmt.
Beides hat einen Preis. Wer sofort fährt, fährt oft mit einem einzigen Paket. Wer wartet, geht ein Risiko ein: Die Frist rückt näher, und ein später Start kann nicht mehr gutgemacht werden.
Zwei Entscheidungen
- Warten oder fahren: Wann startet eine geplante Fahrt?
- Annehmen oder ablehnen: Nimmt man einen neuen Auftrag an, oder ist er den Umweg nicht wert?
Wie weit darf man warten?
Die Aufträge, die noch nicht unterwegs sind, führt man auf einem Stapel, der wie eine einzige Kundenliste aussieht. Aus dem ersten Teil dieser Reihe kennen Sie das Bild: Ein Schnitt zwischen zwei Kunden zeigt, wo eine Fahrt endet und die nächste beginnt. So entstehen die geplanten Fahrten.
Zu jeder geplanten Fahrt gehört eine späteste Abfahrt: Wer danach losfährt, kommt bei mindestens einem Kunden nach der Frist an. Bis dahin ist Warten erlaubt. Die Demo vergleicht drei Strategien: „Sofort“ fährt los, sobald ein Wagen frei ist. „Spätestens“ wartet bis zur letzten Möglichkeit. Dazwischen liegt „Warten“ mit einer festen Wartezeit ab dem ältesten Auftrag der Fahrt.
Ein Beispiel auf einer Geraden
Ein Beispiel (Zahlen aus der Demo, keine Wirklichkeit): Das Lager liegt bei 0, ein Wagen fährt auf einer Geraden. Kunde A wohnt bei 10, sein Auftrag kommt bei 0 herein und hat die Frist 60. Kunde B wohnt bei 20, sein Auftrag kommt bei 15 herein. Fahrzeit gleich Strecke, jeder Auftrag bringt 60 Erlös.
„Sofort“ fährt gleich zu Kunde A und zurück, danach noch einmal zu Kunde B: zwei Fahrten, zusammen 60 Strecke. Zwei Aufträge bringen 120 Erlös, abzüglich der Strecke bleiben 60 Gewinn. „Spätestens“ wartet bis zur Zeit 30, nimmt dann beide in einer Fahrt mit und fährt nur 40 Strecke: 120 minus 40, also 80 Gewinn. Warten hat hier eine Fahrt gespart.
Nun hat Kunde B die kürzere Frist 35. „Sofort“ ist mit dem ersten Kunden noch unterwegs und käme bei Kunde B zu spät, also lehnt es ab. „Spätestens“ steht noch im Lager, nimmt beide an und fährt sie gemeinsam ab: 80 Gewinn gegen 40.
Das Beispiel stammt aus der Demo (dort das Linienbeispiel). Es zeigt den Fall, in dem Warten gewinnt; in der Messung gibt es auch Fälle, in denen es nichts bringt.
Annehmen oder ablehnen
Ein Auftrag wird nur angenommen, wenn ein Plan alle schon angenommenen Aufträge samt dem neuen noch rechtzeitig liefert. Zusätzlich kann man eine Schwelle setzen: Der neue Auftrag wird nur angenommen, wenn der Umweg, den er kostet, höchstens so groß ist wie sein Erlös.
Was die Messung zeigt
Die Demo spielt das mit zufälligen Aufträgen durch, für fünf Kombinationen aus Auftragsstrom und Fahrzeugzahl, jeweils auf vielen Tagen und immer mit denselben Aufträgen für alle Strategien.
- Warten sammelt. Bei wenigen Aufträgen fährt „Spätestens“ gut ein Drittel weniger Fahrten als „Sofort“, und jede Fahrt ist voller. Der Gewinn je Tag steigt stark.
- Der Vorteil schrumpft, wenn viele Aufträge kommen. Dann findet auch der sofort fahrende Wagen schnell etwas zum Mitnehmen. Auf den fest gewählten Testtagen ist der Vorteil bei sehr dichtem Strom nicht mehr nachweisbar, auf frischen Testtagen bleibt er deutlich. Daraus lässt sich nicht schließen, dass Warten dort nichts bringt.
- Die Schwelle hilft nicht jedem. Wer sofort fährt, verliert mit der Schwelle in vier von fünf untersuchten Fällen, denn er fährt oft mit einem einzigen Auftrag, und dann ist jeder neue Umweg groß, sodass viele Aufträge abgelehnt werden. Wer wartet, gewinnt mit der Schwelle in allen fünf Fällen, auf den festen Testtagen in vier davon nachweisbar.
Wo die Messung nicht hinreicht
Im Rechenbild der Demo fährt jeder Wagen genau so lange, wie die Strecke es verlangt: keine Staus, keine Verspätungen. Dann kostet das Warten bis zur spätesten Abfahrt kein Risiko. In einem echten Betrieb wäre das anders, und der Vorteil des Wartens würde schrumpfen. Wie stark, hat die Demo nicht gemessen.
Häufige Missverständnisse
- „Warten ist immer besser.“ Nein. Der Vorteil sinkt, wenn viele Aufträge kommen, und das Rechenbild kennt keine Verspätungen.
- „Eine Schwelle für Umwege ist immer klug.“ Nein. Wer sofort fährt, lehnt damit Aufträge ab, die nach dem Sammeln billig wären.
- „Wer nichts ablehnt, hat den größten Gewinn.“ Nicht in jedem Fall: Beim Warten bringt die Schwelle Gewinn.
Woran Sie das im Alltag erkennen
- Ein Fahrer wartet an der Rampe, weil „vielleicht noch etwas kommt“? Die Frage ist dieselbe wie hier: Wie lange darf er warten, ohne eine Frist zu verpassen?
- Ein Disponent lehnt Aufträge ab, die weit weg liegen? Das ist eine Schwelle. Ob sie lohnt, hängt davon ab, ob die Fahrer sonst mit fast leerem Wagen führen.
Wie ernst ist das Rechenbild zu nehmen?
Die Demo ist ein vereinfachtes Rechenbild: ein Lager in der Mitte eines Quadrats, wenige gleiche Fahrzeuge, zufällige Aufträge, eine feste Frist, ein fester Erlös. Die Rangfolge hängt an Auftragsstrom und Fahrzeugzahl; fünf Kombinationen zeigen das, aber sie belegen keine allgemeine Regel.
Was Sie mitnehmen
- Warten sammelt Aufträge auf weniger, vollere Fahrten, solange die Frist es erlaubt, und das bringt Gewinn.
- Der Vorteil schrumpft, je dichter der Auftragsstrom ist.
- Eine Annahmeschwelle schadet dem, der sofort fährt, und nützt dem, der wartet.
Selbst ausprobieren
In der Demo lassen Sie einen Tag ablaufen, sehen die Wagen auf einem Zeitstrahl und vergleichen die Strategien. Der Knopf „Weiter zum Fachteil“ führt zum zweiten Teil dieser Seite.
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. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.
- Gebiet und Flotte: Depot in der Mitte eines 100 × 100 Gebiets, \(K\) Fahrzeuge der Kapazität 8, Fahrzeit gleich Strecke.
- Aufträge: Poisson-Strom (3, 6, 9 oder 12 je Stunde) in [0, 480] Minuten, gleichverteilter Ort, Last 1 bis 3, Lieferfrist Eingang + 120, Erlös 60 je angenommenem Auftrag.
- Wartestapel: Die Wartenden bilden eine Riesentour; der Split mit Fristen zerlegt sie in Routen (Vorwärtsprüfung, Abbruch beim ersten Verstoß); der neue Auftrag kommt an die Stelle mit dem kleinsten Split (Stück 13).
- Warten: Die Politik \(W_\tau\) startet eine geplante Route zum Zeitpunkt \(\min(\ell,\) Eingang ihres ältesten Auftrags \(+ \tau)\), frühestens bei freiem Fahrzeug; \(\tau = 0\) ist „Sofort“, \(\tau = \infty\) „Spätestens“.
- Annehmen: nur, wenn ein Plan alle noch nicht gestarteten angenommenen Aufträge samt dem neuen rechtzeitig bedient; mit Schwelle zusätzlich nur, wenn die Zusatzstrecke des neuen Plans höchstens 60 beträgt.
- Instanzen: 60 feste (Seeds 0 bis 59) und 60 frische (Seeds ab 200000) je Zelle; ein Lauf je Politik und Instanz (deterministisch). Keine Rechenzeiten.
Die Formeln
Späteste Abfahrt. Eine Route \((i_1, \dots, i_m)\) mit Fahrstrecke \(o_k = c_{0 i_1} + \dots + c_{i_{k-1} i_k}\) bis zum Stopp \(k\) ist bei Abfahrt \(s\) zulässig, wenn \(s + o_k \le d_{i_k}\) für alle \(k\) gilt, also
\[s \le \ell = \min_k (d_{i_k} - o_k)\]
Politik \(W_\tau\). Der Wunschstart einer Route \(r\) ist
\[w_r = \min(\ell_r, t_{\text{älteste}}(r) + \tau)\]
Die Routen werden in der Reihenfolge \((w_r, \ell_r)\) dem Fahrzeug mit der frühesten Rückkehr zugeteilt; der Start ist \(\max(\text{jetzt}, w_r, \text{Rückkehr})\) und nur zulässig, wenn er \(\le \ell_r\) ist.
Gewinn. Je Tag
\[60 \cdot (\text{angenommen}) - \text{gefahrene Strecke}\]
Differenzen zweier Politiken werden je Instanz gepaart gebildet; der Standardfehler ist die Stichprobenstreuung geteilt durch \(\sqrt{60}\). „Gleichauf“ heißt: innerhalb von zwei Standardfehlern.
Herleitung Schritt für Schritt
Dieser Block ist Rechnung dieser Seite aus den Definitionen der Demo, keine Messung.
- Schritt 1, späteste Abfahrt im Linienbeispiel: Die Route (2 1) hat die späteste Abfahrt \(\min(75 - 20,\; 60 - 30)\), also 30: Auftrag 2 (Frist 75) wird nach 20 Strecke erreicht, Auftrag 1 (Frist 60) nach 30. Der Start bei 30 ist damit der späteste zulässige.
- Schritt 2, Gewinn im Beispiel: Sofort fährt zwei Routen mit zusammen 60 Strecke und gewinnt \(2 \cdot 60 - 60 = 60\); Spätestens fährt eine Route mit 40 Strecke und gewinnt \(2 \cdot 60 - 40 = 80\).
- Schritt 3, die Grenzfälle der Politik: Für \(\tau = 0\) ist der Wunschstart der Eingang des ältesten Auftrags, die Route fährt, sobald ein Fahrzeug frei ist. Für \(\tau = \infty\) ist er \(\ell_r\): Das Fahrzeug wartet bis zur letzten zulässigen Abfahrt. Dazwischen wächst die Wartezeit mit \(\tau\).
Durchgerechnete Beispiele
Linienbeispiel (Depot bei 0, Auftrag 1 bei 10 mit Eingang 0 und Frist 60, Auftrag 2 bei 20 mit Eingang 15, ein Fahrzeug): Sofort fährt 2 Routen mit Strecke 60, Spätestens 1 Route mit Strecke 40 und Abfahrt 30 (Gewinn 60 gegen 80). Mit Frist 35 für Auftrag 2 lehnt Sofort den Auftrag ab (das Fahrzeug ist noch unterwegs), Spätestens nimmt beide an (Abfahrt 15; Gewinn 40 gegen 80).
Befunde
Die Zahlen stammen aus der README der Demo und sind in tests/test_claims.py nachgerechnet. Zellen und Politiken wurden vor der Messung festgelegt. Differenz im Mittel ± Standardfehler, in Klammern die Instanzen mit besserem / gleichem / schlechterem Gewinn. Feste Instanzen (60 je Zelle):
| Zelle (Aufträge je Stunde, Fahrzeuge) | Sofort: Gewinn | Spätestens − Sofort | Schwelle − alles annehmen, bei Sofort | Schwelle − alles annehmen, bei Spätestens |
|---|---|---|---|---|
| 3 je Stunde, K = 3 (im Mittel 25 Aufträge) | −68 | +235 ± 14 (59/0/1) | +209 ± 16 (57/0/3) | +76 ± 14 (47/0/13) |
| 6 je Stunde, K = 3 (im Mittel 50 Aufträge) | +384 | +158 ± 21 (50/0/10) | −103 ± 19 (14/0/46) | +28 ± 22 (33/0/27) |
| 6 je Stunde, K = 2 (im Mittel 50 Aufträge) | +392 | +37 ± 21 (35/0/25) | −73 ± 16 (19/0/41) | +80 ± 17 (45/0/15) |
| 9 je Stunde, K = 3 (im Mittel 74 Aufträge) | +715 | +111 ± 22 (45/0/15) | −253 ± 23 (6/0/54) | +94 ± 27 (41/0/19) |
| 12 je Stunde, K = 3 (im Mittel 98 Aufträge) | +1003 | +7 ± 28 (32/0/28) | −286 ± 34 (9/0/51) | +225 ± 26 (54/0/6) |
Frische Instanzen (60 je Zelle):
| Zelle (Aufträge je Stunde, Fahrzeuge) | Sofort: Gewinn | Spätestens − Sofort | Schwelle − alles annehmen, bei Sofort | Schwelle − alles annehmen, bei Spätestens |
|---|---|---|---|---|
| 3 je Stunde, K = 3 (im Mittel 24 Aufträge) | −90 | +253 ± 15 (60/0/0) | +227 ± 15 (57/0/3) | +80 ± 14 (46/0/14) |
| 6 je Stunde, K = 3 (im Mittel 48 Aufträge) | +389 | +141 ± 17 (51/0/9) | −115 ± 19 (13/0/47) | +64 ± 20 (42/0/18) |
| 6 je Stunde, K = 2 (im Mittel 48 Aufträge) | +390 | +41 ± 17 (37/0/23) | −68 ± 14 (17/0/43) | +117 ± 17 (48/0/12) |
| 9 je Stunde, K = 3 (im Mittel 72 Aufträge) | +728 | +112 ± 25 (45/0/15) | −262 ± 22 (3/0/57) | +97 ± 28 (37/0/23) |
| 12 je Stunde, K = 3 (im Mittel 95 Aufträge) | +999 | +111 ± 26 (45/0/15) | −250 ± 30 (8/0/52) | +131 ± 23 (46/0/14) |
Warten sammelt. Bei 3 Aufträgen je Stunde und 3 Fahrzeugen fährt Spätestens 9,9 statt 15,8 Routen je Tag mit 4,55 statt 2,96 Last je Route; die Strecke je angenommenem Auftrag sinkt von 63,8 auf 53,2. Der Preis sind weniger Annahmen (89,5 % gegen 92,0 %).
Der Gewinn des Wartens sinkt mit der Auslastung, ob er bei 12 je Stunde null ist, entscheiden die beiden Instanzmengen nicht gleich. Auf den festen Instanzen fällt Spätestens gegen Sofort von +235 (3 je Stunde) auf +7 ± 28 (12 je Stunde, gleichauf); auf den frischen Instanzen bleibt er dort bei +111 ± 26 (45/0/15). „Gleichauf“ heißt nicht „nichts“.
Die Annahmeschwelle schadet bei „Sofort“ ab 6 Aufträgen je Stunde und nützt beim Warten. Unter „Sofort“ fährt oft ein Auftrag allein, die Zusatzstrecke eines neuen Auftrags ist dann hoch, und die Schwelle lehnt viele Aufträge ab (Annahmen bei 6 je Stunde: 70,5 % ohne, 27,3 % mit Schwelle); dass es Aufträge sind, die nach dem Sammeln billig wären, ist plausibel, aber nicht direkt gemessen.
Die Wartezeit im Einzelnen (6 je Stunde, 3 Fahrzeuge, feste Instanzen):
| Politik (Wartezeit tau) | Annahmen | Strecke je Auftrag | Gewinn je Tag | gegen Sofort | Routen | Last je Route |
|---|---|---|---|---|---|---|
| Sofort (0) | 70,5 % | 49,3 | 384 | – | 16,2 | 4,33 |
| Warten 10 (10) | 70,3 % | 47,8 | 433 | +48 ± 20 (37/0/23) | 15,2 | 4,59 |
| Warten 20 (20) | 70,5 % | 47,0 | 462 | +77 ± 17 (44/0/16) | 14,3 | 4,89 |
| Warten 40 (40) | 69,4 % | 45,8 | 495 | +111 ± 18 (47/0/13) | 13,5 | 5,05 |
| Spätestens (∞) | 68,0 % | 44,1 | 543 | +158 ± 21 (50/0/10) | 12,2 | 5,48 |
Was die Messung zeigt und was nicht
- Belegt: der Vergleich der Politiken im Modell. Wartepolitiken und Schwelle stehen auf denselben Aufträgen gegeneinander, auf festen und frischen Instanzen.
- Belegt nicht: „Warten bringt bei dichtem Strom nichts“. Das stützen nur die festen Instanzen; auf den frischen bleibt der Vorteil bei 12 je Stunde deutlich positiv.
- Belegt nicht: der Fachkanon zu Annahmeschwellen. Die Aussage, Schwellen schlügen „alles annehmen“ erst bei knapper Kapazität, bestätigt die Reihe nicht: Auch bei dünnem Strom nützt die Schwelle schon unter Sofort, vermutlich weil ein angenommener Auftrag unter Sofort im Mittel 63,8 Strecke kostet bei Erlös 60 (nicht direkt gemessen).
- Belegt nicht: ein Widerspruch zur Literatur. Der Fachkanon (Bent und Van Hentenryck) sagt, der Gewinn wachse mit der Dynamik; hier fällt er mit der Rate bei begrenzter Flotte. Das ist ein anderes Modell und keine Widerlegung.
Grenzen
- Deterministisches Modell. Fahrzeit gleich Strecke, keine Verspätungen. Ohne Unsicherheit kostet „Spätestens“ kein Risiko; mit Verspätungsrisiko würde der Vorteil des Wartens schrumpfen (nicht gemessen). Das ist die größte Grenze.
- Ein Depot, eine kleine Flotte. K = 1 bis 4 Fahrzeuge der Kapazität 8; die Rangfolge hängt an Rate und Flotte, die fünf Zellen zeigen das, belegen aber keine allgemeine Aussage.
- Annahmetest hinreichend, nicht notwendig. Zulässige Mengen können abgelehnt werden; die Annahmen sind eine untere Schranke jeder Politik.
- Schwelle auf der Planungsdifferenz. Die Zusatzstrecke ist die des aktuellen Plans, nicht die des endgültigen; das erklärt einen Teil des Befunds, dass die Schwelle bei „Sofort“ schadet.
- Kein Hindsight-Orakel. Die Politiken werden nur untereinander verglichen; die Lücke zum Optimum ist unbekannt.
- Keine Neuzuteilung unterwegs. Fahrzeuge im Einsatz werden nicht umgeleitet.
Erweiterungen und Verweise
- Neue Aufträge vor der Abfahrt, ohne Zeitachse: Stück 13 der Linie („Neue Aufträge, ruhiger Plan“).
- Split mit Fristen und späteste Abfahrten: Stück 8 (Zeitfenster).
Quellen
- Mitrović-Minić, S., Laporte, G. (2004): Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B 38 (7), 635–655.
- Pillac, V., Gendreau, M., Guéret, C., Medaglia, A. L. (2013): A review of dynamic vehicle routing problems. European Journal of Operational Research 225 (1), 1–11.
- Prins, C. (2004): A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31 (12), 1985–2002.
Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der Literaturzeile der Demo (dort nur als Titel oder Abstract gesehen). Die Demo übernimmt keine Zahl aus ihnen.