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
Der Solver arbeitet mit lokalen Verbesserungszügen aus der k-opt-Familie. Im Kern werden Kanten der aktuellen Tour entfernt und die dadurch entstehenden Teilstücke neu verbunden; die resultierende Längenänderung Δ lässt sich effizient lokal berechnen.
Als Moves werden 2-opt und 3-opt verwendet. Beide Moves operieren ausschließlich auf der aktuellen Tour und erfordern keine zusätzlichen Hilfsstrukturen. 2-opt invertiert ein Segment der Tour (zwei Kanten werden ersetzt), während 3-opt drei Kanten ersetzt und damit Touren verbessern kann, die bereits 2-opt-optimal sind. Zusätzlich existiert ein Mix-Modus (z. B. 4× 2-opt + 1× 3-opt), der schnelle Strukturverbesserungen mit gezieltem Feintuning kombiniert.
Die eigentliche Steuerung der Suche erfolgt über unterschiedliche Akzeptanzregeln. Diese bestimmen, ob ein Schritt übernommen wird:
- Simulated Annealing (SA): Verschlechterungen werden temperaturabhängig probabilistisch akzeptiert.
- Threshold Accepting: Akzeptiert Schritte, solange Δ unter einer dynamischen Schwelle liegt.
- Flooding: Akzeptiert Schritte bis zu einem aktuellen „Flood-Level“, das schrittweise abgesenkt wird.
Move-Typ (2-opt/3-opt/Mix) und Akzeptanzregel sind unabhängig kombinierbar. 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.
Für pcb442 wurden mit 3-opt Tourlängen um 50842 erreicht, was einem Gap von ca. 0.126 % zum bekannten Optimum 50778 entspricht. Das ist für eine bewusst schlanke Implementierung mit lokaler Suche ein sehr gutes Ergebnis.
Zusätzlich werden die besten Läufe in einem kleinen Leaderboard (Top-N) gesammelt, inklusive tour.txt und der zugehörigen 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
Die Parameter werden über eine config.json gesteuert. 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).