Riesentour und Split verständlich erklärt

Ein Lieferdienst hat Kunden, die Pakete bekommen, und Wagen, die nur begrenzt viel laden. Wer fährt mit wem, und in welcher Reihenfolge? Das klingt nach zwei Entscheidungen zugleich. Es geht auch mit einer: eine einzige Liste aller Kunden, die man danach an den besten Stellen durchschneidet.

Zuletzt aktualisiert: 11. November 2026

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

Wer fährt mit wem?

Ein Lieferdienst hat morgens eine Liste von Kunden. Jeder bekommt Pakete, und ein Wagen fasst nur eine bestimmte Menge. Man braucht also mehrere Fahrten, und jede startet im Lager und endet dort wieder. Gesucht ist der Plan mit der kürzesten Gesamtstrecke.

Das ist schwerer, als es klingt. Man muss gleichzeitig entscheiden, welche Kunden in dieselbe Fahrt gehören und in welcher Reihenfolge ein Wagen sie besucht. Beides hängt voneinander ab: Wer zusammen fährt, bestimmt die Reihenfolge, und wer günstig hintereinanderliegt, gehört zusammen.

Der Trick: erst eine Liste, dann schneiden

Schreiben Sie alle Kunden in eine einzige Reihenfolge, ganz ohne an Wagen zu denken. Fachleute nennen das eine Riesentour. Dann schneiden Sie die Liste an einigen Stellen durch. Jedes Stück ist eine Fahrt, und jedes Stück muss in einen Wagen passen.

Die Frage ist, wo man schneidet. Die beste Antwort findet man ohne Probieren. Für jedes Stück der Liste, das in einen Wagen passt, kennt man die Länge der zugehörigen Fahrt. Man sucht dann die kürzeste Kette solcher Stücke vom Anfang bis zum Ende der Liste, so wie man auf einer Karte die kürzeste Verbindung von A nach B sucht. Das Durchschneiden heißt Split, englisch für „aufteilen“.

Der Split ist schnell und liefert für diese Liste die bestmögliche Zerlegung. Die Entscheidung „wer fährt mit wem“ ist damit gelöst; übrig bleibt die Frage, welche Liste man nimmt.

Warum eine Liste genügt

Nehmen Sie irgendeinen guten Plan. Hängen Sie seine Fahrten hintereinander, so entsteht eine Liste aller Kunden. Schneidet man sie an den alten Grenzen durch, bekommt man den Plan zurück. Der Split sucht den besten Schnitt, also findet er diesen Plan oder einen besseren.

Daraus folgt: Der beste Plan, den es überhaupt gibt, steckt in irgendeiner Liste. Man muss nie nach Fahrten suchen, es genügt, eine Liste zu finden.

Der Haken: Es gibt sehr viele Listen, und nur wenige führen zum besten Plan. Bei acht Kunden gibt es 40 320 mögliche Listen. Im mittleren Fall führen nur 48 davon zum besten Plan.

Ist die kürzeste Rundreise eine gute Liste?

Naheliegend wäre diese Liste: der kürzeste Rundweg, der alle Kunden besucht, als gäbe es nur einen unbegrenzt großen Wagen. Er hat den kürzesten Weg und klingt nach einem guten Anfang.

Meist ist er es nicht. In der Demo mit acht Kunden führt diese Liste nach dem Schneiden, je nach Karte, nur in zwei bis acht von je zwanzig Fällen zum besten Plan. Der Grund: Der kürzeste Rundweg kennt keine Kapazität. Er legt Kunden nebeneinander, die in verschiedenen Fahrten besser aufgehoben wären, und trennt Kunden, die zusammenfahren sollten.

Warum nicht einfach den Wagen füllen?

Man könnte auch die Liste von vorn lesen und die Pakete in den Wagen laden, bis der nächste Kunde nicht mehr passt, und dann eine neue Fahrt beginnen. Das kostet nichts und ist schnell. Es schaut aber nie auf Entfernungen.

Der Split ist auf derselben Liste nie schlechter und oft deutlich besser. Er darf nämlich auch eine Fahrt früher beenden, wenn der nächste Kunde weit entfernt liegt. Wie viel besser, hängt von der Karte ab.

