Tourenplanung verständlich erklärt

Wer viele Orte mit mehreren Fahrzeugen anfahren muss, steht vor einer Aufgabe, die schon bei wenigen Dutzend Orten nicht mehr durch Probieren zu lösen ist. Diese Seite erklärt zuerst ohne Formeln, warum das so ist und wie man mit einfachen Regeln und gezieltem Nachbessern trotzdem zu guten Plänen kommt.

Danach folgt für Fachleute das Modell mit Formeln, Messwerten und Grenzen. Die zugehörige Demo vergleicht vier selbst gebaute Verfahren mit einem frei verfügbaren Programm von Google; der erste Teil stellt zwei davon vor.

Zuletzt aktualisiert: 28. Oktober 2026

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

Ein Plan für jeden Lieferwagen

Stellen Sie sich einen Lieferdienst vor. Morgens liegen im Lager viele Pakete, und jedes soll an einen anderen Ort. Es gibt mehrere Lieferwagen mit begrenztem Laderaum. Zu planen ist, welcher Wagen welche Orte anfährt und in welcher Reihenfolge, damit die gefahrene Strecke möglichst kurz bleibt. Die Fachsprache nennt das Tourenplanung, englisch Vehicle Routing Problem.

Dazu kommen Regeln aus dem Alltag. Manche Kundinnen und Kunden sind nur in einem bestimmten Zeitraum zu Hause; man spricht von Zeitfenstern. Straßen haben Einbahnregeln und Umwege, deshalb ist der Weg von A nach B nicht immer so lang wie der von B nach A. Ein Plan ist erst gut, wenn er solche Regeln einhält und trotzdem wenig Strecke, Zeit und Kraftstoff kostet.

Warum ist das so schwer?

Bei sehr wenigen Orten kann man alle Möglichkeiten einfach durchprobieren. Mit jedem weiteren Ort wächst ihre Zahl aber nicht um ein Stück, sondern um ein Vielfaches. Das ist wie beim Mischen eines Kartenstapels: Schon bei einem gewöhnlichen Stapel gibt es mehr Reihenfolgen, als ein Rechner je durchprobieren könnte. Bei der Tourenplanung kommt noch die Verteilung auf mehrere Wagen hinzu. Auch die größte Aufgabe, die die Demo zulässt, ist so groß, dass Durchprobieren ausscheidet.

Mathematisch gehört das Problem zu den sogenannten NP-schweren Problemen. Das heißt: Für sie ist bis heute kein Verfahren bekannt, das bei wachsender Größe immer schnell die beste Lösung garantiert. Man sucht deshalb Verfahren, die schnell eine sehr gute Lösung finden, ohne zu versprechen, dass sie die beste ist.

Was hilft: Faustregeln und Nachbessern

Solche Verfahren heißen Heuristiken, also Faustregeln mit System. Zwei davon zeigt dieser Teil. „Sweep“ lässt einen gedachten Zeiger wie einen Scheibenwischer um das Lager kreisen und sammelt die Orte der Reihe nach für die Wagen ein. „Savings“ (Ersparnis) beginnt mit einer eigenen Tour für jeden Ort und legt Touren zusammen, wo dabei am meisten Weg gespart wird. Die Demo kennt noch zwei aufwändigere Verfahren; sie sind im Fachteil beschrieben.

Danach folgt der Schritt des Nachbesserns. Er prüft einen fertigen Plan auf Verbesserungen: Kreuzt sich eine Tour selbst, dreht er ein Stück um. Passt ein Ort besser in den Wagen eines anderen, verschiebt er ihn dorthin. Das wiederholt er, bis nichts mehr besser wird. Weil er nur in der Nähe des bestehenden Plans sucht, nennen Fachleute das lokale Suche.

Als Messlatte dient ein frei verfügbares Programm von Google, OR-Tools. Es rechnet dieselbe Aufgabe mit einigen Sekunden Rechenzeit. Auch es garantiert nicht die beste Lösung, ist aber ein starker Vergleich.

Wie nah kommt man damit heran?

In der Demo zeigt sich: Bei den zufälligen Beispielen ohne Zeitfenster liegen schon einfache Regeln mit Nachbessern im Durchschnitt nicht weit von der Messlatte entfernt. „Savings“ liegt in der Demo nur wenig dahinter, „Sweep“ weiter dahinter. Die Demo erklärt das damit, dass das Nachbessern auch Orte zwischen Wagen verschiebt und so schlechte erste Zuteilungen nachträglich korrigieren kann.

Man prüft das, indem man dieselben Aufgaben mit allen Verfahren rechnet, jeden Plan gleich bewertet und die gefahrene Strecke vergleicht. Genau das tut die Demo. Dabei gewinnt kein Verfahren immer, und die Messung gilt für die zufälligen Beispiele der Demo, nicht für Ihre Touren. Die Zahlen stehen im Fachteil, dort auch eine Beobachtung zu den Zeitfenstern.

