Technische Samenvatting: Eerst Neuraal Clusteren, Vervolgens Routeplannen

Probleemdefinitie

Het artikel behandelt het Capacitated Vehicle Routing Problem (CVRP), een fundamentele uitdaging in de last-mile-logistiek waarbij een vloot voertuigen met uniforme capaciteit $Q$ een reeks klanten met specifieke vraag moet bedienen vanuit een centraal depot, met als doel de totale reiskosten te minimaliseren.

De auteurs identificeren kritieke beperkingen in bestaande Neurale Combinatorische Optimalisatie (NCO)-benaderingen:

1. Autoregressieve (AR) Bottlenecks: Dominante NCO-methoden construeren oplossingen token voor token, wat leidt tot sequentiële decoderingskosten, gevoeligheid voor ruimtelijke symmetrieën en breekbare generalisatie buiten de verdeling (OOD).
2. Methodologische Koppeling: Waar het Traveling Salesman Problem (TSP) puur een routeplanningsopgave is, impliceert het CVRP fundamenteel een partitieprobleem (klanten in capaciteits-gefeaseerde clusters indelen, vergelijkbaar met bin-packing) gekoppeld aan routeplanning. Bestaande NCO-methoden behandelen het CVRP vaak als een taak voor het genereren van rondreizen, waardoor capaciteitsbeperkingen worden overgelaten aan kostbare post-hoc zoektochten.
3. Benchmarks die niet overeenkomen: Standaard benchmarks resamplen knoopcoördinaten i.i.d., en negeren hierbij de vaste geografische ondergrond (bijvoorbeeld het stratenpatroon van een stad) die kenmerkend is voor real-world logistiek, waar hetzelfde gebied dagelijks wordt gerouteerd met variërende vraag.

Methodologie: Neuraal CFRS

De auteurs stellen Neuraal CFRS voor, het eerste puur niet-autoregressieve (NAR), one-shot neurale raamwerk gebaseerd op het klassieke Cluster-First-Route-Second (CFRS)-paradigma. In plaats van routes sequentieel te genereren, voert het model een globale, differentieerbare toewijzing van klanten aan voertuigclusters uit, waarna onafhankelijke TSP's parallel worden opgelost.

De architectuur werkt in drie fasen:

1. Pre-training en Ruimtelijke Ondergrond Prior ($\Psi$)

Om de vaste geografie van real-world logistiek aan te pakken, pre-trainen de auteurs een Spatial Masked Autoencoder (SMAE) over een vaste set potentiële klantlocaties ($X$).

• De SMAE leert $E(2)$-invariante (invariant voor translatie, rotatie en reflectie) embeddings door paarsgewijze Euclidische afstanden en lokale $k$-NN-connectiviteit te reconstrueren zonder absolute coördinaten te consumeren.
• Deze bevroren embeddings ($\Psi$) dienen als een "ruimtelijke vocabulaire", waardoor het downstream-model kan generaliseren naar nieuwe vraaginstanties op dezelfde kaart zonder de geometrie opnieuw te hoeven leren.

2. Fase 1: Zaadgeneratie

Een Seed Transformer (ST) identificeert een subset van knopen om te dienen als initiële clustercentra ("zaadjes").

• Het voorspelt marginale kansen voor knopen die als zaadjes fungeren en leert contrastieve representaties om vergelijkbare knopen te groeperen.
• Een Capaciteitsbewuste Greedy Decoding-strategie selecteert $K$ zaadjes (waarbij $K$ de geschatte vlootgrootte is) en pakt knopen in de buurt op een greedige manier in deze zaadjes op basis van contrastieve gelijkenis, waarbij ruimtelijke spreiding en capaciteitsgevoeligheid worden gewaarborgd.

3. Fase 2: Globale Toewijzing via Differentieerbare Optimale Transport

Een Clustering Transformer (CT) berekent latente afstanden ($\Delta_{ij}$) tussen klanten en de geselecteerde zaadjes.

• Differentieerbare Relaxatie: Om globale capaciteitsbeperkingen end-to-end af te dwingen, wordt het discrete Capacitated Assignment Problem (CAP) gerelaxeerd tot een continu Optimal Transport (OT)-probleem.
• Sinkhorn-Knopp (SK) Algoritme: Het model minimaliseert een entropisch geregulariseerd OT-doelwit, wat resulteert in een continu transportplan ($\hat{Y}$) dat aan de capaciteitsbeperkingen voldoet. Dit plan fungeert als een differentieerbare surrogaat voor de discrete toewijzingsmatrix.