Häufige Missverständnisse

• „Die Liste ist der Tourenplan.“ Nein. Die Liste sagt nichts über Fahrzeuge. Erst der Split macht aus ihr Fahrten.
• „Eine Liste genügt, also ist die Aufgabe leicht.“ Nein. Der Split ist leicht, aber die richtige Liste zu finden ist es nicht. Nur wenige von vielen Listen führen zum besten Plan.
• „Der kürzeste Rundweg ist die beste Liste.“ Meist nicht, siehe oben.

Woran Sie das im Alltag erkennen

• Sie haben eine Liste von Stopps und einen Wagen mit begrenzter Ladung und müssen entscheiden, wo eine Fahrt endet und die nächste beginnt? Das ist die Frage, die der Split beantwortet.
• Jemand hat die Stopps schon sinnvoll hintereinandergeschrieben, etwa nach Postleitzahl oder Strecke? Dann hat er eine Liste, und der Split schneidet sie besser, als es feste Regeln wie „Wagen füllen“ tun.

Wie ernst ist das Rechenbild zu nehmen?

Die Demo ist ein vereinfachtes Rechenbild: höchstens neun Kunden, ein Lager, beliebig viele gleiche Wagen, keine Zeitfenster, Karten aus Zufallszahlen. Sie sagt nichts über große Aufgaben. Dort sucht man gute Listen mit Suchverfahren, und diese Seite erklärt nur, warum das ein sinnvoller Ansatz ist.

Was Sie mitnehmen

• Eine einzige Liste aller Kunden genügt, um jede Tourenaufgabe als Frage nach der richtigen Reihenfolge zu stellen.
• Wie man eine Liste am besten in Fahrten schneidet, findet man ohne Probieren.
• Eine gute Liste zu finden bleibt die eigentliche Arbeit: Die kürzeste Rundreise ist dafür oft keine gute Wahl.

Selbst ausprobieren

In der Demo wählen Sie eine Karte und eine Liste und sehen, wie der Split sie schneidet und wie weit der Plan vom besten entfernt ist. 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: ein Depot, \(n\) Kunden mit ganzzahliger Nachfrage \(q_i\), beliebig viele gleiche Fahrzeuge der Kapazität \(Q\), euklidische Entfernungen \(d(u, v)\), jede Route Depot, Kunden, Depot. Gesucht ist ein Plan kleinster Gesamtlänge (CVRP ohne Flottengrenze).
• Riesentour: eine Permutation \(\pi\) aller Kunden. Hilfsgraph: Knoten \(0, \dots, n\); ein Bogen \((i, j)\) mit \(i < j\), wenn die Kunden \(\pi_{i+1}, \dots, \pi_j\) zusammen höchstens \(Q\) belasten; sein Gewicht ist die Länge der Route \(c(i, j)\). Split: kürzester Weg von \(0\) nach \(n\).
• Instanzen: drei Kartenarten (kleine Karte mit ganzen Koordinaten 0 bis 16, zufällig verteilt 0 bis 100, drei Häufungen), Depot in der Mitte oder in der Ecke, Kapazität aus der Zielroutenzahl (Gesamtnachfrage durch Zielroutenzahl mal 0,9, aufgerundet, mindestens die größte Einzelnachfrage). Aufgezählt werden alle \(n!\) Reihenfolgen für \(n \le 8\) live, \(n = 9\) in vorberechneten Bändern.

Die Formeln

Die Route der Kunden \(\pi_{i+1}, \dots, \pi_j\) in dieser Reihenfolge hat die Länge

\[c(i, j) = d(0, \pi_{i+1}) + \sum_{t = i+1}^{j-1} d(\pi_t, \pi_{t+1}) + d(\pi_j, 0), \qquad \text{zulässig, wenn } \sum_{t=i+1}^{j} q_{\pi_t} \le Q.\]

Der Split folgt aus der Rekursion über die Knoten in ihrer Reihenfolge (der Graph ist azyklisch, alle Bögen laufen nach rechts):

\[f(0) = 0, \qquad f(j) = \min_{i < j,\ (i, j)\ \text{zulässig}} \big( f(i) + c(i, j) \big), \qquad \mathrm{Split}(\pi) = f(n).\]

