Technische Samenvatting: LLM-as-Trainer voor Multi-Task Vehicle Routing Solvers

1. Probleemstelling

Vehicle Routing Problems (VRPs) omvatten een breed scala aan combinatorische optimalisatievarianten (bijv. Capacitated VRP, VRP met tijdvensters, Backhaul-restricties). Hoewel neurale solvers gebaseerd op deep reinforcement learning veelbelovend zijn gebleken voor het efficiënt genereren van haalbare oplossingen, vereisten vroege benaderingen doorgaans het trainen van aparte modellen voor elke specifieke combinatie van restricties. Dit gebrek aan schaalbaarheid is problematisch gezien het bestaan van meer dan 60 VRP-varianten in de praktijk.

Multi-task neurale solvers beogen deze varianten binnen één enkel model te verenigen om apart trainen te vermijden. Echter, een aanzienlijke uitdaging blijft bestaan: verschillende VRP-varianten hebben variërende niveaus van optimalisatiecomplexiteit. Bestaande multi-task trainingsmethoden coördineren gedeelde parameters vaak via loss- of gradiëntbalancering, maar missen expliciete fasegewijze feedback met betrekking tot de relatieve prestaties van verschillende taken tijdens de training. Bij consequent gevolg kunnen modellen bevooroordeeld raken naar makkelijkere varianten, wat de algehele oplossingskwaliteit beperkt. Hoewel meta-learning adaptief trainen biedt, leunt dit doorgaans op bi-level optimalisatie, wat aanzienlijke computationele kosten en extra gradiëntupdates met zich meebrengt.

2. Methodologie: LLM-as-Trainer (LaT)

De auteurs stellen LaT (LLM-as-Trainer) voor, een plug-and-play trainingsparadigma dat een vooraf getraind Large Language Model (LLM) gebruikt als een externe trainer om de gezamenlijke training van multi-task neurale solvers te reguleren. De kerninnovatie ligt in het gebruik van het LLM om cross-task validatiemetrieken te analyseren en een fasegewijze sturingsvector te genereren zonder de architectuur van de solver aan te passen of bi-level optimalisatie te vereisen.

2.1 Trainingsframework

LaT werkt op een standaard autoregressieve Transformer encoder-decoder architectuur (bijv. POMO, CaDA, ReLD), maar introduceert een lichtgewicht zijtak (side branch) bij elke encoderlaag. Het proces volgt deze stappen:

1. Cross-Task Validatie: Op vooraf bepaalde intervallen (elke $T_{ctrl}$ epochs) wordt de huidige policy geëvalueerd op een vaste validatieset voor alle 16 VRP-varianten.
2. Toestandsconstructie: Het systeem berekent de relatieve referentiekloof ($\eta_{r,k}$) voor elke taak $k$ ten opzichte van een vooraf berekende referentieoplossing (gegenereerd door HGS of OR-Tools). Het houdt ook de verandering in deze kloof ($\Delta \eta_{r,k}$) bij en beheert een geschiedenis van recente validatiegegevens.
3. Generatie van LLM-sturing: Deze gestructureerde trainingsstatus (inclusief taakrestricties, huidige kloven, veranderingen in kloven en historische trends) wordt geformatteerd in een prompt en gevoed aan een bevroren, vooraf getraind LLM (specifiek GLM-5.1 in de experimenten). Het LLM genereert een 5-dimensionale sturingsvector $\gamma_r = [\gamma_C, \gamma_O, \gamma_B, \gamma_L, \gamma_{TW}]$, waarbij elke dimensie overeenkomt met één van de vijf elementaire restricties (Capaciteit, Open Route, Backhaul, Route-lengte, Tijdvenster).
4. Injectie in de Solver: Tijdens daaropvolgende trainingsepochs wordt de sturingsvector $\gamma_r$ geconcateneerd met de huidige binaire restrictievector $z_k$ van de taak. Deze gecombineerde vector wordt geïnjecteerd in een lichtgewicht zijtak bij elke encoderlaag. De output van de zijtak wordt toegevoegd aan de backbone-output via een leerbare coëfficiënt $\alpha$.
5. Policy Optimalisatie: De solver wordt bijgewerkt met standaard policy gradient methoden (bijv. POMO-stijl). Het LLM ontvangt geen gradiënten en wordt niet aangeroepen tijdens de inferentie.

2.2 Inferentie

