Tourenplanung Löser

Pseudocode

Das Tourenplanungsproblem verallgemeinert TSP auf eine Flotte. Der praktische Zugang folgt dem Muster erst gruppieren, dann routen: die Kunden auf die Fahrzeuge aufteilen und anschließend je Fahrzeug ein TSP lösen.

VRP(depot, kunden, anzahlFahrzeuge):
    // Phase 1: Kunden auf Fahrzeuge aufteilen
    gruppen = clustern(kunden, anzahlFahrzeuge)
    // per Winkelsektor, k-Means oder Clarke-Wright-Ersparnis

    // Phase 2: jedes Fahrzeug routen
    für jede Gruppe g:
        route[g] = löseTSP(depot + g)

    // Phase 3: Verbesserung zwischen den Touren
    wiederhole, bis keine Verbesserung mehr:
        versuche, einen Kunden in eine andere Tour zu verschieben
        versuche, Kunden zwischen zwei Touren zu tauschen
        geänderte Touren erneut mit 2-opt optimieren

Phase 3 trennt eine mittelmäßige von einer guten Lösung. Erst gruppieren, dann routen liefert vernünftige Touren, doch die Gruppengrenzen sind meist schlecht gezogen, und einen einzelnen Kunden von einer überlasteten Tour in die Nachbartour zu verschieben spart häufig mehr als jede Nachoptimierung innerhalb einer Tour. Bewegungen zwischen Touren sind daher wesentlich und keine Zierde am Schluss.

Durchgerechnetes Beispiel, Schritt für Schritt

Teile sechs Kunden auf zwei Fahrzeuge von einem einzigen Depot auf und beobachte, warum die Verbesserung zwischen den Touren zählt.

Beispielgraph: Ein Depot in der Mitte und sechs ringsum verteilte Kunden: drei im Norden gruppiert und drei im Süden, wobei einer der nördlichen deutlich näher an der Südgruppe liegt als am Rest seiner eigenen Gruppe.

1. Phase 1, nach Sektor gruppieren. Ein Winkelscan vom Depot aus teilt die Kunden in einen Nord- und einen Südsektor, drei und drei. Das ist ausgewogen und geometrisch naheliegend.
2. Phase 2, jede Gruppe routen. Jedes Fahrzeug löst ein TSP über die eigene Gruppe plus Depot, mit nächstem Nachbarn gefolgt von 2-opt. Beide Touren sind intern sauber und kreuzungsfrei.
3. Das Grenzproblem. Der nördliche Kunde, der eigentlich näher an der Südgruppe liegt, zwingt sein Fahrzeug zu einem langen Umweg. Kein noch so gutes 2-opt innerhalb der Nordtour behebt das, denn das Problem ist nicht die Besuchsreihenfolge, sondern die Gruppenzugehörigkeit.
4. Phase 3, zwischen den Touren verschieben. Diesen Kunden in die Südtour zu verschieben verkürzt die Nordtour stark und verlängert die Südtour nur wenig, die Gesamtdistanz sinkt also. Danach wird auf beide Touren erneut 2-opt angewandt.

Die endgültige Aufteilung ist zahlenmäßig nicht mehr ausgewogen, vier Kunden gegen zwei, und dennoch ist die Gesamtdistanz geringer. Das ist der Kernpunkt beim VRP: nach Geometrie zu gruppieren erzeugt ordentlich aussehende Gruppen, doch das Ziel ist die Gesamtdistanz und nicht die Symmetrie. Jede Implementierung, die nach Gruppieren und Routen aufhört, lässt Verbesserungen liegen, die typischerweise im Bereich von 10 bis 20 Prozent liegen.

Komplexität und woher sie kommt

Zeit: NP-schwer; Heuristiken O(n^2) bis O(n^3) · Speicher: O(n^2)

Das VRP enthält TSP als Sonderfall, mit einem einzigen Fahrzeug und ohne Kapazität, und ist damit unmittelbar NP-schwer. Exakte Aufzählung ist außer bei winzigen Instanzen undenkbar; moderne exakte Verfahren auf Basis von Spaltengenerierung und Branch and Cut lösen Instanzen mit rund 100 Kunden unter erheblichem Aufwand. In Produktion kommen Heuristiken zum Einsatz: die Clarke-Wright-Ersparniskonstruktion ist O(n hoch 2 log n), dominiert vom Sortieren der Ersparnisse, Gruppieren und Routen kostet das Clustern plus ein TSP je Fahrzeug, und die lokale Suche zwischen den Touren kostet O(n hoch 2) je Durchgang. Die Distanzmatrix allein belegt O(n hoch 2), was bei großen Instanzen praktisch die bestimmende Speichergrenze ist.