Dominanz. Sei \(R_1, \dots, R_k\) ein beliebiger zulässiger Plan und \(\pi\) die Aneinanderreihung der Routen. Der Weg, der jede Route \(R_r\) als einen Bogen nimmt, ist ein Weg von \(0\) nach \(n\) mit den Kosten des Plans, also

\[\mathrm{Split}(\pi) \le \sum_r \mathrm{Länge}(R_r).\]

Gilt dies für einen optimalen Plan, so ist \(\min_\pi \mathrm{Split}(\pi)\) gleich dem Optimum, denn jede Reihenfolge liefert ohnehin einen zulässigen Plan. Zählung. Eine Lösung mit \(k\) Routen, von denen \(j^{*}\) mindestens zwei Kunden haben, lässt sich auf genau \(k! \cdot 2^{j^{*}}\) Arten hintereinanderhängen: \(k!\) Folgen der Routen, und jede Route mit mindestens zwei Kunden in zwei Richtungen. Das gilt für die Aneinanderreihung der Routen; bei Gleichständen ergeben weitere Reihenfolgen dieselben Kosten.

Herleitung Schritt für Schritt

Dieser Block ist Rechnung dieser Seite aus der Beschreibung der Demo, keine Messung. Die Nummern sind nur Bezugspunkte für den Lesefluss.

• Schritt 1, der Weg im Graphen: Jeder Weg von \(0\) nach \(n\) zerlegt die Folge in aufeinanderfolgende Stücke \((i_0 = 0 < i_1 < \dots < i_m = n)\), und jedes Stück erfüllt die Kapazität, denn nur dann ist der Bogen im Graphen. Die Länge des Wegs ist die Summe der Routenlängen, also die Länge des zugehörigen Plans.
• Schritt 2, warum die Rekursion genügt: Der Graph hat nur Bögen von links nach rechts. Der kürzeste Weg zum Knoten \(j\) endet mit einem Bogen \((i, j)\) und besteht davor aus einem kürzesten Weg nach \(i\); also ist \(f(j)\) das Minimum über alle zulässigen \(i\) von \(f(i) + c(i, j)\).
• Schritt 3, die Dominanz: Hängt man die Routen \(R_1, \dots, R_k\) eines Plans in dieser Reihenfolge hintereinander, so sind die Grenzen der Routen Knoten des Graphen, und jede Route ist ein zulässiger Bogen. Dieser Weg hat die Kosten des Plans, der kürzeste Weg höchstens diese.
• Schritt 4, die Zählung: Jede der \(k!\) Reihenfolgen der Routen und jede Richtung einer Route mit mindestens zwei Kunden ergibt eine eigene Folge (eine Route mit einem Kunden hat nur eine Richtung); das sind \(k! \cdot 2^{j^{*}}\) Folgen.

Durchgerechnete Beispiele

Von Hand nachgerechnetes Beispiel (Depot im Ursprung, Kapazität 7, aus den Tests der Demo): Das Optimum 44,36 hat die Routen (1 4) und (2 6 3 5). Die kürzeste Rundreise durch alle Kunden ist 38,24 lang; ihr Split hat 47,19 in drei Routen, also 6,4 % über dem Optimum. „Füllen bis voll“ kommt auf 55,26 (24,6 % über dem Optimum), wenn die Rundreise als 5 1 4 3 6 2 gelesen wird, in der Leserichtung 2 6 3 4 1 5 der Demo auf 47,19. Der Nächste-Nachbar-Plan mit Split kostet 49,45. Die Zahlen stehen in der README der Demo.

Voreinstellung der App (6 Kunden, kleine Karte, Depot in der Ecke, Seed 11): Optimum 63,30 in zwei Routen; die kürzeste Rundreise ist 47,22 lang, ihr Split 68,38 in drei Routen, also 8,0 % mehr. Von den 720 Reihenfolgen sind 30 besser als die Rundreise, und 8 treffen das Optimum; das sind \(2! \cdot 2^2 = 8\), die Zählformel mit \(k = 2\) und \(j^{*} = 2\).

Befunde

Die Zahlen stammen aus der README der Demo; sie sind Messungen an den festen Instanzen (je Zelle 20, vier Zellen aus Kartenart und Depotlage) und stehen nachgerechnet in tests/test_claims.py.

