Das Traveling Salesman Problem (TSP) ist ein Klassiker der kombinatorischen Optimierung. Gegeben sind n Punkte (Städte). Gesucht ist die kürzeste geschlossene Rundreise, die jeden Punkt genau einmal besucht. Der Suchraum wächst exponentiell, weshalb in der Praxis nahezu ausschließlich heuristische Verfahren eingesetzt werden. Solche Verfahren liefern nicht zwangsläufig die optimale Rundreise, erreichen aber in kurzer Zeit sehr gute Lösungen. Im hier betrachteten Beispiel (TSPLIB pcb442) liegt die beste gefundene Tourlänge bei einem Abstand von etwa 0,13 % zum bekannten Optimum.
Im Mittelpunkt dieses Beitrags steht ein kompaktes, reproduzierbares CLI-Tool in C++20, mit dem sich Heuristiken und Parameter systematisch testen lassen. Neben der Tourlänge werden auch der Suchverlauf und Zwischenstände ausgegeben, sodass der Optimierungsprozess über eine SVG/WebP-Visualisierung nachvollziehbar wird.
Testproblem: pcb442 (TSPLIB)
Als Benchmark dient die TSPLIB-Instanz pcb442 mit 442 Punkten in der Ebene. Schon für dieses relativ kleine Beispiel gibt es unfassbar viele Möglichkeiten: 441!/2 (ungefähr 1.2e976, also eine Zahl mit 977 Stellen). Die Größe dieser Zahl sprengt jede Vorstellung; selbst der Durchmesser des Universums in Millimetern entspricht nur etwa 29!, also extrem weit entfernt von 441!. Für diese Instanz ist ein Referenzwert (Best Known / Optimum) der Tourenlänge von 50778 bekannt.
Distanzdefinition (EUC_2D)
In der TSPLIB ist für pcb442 der Kantengewichtstyp EUC_2D definiert. Die euklidische Distanz zwischen zwei Punkten wird dabei auf die nächste ganze Zahl gerundet. Reinelt gibt dafür folgende Referenzimplementierung an:
xd = x[i] - x[j];
yd = y[i] - y[j];
dij = nint( sqrt( xd*xd + yd*yd ) );Durch diese Rundung pro Kante sind TSPLIB-Tourlängen bei EUC_2D ganzzahlig. Verwendet man stattdessen die kontinuierliche euklidische Distanz ohne Rundung, entstehen nicht-ganzzahlige Tourlängen, die nicht direkt mit TSPLIB-Referenzwerten vergleichbar sind.
Algorithmischer Ansatz
Das Verfahren nutzt lokale Verbesserungszüge aus der k-opt-Familie. Dabei entfernt es Kanten aus der aktuellen Tour und verbindet die entstehenden Teilstücke neu. Die resultierende Längenänderung Δ berechnet es effizient lokal.
Als Moves kommen 2-opt und 3-opt zum Einsatz. Beide operieren ausschließlich auf der aktuellen Tour und benötigen keine zusätzlichen Hilfsstrukturen. 2-opt invertiert ein Segment der Tour und ersetzt dabei zwei Kanten. 3-opt ersetzt drei Kanten und kann dadurch Touren verbessern, die bereits 2-opt-optimal sind. Zusätzlich steht ein Mix-Modus zur Verfügung, etwa 4× 2-opt + 1× 3-opt. Dieser Modus kombiniert schnelle Strukturverbesserungen mit gezieltem Feintuning.
Die Akzeptanzregeln steuern die Suche. Sie legen fest, ob das Verfahren einen neuen Schritt übernimmt. Dadurch lassen sich unterschiedliche Strategien wie reine Verbesserungsschritte, Simulated Annealing oder Threshold Accepting sauber vergleichen.
- Simulated Annealing (SA): Die Methode akzeptiert Verschlechterungen temperaturabhängig und probabilistisch.
- Threshold Accepting: Die Methode akzeptiert Schritte, solange Δ unter einer dynamischen Schwelle liegt.
- Flooding: Die Methode akzeptiert Schritte bis zu einem aktuellen „Flood-Level“, das schrittweise sinkt.
Move-Typ (2-opt/3-opt/Mix) und Akzeptanzregel lassen sich unabhängig kombinieren. So lässt sich das Explorationsverhalten steuern, ohne die Nachbarschaft zu ändern.
Ergebnisse
Die Suche ist stochastisch, da Kandidaten zufällig ausgewählt werden. Bei festem Zufallsseed und identischen Parametern ist der gesamte Optimierungsverlauf jedoch vollständig reproduzierbar. Die verwendete Konfiguration wird zusammen mit der besten Tour gespeichert.
Mit 3-opt erreicht die Implementierung für pcb442 die Tourlänge 50842. Das entspricht einem Gap von ca. 0.126 % zum bekannten Optimum 50778. Für eine bewusst schlanke Implementierung mit lokaler Suche ist das ein sehr gutes Ergebnis.
Zusätzlich sammelt das Programm die besten Läufe in einem kleinen Leaderboard (Top-N). Zu jedem Eintrag gehören die tour.txt und die zugehörige config.json. Damit lassen sich erfolgreiche Parameterkombinationen später exakt reproduzieren.
Auswertung der Testläufe
Bestes Ergebnis: 50842 (Best Known: 50778, Gap: 64 bzw. 0,126 %). Laufzeit des besten Laufs: ca. 195 s.
In den Sweeps dominiert Threshold + 3-opt. Flooding ist deutlich schneller, bleibt aber in der Ergebnisqualität hinter Threshold zurück; Simulated Annealing ist in dieser Konfiguration klar schwächer.
Auszug aus dem Leaderboard
Rang Länge Gap% Algorithmus Move Seed Laufzeit
1 50842 0.126 threshold 3-opt 7777 ~197s
2 51075 0.585 threshold 3-opt - ~201s
3 51128 0.689 threshold 3-opt - ~110s
4 51133 0.699 threshold 3-opt - ~302s
5 51158 0.748 threshold 3-opt - ~208s
6 51212 0.855 threshold 3-opt - ~283s
7 51236 0.902 flooding 3-opt - ~44s
8 51410 1.245 threshold 3-opt 4242 ~198s
9 51431 1.286 threshold 3-opt - ~97s
10 51448 1.319 threshold 3-opt - ~182s
11 51455 1.333 threshold 3-opt - ~98s
12 51484 1.390 flooding 3-opt - ~22s
13 51534 1.489 flooding 3-opt - ~56s
14 51536 1.493 threshold 3-opt - ~270s
15 51581 1.581 threshold 3-opt - ~104s
16 51672 1.761 flooding 3-opt - ~29s
17 51682 1.780 threshold 2-opt - ~46s
18 51699 1.814 flooding 3-opt - ~112s
19 51754 1.922 flooding 3-opt - ~65s
20 51795 2.003 threshold mix - ~75s
23 54465 7.261 sa 3-opt - ~119s Seed = “-” bedeutet: Standard-Seed aus der config.json (hier 2121).
Alle Läufe sind reproduzierbar, da jede Top-Run im Leaderboard mit tour.txt, config.json und stats.txt gespeichert wird.
Steuerung per JSON
Eine config.json steuert die Parameter des Laufs. Das erleichtert reproduzierbare Experimente, weil jede Änderung der Suche dokumentiert ist. Ein Auszug aus der Datei:
{
"algorithm": "threshold",
"input": "data/tsplib/PCB442.TSP",
"distance_mode": "euc_2d",
"move_mode": "3opt",
"moves_per_city": 800,
"max_outer_iterations": 400
}Visualisierung
Der Solver erzeugt SVGs der Tour sowie optional Zwischenstände pro Iteration. Aus den Frames lässt sich ein kurzer Film (z. B. WebP) erzeugen, der die schrittweise Strukturverbesserung sichtbar macht. Der Film endet automatisch, sobald keine weiteren akzeptierten Verbesserungen gefunden werden.
Aktuelle Tour (SVG):
Optimierungsprozess (WebP):
Ausblick
Naheliegende Erweiterungen sind Candidate-Edges (z.B. k-nearest neighbors), gezieltere 3-opt-Varianten sowie parallele Moves (OpenMP/TBB). Damit ließe sich die Qualität weiter steigern, ohne den Charakter des Solvers zu verändern.
Die verwendeten Ideen (lokale Suche + Akzeptanzregeln) lassen sich auch außerhalb des klassischen TSP einsetzen: z. B. bei Routenplanung (Lieferungen, Service-Touren), Fertigungs- und Bohrpfaden (z. B. PCB- oder CNC-Reihenfolgen), Kommissionierung im Lager, Job-Scheduling und allgemeinen Sequenzierungsproblemen. Über angepasste Distanz-/Kostenfunktionen kann das Verfahren auf viele Optimierungsaufgaben mit Tour- oder Reihenfolgestruktur übertragen werden.
Anmerkung: Der Code geht auf einen älteren Ansatz zurück, wurde jedoch vollständig modernisiert.
Referenzen:
TSPLIB 95 (Reinelt),
JEI – Ant Colony Optimization (pcb442: 50778),
TSPLIB (GitHub Mirror).