Technische Samenvatting: Leren met Vooruitzicht (MnLP)

Probleemstelling

Vehicle Routing Problems (VRP's), waaronder het Traveling Salesman Problem (TSP) en het Capacitated Vehicle Routing Problem (CVRP), zijn NP-moeilijke uitdagingen die wijdverbreid zijn in logistiek en industriële planning. Hoewel neurale routingbeleid, met name die gebaseerd op Transformer-architecturen, zijn opgekomen als efficiënte alternatieven voor traditionele heuristieken, staan huidige trainingsparadigma's voor een fundamentele beperking.

De meeste toegepaste leerbenaderingen (SL) voor neurale routing vertrouwen op voorspelling van de volgende knoop. In dit paradigma wordt het model getraind om uitsluitend de directe volgende knoop in een toer te voorspellen op basis van de huidige staat. De auteurs betogen dat deze aanpak leidt tot kortzichtige besluitvorming. Omdat de constructie van een VRP-oplossing een langetermijnplanningstaak is die honderden of duizenden knopen omvat, faalt het optimaliseren uitsluitend voor de directe volgende stap om de langetermijncontext vast te leggen die noodzakelijk is voor globale optimaliteit. Dit resulteert in foutopstapeling en een neiging om vast te komen te zitten in lokale optima, vooral naarmate de probleemgroottes toenemen.

Methodologie: Multi-Node Lookahead Prediction (MnLP)

Om de kortzichtigheid van standaard next-node prediction aan te pakken, stelt het artikel Multi-Node Lookahead Prediction (MnLP) voor, een nieuwe trainingsstrategie die het toegepaste leerparadigma uitbreidt.

Kernconcept

MnLP introduceert een mechanisme waarbij het model wordt getraind om meerdere toekomstige knopen simultaan te voorspellen (bijvoorbeeld de volgende $K$ knopen) in aanvulling op de directe volgende knoop. Dit wordt bereikt door middel van causale en verwijderbare MnLP-modules die uitsluitend tijdens de trainingsfase opereren.

Architectuur

Het voorgestelde raamwerk bouwt voort op het Light-Encoder-and-Heavy-Decoder (LEHD)-model:

1. Gedeelde Encoder: Een lichtgewicht encoder verwerkt ruwe knoopkenmerken (bijvoorbeeld coördinaten) naar knoopembeddings.
2. Hoofdddecoder: Voorspelt de directe volgende knoop ($x_t$) met behulp van standaard attentiemechanismen.
3. MnLP-modules: Een reeks van $K$ hulpmodules ($k=1, \dots, K$) wordt toegevoegd.
   • Causale Keten: De $k$-de module voorspelt de knoop op stap $t+k$ ($x_{t+k}$). Deze ontvangt contextuele informatie van de $(k-1)$-de module en de ground-truth embedding van de knoop op stap $t+k-1$. Dit dwingt een causale keten af waarbij voorspellingen voor toekomstige stappen afhankelijk zijn van de reeks van voorgaande stappen.
   • Haalbaarheid: De modules respecteren probleembeperkingen (bijvoorbeeld niet-bezochte knopen voor TSP, capaciteitsbeperkingen voor CVRP) door onhaalbare knopen te maskeren in de output-logits.
   • Verwijderbaar: Cruciaal is dat deze MnLP-modules tijdens inferentie worden verwijderd. Alleen de hoofd-next-node-head wordt gebruikt, wat geen extra rekenlast garandeert op het testmoment.

Trainingsdoel

De trainingsverliesfunctie is een gewogen som van de hoofdtaakverlies en de hulplookahead-verliezen:
$$\mathcal{L} = \mathcal{L}_{\text{main}} + \gamma \mathcal{L}_{\text{MnLP}}$$
Waarbij:

• $\mathcal{L}_{\text{main}}$ de standaard cross-entropy-verliesfunctie is voor next-node prediction.
• $\mathcal{L}_{\text{MnLP}}$ het gemiddelde cross-entropy-verlies is over de $K$ lookahead-modules.
• $\gamma$ een hyperparameter is die het gewicht van de hulp-supervisie regelt, welke lineair wordt opgevoerd tijdens een warm-upperiode om te voorkomen dat de hulptaak de vroege training domineert.

Deze multi-diepte supervisie fungeert als een regularisator, die de encoder aanmoedigt representaties te leren die langetermijnafhankelijkheden vastleggen en de credit assignment over de reeks verbetert.

Belangrijkste Bijdragen

1. Nieuw Architecturaal Ontwerp: De introductie van MnLP-modules die multi-stap voorspelling mogelijk maken tijdens training zonder de inferentie-architectuur te wijzigen of inferentie-tijd latentie toe te voegen.
2. Multi-Diepte Hulp-supervisie: Een trainingsstrategie die het model leidt om toekomstige beslissingen voorbij de directe volgende stap te anticiperen, wat blootstellingsbias en kortzichtig gedrag effectief mitigeert.
3. Empirische Validatie: Uitgebreide experimenten die aantonen dat MnLP de generalisatie verbetert over verschillende probleemgroottes, distributies en real-world benchmarks.

Experimentele Resultaten

De auteurs hebben MnLP geëvalueerd op TSP- en CVRP-instanties van variërende groottes (100 tot 1000 knopen) en distributies (uniform, rotatie, explosie en real-world benchmarks zoals TSPLib en CVRPLib).

• Prestatiewinst: MnLP presteerde consequent beter dan het basismodel LEHD. Bijvoorbeeld, op TSP met 1000 knopen verbeterde de optimaliteitsgap van 3,563% (LEHD) naar 2,852% (MnLP), een relatieve verbetering van 20%.
• Generalisatie: De methode toonde superieure cross-size en cross-distributie generalisatie. Bij grootschalige instanties ($n=1000$) verbreedde het prestatieverschil tussen MnLP en basismodellen, wat suggereert dat het lookahead-mechanisme bijzonder effectief is voor complexe, langetermijnplanning.
• Real-world Benchmarks: MnLP behaalde state-of-the-art resultaten onder neurale beleid op TSPLib en CVRPLib, en presteerde beter dan andere geavanceerde trainingsstrategieën zoals POMO (RL-gebaseerd) en SA-DABL (SL met augmentatie).
• Efficiëntie: Omdat MnLP-modules bij inferentie worden verwijderd, behoudt de methode dezelfde inferentiesnelheid als het basismodel LEHD.

Betekenis en Claims

Het artikel beweert dat MnLP een kritieke bottleneck in neurale combinatorische optimalisatie aanpakt: het onvermogen van standaard next-node prediction om langetermijnplanningsignalen vast te leggen. Door langetermijn contextueel begrip in te brengen in het trainingsproces zonder de inferentie-efficiëntie te compromitteren, biedt MnLP een schaalbare en effectieve manier om neurale routingbeleid te verbeteren.

De auteurs positioneren MnLP als een generaliseerbare trainingsstrategie die naadloos kan worden geïntegreerd in diverse neurale architecturen. Zij betogen dat het succes van MnLP de hypothese valideert dat multi-stap supervisie essentieel is voor het trainen van robuuste neurale beleid die in staat zijn grote, complexe routingproblemen op te lossen, en zo de kloof overbruggen tussen lokale besluitvorming en globale optimaliteit.