Tourenbildung: eine Reihenfolge, optimal zerlegt erklärt
Stellen Sie sich vor: Ein Disponent hat eine Liste von Kunden und mehrere Fahrzeuge, die jeweils nur begrenzt laden können. Er schreibt zuerst alle Kunden in eine einzige lange Reihenfolge, so, als fahre ein Fahrzeug sie nacheinander ab. Reicht es, diese eine Reihenfolge gut zu wählen? Und wo schneidet man sie danach in einzelne Fahrzeugtouren?
Diese lange Reihenfolge heißt hier Riesentour. Der Split ist das Verfahren, das sie in Fahrzeugtouren zerlegt: Es sucht die billigsten Schnittstellen. Die Antwort lautet ja, belegt durch Nachzählen bis 9 Kunden: Unter allen Reihenfolgen liegt eine, deren Zerlegung durch den Split die beste Lösung ist. Schwer ist nur, sie zu finden. Die Leitfrage lautet deshalb: Wie findet man sie, und wann sind andere Wege zu Touren besser?
Fünfzehn Stücke in drei Gruppen. Die erste bleibt bei der Reihenfolge: Nachzählen aller Reihenfolgen, Verfahren, die gute bauen, und der Vergleich mit dem einfachen Füllen, bis ein Fahrzeug voll ist. Die zweite fragt, was andere Wege leisten: Einzelfahrten zusammenlegen, wo am meisten Weg gespart wird, Kunden nach dem Winkel um das Depot sortieren, Pläne Zug um Zug verbessern oder durch Kreuzen von Kundenfolgen suchen; dazu Zeitfenster, Abholen und Liefern und Straßen statt Kunden, wie bei einem Postboten. Die dritte handelt vom Tag: Aufträge treffen erst nach und nach ein, und am Ende steht die Frage, welches Verfahren bei wie viel Rechenzeit passt. Die Erklärseite zur Riesentour erzählt die Grundidee ohne Formeln; neue Aufträge und Warten oder Fahren fragen, wie ein Plan Aufträge ruhig aufnimmt und wann ein beladener Wagen noch stehen bleiben sollte.
Was diese Linie ist und was nicht: Alle Zahlen sind eigene Messungen an erfundenen Beispielen mit bis zu 100 Kunden, meist mit einem Lauf je Beispiel, keine Aussage über echte Fälle. Verglichen wird bis 12 Kunden mit dem exakten Optimum, darüber mit einem fertigen Fachprogramm namens PyVRP, das nicht beweist, dass sein Ergebnis das beste ist. Das Nachzählen aller Reihenfolgen gelingt nur bis 9 Kunden.
In short: Covers vehicle routing built from one giant tour of all customers that a shortest path splits optimally into routes. Compares savings, sweep, insertion and genetic search, adds time windows, pickup and delivery, arc routing and arriving orders, and ends with choosing a method by time and gap.
Hintergrund zum Thema: Tourenplanung optimieren · Nahverkehr und Fernverkehr.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Riesentour und Split verständlich erklärt
Warum man Lieferfahrten nicht einzeln suchen muss, sondern eine einzige Kundenliste an den richtigen Stellen durchschneiden kann, wie man die besten Schnitte ohne Probieren findet und warum die kürzeste Rundreise als Liste oft enttäuscht: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Neue Aufträge, ruhiger Plan verständlich erklärt
Was passiert mit dem Plan der Fahrer, wenn morgens noch Aufträge eintreffen? Warum das einfache Einfügen den Plan verlängert, die komplette Neuplanung ihn durcheinanderwirbelt und ein dritter Weg fast so viel gewinnt, ohne viel zu ändern: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell und Messwerten.
Warten oder fahren verständlich erklärt
Ein Wagen steht beladen bereit, und es könnte noch ein Auftrag kommen: sofort losfahren oder warten? Und welche Aufträge nimmt man an, wenn jeder Umweg kostet? Erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Von der Reihenfolge zur Wahl: bauen, zerlegen, verändern, suchen, fortschreiben
Die Wurzel ist die Frage, ob eine Reihenfolge der Kunden genügt. Von dort verzweigt die Linie in vier Richtungen: Reihenfolgen bauen und zerlegen (der Strang bis zu den Savings-Varianten und dem Sweep), die Aufgabe verändern (Zeitfenster, Paare, Kanten), die Reihenfolge suchen und die Aufträge im Lauf des Tages fortschreiben.
Im Strang der Zeitfenster und der Fortschreibung kommt die Zeit dazu. Die Verfahrenswahl am Ende sammelt die Verfahren der Linie ein und stellt sie bei Rechenzeit und Abstand zum Besten nebeneinander.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: der Dijkstra-Algorithmus aus den kürzesten Wegen, VRP-Nachbarschaften aus den Trajektorien-Metaheuristiken, der Memetische Algorithmus aus den Populations-Metaheuristiken, die Euler-Tour aus den Graphen und Netzwerken, die Online-Allokation aus den Online-Algorithmen und die Verfahrenswahl beim Anordnen.
Verwandt in anderen Linien
- Trajektorien-Metaheuristiken — Die VRP-Nachbarschaften-Demo prüft Verschieben, Tauschen und 2-opt an mehreren Routen mit Kapazität; Start gegen Nachbarschaft fragt dazu, ob der Startplan oder die Nachbarschaft zählt, wenn der Start aus Savings oder Einfügen nach Split kommt.
- Populations-Metaheuristiken — Der Memetische Algorithmus kreuzt Reihenfolgen einer Lieferroute und poliert sie lokal; Riesentour suchen stellt dieselbe Idee an einer Tour mit mehreren Fahrzeugen neben einen Algorithmus, der die Routen direkt darstellt, und lässt den Split die Folgen bewerten.
- Online-Algorithmen — Die Online-Allokation nimmt nacheinander eintreffende Buchungen an oder lehnt sie ab, ohne die Zukunft zu kennen; Warten oder Fahren stellt dieselbe Frage für Aufträge mit Lieferfrist, die auf einem Tourenplan Platz brauchen, und fragt zusätzlich, wann die Fahrzeuge losfahren.
- Kürzeste Wege — Die Dijkstra-Demo sucht kürzeste Wege im Netz; Riesentour und Split sucht einen kürzesten Weg in einem Hilfsgraphen ohne Kreise, dessen Bögen Routen sind, und zerlegt so jede Kundenreihenfolge optimal.
- Graphen und Netzwerke — Die Euler-Tour-Demo fährt jede Kante genau einmal; Bogenrouting mit Kapazität fragt, was geschieht, wenn ein Fahrzeug nicht alle Kanten in einer Fahrt schafft: Die Pflichtkanten werden in einer Folge mit Richtung gebildet und zerlegt.
- Anordnen: relaxieren und runden — Die Verfahrenswahl beim Anordnen stellt Beweisen und Finden gegeneinander und legt die Regel vor der Messung fest; Tourenbildung: Verfahrenswahl nutzt dasselbe Muster für Touren und legt Zeit gegen Abstand zum Besten.
- Ressourcenwege und Spaltenerzeugung — Die Linie Ressourcenwege und Spaltenerzeugung sucht das Pricing der Spaltenerzeugung als kürzesten Weg mit Zeit- und Lastgrenzen: Zeitfenster und Warten fragt, wie die Fensterbreite die Zahl der Labels steuert, die ein Label-Verfahren erzeugt, während Zeitfenster und Split hier fragt, ob der Hilfsgraph des Splits mit den Fenstern wächst.
Riesentour und Split: Reicht eine Reihenfolge der Kunden?
Verfolgen Sie, wie eine Reihenfolge aller Kunden genügt, um Touren zu bilden: Der Split zerlegt sie auf einem kleinen Graphen per kürzestem Weg optimal in Routen, und das Optimum liegt unter diesen Reihenfolgen. Die Demo zählt alle Reihenfolgen durch und zeigt, wie selten sie das Optimum treffen und warum die kürzeste Rundreise oft eine schlechte Reihenfolge ist. Der Haken: Die Aussagen gelten nur für bis zu 9 Kunden.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Riesentouren erzeugen: Nach Länge oder nach Split?
Sehen Sie, wie sich gute Reihenfolgen bauen lassen: Sechs Verfahren, vom Zufall bis zum Einfügen, bauen Riesentouren, gemessen an der Länge der Rundreise oder an den Kosten des Splits. Die Demo geht ein Verfahren Schritt für Schritt durch und vergleicht alle mit dem Optimum. Überraschend: Die bessere Riesentour hat oft die längere Rundreise. Der Haken: Ob die freie Stelle oder die Kundenreihenfolge den Unterschied macht, wurde nicht getrennt gemessen.
Demo starten →Split gegen Füllen bis voll: Kosten und Fahrzeuge
Vergleichen Sie, wie sich dieselbe Reihenfolge zerlegen lässt: „Füllen bis voll“ beginnt eine neue Route, sobald der nächste Kunde nicht mehr passt, der Split schneidet dort, wo es billig ist. Die Demo zeigt auch die Wirkung der Leserichtung und einer Flottengrenze, also einer Höchstzahl an Fahrzeugen. Der Haken: Die Leserichtung ändert nur „Füllen bis voll“, und bei 12 Kunden bindet die Grenze mit einer Route mehr in keiner gemessenen Kombination.
Demo starten →Savings gegen Riesentour mit Split
Sehen Sie, wie Savings arbeitet: Jeder Kunde fährt zuerst allein, dann werden Routen zusammengelegt, wo es am meisten Weg spart, solange das Fahrzeug reicht. Die Demo stellt diesen Plan neben den Split. Der Haken: Bei bis zu 12 Kunden liegen die Mediane nah beieinander, erst bei 100 Kunden liegt Savings im Median vorn, und das nur gegen einfache Erzeuger ohne Suche nach der besten Reihenfolge.
Demo starten →Savings variieren: Formparameter, Reihenfolge, Mehrfachrechnen
Sehen Sie, was die Stellschrauben von Savings bewirken: Der Formparameter λ gewichtet die Ersparnis anders, die Demo legt die Kosten über ein Raster von λ-Werten, stellt die parallele und die sequentielle Fassung nebeneinander und kippt die Reihenfolge der Liste mit Rauschen. Das beste von neun λ-Werten schlägt einen einzelnen Lauf. Der Haken: Ein einzelnes λ kann einen Plan kippen, auf der Handinstanz schon ab 1,7.
Demo starten →Sweep und Cluster-first: Wo scheitert es?
Verfolgen Sie, wie der Sweep die Kunden nach dem Winkel um das Depot sortiert, bei einem Startkunden aufschneidet und je Gruppe eine Rundreise bildet. Die Demo zerlegt den Verlust in Gruppenbildung, Schnitt und Reihenfolge und vergleicht mit Savings bei gleicher Rundreise. Der Haken: Der Start entscheidet viel, und bei kurzen Routen, enger Kapazität oder einem Depot in der Ecke bleibt der Sweep zurück.
Demo starten →Start gegen Nachbarschaft: Was zählt bei der Lokalsuche?
Sehen Sie, ob bei der Lokalsuche der Startplan oder die Nachbarschaft zählt: Die Demo startet aus Zufallsplänen und aus Savings oder Einfügen und schaltet 2-opt, Verschieben und Tauschen einzeln zu. Ein schlechter Start braucht die reiche Nachbarschaft, ein guter Start kaum. Der Haken: In diesen Messungen zählt der Start deutlich, bei zwölf Kunden weniger, und die Lokalsuche ist bewusst einfach gehalten.
Demo starten →Zeitfenster und Split: Schrumpft der Hilfsgraph?
Fragen Sie, ob der Hilfsgraph des Splits mit Zeitfenstern wächst: Die Demo zeigt, welche Bögen fehlen und warum, und dass er mit engeren Fenstern schrumpft. Sie zeigt auch, warum die Richtung der Riesentour zählt und was späteres Losfahren bringt. Der Haken: Die kürzeste Rundreise ist unter engen Fenstern eine schlechte Riesentour, und nach dem Fensterende zu sortieren hilft kaum.
Demo starten →Solomon gegen Split: Welche Klassen kippen?
Sehen Sie, welche Instanzklassen kippen, wenn erst die Fahrzeuge zählen: Solomons Einfügeverfahren läuft Schritt für Schritt, sechs Klassen von gruppierten bis zufälligen Kunden werden nach Strecke und nach Fahrzeugzahl gewertet. Bei zufälliger Lage kippt der Sieger oft. Der Haken: Wer Fahrzeuge spart, zahlt Strecke, und bei 100 Kunden stehen nur vier Instanzen je Klasse hinter den Zahlen.
Demo starten →Abholen und Liefern: Riesentour über Aufträge
Prüfen Sie, ob eine Reihenfolge auch bei Abholen und Liefern genügt: Eine Folge einzelner Halte lässt sich meist nicht in zulässige Routen zerlegen, eine Folge von Aufträgen dagegen immer, wenn jeder Block mit der besten Route seiner Aufträge bewertet wird. Die Demo zählt alle Folgen durch. Der Haken: Das gilt mit einer Streckengrenze und für höchstens acht Aufträge, ohne Grenze ist ein einziger Weg optimal.
Demo starten →Riesentour suchen: Genetische Suche mit Split
Verfolgen Sie, ob es mehr bringt, die Reihenfolge zu suchen: Ein genetischer Algorithmus kreuzt Kundenfolgen, der Split bewertet sie, gegen einen Algorithmus, der die Routen direkt darstellt, mit und ohne Lokalsuche. Die Demo zeigt eine Kreuzung von Hand und die Lokalsuche Zug für Zug. Der Haken: Die Lokalsuche entscheidet mehr als die Kodierung, und ohne sie liegt je nach Größe mal die eine, mal die andere vorn.
Demo starten →Bogenrouting mit Kapazität: Split auf Kanten
Sehen Sie, was die Kapazität am Postboten ändert: Pflichtkanten werden in einer Folge mit Richtung gebildet und per Split auf Routen verteilt. Die Demo zählt alle Folgen durch und zeigt, dass die Richtung gute Folgen etwa hundertmal seltener macht, solange die Route je Block nicht neu geordnet wird. Der Haken: Es sind höchstens zwölf Pflichtkanten auf eigenen kleinen Graphen.
Demo starten →Neue Aufträge: Neu-Split oder Einfügen
Verfolgen Sie, wie ein Plan bei eintreffenden Aufträgen fortgeschrieben wird: Der neue Auftrag kommt in die Riesentour, und der Split verschiebt nur die Schnittstellen zwischen den Routen. Die Demo zählt, wie viele Stopps dabei ihren Vorgänger wechseln. Neu-Split holt gut die Hälfte des Gewinns einer Neuplanung mit einem Bruchteil der Änderungen. Der Haken: Die Aufträge treffen vor der Abfahrt ein, die Wartezeit des Sammelns wird nicht bewertet.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Warten oder Fahren, Annehmen oder Ablehnen
Sehen Sie, wann Warten sich lohnt: Aufträge treffen über den Tag ein, jeder mit Lieferfrist, und wenige Fahrzeuge fahren erst los, wenn eine geplante Route nicht länger warten darf. Das spart Strecke, solange die Flotte nicht ausgelastet ist, und eine Annahmeschwelle nützt vor allem beim Warten. Der Haken: Die Fahrzeiten sind fest, und bei dichtem Strom verschwindet der Vorteil.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Tourenbildung: Verfahrenswahl
Fragen Sie, welches Verfahren der Linie bei welchem Budget das richtige ist: Die Demo legt Rechenzeit gegen den Abstand zum Besten und zeigt die Treppe aus Savings, bestem Savings, Savings mit Rundreise und genetischer Suche. Sie fragt auch, wie gut die Referenz selbst ist. Der Haken: Die Zeiten stammen aus Python auf einer Maschine, und die Instanzen sind eigene, nicht die der Literatur.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle fünfzehn Stücke: Er fragt danach, ob Kunden, Paare oder Kanten bedient werden, ob es Fristen gibt, ob die Aufträge schon feststehen und was man sehen möchte. Die Blätter sind die Demos der Linie.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Die Größen, bei denen die Aussagen gelten, stehen in den Demos: Aufzählung bis neun Kunden, Messungen bis 100.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
SAT und Constraint Programming
Wie merkt sich ein Löser, warum eine Sackgasse eine war? Sechzehn Stücke vom Konfliktlernen über Beweise, Zähler und Symmetrie bis zu Mengen- und Maschinenschlüssen, lokaler Suche und der Wahl der Modellwelt.
Packen: Reihenfolge und Platzierungsregel
Wie packt man Pakete, Rechtecke und Quader in wenige Behälter, und wie nah am Besten liegt eine einfache Regel? Vierzehn Stücke von der Sortierung bis zur Verfahrenswahl.
Umstauen: Untergrenze und Suche
Wie viele Container müssen mindestens umgestapelt werden, und wann lohnt sich die Suche nach dem Besten? Fünfzehn Stücke von der einfachen Regel bis zur Verfahrenswahl.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.
Takt und Periodizität
Ein Fahrplan, der sich jede Stunde wiederholt: vier Stücke von den Zeitabständen über die Wartezeit der Umsteiger und die Kreisgleichungen bis zum Betriebstag.