Neue Aufträge, ruhiger Plan verständlich erklärt

Morgens bekommt jeder Fahrer seine Liste. Dann trifft noch ein Auftrag ein. Am einfachsten steckt man ihn irgendwo dazu, aber dann wird der Plan mit jedem Auftrag länger. Plant man alles neu, wird er kürzer, doch viele Fahrer bekommen neue Listen. Gibt es einen Mittelweg?

Zuletzt aktualisiert: 11. November 2026

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

Der Plan steht, und es kommt ein Auftrag

Ein Lieferdienst hat seine Fahrten für den Tag geplant. Jeder Fahrer kennt seine Liste von Stopps. Nun trifft noch ein Auftrag ein, bevor die Wagen abfahren. Er muss in einen Plan, und jede Änderung des Plans kostet etwas: Der Fahrer muss seine Liste neu lesen, und Kunden, denen eine Zeit genannt wurde, werden vielleicht umgeplant.

Man hat also zwei Wünsche, die sich widersprechen. Der Plan soll kurz bleiben, und er soll sich möglichst wenig ändern.

Drei Wege, einen neuen Auftrag aufzunehmen

Einfügen: Man sucht die Stelle in einer vorhandenen Fahrt, an der der neue Kunde am wenigsten Umweg macht, und steckt ihn dazu. Alles andere bleibt, wie es war. Das ist ruhig und billig. Aber niemand ordnet nach, und mit jedem Auftrag sieht der Plan weniger gut aus.

Alles neu planen: Man rechnet nach jedem Auftrag den ganzen Plan von vorn. Das Ergebnis ist kurz. Es kann aber sein, dass viele Fahrer plötzlich andere Listen haben.

Neu-Split: Dafür braucht man ein Bild aus dem ersten Teil dieser Reihe: Die Fahrten des Tages hängen sich zu einer einzigen Kundenliste aneinander, und ein Schnitt zwischen zwei Kunden zeigt, wo eine Fahrt endet und die nächste beginnt. Beim Neu-Split setzt man den neuen Kunden an die Stelle der Liste, an der der Plan am kürzesten wird, und legt dann die Schnitte neu. Die Reihenfolge der übrigen Kunden bleibt. Nur die Stellen, an denen Fahrten enden und beginnen, wandern.

Was „der Plan ändert sich“ heißt

Die Demo zählt einen Stopp als geändert, wenn sich der Stopp davor ändert, also der Ort, von dem der Fahrer zu ihm fährt. Der Depot-Start zählt als Stopp davor. Der neue Kunde und die Stopps, die nur wegen ihm einen neuen Vorgänger haben, zählen nicht.

Beim Neu-Split ändert sich so nur wenig: Wo ein Schnitt wandert, bekommt allenfalls ein Stopp einen neuen Vorgänger. Wer neu plant, kann dagegen viele Stopps umhängen.

Ein Beispiel auf einer Geraden

Stellen Sie sich fünf Kunden an einer langen Straße vor, das Lager in der Mitte. Ein Wagen fasst vier Pakete, jeder Kunde bekommt eins. Der Plan mit vier Kunden hat eine Fahrt von der Länge 16. Nun trifft ein fünfter Kunde ein. Beim einfachen Einfügen passt er nicht in die volle Fahrt, also entsteht eine zweite Fahrt nur für ihn, und der Plan ist 18 lang, ohne dass sich sonst etwas ändert. Der Neu-Split dagegen bringt ihn in die Liste ein, schneidet neu und kommt wieder auf 16. Dabei ändert sich genau ein Stopp: Ein Kunde hat danach das Lager als Vorgänger.

Das Beispiel stammt aus der Demo (dort das Linienbeispiel). Es zeigt den Fall, in dem der Neu-Split gewinnt.

Was die Messung zeigt

Die Demo spielt das für 12 bis 100 Kunden durch: Die Hälfte der Kunden ist von Anfang an bekannt, die andere Hälfte trifft nacheinander ein. Beim einfachen Einfügen ist der Plan am Ende weit vom besten bekannten Plan entfernt. Der Neu-Split halbiert diese Lücke und ändert dabei pro neuem Auftrag meist weniger als einen Stopp. Wer alles neu plant, kommt dem besten Plan näher, ändert aber ein Vielfaches an Stopps.