Frage	Befund
Liegt das Optimum unter den Reihenfolgen?	Ja: Das Minimum über alle \(n!\) Reihenfolgen ist in 80 von 80 Instanzen bei \(n = 8\) und in 80 von 80 bei \(n = 9\) gleich dem exakten Optimum.
Wie selten ist es dort?	Median der Bänder 48 von 40 320 (0,119 %) bei \(n = 8\) und 48 von 362 880 (0,013 %) bei \(n = 9\).
Ist die kürzeste Rundreise eine gute Riesentour?	Meist nicht: Ihr Split ist bei \(n = 8\) in 8 / 4 / 4 / 2 von 20 Instanzen optimal (Zellen: zufällig und Gruppen, Depot in der Mitte und in der Ecke), bei \(n = 9\) in 5 / 4 / 1 / 4.
Wie viele Reihenfolgen sind besser als die Rundreise?	Median je Zelle 0,03 bis 4,01 %; im Maximum 73,5 % aller Reihenfolgen (n = 9, Gruppen, Depot in der Ecke).
„Füllen bis voll“ auf der Rundreise	Median 5,5 / 9,9 / 6,2 / 9,4 % über dem Optimum (\(n = 8\)), Maximum 58,8 %; der Split ist auf derselben Reihenfolge nie schlechter.

Zur Absicherung: Split gegen die Aufzählung aller Schnittmengen, exakter Löser gegen die Aufzählung aller Zerlegungen und Reihenfolgen, Held–Karp gegen alle Permutationen, vektorisierter Split gegen den Einzel-Split; die Aufzählung ist an kleinen Instanzen (\(n = 6\)) unabhängig bestätigt.

Was die Messung zeigt und was nicht

• Belegt: die Dominanz und die Seltenheit des Optimums unter den Reihenfolgen, für bis zu neun Kunden und die vier Zellen, vollständig aufgezählt.
• Belegt nur eingeschränkt: „die kürzeste Rundreise ist meist keine gute Riesentour“. Das gilt für diese Instanzen mit der Kapazität aus der Zielroutenzahl bei einem Auslastungsfaktor von 0,9; bei anderen Karten oder Kapazitäten kann die Rundreise besser abschneiden. Eine Vormessung bei vier Auslastungen (\(n = 9\)) hat keinen Trend der Splitvorteile mit der Enge der Kapazität gezeigt.
• Belegt nicht: Aussagen über große Instanzen. Die Aufzählung endet bei neun Kunden; wie sich die Seltenheit des Optimums bei 50 oder 100 Kunden verhält, ist hier nicht gemessen.

Grenzen

• Höchstens 9 Kunden und eigene Instanzen: Karten aus einem Eigenbau nach grobem Muster, nicht die Benchmarkinstanzen der Literatur.
• Maßstab ist das exakte Optimum bei unbegrenzter Flotte; mit höchstens \(B\) Fahrzeugen ändert sich der Split (eine Dimension mehr).
• Leserichtung: Die kürzeste Rundreise wird in der lexikographisch kleineren Richtung gelesen; der Split hängt nicht von der Leserichtung ab, „Füllen bis voll“ schon.
• Bänder sind Spannen über 20 feste Instanzen je Zelle, keine Trends und keine Aussagen über andere Kartenarten.

Erweiterungen und Verweise

• Wie erzeugt man gute Listen? Nächster Nachbar, Einfügen, Savings und Sweep als Verfahren: Stücke 2, 4 und 6 der Linie Tourenbildung; die Suche über Listen (memetischer Algorithmus mit Split): Stück 11.
• Zeitfenster (Etiketten im Hilfsgraphen): Stück 8. Flottengrenze: Stück 3.
• Die Fall-Demo vrp_demo rechnet Touren mit mehreren Fahrzeugen; ihr genetischer Algorithmus dekodiert mit demselben Split.

Quellen

• Beasley, J. E. (1983): Route first, cluster second methods for vehicle routing. Omega 11 (4), 403–408.
• 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 Demo und der Planung dieser Reihe (Idee laut Sekundärquellen). Die Demo übernimmt keine Zahl aus ihnen.