Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

Die Studie stellt RL-CMSA vor, einen hybriden Ansatz, der konstruktive Lernverfahren, eine Mergemethode und exakte MILP-Optimierung kombiniert, um das min-max Multiple Traveling Salesman Problem effizienter zu lösen als bestehende genetische Algorithmen.

Das Wesentliche

Stell dir vor, du bist der Chef einer riesigen Lieferfirma. Du hast einen großen Lagerhof (das Depot) und hunderte von Kunden, die Pakete erwarten. Du hast auch eine Flotte von Lieferwagen (die „Verkäufer"). Deine Aufgabe ist es, Routen zu planen, damit jeder Kunde genau einmal bedient wird.

Das große Problem dabei: Du willst nicht nur, dass alle Pakete schnell geliefert werden, sondern dass niemand überarbeitet wird. Wenn ein Fahrer 100 Kilometer fährt und ein anderer nur 10, ist das unfair und ineffizient. Dein Ziel ist es also, die längste einzelne Route so kurz wie möglich zu halten. Das nennt man das „Min-Max"-Problem.

Dieser wissenschaftliche Artikel stellt eine neue, clevere Methode vor, um genau dieses Problem zu lösen. Sie nennen ihre Methode RL-CMSA. Hier ist, wie sie funktioniert, erklärt mit einfachen Bildern:

1. Der Baumeister mit dem Zauberstab (Construct & Reinforcement Learning)

Stell dir vor, du hast einen Baumeister, der neue Routen entwirft. Früher hat er einfach zufällig Städte zusammengefasst. Aber in dieser neuen Methode hat der Baumeister ein Gehirn, das aus Erfahrung lernt (das ist der „Reinforcement Learning"-Teil).

• Die Lernkurve: Der Baumeister merkt sich: „Aha! Wenn ich Stadt A und Stadt B in derselben Route habe, war die Tour sehr gut." Diese Erkenntnis speichert er in einem kleinen Notizbuch (den sogenannten Q-Werten).
• Der Clou: Beim nächsten Mal baut er neue Routen, indem er Städte, die er früher erfolgreich zusammengebaut hat, wieder zusammenbringt. Er lernt also aus seinen besten Ideen, statt immer wieder von vorne anzufangen.

2. Der große Pool (Merge)

Der Baumeister wirft viele verschiedene, gute Routen in einen riesigen Pool. Es ist wie ein großer Korb voller fertiger Puzzle-Teile.

• Wenn zwei Routen fast gleich aussehen, behält er nur die kürzere.
• Wenn eine Route viel zu lang ist, wirft er sie weg, denn sie wird uns nie helfen, das Problem zu lösen.
• Alte, nicht mehr genutzte Routen werden langsam aus dem Pool entfernt, damit Platz für frische Ideen bleibt.

3. Der Super-Logiker (Solve)

Jetzt kommt der eigentliche Trick. Anstatt alle Routen selbst zu prüfen (was ewig dauern würde), nimmt der Algorithmus den Pool und sagt zu einem Super-Computer (einem mathematischen Löser): „Hier sind 500 gute Teilstrecken. Baue mir daraus die 10 besten Gesamtrouten, die alle Kunden abdecken und bei denen die längste Route so kurz wie möglich ist."

Der Computer rechnet blitzschnell alle Kombinationen durch und findet die perfekte Zusammenstellung aus dem Pool. Das ist wie ein Puzzle, bei dem du nicht jeden Stein selbst suchst, sondern jemandem gibst, der die fertigen Teile hat und sofort das perfekte Bild zusammenfügt.

4. Das Feinschleifen (Improve)

Selbst die beste Lösung hat noch kleine Macken. Vielleicht ist ein Paket in einer Route etwas umständlich platziert. Der Algorithmus schaut sich die Lösung an und macht kleine Korrekturen:

• Verschieben: Ein Paket von Route A zu Route B schieben, wenn es dort besser passt.
• Tauschen: Zwei Pakete zwischen zwei Routen tauschen.
• Entfernen: Überflüssige Umwege streichen.

5. Warum ist das besser als die alten Methoden?

Früher haben viele Algorithmen wie ein Jäger gearbeitet: Sie haben wild im Wald umhergesucht, hoffen, ein Reh zu finden, und wenn nicht, fangen sie von vorne an. Das ist oft zufällig und unzuverlässig.

Unsere neue Methode (RL-CMSA) ist wie ein erfahrener Architekt:

1. Er lernt aus seinen besten Entwürfen.
2. Er sammelt die besten Bauteile.
3. Er nutzt einen Computer, um die perfekte Kombination zu finden.
4. Er poliert das Ergebnis bis zum Glanz.

Das Ergebnis:
Die Tests zeigen, dass diese Methode besonders dann glänzt, wenn es viele Lieferwagen und viele Kunden gibt. Sie findet schneller Lösungen, die fairer sind (niemand fährt zu weit), und sie ist viel zuverlässiger als die bisherigen Spitzenreiter. Sie macht aus dem Chaos der Lieferplanung eine geordnete, faire und effiziente Sache.

Kurz gesagt: Sie kombiniert die Kreativität eines Lernenden mit der Präzision eines Supercomputers, um sicherzustellen, dass kein Lieferfahrer überarbeitet wird.

Technische Zusammenfassung

Titel: Construct, Merge, Solve & Adapt mit Reinforcement Learning für das Min-Max Multiple Traveling Salesman Problem

1. Problemstellung

Das Paper adressiert das Multiple Traveling Salesman Problem (mTSP), eine Erweiterung des klassischen TSP, bei der $m$ Touren von einem gemeinsamen Depot ausgehen und alle Kunden genau einmal besuchen. Der Fokus liegt auf der Min-Max-Variante.

• Ziel: Minimierung der Länge der längsten Tour unter den $m$ Touren.
• Anwendungskontext: Diese Zielfunktion ist entscheidend für die Arbeitslastausbalancierung (Workload Balance) in Szenarien wie der letzten Meile (Last-Mile Delivery) mit identischen Fahrzeugen, koordinierter Multi-Roboter-Patrouille oder UAV-Einsatzplanung.
• Herausforderung: Das Problem ist NP-schwer. Exakte Algorithmen skalieren nur für kleine Instanzen, während Heuristiken und Metaheuristiken für große Instanzen benötigt werden.

2. Methodik: RL-CMSA

Die Autoren schlagen einen hybriden Ansatz vor, der das Framework Construct, Merge, Solve & Adapt (CMSA) mit Reinforcement Learning (RL) kombiniert. Der Algorithmus iteriert durch sechs Phasen, bis ein Zeitlimit erreicht ist:

A. Construct (Konstruktion)

In dieser Phase werden $n_{solutions}$ Kandidatenlösungen probabilistisch generiert. Der Prozess ist zweistufig:

1. Clustering (Clustering-Phase): Die Städte (ohne Depot) werden in $m$ Cluster (eine pro Fahrzeug) partitioniert.
   • Steuerung durch Q-Werte: Die Zuweisung wird durch gelernte Q-Werte (Paar-Wahrscheinlichkeiten) geleitet, die anzeigen, wie wahrscheinlich es ist, dass zwei Städte in derselben Route liegen.
   • Seeding: Zentren werden mittels einer k-means++-ähnlichen Methode gewählt, wobei die Wahrscheinlichkeit durch die Distanz zum Depot und die Q-Werte gewichtet wird.
   • Zuweisung: Städte werden basierend auf angularer Distanz, Insertionskosten und der durchschnittlichen Q-Kompatibilität mit dem Cluster zugewiesen.
2. Route (Routen-Phase): Für jedes Cluster wird eine Tour mittels einer schnellen Greedy-Insertions-Heuristik erstellt und durch lokale Suche (2-opt und Or-opt) verbessert. Anschließend werden inter-route-Operatoren (Remove, Shift, Swap) angewendet, um die Lösung zu verfeinern.

B. Merge (Zusammenführung)

Die generierten Routen werden in einen Pool von Kandidatenrouten ($R_{cand}$) aufgenommen.

• Deduplizierung: Nur die kürzeste Route für eine bestimmte Menge von besuchten Städten wird behalten.
• Pruning: Routen, die länger als die aktuelle beste maximale Routenlänge sind, werden verworfen.
• Alterung: Jede Route erhält ein "Alter" (initial 0), das im Laufe der Iterationen erhöht wird.

C. Solve (Lösen)

Es wird ein gemischt-ganzzahliges lineares Programm (MILP) als Set-Covering-Problem formuliert.

• Ziel: Auswahl von genau $m$ Routen aus dem Pool $R_{cand}$, sodass jede Stadt mindestens einmal abgedeckt ist und die Länge der längsten ausgewählten Route minimiert wird.
• Solver: Der Teilproblem-Löser (CPLEX) findet die beste Kombination der im Pool vorhandenen Routen. Da Routen überlappen können, ist das Ergebnis noch keine gültige mTSP-Lösung (diese wird im nächsten Schritt korrigiert).

D. Improve (Verbesserung)

Die vom MILP-Löser gefundene Lösung wird durch lokale Suchoperatoren verfeinert, um Überlappungen zu entfernen und die Zielfunktion zu minimieren:

• Remove: Entfernt doppelte Städte aus Routen.
• Shift: Verschiebt eine Stadt von einer Route in eine andere.
• Swap: Tauscht zwei Städte zwischen verschiedenen Routen.
• Die Auswahl der Operatoren erfolgt probabilistisch, wobei Verbesserungen der Hauptzielgröße (maximale Länge) priorisiert werden.

E. Learn (Lernen)

Das Reinforcement Learning aktualisiert die Q-Werte basierend auf den gefundenen Lösungen:

• Co-occurrence: Wenn ein Städtepaar $\{i, j\}$ in einer hochwertigen Lösung (insbesondere in der besten Lösung $R_{best}$) gemeinsam in einer Route vorkommt, wird der Q-Wert erhöht (Reinforcement).
• Anpassung: Q-Werte driften gegen 0 (hohe Wahrscheinlichkeit für gleiche Cluster) oder 1 (geringe Wahrscheinlichkeit), je nachdem, ob das Paar in der besten Lösung vorkam.
• Reset: Bei Stagnation werden die Q-Werte zurückgesetzt, um die Suche zu diversifizieren.

F. Adapt (Anpassung)

Der Pool $R_{cand}$ wird aktualisiert:

• Neue Routen aus $R_{best}$ werden mit Alter 0 eingefügt.
• Routen, die nicht in $R_{best}$ vorkommen, altern.
• Routen, die ein maximales Alter ($age_{max}$) erreichen, werden entfernt. Dies hält den Pool kompakt und aktuell.

3. Wichtige Beiträge

• Hybride Architektur: Kombination von konstruktiver Heuristik, exakter Optimierung (MILP) und Reinforcement Learning zur Steuerung der Konstruktion.
• RL-gesteuerte Clustering: Die Nutzung von Q-Learning, um die Wahrscheinlichkeit zu steuern, dass Städte in derselben Route landen, ist ein innovativer Ansatz für das mTSP.
• Robustheit: Der Algorithmus zeigt eine hohe Stabilität über viele Läufe hinweg, da er die Suche in vielversprechende Regionen des Suchraums lenkt.

4. Ergebnisse

Die Leistung von RL-CMSA wurde mit einem State-of-the-Art Hybrid Genetic Algorithm (HGA) verglichen.

• Testdaten: Zufallsgenerierte Instanzen ($n \in \{50, 100, 200\}$) und TSPLIB-Instanzen (eil51, berlin52, eil76, rat99).
• Variablen: Anzahl der Fahrzeuge $m$ variierte zwischen 1%, 5%, 10% und 15% der Stadtanzahl.
• Ergebnisse auf Zufallsinstanzen:
  • RL-CMSA liefert in den meisten Fällen bessere durchschnittliche Zielwerte als HGA.
  • Die Robustheit (Häufigkeit, die beste Lösung zu finden) ist bei RL-CMSA deutlich höher, insbesondere bei größeren Instanzen ($n=200$) und höherer Fahrzeuganzahl ($m$).
  • Bei sehr kleinen $m$ (z.B. 1%) und großen $n$ ist HGA manchmal schneller oder gleichauf, da die Sub-Probleme für den MILP-Löser bei wenigen, langen Routen schwieriger zu kombinieren sind.
  • Mit steigendem $m$ verbessert sich die Leistung von RL-CMSA signifikant, da kürzere Routen mehr Kombinationsmöglichkeiten im MILP bieten.
• Statistische Signifikanz: Wilcoxon-Vorzeichen-Rang-Tests bestätigen, dass RL-CMSA in den meisten Konfigurationen (insbesondere für $n=100$ und $n=200$ mit $m \ge 5\%$) statistisch signifikant überlegen ist.
• Suchtrajectorien (STN): Die Analyse der Suchpfade zeigt, dass HGA eine breitere, aber weniger zielgerichtete Suche durchführt, während RL-CMSA schnell in eine hochwertige Region konvergiert und dort konsistente Ergebnisse liefert.
• TSPLIB: Auf den Standard-Instanzen erreicht RL-CMSA in 5 von 16 Konfigurationen bessere Ergebnisse als HGA und ist in den meisten Fällen schneller.

5. Bedeutung und Ausblick

Das Paper demonstriert, dass die Integration von Reinforcement Learning in das CMSA-Framework eine effektive Strategie zur Lösung komplexer kombinatorischer Optimierungsprobleme wie des Min-Max mTSP ist. Der Ansatz balanciert Exploration (durch diverse Konstruktion) und Exploitation (durch exakte Lösung und lokale Suche) erfolgreich.

Zukünftige Arbeiten sollen die Route-Pools durch große Nachbarschaften erweitern, das RL-Schema auf höherordentliche Routenmerkmale ausweiten und den Ansatz auf allgemeinere Routing-Probleme mit zusätzlichen Constraints übertragen.