Lösung des Multi-Depot-Geschlossenen-Pfad-Mehrfach-Traveling-Salesman-Problems mittels k-means++-hierarchischem Clustering und neuronalen kombinatorischen Netzen

Schlauere Routen für viele Fahrer

Von Paketlieferwagen über Lieferdrohnen bis hin zu Konvois für Katastrophenhilfe stehen Planer oft vor einem Rätsel: Wie können mehrere Fahrzeuge, die an unterschiedlichen Standorten starten, die Aufgabe teilen, Hunderte oder Tausende von Stopps zu besuchen, ohne Zeit oder Treibstoff zu verschwenden? Dieses Paper stellt eine neue Methode zum Zerlegen und Beherrschen dieses Problems vor, die einen klassischen Clustering-Trick mit einem modernen neuronalen Netzwerk kombiniert, sodass Computer effiziente Routen in Sekunden statt Minuten oder Stunden erstellen können.

Die Herausforderung vieler Depots und vieler Fahrer

Die Studie beschäftigt sich mit einer anspruchsvollen Variante des bekannten Traveling-Salesperson-Problems, bei der statt eines Reisenden viele unterwegs sind, jeweils startend und endend an ihrem eigenen Depot. Gemeinsam müssen sie jede Stadt genau einmal besuchen und dabei die Gesamtdistanz möglichst kurz halten. Dieses Szenario spiegelt Aufgaben wie die Koordination von Lkw-Flotten, Roboterguppen oder Luftdrohnen wider, die sich die Arbeit in einer Region teilen. Da die Anzahl möglicher Routenkombinationen mit wachsender Zahl an Städten und Fahrern explosionsartig zunimmt, werden exakte Methoden zu langsam, und traditionelle Suchverfahren geraten oft an ihre Grenzen oder müssen die Lösungsqualität zugunsten von Geschwindigkeit opfern.

Grenzen klassischer Suche und einfacher Aufteilung

Jahrelang setzten Ingenieure auf „Metaheuristiken“ wie genetische Algorithmen, Ameisenkolonien oder Partikelschwärme. Diese ahmen natürliche Prozesse nach, um viele Kandidatenrouten zu durchsuchen und schrittweise zu verbessern. Sie sind zwar flexibel, haben aber zwei große Nachteile: Es gibt keine festen Garantien zur Qualität einer Lösung, und bei großen Karten können sie sehr langsam sein, besonders wenn für jede neue Aufgabe die Suche neu gestartet werden muss. Eine verbreitete Beschleunigung ist, die Städte zunächst mit Werkzeugen wie k-means in Regionen zu clustern und dann innerhalb jedes Clusters ein kleineres Problem zu lösen. Zwar hilft diese Split-then-solve-Strategie, doch die Endqualität bleibt vom zugrunde liegenden Suchverfahren abhängig, und das Streben nach besseren Routen führt meist zu noch längeren Laufzeiten.

Ein Netzwerk das Routen lernt — und wie man es skaliert

In den letzten Jahren setzte sich eine andere Idee durch: Ein neuronales Netzwerk so trainieren, dass es direkt gute Routen ausgibt. Nach dem Lernen an vielen Beispielkarten kann ein solches Netzwerk eine komplette Tour in einem einzigen Vorwärtsdurchlauf vorschlagen, ähnlich wie ein Sprachmodell einen Satz formuliert. Diese neuronalen Löser funktionieren bei Einzelfahrer-Problemen moderater Größe beeindruckend gut, stolpern jedoch, wenn sie viele Fahrer koordinieren sollen oder wenn die Seite der Städte deutlich größer ist als im Training. Der zentrale Schritt der Autoren besteht darin, einen solchen neuronalen Löser in einen sorgfältigen zweistufigen Prozess einzubetten, der eine riesige Multi-Fahrer-Aufgabe in viele kleinere, vertraute Teilprobleme umformt, die das Netzwerk komfortabel bewältigen kann.

Wie die zweiphasige Methode funktioniert

Die vorgeschlagene Methode, KHC-NCN genannt, beginnt mit einer verbesserten Version von k-means-Clustering, um Städte Depots und Fahrern zuzuweisen. Wenn eine resultierende Region zu viele Städte enthält, als dass der neuronale Löser sie zuverlässig bearbeiten könnte, teilt die Methode die Region automatisch weiter in kleinere Stücke, die jeweils etwa die Größe haben, die das Netzwerk während des Trainings gesehen hat. Die Koordinaten in jedem Stück werden in ein standardisiertes Quadrat skaliert, sodass sie dem Trainingsdatensatz noch stärker ähneln. Das neuronale Netzwerk erzeugt dann für jedes kleine Stück eine Route. Abschließend verbindet ein Merge-Schritt diese Teilrouten zu einer einzigen Schleife pro Fahrer, wobei einfache geometrische Regeln genutzt werden, um Stücke dort zu verknüpfen, wo dies den geringsten zusätzlichen Abstand verursacht.

Geschwindigkeit und Qualität auf echten Benchmark-Karten

Die Autoren testen ihre Methode an einer breiten Sammlung standardisierter Karten aus einem öffentlichen Benchmark-Set, das in der Routing-Forschung weit verbreitet ist. Sie vergleichen gegen viele etablierte Suchtechniken sowie gegen einen führenden handentwickelten Solver und einen anderen neuronalen Ansatz. In 44 Testfällen mit verschiedenen Kartengrößen und Fahrerzahlen findet ihre Methode in nahezu drei Vierteln der Fälle kürzere Gesamtstrecken und ist dabei deutlich schneller, oft um mehrere Größenordnungen. Sie schlägt sich besonders gut, wenn die Anzahl der Städte in die Hunderte oder Tausende wächst, also dort, wo viele klassische Ansätze langsamer werden oder schlechtere Routen liefern.

Was das für reales Routing bedeutet

Einfach gesagt zeigt die Studie, dass es sich lohnt, ein schnelles neuronales Netzwerk viele kleine, gut geformte Teilprobleme lösen zu lassen, statt viel Zeit für ein einziges großes Problem aufzuwenden. Indem Städte so geclustert werden, dass sie in die Komfortzone des Netzwerks passen, und die Teilantworten geschickt kombiniert werden, liefert die Methode Routen, die sowohl kurz als auch schnell zu berechnen sind. Für Anwendungen wie Logistik, Multi-Roboter-Planung und Notfalleinsatz weist das auf einen praktischen Weg hin, nahezu in Echtzeit Routenvorschläge zu erzeugen, die Fahrzeuge und Energie besser nutzen als viele bestehende Werkzeuge.

Zitation: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Schlüsselwörter: Fahrzeugrouting, Neuronale Netze, Clustering, Optimierung, Logistik