Neues Lernverfahren löst das Min‑Max Multiple Traveling Salesmen Problem

Das Min‑Max Multiple Traveling Salesmen Problem (m³‑TSP) verlangt, mehrere Routen so zu koordinieren, dass die längste Strecke minimiert wird. Da das Problem NP‑schwer ist, stoßen klassische Optimierer bei größeren Instanzen schnell an ihre Grenzen. Lernbasierte Ansätze haben deshalb an Bedeutung gewonnen, weil sie in kurzer Zeit qualitativ hochwertige Näherungslösungen liefern können.

In der vorliegenden Arbeit wird ein neues Zwei‑Stufen‑Framework namens Generate‑and‑Split (GaS) vorgestellt. Dabei wird ein Reinforcement‑Learning‑Modell mit einem optimalen Split‑Algorithmus in einem gemeinsamen Trainingsprozess verknüpft. Der Split‑Algorithmus arbeitet nahezu linear in der Anzahl der Städte und garantiert in euklidischem Raum die optimale Aufteilung einer vorgegebenen Route. Um die teilweise Beobachtbarkeit des Problems zu adressieren, nutzt das Modell eine LSTM‑erweiterte Architektur.

Umfangreiche Experimente zeigen, dass GaS die bisherigen lernbasierten Verfahren deutlich übertrifft – sowohl in der Lösungsqualität als auch in der Übertragbarkeit auf neue Problemgrößen. Das Ergebnis unterstreicht, dass die Kombination aus lernbasiertem Pfad‑Generieren und einem optimalen Split‑Algorithmus ein vielversprechender Ansatz für komplexe logistische Optimierungsaufgaben ist.