Die Lokalsuche, die nach jedem Auftrag einzelne Stopps probeweise umhängt oder tauscht, liegt dazwischen. Sie gewinnt mehr als der Neu-Split, ändert aber auch mehr. Kurz: Der Neu-Split holt gut die Hälfte des Gewinns der Neuplanung und ändert nur einen kleinen Teil ihrer Stopps.

Wann der Neu-Split verliert

Er ist nicht auf jedem Plan besser. In der Demo gibt es einen Fall, in dem das einfache Einfügen schon den besten Plan trifft und der Neu-Split ihn verschlechtert. Außerdem schneidet er die Liste oft in etwas mehr Fahrten, also braucht er etwas mehr Wagen. Dass die kürzere Strecke mit mehr Fahrten einhergeht, hat die Demo gemessen; ob das eine Ursache ist, zeigt sie nicht.

Das Sammelfenster: später antworten, seltener ändern

Man kann auch warten, bis mehrere Aufträge zusammengekommen sind, und sie dann gemeinsam einplanen. Der Plan ändert sich dann seltener, und das Endergebnis ist dasselbe, denn es werden dieselben Schritte nur später ausgeführt. Dafür weiß der Kunde erst am Ende des Fensters, ob sein Auftrag im Plan steht.

Diese Wartezeit hat die Demo nicht bewertet, denn alle Aufträge treffen dort ein, bevor ein Wagen abfährt. Ob das Warten sich lohnt, ist eine Frage der Zeit. Die nächste Seite dieser Reihe, „Warten oder fahren“, behandelt sie.

Häufige Missverständnisse

• „Ein ruhiger Plan ist ein schlechter Plan.“ Nein. Der Neu-Split ist ruhig und trotzdem deutlich kürzer als das einfache Einfügen. Er erreicht aber nicht die Neuplanung.
• „Neu-Split ist immer besser.“ Nein, es gibt Fälle, in denen er verliert.
• „Das Sammelfenster verbessert den Plan.“ Nein. Im Rechenbild der Demo ändert es das Endergebnis nicht, es spart nur Zwischenänderungen und kostet Antwortzeit.

Woran Sie das im Alltag erkennen

• Morgens stehen die Fahrten, und bis zur Abfahrt kommen noch Aufträge dazu? Dann stellen Sie sich dieselben drei Fragen: einfach einstecken, alles neu planen oder nur die Grenzen zwischen den Fahrten verschieben.
• Ihre Fahrer klagen, dass sich die Listen ständig ändern? Dann hilft es, die Änderungen zu zählen und gegen die gesparte Strecke zu stellen.

Wie ernst ist das Rechenbild zu nehmen?

Die Demo ist ein vereinfachtes Rechenbild: Alle Aufträge treffen vor der Abfahrt ein, es gibt keine Zeitfenster, keine Fristen und keine Obergrenze für die Zahl der Wagen. Die Karten sind aus Zufallszahlen, die Instanzen höchstens 100 Kunden groß. Die Demo zeigt, wie sich ein Plan mit der Art des Einfügens verändert, nicht, wie ein echter Betrieb entscheiden sollte.

Was Sie mitnehmen

• Wer neue Aufträge aufnimmt, tauscht Kürze gegen Ruhe: einfaches Einfügen ist ruhig und lang, Neuplanung kurz und unruhig.
• Der Neu-Split verschiebt nur die Schnittstellen der Kundenliste und gewinnt so einen großen Teil der Kürze für wenige Änderungen.
• Ob Sammeln sich lohnt, hängt von der Zeit ab, und die fehlt in diesem Rechenbild.

Selbst ausprobieren

In der Demo lassen Sie Aufträge eintreffen und sehen, welche Stopps sich ändern. 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.