Lohnt sich das, und wie ernst ist das Modell zu nehmen?

Die Demo rechnet auf einem erfundenen Straßennetz mit zufällig erzeugten Orten und Bedarfen, nicht auf echten Karten- oder Kundendaten. Entfernungen werden als Kilometer gedeutet, Geschwindigkeit, Kosten je Kilometer und Abgase sind einstellbare Annahmen. Nicht abgebildet sind etwa mehrere Lager, Arbeitszeiten der Fahrer und Aufträge, die erst während der Fahrt eintreffen.

Für die Frage „Lohnt sich Optimierung bei uns?“ kann die Demo nur einen Teil beantworten. Sie rechnet an einem erfundenen Beispiel nach, wie weit der beste der vier Pläne von einer einfachen Abarbeitung der Orte in der Reihenfolge der Eingabe entfernt ist, und zeigt Strecke, Fahrzeit, Kraftstoffkosten und Kohlendioxid. Über Ihren Betrieb sagt sie nichts. Auch die Vergleichsbasis ist einfach: Sie sagt nicht, wie viel eine gute manuelle Planung schon herausholt. Wie groß der Gewinn bei Ihnen ausfällt, hängt davon ab, wie Ihre Orte liegen, wie knapp Laderaum und Zeitfenster sind und wie oft die Planung wiederkehrt. Diese Seite nennt deshalb keine allgemeine Ersparnis.

Mitnehmen können Sie: Einfache Regeln mit Nachbessern kommen in der Demo oft nah an eine gute Lösung heran, aber kein Verfahren ist immer vorn. Ob sich der Aufwand bei Ihnen lohnt, zeigt erst ein kleiner Test mit echten Adressen, Zeitfenstern und Fahrzeugen, etwa einer Woche Ihrer Touren. Ihr Planungsteam, eine Planungssoftware oder ein Dienstleister rechnet sie nach, und Sie vergleichen das Ergebnis mit dem, was Ihre Disponenten tatsächlich geplant und gefahren haben. Die Demo kann das nicht leisten, weil sie ein erfundenes Netz verwendet.

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: kapazitiertes Tourenproblem mit optionalen Zeitfenstern (CVRPTW). Gegeben sind \(n\) Stopps \(I\) mit Bedarf \(w_i\), ein Depot (Knoten \(0\)), \(K\) Fahrzeuge mit gleicher Kapazität \(Q\) und eine gerichtete Distanzmatrix \(D\) aus kürzesten Wegen im Straßennetz; optional Zeitfenster \([e_i, l_i]\) und Servicezeit \(s_i\). Der Regler erlaubt bis zu 30 Stopps.
• Netz: synthetisch und prozedural erzeugt, bewusst ohne Kartendienst. Optional asymmetrisch: Rund ein Viertel der Streckenabschnitte wird in einer Richtung um den Faktor 1,4–2,5× verlängert, sodass im Allgemeinen \(D_{ij} \neq D_{ji}\) gilt.
• Maßstab: Distanzen werden als km gedeutet; Geschwindigkeit, Kosten je km und CO₂ je km sind Regler und rechnen die Distanz nur in Fahrzeit, Kosten und CO₂ um. Zeitfenster laufen auf derselben Skala wie die Kartendistanz, nicht in Stunden.
• Zielfunktion: lexikografisch statt mit harten Nebenbedingungen: erst Kapazitätsüberschreitung, dann Zeitfenster-Verletzungen, dann Distanz. So liefert die App für jede Eingabe, auch für unlösbare, die nach diesem Maßstab beste gefundene Lösung. OR-Tools behandelt dagegen die Kapazität als harte Nebenbedingung und die Zeitfenster als weiche (Strafkosten).
• Vergleichsbasis: die „unoptimierte Ausgangslage“: Stopps in Eingabereihenfolge der Reihe nach kapazitätskonform in Fahrzeuge gefüllt, ohne Konstruktion und ohne lokale Suche. Die Primäransicht der Demo vergleicht die beste der vier eigenen Methoden damit; OR-Tools bleibt dort außen vor, weil es per Button gestartet wird.
• Schwere: Für \(K = 1\), \(Q \to \infty\) und ohne Zeitfenster entsteht das asymmetrische TSP, das als NP-schwer bekannt ist. Da dies ein Spezialfall ist, ist auch das allgemeine CVRPTW NP-schwer.

Die Verfahren

