🤖 AI

Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation

Dit artikel introduceert EvoReal, een framework dat LLM-gestuurde evolutionaire synthese benut om structureel realistische trainingsinstanties te genereren en neurale solvers progressief aan te passen, waardoor de generalisatiekloof tussen synthetische data en real-world routing benchmarks zoals TSPLib en CVRPLib aanzienlijk wordt verkleind.

Oorspronkelijke auteurs: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Gepubliceerd 2026-01-30

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Probleem: De "Wieltjes" vs. De "Echte Weg"

Stel je voor dat je een robot leert om de beste bezorger ter wereld te worden.

De Huidige Situatie:
Op dit moment leren we deze robots (genaamd Neural Solvers) met behulp van "wieltjes". We genereren miljoenen nep-bezorgroutes op een computer waar de huizen perfect uitgelijnd zijn in een net raster, zoals op een schaakbord. De robot wordt echt goed in het oplossen van deze perfecte, rasterachtige puzzels.

Het Probleem:
Wanneer je die robot de echte wereld in stuurt, crasht hij. Echte steden zijn geen rasters. Ze hebben clusters van huizen, kronkelende wegen en vreemde patronen. De robot, die alleen getraind is op perfecte rasters, raakt in de war en maakt verschrikkelijke bezorgroutes. Dit wordt de generalisatiekloof genoemd. Het is alsof je iemand leert zwemmen in een rustig, leeg zwembad, om diegene vervolgens in een stormachtige oceaan met golven en stromingen te gooien.

De Oplossing: EvoReal (De "Slimme Simulator")

De auteurs van dit paper hebben een nieuw systeem ontwikkeld genaamd EvoReal. In plaats van de robot gewoon in de echte oceaan te gooien, hebben ze een "Slimme Simulator" gebouwd die de robot leert hoe hij met de storm moet omgaan voordat hij het zwembad verlaat.

Zo werkt het, stap voor stap:

1. De "Architect" (De LLM)

Het team heeft een Large Language Model (LLM) gebruikt—denk aan een superintelligente, creatieve architect. De taak van deze architect is niet om de vrachtwagen te besturen; het is om de trainingscursussen te ontwerpen.

Normaal gesproken maken we gewoon willekeurige trainingscursussen. Maar de LLM krijgt de opdracht om naar echte bezorgkaarten te kijken (zoals de beroemde TSPLib en CVRPLib benchmarks) en te zeggen: "Hm, echte steden hebben deze specifieke patronen: sommige gebieden zijn druk, andere zijn verspreid, en sommige hebben herhalende vormen."

2. De "Evolutionaire Gym" (Generator Evolutie)

De LLM ontwerpt niet zomaar één cursus; het draait een evolutionaire gym.

Generatie: De LLM schrijft code om nep-bezorgroutes te creëren die er precies uitzien als echte steden (met clusters, gaten en vreemde vormen).
Testen: Het test deze nep-routes op de robot.
Reflectie & Verbetering: Als de robot moeite heeft met een specifiek type nep-route, kijkt de LLM naar de code en zegt: "Ah, deze generator maakte de clusters niet compact genoeg," en herschrijft de code om de volgende batch nep-routes nog realistischer te maken.
Resultaat: In de loop van de tijd evolueert de LLM een "generator" die synthetische data creëert die statistisch gezien de echte wereld nabootst.

3. De "Progressieve Training" (De Ladder)

Zodra de LLM deze perfecte "echt-als-de-werkelijkheid-lijkende" trainingscursussen heeft gebouwd, begint de robot niet direct op het moeilijkste niveau. Hij klimt een ladder op:

Fase 1 (De Brug): De robot wordt eerst getraind op de nieuwe, realistische synthetische data van de LLM. Hij leert om te gaan met clusters en onregelmatige patronen in een veilige, gesimuleerde omgeving. Het is alsof hij oefent in een zwembad met kunstmatige golven.
Fase 2 (Het Echte Werk): Zodra de robot zelfverzekerd is, krijgt hij een laatste, korte trainingssessie op de daadwerkelijke real-world benchmark problemen. Omdat hij in Fase 1 al de "vibe" van echte steden heeft geleerd, past hij zich direct aan.

De Resultaten: Van "Goed in Schaken" naar "Grandmaster van de Stad"

Het paper testte dit op twee beroemde sets van real-world routingproblemen (TSPLib en CVRPLib).

Vóór EvoReal: De beste AI-modellen waren als studenten die alleen studeerden voor een specifiek type wiskundetoets. Wanneer ze een real-world probleem zagen, daalde hun score aanzienlijk (soms met 30% of meer).
Ná EvoReal: De modellen die met deze methode getraind werden, werden ongelooflijk sterk.
- Op de TSPLib (Traveling Salesman) benchmarks kromp de kloof tussen hun oplossing en de perfecte oplossing tot slechts 1,05%.
- Op de CVRPLib (Vehicle Routing) benchmarks kromp de kloof tot 2,71%.

De Belangrijkste Les:
Het paper stelt dat door een LLM te gebruiken om betere trainingsdata te evolueren (in plaats van alleen de robot zelf te evolueren), zij de kloof tussen nep en echt hebben overbrugd. De robot leerde te generaliseren omdat hij werd getraind op "nep" data die precies aanvoelde als "echte" data.

