Offline Decision Transformers übertreffen klassische Heuristiken beim Travelling Salesman Problem

Neurale Ansätze zur kombinatorischen Optimierung, wie das Travelling Salesman Problem, sind in der Industrie von großer Bedeutung, bleiben jedoch NP-schwer. Traditionelle Methoden der Online‑Reinforcement‑Learning‑Optimierung erschweren die praktische Umsetzung und nutzen das umfangreiche Wissen aus klassischen Algorithmen nicht vollständig aus.

Die neue Studie nutzt das Offline‑RL‑Framework Decision Transformer, um aus Datensätzen bestehender Heuristiken zu lernen. Durch die Integration eines Pointer Networks wird die variablene Aktionsraumgröße bei der Knotenauswahl effizient gehandhabt, während Expectile‑Regression eine optimistische Abschätzung des Return‑to‑Go ermöglicht – ein entscheidender Faktor bei stark variierenden optimalen Werten.

Experimentelle Ergebnisse zeigen, dass der Ansatz konsequent bessere Touren liefert als die vier klassischen Heuristiken, auf denen er trainiert wurde. Damit demonstriert die Arbeit das enorme Potenzial von Offline‑RL, vorhandenes Domänenwissen nicht nur zu replizieren, sondern zu übertreffen.