• Sweep: Stopps nach Polarwinkel um das Depot sortieren und reihum den Fahrzeugen zuweisen, solange die Kapazität reicht.
• Savings (Clarke & Wright): Einzeltour je Stopp, dann Touren in absteigender Ersparnis zusammenlegen. Weil \(D\) asymmetrisch sein kann, werden beide Verbindungsrichtungen getrennt geführt.
• Beam Search: dieselben Zusammenlegungen, aber mehrere Teilzustände parallel (Breite 16 ohne und 8 mit Zeitfenstern), bei jedem Schritt mit „zusammenlegen“ und „überspringen“ als Kandidaten. Die Verschachtelung nach dem monobeam-Verfahren sorgt dafür, dass eine größere Breite das Ergebnis nachweislich nie verschlechtert.
• Genetischer Algorithmus: Das Chromosom ist eine Permutation der Zusammenlegungs-Prioritäten, nicht der Stopp-Reihenfolge, er durchsucht also denselben Entscheidungsraum wie Beam Search. Order Crossover, Mutation und Elitismus; eine Zusammenlegung wird abgelehnt, wenn sie die Kapazität überschreitet oder die Zeitfenster der beiden Teiltouren verschlechtert. Für die Populationsgröße gilt keine Monotonie-Garantie.
• Lokale Suche für alle vier: 2-opt innerhalb einer Tour, Or-opt für Segmente aus einem bis zwei Stopps auch zwischen Fahrzeugen, bei Überladung zusätzlich ein Tausch zwischen zwei Touren. Ein Zug wird lexikografisch nach (Kapazität, Zeitfenster-Verletzungen, Distanz) akzeptiert.
• OR-Tools: Konstruktion mit Path-Cheapest-Arc, danach Guided Local Search, innerhalb eines Zeitlimits und ohne Optimalitätsgarantie bei den in der App üblichen Größen.

Die Formeln

Das vollständige Programm in Arc-Form: \(x_{ijv} = 1\), wenn Fahrzeug \(v\) direkt von \(i\) nach \(j\) fährt. Die Zielfunktion summiert die Distanzen aller gefahrenen Kanten. Dazu kommen Nebenbedingungen für Besuch, Fluss, Kapazität und die Zeitfenster-Propagation mit Big-M. Im Code wird dieses Programm nie in dieser Form gelöst; nur OR-Tools löst intern ein äquivalentes Modell.

\[\min \; \sum_{v=1}^{K}\sum_{i=0}^{n}\sum_{j=0}^{n} D_{ij}\, x_{ijv}\]

Die Zahl der Lösungen ist der Grund für die Heuristiken. Für jede der \(\binom{n+K-1}{K-1}\) Aufteilungen der Stoppzahl auf die \(K\) Touren gibt es \(n!\) Möglichkeiten, alle Stopps in einer Reihenfolge auf diese Plätze zu verteilen:

\[n! \binom{n+K-1}{K-1}\]

Die Fahrzeuge der App sind identisch, die Zahl wirklich verschiedener Lösungen ist daher höchstens um den Faktor \(K!\) kleiner. Den Zahlenwert für die größte einstellbare Instanz nennt der Expander der Demo (die README nennt ihn nicht); er schließt vollständiges Durchprobieren aus.

Der Savings-Algorithmus bewertet die Verbindung einer Tour, die in \(i\) endet, mit einer Tour, die in \(j\) beginnt, über die eingesparten Wege zum und vom Depot. Bei symmetrischem \(D\) gilt \(s_{ij} = s_{ji}\) und es bleibt die klassische Ersparnis:

\[s_{ij} = D_{i,0} + D_{0,j} - D_{i,j}\]

Die Zeitfenster werden entlang einer Tour rekursiv fortgeschrieben: Ankunft \(a\) am Stopp \(r_k\) aus der Abfahrt \(t\) am Vorgänger plus Fahrstrecke. Der Dienstbeginn ist \(\max(a, e)\), und eine Verletzung liegt vor, wenn \(\max(a, e) > l + \varepsilon\) gilt:

\[t_0 = 0, \qquad a_{r_k} = t_{r_{k-1}} + D_{r_{k-1},\,r_k}\]

Befunde

Alle Zahlen stammen aus der Benchmark-Auswertung der README (auch im Tab „Vergleich“ der Demo). Sie gelten für zufällige Instanzen mit Kapazität 35: 15 Instanzen ohne und 9 mit Zeitfenstern. Alle fünf Methoden werden mit derselben Bewertungsfunktion auf demselben Netz verglichen, die vier eigenen nach derselben lokalen Suche (2-opt + Or-opt). Die Prozentwerte sind der durchschnittliche Abstand zu OR-Tools, in Klammern der kleinste und größte Wert über die Instanzen. Instanzgrößen, Fahrzeugzahlen und Zufalls-Seeds der Instanzen nennt die README nicht.

