Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

Die Autoren zeigen, dass eine einfache exakte Methode alle klassischen TSPTW-M-Testinstanzen mit 50 oder mehr Kunden in unter zehn Sekunden löst, was beweist, dass diese Benchmarks nicht mehr repräsentativ für die Bewertung von Algorithmen sind und bei der Erstellung von Trainingsdaten für maschinelles Lernen Vorsicht geboten ist.

Das Wesentliche

Der große Irrtum bei den „schwierigsten" Aufgaben: Eine einfache Erklärung

Stellen Sie sich vor, Sie sind ein Trainer für einen extrem schnellen Rennwagen. Ihr Ziel ist es, herauszufinden, wie schnell Ihr Wagen wirklich ist. Dazu stellen Sie ihm eine Strecke vor. Aber hier ist das Problem: Die Strecke, die Sie gewählt haben, ist so gebaut, dass sie für jeden Wagen, egal wie schlecht er fährt, in Rekordzeit zu schaffen ist.

Genau das ist die Botschaft von Francisco J. Soulignac in seinem Papier über das Traveling Salesman Problem with Time Windows (TSPTW).

Hier ist die Geschichte in einfachen Worten:

1. Das Problem: Der Lieferant mit dem strengen Zeitplan

Stellen Sie sich einen Lieferfahrer vor, der 50 oder mehr Kunden besuchen muss. Jeder Kunde hat ein Zeitfenster: Er kann nur zwischen 10:00 und 10:30 Uhr angerufen werden.

• Kommt der Fahrer zu früh, muss er warten (das kostet Zeit).
• Kommt er zu spät, ist der Kunde sauer (das ist verboten).
• Der Fahrer muss am Ende wieder zum Lager zurückkehren.

Die Aufgabe ist es, die perfekte Route zu finden, die entweder die gesamte Zeit bis zur Rückkehr minimiert (Makespan) oder die tatsächliche Fahrzeit (ohne Wartezeiten) minimiert.

2. Der alte Maßstab: Die „klassischen" Prüfungsfragen