• Problem: CVRP ohne Flottengrenze und ohne Zeitfenster (Depot, \(n\) Kunden mit Nachfrage \(q_i\), Kapazität \(Q\), euklidische \(d_{ij}\)). Die Kapazität folgt aus der Auslastung (90 %, drei Zielrouten).
• Ein Tag: Die ersten \(n/2\) Kunden einer Zufallsreihenfolge (Seed gleich Instanzseed) sind bekannt und mit dem besten von neun \(\lambda\) (Savings, Rundreise je Route) zu einem Plan gebaut; die übrigen treffen nacheinander vor der Abfahrt ein.
• Politiken: Einfügen (billigste zulässige Stelle in den Routen, sonst neue Route), Einfügen + Lokalsuche (2-opt, Verschieben, Tauschen), Neu-Split (neuer Kunde in die Riesentour, dann Split), Neu-Split + Lokalsuche, Sammelfenster (alle \(k\) Aufträge, einzeln wie Neu-Split eingefügt) und Neuplanung von Grund auf (Savings mit Rundreise über alle Bekannten).
• Instanzen: 60 feste (\(n = 12\): 20, 25: 16, 50: 16, 100: 8), dazu frische (Seeds ab 200000, 8 je Größe 25 und 50 mit je drei Eintreffensreihenfolgen). Keine Rechenzeiten.

Die Formeln

Einfügen in die Riesentour. Trifft Kunde \(u\) ein, wird für alle Plätze \(p\)

\[\sigma^{(p)} = (\sigma_1, \dots, \sigma_p, u, \sigma_{p+1}, \dots)\]

gebildet und das \(p\) mit dem kleinsten \(\operatorname{Split}(\sigma^{(p)})\) gewählt (Gleichstand: das kleinste \(p\)); der neue Plan ist die Zerlegung dieses Splits. Die Reihenfolge von \(\sigma\) ohne \(u\) bleibt unverändert; nur die Schnittstellen wandern.

Sammelfenster. Die in einem Fenster gesammelten Aufträge werden nacheinander wie oben eingefügt; der Endplan nach einem Fenster ist der des Neu-Splits nach jedem Auftrag desselben Fensters, weil dieselben Schritte in derselben Folge laufen.

Planänderung. Sei \(\pi_x\) der Vorgänger von Stopp \(x\) in einem Plan (\(0\) für das Depot). Die Planänderung zwischen altem und neuem Plan ist

