Gewinn-Touren verständlich erklärt

Ein Fahrer hat mehr mögliche Kunden, als er an einem Tag schaffen kann. Jeder Kunde bringt etwas ein, aber nicht jeder passt noch in die Zeit. Welche nimmt man mit, und in welcher Reihenfolge? Diese Seite zeigt, wo die Auswahl entsteht und wann eine einfache Regel genügt.

Zuletzt aktualisiert: 11. November 2026

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

Mehr Kunden als Zeit

Stellen Sie sich einen Außendienstfahrer vor. Morgens liegen mehr Kundentermine an, als er bis zum Abend schafft. Jeder Kunde ist unterschiedlich viel wert: ein großer Auftrag, ein kleiner Auftrag, ein Besuch, der nur ein bisschen Umsatz bringt. Und jeder Kunde kostet Zeit, nicht nur beim Besuch, sondern auch beim Hinfahren. Den Weg, den ein Fahrer an einem Tag fährt, nennen wir hier eine Tour.

Damit stellt sich nicht nur die bekannte Frage der Reihenfolge, sondern vorher eine zweite: Wen besucht er überhaupt? Beides hängt zusammen. Ein wertvoller Kunde, der weit weg wohnt, kann den Platz von zwei nahen Kunden kosten, die zusammen mehr einbringen. Erst die Auswahl macht die Route, und erst die Route zeigt, ob die Auswahl passt.

Um nachzurechnen, wie gut verschiedene Vorgehen abschneiden, nutzt diese Seite ein vereinfachtes Rechenbild mit zufällig erzeugten Kunden und einer festen Zeit je Fahrt (in der Fachsprache heißt das Modell). Dazu gehört eine Demo, ein Programm zum Ausprobieren, das dieselben Rechnungen live zeigt. Die Aussagen in diesem Teil beschreiben das Rechenbild, nicht einen echten Betrieb.

Fünf Wege, einen Plan zu finden

Das Beste im Verhältnis zur Zeit. Man nimmt immer den Kunden, der gemessen an der zusätzlichen Fahrzeit am meisten einbringt, und baut ihn an der günstigsten Stelle in die Tour ein. Das geht schnell und ist leicht zu verstehen. Eine noch einfachere Regel, den wertvollsten Kunden zuerst, liegt in der Demo weiter zurück (Zahlen im Fachteil).

Nachbessern. Man verbessert den Plan in kleinen Schritten: Besuche in der Tour umstellen, einen weiteren Kunden in freie Zeit einschieben, einen Kunden im Plan gegen einen wertvolleren außerhalb des Plans tauschen. Das ist wie ein Disponent, der abends noch einmal über den Plan schaut.

Wegnehmen und neu einsetzen. Man nimmt ein paar Kunden aus dem Plan heraus, setzt sie mit etwas Zufall wieder ein und bessert danach nach. Das wiederholt man oft und behält das Beste. Beispiel: Der weit entfernte Kunde wird herausgenommen, und an seiner Stelle werden zwei nahe eingesetzt. Der Zufall sorgt dafür, dass nicht jedes Mal dasselbe probiert wird. So entdeckt man Pläne, auf die schrittweises Nachbessern nicht kommt.

Ein fertiger Löser. Ein Löser ist ein fertiges Rechenprogramm für solche Aufgaben; OR-Tools ist ein frei verfügbares Beispiel. Er lässt sich einstellen, und wie gut er in der Demo abschneidet, hängt von der Einstellung ab.

Beweisen. Ein exaktes Verfahren rechnet so lange, bis sicher ist, dass es keinen besseren Plan gibt. Das gelingt in der Demo nur bei kleinen Aufgaben, etwa wenn die Zeit knapp ist und jede Tour nur wenige Kunden hat.

Wo entsteht die Auswahl?

Die Reihenfolge allein verändert nie, wer im Plan ist. Man kann die Besuche einer Tour noch so geschickt umstellen: Es bleiben dieselben Kunden. Die Auswahl ändert sich erst, wenn man einen Kunden einschiebt oder austauscht, und in der Demo vor allem dann, wenn man Kunden herausnimmt und neu einsetzt.

Das ist die zentrale Beobachtung der Demo: Wer nur die Wege kürzer macht, lässt Wert liegen. Der Gewinn kommt davon, dass man andere Kunden wählt.

Wann reicht eine einfache Regel?

