Travelling Salesman Problem (TSP): Brute Force, Held–Karp und Dynamic Programming

Das Travelling Salesman Problem (TSP) sucht die kostengünstigste Rundreise, die an einem Startpunkt beginnt, jeden erforderlichen Ort genau einmal besucht und zum Start zurückkehrt.

Graphmodell

• Orte sind Knoten.
• Verbindungen sind Kanten.
• Distanz, Zeit oder Kosten sind Kantengewichte.

TSP ist kein gewöhnliches Shortest-Path-Problem. Dijkstra beantwortet beispielsweise die Frage nach dem günstigsten Weg zwischen zwei Punkten. TSP optimiert dagegen eine komplette Rundreise über alle Punkte.

Beziehung zum Hamiltonian Cycle

Ein Hamiltonian Cycle besucht jeden Knoten genau einmal und kehrt zum Start zurück.

TSP erweitert diese Idee um Gewichte und Optimierung: Gesucht wird der günstigste Hamiltonian Cycle.

Brute Force

Die einfachste exakte Methode testet alle möglichen Reihenfolgen.

Bei festem Startpunkt existieren ungefähr:

(n - 1)!

Möglichkeiten.

Dadurch wird die Methode bereits bei moderaten Eingaben unpraktisch.

Held–Karp mit Dynamic Programming

Ein Zustand wird typischerweise als

dp[visited][last]

definiert.

Er beschreibt die minimalen Kosten, um am Start zu beginnen, eine bestimmte Menge von Städten zu besuchen und bei last zu enden.

Die besuchten Städte werden häufig als Bitmaske gespeichert.

Komplexität:

Zeit:   O(n² × 2^n)
Speicher: O(n × 2^n)

JavaScript-Beispiel

function tspHeldKarp(dist) {
  const n = dist.length;
  const size = 1 << n;

  const dp = Array.from(
    { length: size },
    () => Array(n).fill(Infinity)
  );

  dp[1][0] = 0;

  for (let mask = 1; mask < size; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      if (dp[mask][u] === Infinity) continue;

      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;

        const nextMask = mask | (1 << v);

        dp[nextMask][v] = Math.min(
          dp[nextMask][v],
          dp[mask][u] + dist[u][v]
        );
      }
    }
  }

  const fullMask = size - 1;
  let answer = Infinity;

  for (let last = 1; last < n; last++) {
    answer = Math.min(
      answer,
      dp[fullMask][last] + dist[last][0]
    );
  }

  return answer;
}

Warum ist TSP schwierig?

Die Optimierungsvariante ist NP-hard. Für große Instanzen werden deshalb häufig Heuristiken und spezialisierte Solver eingesetzt.

Typische Verfahren sind:

• Nearest Neighbor
• 2-opt
• Branch and Bound
• Genetic Algorithms
• Simulated Annealing
• Ant Colony Optimization

Symmetrisches und asymmetrisches TSP

Beim symmetrischen TSP gilt:

cost(A, B) = cost(B, A)

Beim asymmetrischen TSP kann die Rückrichtung andere Kosten besitzen, etwa durch Einbahnstraßen, Verkehr oder Maut.

Reale Anwendungen

• Lieferplanung
• Techniker-Routen
• Lagerroboter
• Besuchsplanung im Vertrieb
• CNC- und Fertigungsprozesse
• PCB-Produktion

TSP und Vehicle Routing Problem

TSP betrachtet typischerweise einen Reisenden.

VRP erweitert das Problem um mehrere Fahrzeuge, Kapazitäten, Zeitfenster, mehrere Depots und weitere betriebliche Bedingungen.

Wann verwenden?

TSP passt, wenn ein einzelner Akteur alle erforderlichen Orte besuchen muss und die Gesamtkosten der Rundreise minimiert werden sollen.

Fazit

Brute Force ist einfach, aber faktoriell. Held–Karp reduziert die Laufzeit auf O(n²2^n), bleibt jedoch exponentiell. Für große praktische Probleme werden deshalb meist Heuristiken, Approximationen oder spezialisierte Routing-Solver verwendet.