Ein Fahrzeug, ohne Kapazität, Rückkehr zum Start: finde die minimalkostige geschlossene Tour, die jeden von N Knoten genau einmal besucht. Das Stammproblem der Routenoptimierung — alle VRP-Varianten leiten sich davon ab (akademisch: TSP).
Kurz gesagt
Kommt Ihnen das bekannt vor?
- Wir haben einen Einzelfahrzeug-Servicebetrieb — ein Techniker besucht täglich 8-15 Kunden, die Reihenfolge legt der Techniker nach Gefühl fest.
- In unserem mittelständischen Produktionsbetrieb fährt ein Außendienstler einmal pro Woche eine Regionaltour (15-40 Lieferanten- oder Kundenbesuche); ein Fahrzeug, keine Kapazitätsbindung, die Reihenfolge ist nicht optimal.
- Wir betreiben eine PCB-Bohrmaschine oder einen automatischen Bestücker — der Bohr- oder Bestückkopf wandert über 500-5.000 Punkte, die Reihenfolge liegt beim Maschinenprogrammierer.
- Wir planen eine Kabelverlegung oder eine Rohrverlege-Sequenz — eine Crew, eine Tour, keine Kapazitätsbindung.
- Ein automatischer Lagerroboter (Single-Pick-AS/RS) baut Regaltouren — der Roboter hat keine Kapazitätsbindung oder trägt ein einzelnes Objekt.
- Innerstädtische Kühlketten-Lieferantentour (ein Fahrzeug, kleine Ladegröße); die Reihenfolge ergibt sich aus Routine des Fahrers.
- Knotenzahl liegt bei 50-500 — eine Größe, die ein exakter MIP-Solver schafft; trotzdem hält die Intuition 'TSP ist NP-schwer, also Heuristik' uns bei der Heuristik fest.
Warum es wichtig ist
Wie wird es gelöst?
Technische Tiefe
Wie wird es gelöst?
Technische TiefeIn einem Satz: Erstelle zuerst die paarweise Entfernungsmatrix (reale Straßenentfernung, symmetrisch oder asymmetrisch), dann je nach Größe — unter 1.000 Knoten exakter MIP-Solver, darüber k-opt-Lokalsuche (Lin-Kernighan-Familie) — und du hast die Tour in Minuten.
In der Operations-Research-Literatur (Disziplin, die Mathematik und Computer für Geschäftsentscheidungen einsetzt) trägt das Problem den Namen Travelling Salesman Problem (TSP — Rundreiseproblem) und wird seit 70+ Jahren als Stammproblem der modernen kombinatorischen Optimierung untersucht. Kanonische Aufgabe: Gegeben N Knoten (Städte, Kunden, Bohrpunkte, Kabelknoten) und eine paarweise Entfernungsmatrix (oder Zeit oder Kosten) — finde die Hamilton-Tour (geschlossene Tour, die jeden Knoten einmal besucht) mit minimalen Gesamtkosten, die jeden Knoten genau einmal besucht und zum Start zurückkehrt. Ein Fahrzeug, keine Kapazität, keine Zeitfenster, Depot = Startknoten. Lösung in drei Stufen:
1. Modellierung. Eingaben: Knotenliste (jeweils Position oder Identifikations-Tag), paarweise Entfernungsmatrix (Euklidisch, reale Straßenentfernung oder Zeit — straßenbasiert in der Stadt, Manhattan an einem Maschinenkopf), Symmetrieeigenschaft (wenn Entfernung A→B = B→A, symmetrisches TSP; sonst — etwa Einbahnstraße — asymmetrisches TSP / ATSP), metrische Eigenschaft (gilt die Dreiecksungleichung, metrisches TSP und eine 3/2-Approximations-Heuristik mit Garantie ist anwendbar). Zielfunktion: minimale Gesamttour-Kosten. Bedingungen: jeder Knoten genau einmal besucht + eine einzige geschlossene Tour (Subtouren verboten).
2. Solver-Entscheidung. Drei akademische Hauptansätze: (i) Exaktes Branch-and-Cut-MIP (Branch-and-Cut — Baumsuche mit Schnittebenen-Verschärfung) — die Cutting-Plane-Methode wurde in den 1950ern eingeführt; reife Solver haben TSP-Instanzen bis 85K+ Knoten exakt gelöst. Für Feldgrößen (50-500 Knoten) reichen kommerzielle oder reife Open-Source-MIP-Solver (Mixed-Integer Linear Programming — Optimierung mit teils 0/1-, teils stetigen Variablen), Lösezeit Minuten. (ii) Dynamische Programmierung (Held-Karp) — die O(n²·2^n)-DP-Formulierung aus den 1960ern; praktisch für n < 25, Lehrreferenz. (iii) Heuristik — Lin-Kernighan-Familie — k-opt-Lokalsuche (k Kanten aus der Tour entfernen und neu verdrahten); die moderne LKH-Implementierung (Lin-Kernighan-Helsgaun) bleibt bis Millionen-Knoten-Größe innerhalb 0,1-1% am Optimum und ist die Referenzheuristik für Feldinstanzen ab 1.000 Knoten. Baustein-Heuristiken: Nearest-Neighbor, Christofides-3/2 (metrisches TSP), Savings-Algorithmus, 2-opt, 3-opt-Lokalsuche.
3. Feldintegration. Output je nach Einsatz dreischichtig: (a) Feldservice-Betrieb — geordnete Stoppliste + Navigation in der Fahrer-Mobile-App, am Tagesanfang zugewiesen, untertags meist nicht neu optimiert; (b) Maschinenprogrammierung — Bohr- oder Bestückreihenfolge in das NC-Programm einer PCB-Bohr- oder Bestückmaschine eingebettet, einmal pro Teile-Charge berechnet; (c) Kabel- oder Rohrroute — der Routenplan eines Bauingenieurs, einmalige Entscheidung vor dem Dry Run. Das TSP-Modul ist meist in eine Routing-Software oder in ein Linien-Programmierpaket eingebettet — selten als eigenständiges Produkt verkauft. Quartalsweise Betriebsrunde: reale Tourstrecke vs Plan, Fahrerzeitabweichung, Zusatztouren-Zahl.
Alternativen
Intuitive Reihenfolge + Spreadsheet
KostenlosKeine Lizenz
Für wen geeignet: Sehr klein (unter 10 Stopps/Tag), was der Planer im Kopf behalten kann
- + Keine Softwarekosten
- + Feldwissen des Planers zählt
- + Telefonreaktion auf ETA-Änderungen
- − Ab 20 Stopps weicht der menschliche Verstand 20-40% vom Optimum ab
- − Inkonsistent — Reihenfolge unterscheidet sich täglich
- − Keine Messung — Streckenwerte werden nicht protokolliert
- − Bricht schnell zusammen, sobald Mehrfach-Fahrzeug oder Kapazität dazukommt (wird zum VRP)
Allgemeine Routing- / Feldservice-Software (eingebettetes TSP-Modul)
Enterprise100-400 TRY/Fahrzeug/Monat Abo oder 200K-800K TRY Einmal-Lizenz
Für wen geeignet: Feldservice-Betrieb (10-50 Fahrzeuge), Einzelfahrzeug-Tour, ohne Kapazität
- + Tourreihenfolge-Motor ist vorhanden — Nearest-Neighbor + lokale Verbesserung ist typisch
- + Fahrer-Mobile-App, Navigation, Kundeninfo integriert
- + Lokale Karten- und Verkehrsdaten
- − Algorithmustransparenz gering — 'welches Verfahren wird verwendet' wird selten klar beantwortet
- − Ein Solver mit Optimum-Garantie fehlt meist, nur schnelle Näherung
- − Ab 500 Stopps wächst der Abstand zur besten Tour
Open-Source-Solver + eigenes TSP-Modul
Open SourceLizenz kostenlos; Eigenentwicklung 8-16 Wochen oder 200K-800K TRY Beratung
Für wen geeignet: Betrieb mit Tech-Team, Maschinenprogrammierung (PCB, CNC), spezialisierte Feldroute
- + Solver mit Optimum-Garantie sind Open-Source verfügbar
- + Industrieübliche Heuristik-Werkzeuge, die bis Millionen-Stopp-Größe nahezu optimal bleiben, sind Open-Source
- + Varianten wie Einbahnstraßen-Touren und profitorientierte Touren lassen sich anpassen
- − Interner Optimierungs-Spezialist + Integrationsteam nötig
- − Vom ersten Prototyp zum Feldsystem 3-6 Monate
- − Wartung bleibt intern
Branchenspezifisches Maschinen-Programmierpaket (PCB / CNC)
Enterprise500K-3M TRY eingebettet ins Maschinen-Softwarepaket
Für wen geeignet: Automatische PCB-Bohrmaschine, Bestücker, Laserschnitt — Maschinenhersteller-Paket
- + Bohr-/Bestückkopf-Reihenfolge vom Maschinenhersteller kalibriert
- + Maschinenprogramm-Ausgabe lädt direkt in die Maschine
- + Bedienschulung kommt vom Maschinenhersteller
- − An den Maschinenhersteller gebunden — bei neuer Maschine neuer Kauf
- − Algorithmus undurchsichtig, Abstand zur besten Tour nicht messbar
- − Anpassung (z. B. Werkzeugwechsel-Strafe) schwierig
Empfehlung
Im Gespräch fragen
- Welcher Ansatz steckt im Tour-Modul — Solver mit Optimum-Garantie, Nearest-Neighbor + lokale Verbesserung, industrieübliche Heuristik oder nur Nearest-Neighbor?
- Unterstützt die Entfernungsmatrix Einbahnstraßen und richtungsabhängige Fahrzeit, oder werden A→B und B→A stets als gleich angenommen?
- Wie wird die Entfernungsmatrix erzeugt — Luftlinie, reale Straße oder verkehrsabhängige Fahrzeitmatrix? Aktualisierungstakt?
- Wie lange dauert die Lösung für typische Instanzgrößen — 100, 500, 1.000 Stopps?
- Wird der prozentuale Abstand zur best möglichen Tour vom Modul gemeldet?
- Wenn das Problem von einem Fahrzeug zu mehrfach-fahrzeugiger kapazitierter Routenplanung wächst (Kapazität, mehrere Touren, Depot-Rückkehr), kann die gleiche Infrastruktur weiter genutzt werden, oder ist es ein separates Modul?
- Falls der Vertrag endet, in welchem Format können Tourdaten (Stopp-Positionen, erzeugte Touren, Entfernungsmatrizen) exportiert werden?
Technische Details
Redakteursnotiz
Dieses Problem heißt im Betrieb meist “Tour-Planung”, “Besuchsreihenfolge” oder “Routensequenz”. Sein akademischer Name ist eindeutig: Travelling Salesman Problem (TSP). TSP ist das Stammproblem der Operations Research — VRP (#002), PDPTW (#046), Berth Allocation (#026) und Dutzende anderer Routing- / Scheduling-Probleme sind strukturelle Erweiterungen des TSP. Die strukturelle Trennung ist scharf: TSP ist Einzelfahrzeug, geschlossene Tour, keine Kapazität, Rückkehr zum Start, keine Zeitfenster. VRP fügt Mehrfach-Fahrzeug + Depot + Kapazität hinzu; VRPTW Zeitfenster; PDPTW Quelle-Ziel-Paarung und Reihenfolgebedingung. Ein “Routing-Modul” zu kaufen, ohne zu prüfen, welche dieser Strukturen es tatsächlich löst, heißt Monate später festzustellen, dass die Infrastruktur bei Mehrfach-Fahrzeug-Bedarf nicht ausreicht.
Im Sektor am häufigsten übersehen: die praktische Anwendbarkeitsschwelle moderner exakter TSP-Solver. Die Praxisintuition lautet oft “TSP ist NP-schwer (Klasse von Problemen, deren Lösezeit mit der Größe explodiert), exakt nicht möglich, Heuristik notwendig”. Die Realität: reife Branch-and-Cut-Solver haben 85K+ Knoten-Instanzen exakt gelöst; eine Feldinstanz mit 100-500 Knoten erreicht in Minuten das Optimum auf einem modernen MIP-Solver. Heuristiken (Nearest-Neighbor + 2-opt) sind in den meisten Produkten Default — sie weichen auf realen Felddaten 15-30% vom Optimum ab. Praktische Regel: unter 1.000 Knoten ist operatives TSP exakt-MIP-lösbar; im Bereich 1.000-100K Knoten bleibt die LKH-Heuristik innerhalb 0,1-1% am Optimum. Die Intuition “Heuristik notwendig” stimmt nicht; ohne Skalenwissen kann man nicht entscheiden.
Zweiter übersehener Punkt: symmetrisch vs asymmetrisch. Innerstädtische Routen mit Einbahnstraßen, Auf- und Abfahrten oder richtungsabhängiger Fahrzeit erzeugen eine asymmetrische Entfernungsmatrix — A→B unterscheidet sich von B→A. Die meisten Produkt-TSP-Module setzen Symmetrie voraus; asymmetrische Daten ergeben ein falsches Optimum. Asymmetrisches TSP (ATSP) braucht eine andere Formulierung.
Schritt für Schritt — für KMU
Stufe 1 — Erst messen, dann planen. Mindestens 8-12 Wochen Tour-Daten: pro Tour — Anzahl Stopps, Stopp-Positionen, reale Tourstrecke (Fahrzeug-Tacho), Tourdauer, Fahreridentität, ob die Reihenfolge untertags geändert wurde, ob Kundenbesuchsfenster eingehalten wurden. Entfernungsmatrix: typische Straßenentfernung und Zeit zwischen allen besuchten Knotenpaaren (Nebenzeit vs Stoßzeit). Ohne diese Inventur lässt sich nicht sagen, welche Software welches Ergebnis liefert.
Stufe 2 — Wissenskapital heben. Lücke der aktuellen intuitiven Reihenfolge zum Optimum schätzen: auf einem 30-50 Knoten-Tagessatz mit einem Open-Source-MIP-Solver die exakte Tour rechnen, mit der realen Fahrertour vergleichen. Typische Lücke 15-30%. Diese Lücke ist die Hauptkennzahl des Business Case. Variiert die Knotenzahl täglich, eigene Mittelwerte für typische vs Spitzentage bilden.
Stufe 3 — Pilot. 6-10 Wochen. Für ein Fahrzeug oder eine Maschine das TSP-Modul parallel zur aktuellen intuitiven Reihenfolge laufen lassen. Die Entscheidung bleibt beim Fahrer / Operator; das System gibt Empfehlungen. Erfolgskriterien vor dem Pilot schriftlich: durchschnittliche Tourstrecke -10% mindestens, Tourdauer -8%, Fahrerzufriedenheit neutral oder positiv.
Stufe 4 — Roll-out. 4-9 Monate auf die ganze Flotte oder den ganzen Maschinenpark. Quartalsbetriebsrunde: reale Tourstrecke vs Plan, Fahrerzeit-Abweichung, Kunden-Fensterquote, Maschinen-Kopf-Zeit-Bericht.
Risiken — was schiefgehen kann
- Statische Fahrzeit-Annahme. Eine auf Einzelpunkt-Durchschnitten gebaute Entfernungsmatrix weicht zu Spitzenzeiten 50-100% vom realen Wert ab. Stundenbandweise Fahrzeitmatrizen (z. B. 30-Minuten-Bogenprofil) sind notwendig; im Pilot müssen Plan- vs Ist-Fahrzeiten verglichen werden.
- Servicezeit im Modell? Ein Servicetechniker verbringt 30-90 Minuten an jedem Stopp; ist diese Servicezeit nicht im Tourplan, ist die Reihenfolge mathematisch optimal, aber operativ nicht umsetzbar. Servicezeit pro Knoten als fester oder probabilistischer Wert modellieren.
- Knotenzahl wächst, Heuristik driftet vom Optimum ab. Bei 50 Knoten liegt Nearest-Neighbor + 2-opt 5-10% am Optimum; bei 500 Knoten 15-25%; bei 5.000 Knoten 30%+. Mit wachsender Skala ist der Übergang zu LKH oder exaktem MIP notwendig; Einfrieren der Heuristik kumuliert Verluste mit Wachstum.
- Lock-in beim Routing-Software-Anbieter. Ohne Vertragsklausel zum jährlichen Export der Tourdaten, Entfernungsmatrizen und Lösungshistorie in einem Standardformat geht beim Wechsel das Tour-Gedächtnis des Betriebs verloren. Kundenstandorte und Besuchsfenster sind der Kern dieses Gedächtnisses."
Technische Sicht auf die Lösungsmethode
| Ansatz | Typische Größe | Lösezeit | Optimum garantiert? |
|---|---|---|---|
| Intuitive Reihenfolge (Planer + Kopf) | <20 Knoten | sofort | Nein, 60-80% Optimum |
| Nearest-Neighbor + 2-opt | 20-200 Knoten | Sekunden | Nein, 85-95% Optimum |
| Christofides 3/2 (metrisches TSP) | 50-500 Knoten | Sekunden | 3/2-Approximationsgarantie |
| Dynamische Programmierung (Held-Karp) | <25 Knoten | Minuten | Ja (exakt) |
| Branch-and-Cut-MIP (Princeton-Georgia Tech-Gruppe) | 50-100K Knoten | Minuten-Stunden | Ja (innerhalb Bound) |
| Lin-Kernighan / LKH | 1K-1M+ Knoten | Minuten-Stunden | Nein, 0,1-1% am Optimum |
| Metaheuristik (Tabu, genetisch, Ant Colony) | flexibel | flexibel | Nein, gute Praxisqualität |
TSP-Varianten — nach Anwendung wählen:
- Symmetrisches TSP: Entfernung A→B = B→A. Überlandstraßen, Luftlinie, PCB-Bohrung. Einfachste und meiststudierte Variante.
- Asymmetrisches TSP (ATSP): Richtungsabhängige Entfernung. Einbahnstraßen, richtungsabhängige Fahrzeit. Etwas schwieriger zu modellieren, Branch-and-Cut weiterhin anwendbar.
- Euklidisches TSP: Knoten in der Ebene, Entfernung gerade Strecke. PCB-Bohrung, Inline-Fertigung.
- Metrisches TSP: Dreiecksungleichung gilt (A→C ≤ A→B + B→C). Christofides-3/2-Garantie gilt.
- TSP with profits / OP: Knoten tragen einen Wert (Profit); nicht jeder Knoten muss besucht werden. Die “Prioritätskunde”-Variante für Feldservice.
Zielfunktion — Wahl:
- Ziel 1 — Minimale Gesamtstrecke / Kraftstoff: Fokus Kraftstoff + Fahrerzeit.
- Ziel 2 — Minimale Gesamtzeit: Fokus Fahrerzeit / Maschinenzyklus.
- Ziel 3 — Minimale maximale Stoppzeit (Min-Max-TSP): Faire Verteilung oder Arbeitssicherheit.
Akademische Quellen
Im sources-Block dieser Seite gelistet.
Quellen
- Dantzig, G., Fulkerson, R. und Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410. Begründende Cutting-Plane-Arbeit.
- Lin, S. und Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. Grundlage der modernen Heuristikfamilie.
- Applegate, D., Bixby, R., Chvátal, V. und Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. Kanonisches Buch zum exakten Branch-and-Cut-Solver der Forschungsgruppe Princeton-Georgia Tech.
- Held, M. und Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. Die O(n²·2^n)-DP-Formulierung.
- Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. LKH — bleibt bis Millionen-Knoten innerhalb 0,1-1% am Optimum.
- YÖK Tez Merkezi — Stichwort: ‘gezgin satıcı’ oder ‘TSP’ oder ‘Tour-Optimierung’ — 30+ Arbeiten der TR-Akademie. tez.yok.gov.tr
Glossar
- Travelling Salesman Problem
- Das Stammproblem der kombinatorischen Optimierung: in einem Graphen die Hamilton-Tour minimaler Kosten finden, die jeden Knoten genau einmal besucht und zum Start zurückkehrt.
- Branch-and-Cut
- Das exakte MIP-Lösungsrahmenwerk, das Branch-and-Bound mit Schnittebenenverfahren kombiniert — an jedem Knoten des Suchbaums verschärfen gültige Ungleichungen (Schnitte) die LP-Relaxation vor dem Verzweigen.
- MIP
- Optimierungsmodell, bei dem ein Teil der Entscheidungsvariablen ganzzahlig sein muss (z. B. Anzahl LKW, Anzahl Schichten).
- VRP
- Die Entscheidung, welche Fahrzeuge — ausgehend von einem oder mehreren Depots — welche Kunden in welcher Reihenfolge anfahren.
Ähnliche Probleme
Mehrere Fahrzeuge, viele Kunden — welches Fahrzeug in welcher Reihenfolge, Kapazität nicht überschritten, Gesamtstrecke minimal?
Ein Distributor oder Lieferant, der täglich von einem Depot aus 10-100 Kunden beliefert (Lebensmittel, Getränke, Wasser, B2B-Ersatzteile); feste Fahrzeugkapazität (2-5 t, 30 m³), bekannte Bestellmengen je Kunde, flexible Lieferzeit. Jeden Morgen drei Fragen: wie viele Fahrzeuge fahren heute los, welches Fahrzeug bedient welche Kunden, in welcher Reihenfolge — Kapazität nicht überschritten, Gesamtstrecke minimiert. Ein Disponent schafft 15-25 Kunden im Kopf; darüber sinkt die Routenqualität, Kunden derselben Region landen auf zwei Fahrzeugen, 1-2 Fahrzeuge pro Tag fahren unnötig zusätzlich. 10-25 % der Gesamtstrecke und 1-2 Fahrzeuge pro Tag hängen von der Planqualität ab; Kraftstoff + Fahrer machen 30-50 % der Betriebskosten aus.
Mehrere Werke, mehrere Kunden — Wie viel liefert jedes Werk an jeden Kunden, damit die Gesamtfracht minimal wird?
Für Lebensmittel-, Verpackungs- oder Textil-KMU, die wöchentlich aus 3-8 Werken oder Regionallagern an 20-100 Kunden liefern. Die wöchentliche Entscheidung lautet: welches Werk schickt wie viel an welchen Kunden, bei festen Werkkapazitäten, festgelegten Kundenbedarfen und je Werk-Kunde-Paar unterschiedlichen Stückkosten (Entfernung + Fahrzeugtyp + Vertrag). Ziel ist die niedrigste Gesamtfrachtrechnung über das Netz. Die Faustregel 'nächstgelegenes Werk' oder 'das machen wir schon immer so' kostet gegenüber einer systematischen Zuweisung typischerweise 10-20% zusätzlichen Diesel- und Fahrzeugaufwand.