Neues Verfahren verbessert neuronale Optimierer bei realen Routenproblemen

Neurale Kombinatorische Optimierung (NCO) hat in den letzten Jahren enorme Fortschritte erzielt und kann inzwischen komplexe synthetische Routingaufgaben zuverlässig lösen. Dennoch bleibt die Übertragbarkeit dieser Modelle auf echte VRP‑Probleme – etwa die bekannten Benchmark‑Sätze von TSPLib und CVRPLib – stark eingeschränkt. Das neue Verfahren EvoReal adressiert dieses Problem, indem es synthetische Instanzen erzeugt, die strukturell den realen Daten sehr ähnlich sind.

EvoReal kombiniert einen evolutionären Generator mit großen Sprachmodellen (LLMs). Die LLMs liefern dabei Richtlinien, damit die erzeugten Instanzen nicht nur zufällig, sondern gezielt realistische Muster aufweisen. Durch diese gezielte Synthese erhält das Modell eine reichhaltige, strukturierte Trainingsbasis, die die Vielfalt echter Routenprobleme besser abbildet.

Nach der Erzeugung der synthetischen Daten werden vortrainierte NCO‑Modelle zunächst an diese neuen Verteilungen angepasst und anschließend direkt auf den Benchmark‑Instanzen feinjustiert. Dieser progressive Ansatz führt zu einer deutlich verbesserten Generalisierung: Der Abstand zu optimalen Lösungen sinkt auf lediglich 1,05 % für TSPLib‑Aufgaben und 2,71 % für CVRPLib‑Aufgaben – ein bemerkenswertes Ergebnis über ein breites Spektrum an Problemgrößen hinweg.