Samenvattende Analogie

De Oude Manier: Een piloot trainen om te vliegen in een simulator zonder wind, om hem vervolgens in een orkaan te sturen.
De EvoReal Manier: Een AI gebruiken om een simulator te ontwerpen die de turbulentie, windstoten en stormen van een orkaan perfect nabootst. De piloot traint in deze hyperrealistische simulator en vliegt daarna perfect in het echte vliegtuig.

Het paper bewijst dat betere generatie van trainingsdata (gestuurd door AI) een krachtigere manier is om deze robots te verbeteren dan simpelweg de robots zelf aanpassen.

Technische Samenvatting: Het overbruggen van synthetische en echte routeproblemen via LLM-gestuurde instantiegeneratie en progressieve adaptatie

Probleemstelling

Methoden voor Neurale Combinatorische Optimalisatie (NCO) hebben state-of-the-art prestaties behaald op synthetische Vehicle Routing Problems (VRPs), met name die met uniform verdeelde knopen. Echter, er blijft een aanzienlijke generalisatiekloof bestaan wanneer deze modellen worden toegepast op real-world routing-scenario's, zoals die in de TSPLib en CVRPLib benchmarks. Bestaande neurale solvers worstelen met het aanpassen aan de heterogene, niet-uniforme structurele patronen die inherent zijn aan authentieke datasets. Hoewel Large Language Models (LLMs) veelbelovend zijn gebleken bij het evolueren van heuristieken en het direct oplossen van Combinatorial Optimization Problems (COPs), falen ze vaak bij middelgrote tot grote instanties (bijv. >50 knopen) vanwege contextbeperkingen en coherentieproblemen bij het verwerken van uitgebreide tekstuele beschrijvingen. Bijgevolg is er behoefte aan een framework dat de distributieverschuiving tussen synthetische trainingsdata en real-world benchmarks overbrugt zonder architecturale wijzigingen aan de solvers te vereisen of uitsluitend te vertrouwen op directe fine-tuning, wat vaak beperkte verbeteringen oplevert.

Methodologie: EvoReal

De auteurs stellen EvoReal voor, een datacentrisch framework dat LLMs gebruikt om data-generatoren te evolueren in plaats van de routingproblemen direct op te lossen. Het framework bestaat uit twee primaire componenten: een LLM-gestuurd evolutionair module voor instantie-synthese en een progressieve fine-tuning strategie voor modeladaptatie.

1. LLM-gestuurde Evolutionaire Instantie-synthese

In plaats van LLMs te prompten om TSP- of CVRP-instanties op te lossen, prompten zij in EvoReal om code-gebaseerde data-generatoren te genereren die synthetische instanties produceren die de real-world distributies nabootsen.

Generator Representatie: Elke generator wordt gedefinieerd door een functiebeschrijving, een code-implementatie (gebaseerd op PyTorch) en een fitness score.
Structurele Uitlijning: Het evolutieproces beoogt de divergentie te minimaliseren tussen de synthetische distributie gegenereerd door de LLM ( $D(h_\phi(Z))$ ) en de doelgerichte real-world distributie ( $D_{real}$ ). De divergentie wordt gemeten via proxy-metrieken, specifiek de gemiddelde optimaliteitskloof op een validatieset.
Modularisering en Categorisering: Om diverse structurele patronen te vangen, wordt de validatieset (TSPLib/CVRPLib) gesegmenteerd in categorieën op basis van statistische kenmerken:
- FFT Energie: Meet globale periodiciteit of herhaling.
- NN-Ratio (Coefficient of Variation): Meet de variatie in nearest-neighbor afstanden om onderscheid te maken tussen grid-achtige, willekeurige en geclusterde lay-outs.
- Op basis van deze metrieken worden instanties gecategoriseerd in typen (bijv. S1 voor repetitieve structuren, S2 voor zwak-geclusterde/grid-achtige structuren, S3 voor lokale aggregaties). Gespecialiseerde generatoren worden geëvolueerd voor elk type.
Evolutionair Proces: Het framework past de ReEvo (Reflective Evolution) benadering aan met specifieke modificaties:
- Rank-gebaseerde Selectie: Selecteert nakomelingen op basis van fitness-ranking om convergentie te versnellen.
- Vertraagde Selectie: Selectie vindt plaats na crossover en mutatie om voortijdige eliminatie van diverse kandidaten te voorkomen.
- Reflectiemechanismen: Gebruikt short-term reflectie (het vergelijken van ouder-paren) en long-term reflectie (het destilleren van inzichten om mutatie te sturen) om de generatoren iteratief te verfijnen.

2. Progressieve Fine-Tuning Strategie

Zodra optimale generatoren zijn geïdentificeerd, ondergaan de vooraf getrainde neurale solvers (POMO en LEHD) een tweefasig progressief fine-tuning proces om de synthetisch-realistische kloof te overbruggen:

Fase Eén (Structurele Adaptatie): Het model wordt gefinetuned op grootschalige synthetische data gegenereerd door de geëvolueerde LLM-gestuurde generatoren. In deze fase wordt het model blootgesteld aan diverse, TSPLib-stijl structurele patronen (gemengde distributies van S1, S2, S3) zonder de modelarchitectuur te wijzigen. Het doel is om de interne representaties van het model uit te lijnen met de structurele priors van real-world data.
Fase Twee (Directe Adaptatie): Het model, dat nu is aangepast aan diverse structuren, wordt verder gefinetuned direct op werkelijke benchmark-instanties (TSPLib/CVRPLib). Deze fase stelt het model in staat om te transformeren van "gemakkelijke" synthetische taken naar "moeilijke" real-world gevallen, waardoor de uiteindelijke prestatiekloof effectief wordt verkleind.

Belangrijkste Bijdragen

EvoReal Framework: De introductie van een nieuw framework dat LLMs gebruikt om data-generatoren te evolueren in plaats van solvers. Deze benadering synthetiseert structureel realistische VRP-instanties die statistisch gezien de real-world distributies nabootsen, wat de kernoorzaak van de generalisatiekloof aanpakt.
Progressieve Fine-Tuning Strategie: Een tweefasige adaptatiestrategie die eerst neurale solvers uitlijnt met diverse, door LLM geëvolueerde distributies en deze vervolgens verfijnt op real benchmark data. Dit maakt effectieve domeinadaptatie mogelijk zonder architecturale wijzigingen, waarbij het superieur is aan directe fine-tuning op enkel real data.
State-of-the-Art Prestaties: Het framework demonstreert significante verbeteringen in generalisatie over een breed spectrum van probleemgroottes op de TSPLib en CVRPLib benchmarks, waarbij nieuwe state-of-the-art resultaten voor neurale solvers worden behaald.

Experimentele Resultaten

De auteurs evalueerden EvoReal op 70 TSPLib problemen en 100 CVRPLib SetX problemen, waarbij ze werden vergeleken met klassieke solvers (Concorde, LKH-3, ORTools) en diverse neurale baselines (POMO, LEHD, SGBS, CNF, etc.).

TSPLib Prestaties:
- LEHD (onze methode) met 50 RRC iteraties bereikte een algehele optimaliteitskloof van 1,05% op TSPLib, wat aanzienlijk beter presteert dan andere learning-based methoden en de kloof tot Concorde verkleint.
- POMO (onze methode) reduceerde de algehele kloof naar 11,59%, een substantiële verbetering ten opzichte van de vooraf getrainde POMO (26,66%).
- De methode toonde bijzondere kracht op grootschalige instanties (1000–5000 knopen), waar traditionele neurale solvers doorgaans significant degraderen.
CVRPLib Prestaties:
- LEHD (onze methode) bereikte een algehele kloof van 2,71% op CVRPLib SetX, waarmee het alle andere neurale solvers overtreft en concurrerend blijft met ORTools.
- De progressieve fine-tuning strategie verminderde de prestatieverschillen tussen kleine en grote instanties opvallend.
Ablatie-studies:
- Het verwijderen van ofwel Fase 1 of Fase 2 van de fine-tuning strategie resulteerde in een verslechterde prestatie, wat de noodzaak van de progressieve aanpak bevestigt.
- Het vergelijken van geëvolueerde generatoren met naïeve distributie-generatoren (Gaussian, Beta, etc.) toonde aan dat de door LLM geëvolueerde generatoren consistent lagere optimaliteitskloven bereikten, wat hun vermogen valideert om complexe structurele kenmerken te vangen.
- Het framework bleek robuust over verschillende LLMs, waarbij OpenAI o3 de beste generatorprestaties opleverde.

Betekenis en Claims

Het artikel claimt dat EvoReal succesvol de generalisatiekloof tussen synthetische en real-world routingproblemen overbrugt door de focus te verschuiven van het evolueren van solvers naar het evolueren van data-distributies. De auteurs benadrukken dat hun aanpak:

Automatisering van Ontdekking: Het maakt de automatische ontdekking van data-generatoren mogelijk die aansluiten bij real-world structurele priors, een taak die moeilijk te bereiken is met handmatige heuristische vormgeving.
Efficiëntie: Het behaalt deze winsten zonder dat kostbare hertraining vanaf nul of architecturale wijzigingen aan bestaande SOTA neurale solvers nodig zijn.
Schaalbaarheid: De methode is effectief over een breed scala aan probleemgroottes, waarbij specifiek wordt ingegaan op de degradatie van neurale solvers op grootschalige instanties waar zij voorheen faalden.
Superioriteit boven Directe Fine-Tuning: De resultaten tonen aan dat het adapteren van modellen via geëvolueerde synthetische distributies (Fase 1) vóór directe fine-tuning (Fase 2) betere generalisatie oplevert dan het direct fine-tunen op real data, wat suggereert dat de "curriculum" van structurele adaptatie cruciaal is voor robuustheid.

De auteurs concluderen dat deze generator-gebaseerde adaptatiepipeline een veelbelovende richting biedt voor het verbeteren van de praktische toepasbaarheid van NCO-methoden in real-world logistiek en transportscenario's.