Seit Jahrzehnten verwenden Forscher und Computer-Algorithmen dieselben alten Test-Strecken (die „klassischen Benchmarks"), um zu prüfen, wer der beste Lösungsfinder ist. Es ist wie ein Schultest, bei dem alle Schüler seit 40 Jahren dieselben Aufgaben lösen.

Die Annahme war: „Wenn ein Algorithmus diese alten Aufgaben schnell löst, ist er ein Genie."

3. Die Überraschung: Der Trick im System

Der Autor hat einen sehr einfachen, fast dumm wirkenden Algorithmus entwickelt. Er funktioniert wie ein Rückwärts-Detektiv:

• Statt zu überlegen: „Wo fange ich an und wohin gehe ich?", denkt er: „Ich bin schon am Ziel. Wie komme ich rückwärts so schnell wie möglich zurück zum Start?"
• Er ignoriert dabei viele komplizierte mathematischen Tricks, die andere verwenden.

Das Ergebnis war schockierend:
Dieser einfache „Rückwärts-Detektiv" hat alle großen klassischen Test-Strecken (mit 50+ Kunden) in weniger als 10 Sekunden gelöst.

• Andere, hochkomplexe Super-Computer, die Jahre an Forschung repräsentieren, brauchten dafür oft Stunden oder schafften es gar nicht.
• Der Autor sagt im Grunde: „Diese alten Test-Strecken sind nicht mehr schwer genug. Sie haben einen strukturellen Fehler, den mein einfacher Trick ausnutzt."

4. Die Analogie: Der Schlüssel zum Schloss

Stellen Sie sich die alten Test-Strecken wie ein Schloss vor, das mit einem meistens offenen Fenster gebaut wurde.

• Die komplexen Algorithmen sind wie Meister-Schlossknacker, die versuchen, das Schloss mit Spezialwerkzeugen zu knacken.
• Der einfache Algorithmus des Autors ist wie ein Kind, das einfach durch das offene Fenster klettert.

Das Kind (der einfache Algorithmus) sieht aus wie ein Wunderkind, weil es das Schloss in 10 Sekunden öffnet. Aber das liegt nicht daran, dass es ein besserer Schlossknacker ist, sondern daran, dass das Fenster offen stand. Wenn man die Fenster schließt (die Zeitfenster der Kunden enger macht), kann das Kind gar nicht mehr durchkommen.

5. Warum das wichtig ist (Die Warnung)

Der Autor warnt uns vor zwei Dingen:

1. Für Forscher: Wenn Sie Ihren neuen, genialen Algorithmus nur auf diesen alten Test-Strecken testen, werden Sie denken: „Wow, mein Algorithmus ist der Schnellste der Welt!" Aber das ist eine Täuschung. Sie haben nur das offene Fenster gefunden. Um wirklich zu wissen, ob Ihr Algorithmus gut ist, müssen Sie ihn an schwereren Strecken testen, bei denen die Zeitfenster sehr eng sind (wie bei einem echten, chaotischen Lieferdienst).
2. Für Künstliche Intelligenz (KI): Viele KI-Modelle werden heute mit Daten trainiert, die genau wie diese alten, „offenen Fenster"-Strecken erstellt wurden. Das führt dazu, dass die KI lernt, diese spezifischen Tricks zu nutzen, anstatt wirklich intelligentes Verhalten zu lernen. Wenn sie dann in der echten Welt (wo die Fenster zu sind) eingesetzt wird, versagt sie.

Fazit

Die Botschaft ist klar: Hören Sie auf, nur die alten, leichten Testaufgaben zu verwenden. Sie sind veraltet und täuschen uns über die wahre Leistungsfähigkeit unserer Algorithmen. Wir brauchen neue, härtere Herausforderungen, bei denen die Zeitfenster so eng sind, dass man nicht mehr einfach „durch das Fenster klettern" kann. Nur so finden wir wirklich starke Lösungen für die Probleme von morgen.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows" von Francisco J. Soulignac auf Deutsch.

1. Problemstellung

Das Paper befasst sich mit dem Traveling Salesman Problem with Time Windows (TSPTW). Dabei muss ein Fahrzeug eine Reihe von Kunden innerhalb ihrer vordefinierten Zeitfenster $[a(v), b(v)]$ besuchen. Das Fahrzeug darf früh eintreffen und warten, aber nicht zu spät kommen. Es startet und endet an einem Depot.

Der Autor unterscheidet drei Hauptvarianten des Problems basierend auf der Zielfunktion:

• TSPTW-M (Makespan): Minimierung der Gesamtzeit bis zur Rückkehr zum Depot (Abschlusszeit).
• TSPTW-D (Duration): Minimierung der gesamten Fahrzeit (Differenz zwischen Abfahrt und Rückkehr), wobei Wartezeiten nicht zur Fahrzeit zählen.
• TSPTW-TT (Total Travel Time): Minimierung der reinen Reisezeit ohne Wartezeiten.

Das zentrale Problem des Papers ist die Repräsentativität der klassischen Benchmark-Instanzen (z. B. von López-Ibáñez und Blum, 2023). Diese werden seit Jahrzehnten verwendet, um Algorithmen zu bewerten und als Trainingsdaten für maschinelle Lernverfahren zu dienen. Der Autor argumentiert, dass diese Instanzen, insbesondere solche mit 50 oder mehr Kunden, aufgrund ihrer spezifischen Struktur (enge Zeitfenster) nicht mehr als alleiniges Maß für die Leistungsfähigkeit von Algorithmen geeignet sind.

2. Methodik

Der Autor stellt einen einfachen, exakten Solver vor, der auf einer rückwärts gerichteten, informierten Suche (Backward Informed Search) basiert.

• Algorithmus 1 (Backward Best-First Search):

  • Die Suche beginnt am Enddepot und arbeitet sich rückwärts durch die Kunden.
  • Es wird ein Baum von Teilrouten durchsucht.
  • Heuristik: Bei der Auswahl der nächsten Teilroute wird priorisiert, welche Route das Enddepot am frühesten erreicht ($\delta_m(R)$), unter der Bedingung, dass sie noch innerhalb eines oberen Schätzwerts ($ub$) liegt. Im Falle von Gleichstand wird die spätestmögliche Abfahrt maximiert, um Wartezeiten zu minimieren.
  • Pruning (Beschneidung):
    • Unreachable Function: Eine Vorverarbeitung berechnet, welche Knoten nicht vor einem bestimmten Knoten $v$ besucht werden können, wenn $v$ zu einem bestimmten Zeitpunkt erreicht wird. Dies eliminiert ganze Teilbäume.
    • Dominanz-Prüfung: Eine Teilroute $R$ wird verworfen, wenn eine andere Teilroute $Q$ mit denselben besuchten Knoten existiert, die früher ankommt oder später abfahren kann, ohne die Zeitfenster zu verletzen.
  • Algorithmus 2: Führt Algorithmus 1 iterativ aus, indem der obere Schätzwert ($ub$) schrittweise gesenkt wird, bis die optimale Lösung gefunden ist.

• Algorithmus 3 (Lösung für TSPTW-D):

  • Nutzt den Solver für TSPTW-M als Unterprogramm.
  • Verwendet eine Sliding-Window-Strategie, um verschiedene Abfahrtszeiten zu testen und diejenige zu finden, die die minimale Gesamtdauer ($\Delta(R)$) ergibt.
  • Nutzt lokale Suchheuristiken (Swap, 2-opt, Shift), um die Suche zu beschleunigen.

3. Wichtige Beiträge

1. Entlarvung der Benchmark-Schwäche: Der Autor zeigt, dass die klassischen Benchmark-Instanzen mit $\ge 50$ Kunden durch einen sehr einfachen Algorithmus in weniger als 10 Sekunden gelöst werden können. Dies widerlegt die Annahme, dass diese Instanzen „schwierig" genug für moderne exakte Solver oder ML-Modelle sind.
2. Strukturelle Verzerrung: Die klassischen Instanzen (Lan, Dum, Gen, Ohl, DaS) nutzen oft eine einfache Methode zur Generierung von Zeitfenstern (basierend auf einer zweiten-Nachbar-Route mit einem kleinen $\omega$). Dies erzeugt eine inhärente Struktur, die von einfachen Suchalgorithmen ausgenutzt werden kann, während komplexere Algorithmen (wie Branch-and-Cut) oft mehr Rechenzeit für die Berechnung von Strafen oder Relaxationen verschwenden.
3. Warnung vor ML-Datensätzen: Viele maschinelle Lernverfahren generieren ihre Trainingsdaten basierend auf diesen gleichen Prinzipien. Das Paper warnt davor, dass Modelle, die nur auf diesen Daten trainiert werden, überangepasst (overfitted) sein könnten und in realen Szenarien mit lockereren Zeitfenstern versagen.
4. Lösung offener Instanzen: Der vorgestellte Algorithmus löst alle bisher ungelösten Instanzen der klassischen Benchmarks (insbesondere 4 offene Instanzen in den Datensätzen von Fontaine et al. und 14 in den Datensätzen von Lera-Romero et al.) extrem schnell.

4. Ergebnisse

Die Experimente wurden auf einer Laptop-Hardware (AMD Ryzen 7) durchgeführt.

• TSPTW-M Ergebnisse:

  • Der Algorithmus löst alle Instanzen der klassischen Benchmarks (Asc, Dum, Gen, Lan, Ohl, Pot, DaS) mit $\ge 50$ Kunden in unter 10 Sekunden.
  • Er löst sogar die 4 Instanzen, die in früheren Studien (Fontaine 2024, Rudich 2023) als offen galten.
  • Gegenprobe: Bei Instanzen mit lockeren Zeitfenstern (generiert nach Fontaine 2024 / Rifki et al. 2020, Parameter $\beta \in \{0, 25\}$) versagt der Algorithmus oft oder benötigt extrem lange, selbst bei kleinen Instanzen (30–40 Kunden). Hier schneiden generischere Algorithmen (wie Ler22 oder Rud23) besser ab.
  • Der Algorithmus ist bei kleinen Instanzen (< 50 Kunden) oft langsamer oder scheitert, was die Annahme widerlegt, dass „mehr Kunden" automatisch „schwieriger" bedeutet. Die Enge der Zeitfenster ist der kritischere Faktor.

• TSPTW-D Ergebnisse:

  • Durch Anwendung des TSPTW-M-Solvers als Vorverarbeitung (Sliding Window) werden alle klassischen Instanzen mit $\ge 50$ Kunden in unter 30 Minuten gelöst.
  • Auch hier zeigt sich, dass die klassischen Benchmarks für die Duration-Variante zu einfach sind.

5. Bedeutung und Fazit

Das Paper hat weitreichende Implikationen für die Forschung im Bereich der kombinatorischen Optimierung und des maschinellen Lernens:

• Benchmarking: Die klassischen Benchmarks sollten nicht mehr als alleiniges Evaluationsmaß für TSPTW-Algorithmen verwendet werden. Sie führen zu irreführenden Ergebnissen, die den Eindruck erwecken, Algorithmen seien hocheffizient, obwohl sie nur die spezifische Struktur dieser synthetischen Daten ausnutzen.
• Zukünftige Forschung: Um robuste Algorithmen zu entwickeln, müssen Benchmarks mit lockeren Zeitfenstern (hoher $\beta$-Wert) und Instanzen, die reale Szenarien besser abbilden, verwendet werden.
• Maschinelles Lernen: Trainingsdatensätze für ML-Modelle sollten nicht auf den gleichen einfachen Generierungsprinzipien basieren, die die klassischen Benchmarks nutzen, da dies zu Modellen führt, die nicht auf schwierigere, realistischere Probleme verallgemeinern können.

Kernaussage: Die Einfachheit der Lösung für die klassischen Benchmarks ist kein Beweis für die Überlegenheit eines Algorithmus, sondern ein Hinweis darauf, dass die Benchmarks selbst veraltet und zu einfach für die heutigen Anforderungen sind. Die Forschung muss sich auf Instanzen konzentrieren, bei denen die Zeitfenster so weit geöffnet sind, dass die Struktur der Lösung nicht trivial vorhersagbar ist.