Wann Flottendisposition (mTSP) passt und wann nicht

Kläre zuerst, welche Nebenbedingungen dein reales Problem hat, denn jede davon führt in eine andere Familie.

Häufige Fehler

• Nach Gruppieren und Routen aufhören. Die Gruppengrenzen sind fast nie optimal, und die Verbesserung zwischen den Touren holt typischerweise 10 bis 20 Prozent der Distanz zurück. Phase 3 wegzulassen ist der häufigste und zugleich teuerste Fehler.
• Auf ausgewogenen Touren bestehen. Die Kunden gleichmäßig auf die Fahrzeuge zu verteilen wirkt ordentlich, minimiert aber selten die Distanz. Ist das Ziel die Gesamtkosten, lasse die Tourgrößen ungleich ausfallen; ist das Ziel Fairness zwischen Fahrern, sage das ausdrücklich und modelliere es als Nebenbedingung.
• Luftlinie über einem Straßennetz verwenden. Die euklidische Distanz ignoriert Einbahnstraßen, Flüsse und Autobahnen. In Städten können reale Fahrzeiten die Luftlinie um mehr als das Doppelte übersteigen, und über der falschen Metrik optimierte Touren sind über der echten nicht optimal.
• Die Fahrzeugzahl als fest behandeln, obwohl sie es nicht ist. Manchmal ist ein Fahrzeug weniger mit längeren Touren billiger als ein weiterer Fahrer samt Fahrzeug. Ist die Flottengröße eine Entscheidung und keine Vorgabe, nimm sie ins Modell auf, statt sie aus Gewohnheit festzuschreiben.
• Servicezeiten ignorieren. Die Entladezeit je Stopp dominiert bei dichten städtischen Zustellungen häufig über die Fahrzeit. Nur die gefahrene Distanz zu optimieren erzeugt Touren, die nicht in den Arbeitstag passen.

Häufig gestellte Fragen

Was ist das Tourenplanungsproblem?

Das VRP sucht die kostengünstigste Menge von Touren für eine Flotte, die von einem Depot ausfährt und eine Menge von Kunden bedienen muss, wobei jedes Fahrzeug zum Depot zurückkehrt. Es verallgemeinert das Problem des Handlungsreisenden auf mehrere Fahrzeuge und ist die Grundlage von Zustellplanung, Abfallsammlung und Warendistribution.

Was ist der Unterschied zwischen TSP und VRP?

Das TSP führt ein einziges Fahrzeug durch alle Städte, ohne weitere Einschränkung als jede einmal zu besuchen. Das VRP führt eine Flotte von einem Depot aus und entscheidet zusätzlich, welche Kunden welchem Fahrzeug zugeordnet werden. Das TSP ist der Sonderfall des VRP mit einem Fahrzeug und unbegrenzter Kapazität.

Wie löst man ein VRP in der Praxis?

Mit dem Muster erst gruppieren, dann routen: die Kunden per Winkelsektor, k-Means oder Clarke-Wright-Ersparnis auf die Fahrzeuge aufteilen, für jedes Fahrzeug ein TSP lösen und anschließend durch Verschieben und Tauschen von Kunden zwischen den Touren verbessern. Diese letzte Phase ist wesentlich, da die Gruppengrenzen selten optimal sind.

Warum ist das VRP schwierig?

Weil es das TSP als Sonderfall enthält und obendrein die Zuordnungsentscheidung hinzufügt. Man muss gleichzeitig entscheiden, welche Kunden zusammengehören und in welcher Reihenfolge sie besucht werden, und beide Entscheidungen wirken aufeinander. Es ist NP-schwer, und heutige exakte Verfahren bewältigen unter erheblichem Aufwand die Größenordnung von 100 Kunden.

Sollten die Touren ausgewogen sein?

Nur wenn Fairness zwischen Fahrern ein ausdrückliches Ziel ist. Geht es um Gesamtdistanz oder Gesamtkosten, verschlechtert das Erzwingen gleich großer Touren die Lösung fast immer. Eine ungleiche Aufteilung, die die Gesamtdistanz senkt, ist die richtige Antwort, sofern keine Nebenbedingung etwas anderes verlangt.