\[\#\{x \text{ steht im Plan} :\pi^{\text{neu}}_x \ne \pi^{\text{alt}}_x\}\]

ohne den neuen Kunden und ohne die Stopps, deren neuer Vorgänger der neue Kunde ist.

Herleitung Schritt für Schritt

Dieser Block ist Rechnung dieser Seite aus den Definitionen der Demo, keine Messung.

• Schritt 1, warum der Neu-Split die Reihenfolge nicht ändert: Die Folge \(\sigma^{(p)}\) enthält alle alten Kunden in ihrer alten Reihenfolge; der Split zerlegt eine feste Folge nur in aufeinanderfolgende Stücke. Er kann also nur ändern, welche Kunden in einer Route zusammenfahren, nicht die Reihenfolge innerhalb der Folge.
• Schritt 2, warum nur wenige Vorgänger wechseln: Der Vorgänger eines Stopps \(x\) ist sein Vorgänger in der Folge, außer \(x\) beginnt eine Route; dann ist es das Depot. Er ändert sich daher nur dort, wo vor \(x\) ein Schnitt neu entsteht oder entfällt. Steht der neue Kunde unmittelbar vor \(x\), zählt das nicht.
• Schritt 3, das Sammelfenster: Das Fenster fügt dieselben Aufträge in derselben Reihenfolge mit demselben Split ein, nur später. Der Endplan ist der gleiche; die Zwischenpläne des Einzelverfahrens entfallen, und mit ihnen deren Änderungen.

Durchgerechnete Beispiele

Linienbeispiel (Kunden bei −1, −3, +4, −4, Kapazität 4, Nachfragen 1, Plan (3 4 2 1) mit Länge 16; Kunde 5 bei +1): Einfügen eröffnet die Route (5) und endet bei 18, ohne Änderung. Neu-Split ändert genau einen Stopp (Kunde 4 hat danach das Depot als Vorgänger) und endet bei 16.

Handinstanz (Stück 1 bis 4, Kapazität 7, Seed 0; die Kunden 5, 3, 2 bekannt, 1, 6, 4 treffen ein): Einfügen 44,36 (das Optimum) ohne Änderung, Neu-Split 49,45 mit einer Änderung und drei Routen, Neuplanung 44,36 mit vier Änderungen. Neu-Split ist nicht auf jeder Instanz besser; dieser Fall steht ausdrücklich in der Demo.

Befunde

Die Zahlen stammen aus der README der Demo (feste Instanzen, 50 % von Anfang an bekannt); sie sind nachgerechnet in tests/test_claims.py.

Endlücke zur Referenz in % (Planänderungen je Tag)	n = 12	25	50	100
Einfügen in die Routen	23,2 (0,0)	30,6 (0,0)	37,5 (0,0)	47,8 (0,0)
Einfügen + Lokalsuche	3,2 (9,2)	6,9 (29,0)	10,6 (77,9)	7,5 (158,8)
Neu-Split nach jedem Auftrag	3,9 (3,8)	16,0 (6,4)	18,0 (18,1)	23,8 (25,1)
Neu-Split + Lokalsuche	1,6 (8,7)	5,1 (31,2)	5,4 (98,2)	7,7 (191,5)
Sammelfenster, alle 5 Aufträge	3,9 (1,4)	16,0 (2,9)	18,0 (7,1)	23,8 (11,4)
Neuplanung von Grund auf	2,4 (13,9)	3,2 (73,7)	5,1 (204,9)	6,4 (729,2)
Offline-Plan (alle Kunden bekannt)	1,4	1,5	2,5	4,0

Der Neu-Split fängt 53 / 60 / 58 % des Gewinns der Neuplanung ein (n = 25 / 50 / 100), mit 9 / 9 / 3 % von deren Änderungen. Je Eintreffen ändert er im Mittel 0,5 / 0,7 / 0,5 Stopps, die Lokalsuche 2,2 / 3,1 / 3,2, die Neuplanung 5,7 / 8,2 / 14,6. In 172 von 172 Zeilen ist die Endlänge von Sammelfenster (\(k = 5\) und \(k = 10\)) und Neu-Split nach jedem Auftrag gleich.

Was die Messung zeigt und was nicht

• Belegt: der Vergleich der Politiken vor der Abfahrt. Neu-Split gegen Einfügen, Länge gepaart billiger / gleich / teurer: n = 12: 19 / 0 / 1, n = 25: 16 / 0 / 0, n = 50: 16 / 0 / 0, n = 100: 7 / 0 / 1.
• Belegt nicht: eine Aussage zum Sammelfenster. Ohne Zeitachse ist „das Sammelfenster fängt den größten Teil der Verbesserung ein“ trivial wahr (100 %) und beantwortet die Frage nicht; die Antwortzeit bis zur Zusage ist nicht bepreist. Die Messreihe Planstabilität im Nahverkehr (mit Fahrzeugen, die abfahren, und Lokalsuche) fand das Gegenteil: periodische Neuplanung fängt bei einem Viertel der Änderungen nur gut ein Drittel des Gewinns ein. Die Zeit gehört zu Stück 14.
• Belegt nicht: eine Ursache für die höhere Routenzahl. Der Endplan des Neu-Splits hat 3,15 / 3,38 / 3,31 / 3,62 Routen gegen 3,05 / 3,00 / 3,00 / 3,00 beim Einfügen; gemessen ist nur das gemeinsame Auftreten.

Grenzen

• Eintreffen vor der Abfahrt, keine Zeitachse, keine Flottengrenze. Eine Vorrechnung mit knapper Flotte (Auslastung 98 %, 25 und 50 Kunden, je 16 Instanzen) zeigte keinen Unterschied in den Annahmen zugunsten einer Politik; sie ist nicht Teil der Demo.
• Eine einfache Lokalsuche (erste Verbesserung mit 2-opt, Verschieben und Tauschen); wie sich der Gewinn je Änderung mit reicheren Nachbarschaften ändert, ist nicht gemessen.
• Eigene Instanzen, eine Eintreffensreihenfolge je feste Instanz, bei 100 Kunden nur 8 Instanzen; die Referenz (PyVRP, 5 Sekunden) ist keine Untergrenze.
• Das Maß der Planänderung zählt Vorgänger; andere Maße (Fahrer, Kunden, Routenzuordnung) können anders ausfallen.

Erweiterungen und Verweise

• Zeitachse, Warten und Annehmen: Stück 14 der Linie Tourenbildung („Warten oder fahren“).
• Riesentour und Split: Stück 1; die Fall-Demos zum Same-Day-Nahverkehr rechnen Neuplanung mit Lokalsuche und Änderungsstrafe.

Quellen

• 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.
• Bent, R., Van Hentenryck, P. (2004): Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research 52, 977–987.
• 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. Die Demo übernimmt keine Zahl aus ihnen.