Das hängt vom Fall ab, und die Demo zählt es nach, statt es zu behaupten. Ist die Zeit knapp und gibt es nur wenige machbare Kunden, liegen alle Verfahren dicht beieinander, und eine einfache Regel genügt. Je mehr Kunden eine Tour in der Demo enthält, desto mehr lassen einfache Regeln liegen (Zahlen im Fachteil). Besonders groß ist der Abstand in der Demo, wenn gerade die weit entfernten Kunden die wertvollen sind.

Bei gleichen Werten fällt eine andere Eigenschaft auf: Dann zählt nur noch, wie viele Kunden hineinpassen, und ein Löser in Standardeinstellung ist in der Demo fast so gut wie die eigene Suche. Eine Einstellung, die bei ungleichen Werten hilft (etwa eine Strafe fürs Weglassen eines Kunden, die auf die üblichen Werte zugeschnitten ist), kann bei gleichen Werten schaden.

Woran merken Sie es im Betrieb? Drei Fragen: Haben Sie mehr Kunden als Zeit? Sind die Werte der Kunden sehr verschieden? Liegen die wertvollen Kunden weit entfernt? Je öfter die Antwort ja lautet, desto eher lohnt der Blick auf die Auswahl, nicht nur auf die Route. Ein Zeichen im Alltag: Ein erfahrener Disponent verbessert einen maschinell erzeugten Plan regelmäßig mit einem einzigen Tausch.

Wie ernst ist das Modell zu nehmen?

Stark vereinfacht: gleichmäßig verteilte Kunden, feste Fahrzeiten, keine Zeitfenster, Werte frei gewählt. Die Reihenfolge der Verfahren und die Frage, wo die Auswahl entsteht, lassen sich übertragen; die genauen Abstände nicht.

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

Team Orienteering (Prize-Collecting-Tourenplanung ohne Zeitfenster): Ein Depot in der Mitte eines 100 × 100-Gebiets, n Kunden (15, 25, 40 oder 60) gleichverteilt, K Fahrzeuge (1 bis 4) mit je einer Tour. Fahrzeit = aufgerundet 1,2 × Distanz (die Dreiecksungleichung gilt), Service 6 Minuten je Kunde. Das Zeitbudget je Tour ist ein Anteil f (0,2 bis 1,0) eines Rundreise-Richtwerts über alle Kunden (Nächster Nachbar plus 2-opt, einschließlich Service), geteilt durch K. Die Messreihe enthält außerdem n = 20 sowie die Budgetanteile 0,1 und 0,7. Prämien: gleich (10), gestreut (lognormal, Mittel 60, Streuung 0,6) oder „fern = wertvoll“ (20 + 1,2 × Abstand zum Depot, mit etwas Rauschen).

Verglichen werden die Verhältnisregel „Prämie je Zusatzzeit“, die Regel „höchste Prämie zuerst“, eine Lokalsuche in Stufen (Routenzüge, Einfügen, Ersetzen), eine eigene Suche (ILS: Kunden entfernen, verrauscht wieder einfügen, Lokalsuche), OR-Tools in zwei Einstellungen und das exakte Verfahren CP-SAT. „Bester bekannter Wert“ ist das Maximum aller Verfahren auf der Instanz (bei bewiesenem Optimum das Optimum); „Anteil am Besten“ ist Prämie ÷ bester Wert, „Punkte“ sind Prozentpunkte dieses Anteils.

Die Formeln

Gesucht ist die Auswahl $y_i$ und die Bogenwahl $x_{ijk}$ mit der größten Prämiensumme:

\[\max \sum_{i} p_i \, y_i\]

Jeder Kunde wird höchstens einmal bedient, und zwar genau dann, wenn irgendein Fahrzeug ihn anfährt:

\[\sum_{k}\sum_{j} x_{ijk} = y_i \quad (i = 1, \dots, n)\]

Jede Tour (Fahrt und Service, Rückkehr eingeschlossen) darf das Zeitbudget nicht überschreiten:

\[\sum_{(i,j)} t_{ij}\, x_{ijk} + s \sum_{i=1}^{n}\sum_{j} x_{ijk} \le T \quad (k = 1, \dots, K)\]

