TSP-Routenoptimierung
Kürzeste Route finden, die alle Standorte besucht und zum Depot zurückkehrt. Verwendet heuristische Algorithmen (Nächster-Nachbar, Clarke-Wright-Sparverfahren)…
Verwendet heuristische Algorithmen (Nächster-Nachbar, Clarke-Wright-Sparverfahren) zur Lösung des Handlungsreisenden-Problems. Geben Sie Standortkoordinaten ein, um eine optimierte Route zu finden.
Was ist das Problem des Handlungsreisenden (TSP)?
TSP fragt: Was ist die kuerzeste Route, die alle Standorte genau einmal besucht und zum Ausgangspunkt zurueckkehrt? Es ist eines der meistuntersuchten Probleme der kombinatorischen Optimierung.
TSP ist NP-schwer. Praktische Loesungen verwenden Heuristiken: Naechster-Nachbar (schnell, ca. 25% ueber optimal), Clarke-Wright-Sparverfahren und Metaheuristiken wie 2-opt.
TSP findet Anwendung bei Letzte-Meile-Zustellung, Aussendienst, PCB-Bohrung und Lager-Pickpfadoptimierung.
Formula: Ziel: min Σ d(route[i], route[i+1]) Nächster Nachbar: gierig nächsten unbesuchten Standort besuchen Sparverfahren: s(i,j) = d(Depot,i) + d(Depot,j) − d(i,j)
Berechnungsbeispiel
Depot bei (0,0), 4 Stopps bei (3,4), (6,1), (8,5), (2,7). Nächster Nachbar ab Depot: (3,4) d=5,0, dann (2,7) d=3,2, dann (8,5) d=6,3, dann (6,1) d=4,5, Rückkehr d=6,1. Gesamt = 25,04 (die gerundeten Teilstrecken ergeben 25,1). Bei vier Stopps ist das bereits die kürzeste Tour — keine der 24 Reihenfolgen ist kürzer —, und das Savings-Verfahren liefert dieselben 25,04.
Wann Sie diesen Rechner verwenden sollten
- Ein Lieferdisponent plant eine Tagesroute für einen Fahrer, der 10-30 Kundenstandorte besucht
- Ein Außendienstmanager optimiert Technikerrouten zur Minimierung der Fahrtzeit zwischen Serviceeinsätzen
- Ein Lageringenieur entwirft einen optimalen Kommissionierpfad durch mehrere Gangpositionen
- Ein Vertriebsmitarbeiter plant eine Mehrstädtereise mit minimaler Fahrstrecke
Häufige Fehler, die vermieden werden sollten
- Annahme, die Nearest-Neighbor-Lösung sei optimal — es ist eine Greedy-Heuristik die 20-25% über der optimalen Route liegen kann
- Luftlinienentfernungen für Straßenrouting verwenden — tatsächliche Fahrstrecken können 20-40% länger sein
- Rückreise zum Depot vergessen — TSP erfordert Rückkehr zum Startpunkt
- TSP auf Probleme anwenden, die eigentlich VRP sind — bei Kapazitätsbeschränkungen oder Zeitfenstern VRP-Tool verwenden
Wie die Ergebnisse zu interpretieren sind
- Vergleichen Sie Nearest-Neighbor- und Clarke-Wright-Ergebnisse: bei großen Unterschieden gibt es Optimierungspotenzial mit fortgeschrittenen Methoden
- Rechenzeit in Millisekunden hilft einzuschätzen, ob Echtzeit-Umrouting für Ihre Problemgröße machbar ist
- Die Routenkartenvisualisierung hilft, offensichtliche Ineffizienzen wie kreuzende Routen zu identifizieren
Verwandte Standards & Referenzen
- Nearest Neighbor und Clarke-Wright-Einsparungen (1964) — die in diesem Werkzeug verglichenen konstruktiven Heuristiken
- Lin-Kernighan-Lokalsuche — die De-facto-Referenzheuristik für hochwertige TSP-Touren
- TSPLIB — die öffentliche Standard-Benchmark-Bibliothek zum Vergleich der Lösungsqualität von TSP-Solvern
Häufig gestellte Fragen
Welchen Algorithmus sollte ich verwenden?
Unter 15 Stopps: Naechster Nachbar fuer schnelle Ergebnisse. 15-50: Clarke-Wright + 2-opt. 50+: Metaheuristiken oder Google OR-Tools.
Wie unterscheidet sich TSP von realer Tourenplanung?
Reale Tourenplanung fuegt Zeitfenster, Fahrzeugkapazitaet, Verkehr und Mehrfahrzeug-Probleme (VRP) hinzu. TSP liefert die Distanz-Untergrenze als Benchmark.