Na voltooiing van de training wordt de uiteindelijke sturingsvector vastgezet en wordt het LLM verwijderd. De ingezette solver behoudt alleen de geleerde zijtakken en de vaste sturingsvector, wat geen LLM API-aanroepen vereist en een verwaarloosbare computationele overhead introduceert.

3. Belangrijkste Bijdragen

Het artikel benadrukt drie primaire bijdragen:

• Nieuw Trainingsparadigma: LaT is het eerste trainingsparadigma dat een vooraf getraind LLM introduceert als een externe trainer specifiek voor multi-task voertuigroutering-solvers. Het incorporeert expliciet de cross-task validatieprestaties in de policy optimalisatie-loop.
• Lichtgewicht Sturingsmechanisme: De auteurs ontwerpen een mechanisme dat een fasegewijze sturingsvector genereert vanuit validatiemetrieken. Deze vector wordt gecombineerd met taakrestricties en geïnjecteerd in encoderlagen, waardoor extra trainingsinformatie wordt geboden zonder de computationele last van bi-level optimalisatie of inner-loop updates.
• Plug-and-Play Generaliteit: De methode is ontworpen om te worden geïntegreerd met bestaande neurale solvers (gedemonstreerd op ReLD en CaDA backbones) zonder de kern van de autoregressieve policy of decoderarchitectuur te wijzigen.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op 16 VRP-varianten gevormd uit vijf elementaire restricties, met probleemgroottes van 50 en 100 knopen.

• Prestaties op getrainde varianten: LaT-varianten (LaT-ReLD en LaT-CaDA) behaalden consistent lagere relatieve referentiekloven vergeleken met hun backbone-modellen over alle zes de trainingsvarianten. Zo verminderde LaT-CaDA de gemiddelde kloof op getrainde varianten van 1,810% naar 1,669%.
• Zero-Shot Generalisatie: Op de resterende tien ongeziene VRP-varianten toonde LaT een sterke generalisatie. LaT-CaDA presteerde beter dan de baseline CaDA in alle 20 ongeziene settings (50 en 100 knopen), waarbij de gemiddelde kloof daalde van 5,490% naar 5,067%.
• Vergelijking met SOTA: LaT-varianten behaalden de laagste kloven in de meerderheid van de settings vergeleken met andere state-of-the-art multi-task solvers (bijv. MVMoE, CCL, PoMtVRS).
• Efficiëntie: De methode introduceerde een verwaarloosbare overhead in de inferentietijd (3–4 seconden voor 50-knopen instanties), vergelijkbaar met de backbones. De trainingstijd nam met minder dan 1,5% toe door periodieke LLM-aanroepen.
• Ablatie-studies:
  • Het verwijderen van de door het LLM gegenereerde sturing (vervangen door een vaste vector) verslechterde de prestaties, wat de waarde van de adaptieve sturing bevestigt.
  • Het verwijderen van de taakrestrictievector verslechterde de prestaties ook, wat de noodzaak van expliciete taakinformatie aantoont.
  • Het vervangen van het LLM door een MLP-gebaseerde sturingsgenerator resulteerde in hogere kloven, wat suggereert dat de verbetering voortkomt uit de redeneercapaciteiten van het LLM in plaats van enkel een grotere modelcapaciteit.
  • Injectie van sturing na elke encoderlaag (LaT EncAll) bleek superieur aan injectie enkel bij de input, output of decodercontext.

5. Betekenis en Claims

Het artikel claimt dat LaT effectief de beperking van bestaande multi-task solvers aanpakt door expliciet te reageren op de huidige verschillen in cross-task prestaties. Door een bevroren LLM te gebruiken als een periodieke "trainer", biedt de methode fasegewijze feedback die de neurale solver stuurt om het leren over varianten van verschillende moeilijkheidsgraden te balanceren.

De auteurs benadrukken dat LaT de oplossingskwaliteit verbetert op zowel getrainde als ongeziene varianten, terwijl de efficiëntie van de inferentie behouden blijft. Ze merken op dat hoewel LaT consistente verbeteringen laat zien, de effectiviteit kan afhangen van de specifieke backbone-architectuur (bijv. LaT-CaDA vertoonde meer consistente winst dan LaT-ReLD op ongeziene varianten). Het artikel concludeert dat deze aanpak een algemeen en effectief trainingsparadigma biedt voor complexe scenario's met meerdere restricties, waarbij toekomstig werk bredere restrictiesets en meer consistente sturingsmechanismen over diverse solvers kan verkennen.