Frage	Befund
Sweep, ohne Zeitfenster	Abstand zu OR-Tools +9,5 % (−0,0 % bis +29,1 %), Rechenzeit ~2 ms, beste Lösung in 5 von 15 Instanzen.
Savings, ohne Zeitfenster	+1,2 % (−0,2 % bis +5,0 %), ~1 ms, beste Lösung in 8 von 15 Instanzen.
Beam Search, ohne Zeitfenster	+0,2 % (−0,2 % bis +2,9 %), ~340 ms, beste Lösung in 13 von 15 Instanzen.
Genetischer Algorithmus, ohne Zeitfenster	+0,3 % (−0,2 % bis +2,9 %), ~450 ms, beste Lösung in 12 von 15 Instanzen.
OR-Tools, ohne Zeitfenster	Referenz, ~3 s, beste Lösung in 14 von 15 Instanzen. Die Spalte „beste Lösung“ summiert sich auf mehr als 15, weil ein Gleichstand für jede beteiligte Methode zählt.
Beitrag der Nachbearbeitung	Vor Einführung von Or-opt (nur 2-opt) lag Sweep im Schnitt 37 % hinter OR-Tools, in der Tabelle oben mit Or-opt +9,5 %. Der Wert 37 % stammt aus einem früheren Stand der Demo; die README nennt dazu weder Instanzzahl noch Kapazität. Die beiden Werte sind deshalb nicht streng vergleichbar.
Zeitfenster	Summe der Verletzungen über 9 von 9 Testfälle (Kapazität 35): Sweep 30, Savings 33, Beam Search 31, genetischer Algorithmus 27, OR-Tools 53. OR-Tools ist zeitlimitiert und nicht bei jedem Lauf bit-genau reproduzierbar. Nach der Korrektur des Modells (früheste Ankunft als Untergrenze) sank die Zahl von 79 auf etwa 54; weder höhere Strafgewichtung noch längeres Zeitlimit änderten das auf den schwierigsten Instanzen.
Rechenzeit insgesamt	Bei 30 Stopps, 5 Fahrzeugen, asymmetrischem Netz und Zeitfenstern läuft laut README ein kompletter Rerun aller vier eigenen Heuristiken samt lokaler Suche in der Regel unter 3,5 Sekunden.
Ersparnis gegenüber der Eingabereihenfolge	Die App berechnet sie für das jeweils gewählte Szenario. Die README enthält dazu keine Messreihe, deshalb steht hier keine Zahl.

Grenzen

• Abstand zu OR-Tools ist kein Abstand zum Optimum: OR-Tools läuft mit Zeitlimit und ohne Optimalitätsgarantie. Ein Wert von −0,2 % heißt nur, dass eine eigene Methode bei einer Instanz besser war als OR-Tools in dieser Zeit.
• Kleine Stichprobe: 15 bzw. 9 zufällige Instanzen. Beam Search und genetischer Algorithmus haben dieselbe Spanne (−0,2 % bis +2,9 %), ihr Unterschied im Mittel (+0,2 % gegen +0,3 %) ist klein; die README folgert selbst: kein Verfahren gewinnt universell.
• Zeitfenster-Befund: Dass OR-Tools dort schlechter abschneidet, gilt für diese neun Testfälle und dieses Modell mit weich modellierten Zeitfenstern. Die Erklärung (Guided Local Search zielt primär auf Distanz) ist in der README als plausibel, nicht als bewiesen genannt.
• Vergleichsbasis: Die Eingabereihenfolge ist keine Planung, wie sie ein Disponent macht. Der ausgewiesene Gewinn sagt nichts über den Gewinn gegenüber einer guten manuellen Planung.
• Überladung möglich: Die eigenen Heuristiken überladen bei zu knapper Fahrzeugzahl ein Fahrzeug still und warnen nur, während OR-Tools in diesem Fall keine Lösung liefert. Bei unlösbaren Eingaben wird die nach der lexikografischen Zielfunktion beste Lösung gezeigt.
• Nicht abgebildet: mehrere Depots, Fahrerarbeitszeiten, dynamische Aufträge, Pickup and Delivery und echtes Kartenmaterial. Parameter wie Geschwindigkeit, Kosten je km und CO₂ je km sind Annahmen, keine Messwerte.

Quellen

• Clarke, G., Wright, J. W. (1964): Savings-Algorithmus für die Tourenplanung.
• Croes, G. A. (1958): 2-opt. Or, I. (1976): Or-opt.
• Voudouris, C., Tsang, E. (1999): Guided Local Search, die Metaheuristik in OR-Tools.
• Lemons, N., Linares López, C., Holte, R. C., Ruml, W. (2022): Beam Search: Faster and Monotonic (ICAPS).
• Prins, C. (2004): Split-Verfahren für genetische Algorithmen in der Tourenplanung.
• Garey, M. R., Johnson, D. S. (1979): Computers and Intractability. Toth, P., Vigo, D. (2014): Vehicle Routing: Problems, Methods, and Applications.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/vrp-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus README und Quelltext der Demo.