4. Fase 3: OR Decoding

Het continue transportplan $\hat{Y}$ leidt een exacte Mixed Integer Programming (MIP)-oplosser naar het herwinnen van de definitieve discrete clusters.

• Versparsing: Het model gebruikt vertrouwensdrempels om ofwel vast te zetten hoog-vertrouwde toewijzingen (Hard Assignment) ofwel te snoeien laag-kansverbindingen (Sinkhorn-Guided Sparsification).
• Dit reduceert de zoekruimte voor de exacte oplosser drastisch, die vervolgens de resterende deelvragen oplost als onafhankelijke TSP's met behulp van kant-en-klare oplossers (bijvoorbeeld LKH-3).

Belangrijkste Bijdragen

1. Niet-autoregressief Raamwerk: Introduceert de eerste puur NAR-neurale solver voor CVRP die sequentiële decoderingsbottlenecks omzeilt door het probleem te framen als een globale partitietak.
2. Differentieerbare Capaciteitsbeperkingen: Ontwikkelt een nieuwe end-to-end differentieerbare laag met behulp van entropische Optimale Transport om vlootcapaciteitsbeperkingen af te dwingen, en overbrugt zo de kloof tussen neurale toewijzing en exacte geheeltallige programmering.
3. Symmetrie-abstractie: Biedt formele theoretische garanties dat de architectuur intrinsiek $E(2)$-ruimtelijke symmetrieën, permutatie tussen routes en doorloop-symmetrieën binnen routes afbouwt door constructie, waardoor dure data-augmentatie overbodig wordt.
4. Ruimtelijke Ondergrond Prior: Demonstreert dat het benutten van een voorgeprende ruimtelijke vocabulaire op vaste geografie extreme parameter-efficiëntie mogelijk maakt en zero-shot schaling naar grote probleemgroottes.

Experimentele Resultaten

Het raamwerk werd geëvalueerd op zowel operationele settings met constante capaciteit (vaste geografie) als standaard benchmarks (i.i.d. coördinaten).

• Zero-Shot Generalisatie: Neuraal CFRS schaalt robuust naar out-of-distribution instanties tot $N=1000$ klanten.
  • Onder een setting met constante capaciteit ($Q=50$) bereikt het een optimaliteitskloof van < 4% op $N=1000$-instanties in minder dan 30 seconden.
  • Opmerkelijk is dat een ultra-lightweight single-layer architectuur (682K parameters) op deze schaal een benaderende 5% kloof behoudt, wat de notie uitdaagt dat diepe architecturen vereist zijn voor routeplanning op grote schaal.
• Standaard Benchmarks: Op de standaard CVRP100-benchmark bereikt de variant met exacte decoding een optimaliteitskloof van 2,73%, wat beter presteert dan greedige autoregressieve baselines (zoals POMO, BQ, LEHD) en concurreert met klassieke heuristieken.
• Efficiëntie: De methode elimineert volledig de afhankelijkheid van post-hoc lokale zoektochten voor de initiële clustering, en vertrouwt in plaats daarvan op het vermogen van het neurale model om de exacte oplosser te sturen.

Betekenis en Claims

Het artikel betoogt dat Neuraal CFRS een structurele verschuiving vertegenwoordigt in NCO voor routeplanningsproblemen:

• Alignering met Sterke Punten van Deep Learning: Het benut het vermogen van deep learning om gelijkenis en toewijzing te leren over een globale context, in plaats van het te dwingen lange sequentiële rondreizen te construeren.
• Haalbaarheid in Realiteit: Door rekening te houden met vaste ruimtelijke ondergronden en constante capaciteiten, sluit het raamwerk aan bij het geamortiseerde, latency-gevoelige regime van real-world logistiek, en biedt het een haalbaar pad voor dagelijkse routeplanning in statische servicegebieden.
• Paradigmaverschuiving: De resultaten suggereren dat taakspecifieke aanpassing (bijvoorbeeld pre-training op ruimtelijke ondergrond) state-of-the-art resultaten kan opleveren zonder uitgebreide fine-tuning, en dat eenvoudige, ondiepe architecturen zeer effectief kunnen zijn wanneer ze worden gekoppeld aan de juiste inductieve bias (CFRS-decompositie en ruimtelijke priors).

De auteurs concluderen dat hoewel het raamwerk competitief presteert, toekomstig werk zich moet richten op het verbeteren van zero-shot schaling naar nog grotere instanties en het verfijnen van het vermogen van het model om capaciteitsbenutting te balanceren met ruimtelijke efficiëntie in uitzonderlijke gevallen.