Dazu gehören Binärbedingungen für $x$ und $y$, Flusserhaltung je Fahrzeug und Kunde (Zufluss gleich Abfluss), höchstens ein Abgang je Fahrzeug aus dem Depot mit Rückkehr dorthin und ein Teiltourverbot (keine Kreise ohne Depot). $T$ ist der Anteil $f$ eines Rundreise-Richtwerts $R$ über alle Kunden, geteilt durch $K$: $T = f \cdot R / K$; der Service $s$ wird je angefahrenem Kunden gerechnet, nicht am Depot. CP-SAT bildet das als Mehrfach-Kreis mit Selbstschleife für nicht bediente Kunden ab.

Befunde

Alle Zahlen stammen aus der Vorab-Messreihe der Demo (meist Zufalls-Seeds 0 bis 29, 30 Instanzen je Zelle, Mittel über die Instanzen; ± ist der Standardfehler); abweichende Instanzzahlen und Quellen stehen in der jeweiligen Zeile.

Frage	Befund
Wie weit liegen die Verfahren auseinander? (25 Kunden, 2 Fahrzeuge, Budgetanteil 0,5, gestreute Prämien)	Anteil am besten bekannten Wert: höchste Prämie zuerst 87,4 %, Verhältnis-Greedy 92,7 %, plus Lokalsuche 96,8 %, OR-Tools (Standard) 95,7 %, OR-Tools (abgestimmt, zeitgleich) 98,5 %, eigene Suche (ILS) 99,9 %
Gibt es einen Kipppunkt über dem Budget? (25 Kunden, 2 Fahrzeuge, gestreut, Budgetanteil 0,3 bis 1,0, 7 Zellen)	Oberhalb von Budgetanteil 0,3 nein: der Rückstand des Verhältnis-Greedy liegt in diesen 7 Zellen zwischen 5,2 und 8,1 Punkten; bei Budgetanteil 0,2 sind es 2,9 Punkte, bei 0,1 sind alle Instanzen trivial (der Anstieg liegt davor, zwischen 0,2 und 0,4)
Wo entsteht die Auswahl? (25 Kunden, 2 Fahrzeuge, Budgetanteil 0,4, gestreut)	Routenzüge allein ändern die Kundenmenge in 30 von 30 Instanzen nicht (über alle 7 Ablationszellen, das sind 25 Kunden mit Budgetanteil 0,4 und 0,7 in drei Prämienarten sowie 40 Kunden: 210 von 210) und sparen 1,9 % Fahrzeit; Einfügen +1,0 ± 0,6 Punkte, Ersetzen weitere +2,1 ± 0,8 (je gegenüber der Vorstufe; Routenzüge ändern die Prämie nicht); im ILS bringt Ersetzen +0,1 ± 0,1 Punkte gegenüber dem ILS ohne Ersetzen, Einfügen im Lokalsuchschritt +2,4 ± 0,6 gegenüber dem ILS nur mit Routenzügen
Wann reicht Greedy mit Lokalsuche? (19 Zellen des Haupt-Sweeps)	In 3 Zellen höchstens 2 Punkte hinter dem Besten, in 11 Zellen zwischen 2 und 6 Punkten, in 5 Zellen mehr als 6 Punkte (Schwellen gesetzt, nicht hergeleitet); die 5 Zellen: „fern = wertvoll“ (2), gleiche Prämien (2), 60 Kunden; die 3 Zellen mit höchstens 2 Punkten sind knappe Budgets, darunter die triviale Zelle mit Budgetanteil 0,1; die 19 Zellen sind ausgewählte Szenarien, kein Querschnitt
Wie weit liegt OR-Tools hinter dem ILS? (Budgetanteil 0,5, gestreut, 2 Fahrzeuge, n = 20 / 40 / 60)	abgestimmt und zeitgleich +2,3 ± 0,7 / +3,7 ± 0,7 / +6,5 ± 0,9 Punkte; mit der Standard-Einstellung bei 1 Fahrzeug, gestreuten Prämien und 40 bis 60 Kunden +13,4 bis +14,8 Punkte (3 Zellen: 40 Kunden bei Budgetanteil 0,4 und 0,5, 60 Kunden bei 0,5)
Hängt das an der Prämienart? (25 Kunden, 2 Fahrzeuge, Budgetanteil 0,4)	„fern = wertvoll“: ILS − OR-Tools +6,7 ± 1,1 (Standard) bzw. +4,8 ± 0,8 (abgestimmt); gleiche Prämien: +0,3 ± 0,3 (Standard) bzw. +3,9 ± 1,2 (abgestimmt, schlechter als Standard); bei Budgetanteil 0,7: +2,0 (Standard) bzw. +3,4 (abgestimmt)
Wie oft schlägt OR-Tools (abgestimmt, zeitgleich) den ILS? (840 Instanzen der Sweeps)	in 1 von 840 Instanzen strikt besser (mit der Standard-Einstellung in 4 von 840); gleichauf mit dem ILS in 337 von 831 nicht leeren Instanzen (9 Instanzen sind leer, das heißt: kein Kunde erreichbar)
Wie weit liegt der ILS vom Optimum? (1 Fahrzeug, 20 Kunden, Budgetanteil 0,5, 20 Instanzen, exaktes Optimum)	ILS 100,0 % des Optimums (unter dem Optimum in 0 von 20), Verhältnis-Greedy 92,9 % (16 von 20), plus Lokalsuche 94,8 % (14 von 20), OR-Tools (Standard) 87,6 % (17 von 20)
Wie weit beweist CP-SAT? (25 Kunden, 2 Fahrzeuge, gestreut, 30 s, ein Worker)	Optimum bewiesen in 30 / 30 / 23 / 3 / 0 / 0 / 0 / 5 von 30 Instanzen bei Budgetanteil 0,2 / 0,3 / 0,4 / 0,5 / 0,65 / 0,7 / 0,8 / 1,0 (8 Zellen); Schranke bei Budgetanteil 0,5 im Mittel 80 % über dem besten bekannten Wert der nicht bewiesenen Instanzen
Lässt sich der ILS verbessern? (7 Varianten, 5 s, getrennte Instanzen)	keine der 7 Varianten ist im Mittel besser: der jetzige ILS liegt bei 99,92 % des Besten, die beste Variante bei 99,68 %, ein zehnmal längerer Lauf des jetzigen ILS (kein Variantenkandidat) bei 99,97 %; ILS mit 30000 statt 3000 Iterationen findet in 5 von 30 Instanzen mehr (n = 40 und 60)
Wirkt die Abstimmung von OR-Tools? (8 Kandidaten, 5 Zellen mit je 12 Instanzen = 60 Instanzen, Zufalls-Seeds 1000 bis 1011)	gewählt wurde die Einstellung mit 96,48 % des ILS gegen 94,52 % für die Standard-Einstellung (gewählt und bewertet auf denselben Instanzen; die Wirkung zeigt der Vergleich der Spalten in der Messreihe: abgestimmter Rückstand kleiner in 21 von 28 Zellen, größer in 6, gleich in 1)
Wie gut ist der ILS bei kleinem Rechenbudget? (2 Fahrzeuge, Budgetanteil 0,5, gestreut, je 10 Instanzen)	bei 300 Iterationen im Mittel über 10 Instanzen mindestens 99,4 % des besten der drei Läufe mit 300, 1000 und 3000 Iterationen (n = 15, 25, 40, 60; bei n = 60 die schlechteste Instanz 95,1 %), Rechenzeit bei n = 60 im Mittel 2,7 s statt 27,4 s bei 3000 Iterationen

Grenzen

• Keine Zeitfenster, keine Cluster: Orte gleichverteilt, Fahrzeiten deterministisch, eine Tour je Fahrzeug; Prämien und ihr Verhältnis zur Fahrzeit frei gewählt.
• Der ILS ist ein eigenes Verfahren und stellt meist den „besten bekannten Wert“: sein Anteil ist per Konstruktion nahe 100 %. Bewiesen ist das Optimum nur bei kleinen Touren (wenige Kunden je Fahrzeug oder knappes Budget).
• OR-Tools nur in zwei Einstellungen: die Aussagen gelten für diese Einstellungen, nicht für das Verfahren; die abgestimmte Einstellung überträgt sich bei 25 Kunden und 2 Fahrzeugen nicht auf gleiche Prämien.
• Eine Live-Instanz ist kein Beleg; Rechenzeiten stammen vom Entwicklungsrechner, OR-Tools und CP-SAT sind zeitlimitiert und nicht bitgleich reproduzierbar.
• Die Schwellen der Meldung in der Demo (2 und 6 Punkte) sind gesetzt, nicht hergeleitet.

Quellen

• Verfahren, Zahlen und Tests: README und Quelltext des Repos gewinn-touren-demo auf GitHub.
• Die Fachbegriffe Team Orienteering und Prize-Collecting-Tourenplanung sind in der Literatur üblich; die README der Demo nennt dazu keine Quelle.

Literatur nicht nachgeschlagen und nicht aus der README übernommen: sie nennt keine.