Riepilogo Tecnico: Cluster Neurale Prima, Instradamento Dopo

Definizione del Problema

Il documento affronta il Problema di Instradamento dei Veicoli con Capacità (CVRP), una sfida fondamentale nella logistica dell'ultimo miglio in cui una flotta di veicoli con capacità uniforme $Q$ deve servire un insieme di clienti con richieste specifiche da un deposito centrale, minimizzando la distanza totale di viaggio.

Gli autori identificano limitazioni critiche negli attuali approcci di Ottimizzazione Combinatoria Neurale (NCO):

1. Colli di bottiglia Autoregressivi (AR): I metodi NCO dominanti costruiscono le soluzioni token per token, portando a costi di decodifica sequenziale, sensibilità alle simmetrie spaziali e una generalizzazione fragile fuori distribuzione (OOD).
2. Disconnessione Metodologica: Mentre il Problema del Commesso Viaggiatore (TSP) è puramente un compito di instradamento, il CVRP coinvolge fondamentalmente un problema di partizionamento (raggruppare i clienti in cluster compatibili con la capacità) accoppiato all'instradamento. I metodi NCO esistenti trattano spesso il CVRP come un compito di generazione di tour, lasciando che i vincoli di capacità siano imposti da una ricerca post-hoc costosa.
3. Disallineamento dei Benchmark: I benchmark standard ricampionano le coordinate dei nodi in modo i.i.d., ignorando il supporto geografico fisso (ad esempio, la rete stradale di una città) tipico della logistica reale, dove la stessa area viene instradata quotidianamente con richieste variabili.

Metodologia: Neural CFRS

Gli autori propongono Neural CFRS, il primo framework neurale puramente non autoregressivo (NAR), one-shot, basato sul classico paradigma Cluster-First-Route-Second (CFRS). Invece di generare rotte sequenzialmente, il modello esegue un'assegnazione globale e differenziabile dei clienti ai cluster dei veicoli, dopodiché i TSP indipendenti vengono risolti in parallelo.

L'architettura opera in tre fasi:

1. Pre-addestramento e Priorità del Supporto Spaziale ($\Psi$)

Per affrontare la geografia fissa della logistica reale, gli autori pre-addestrano un Autoencoder Mascherato Spaziale (SMAE) su un insieme fisso di potenziali ubicazioni dei clienti ($X$).

• L'SMAE apprende embedding invarianti $E(2)$ (invarianti per traslazione, rotazione e riflessione) ricostruendo le distanze euclidee a coppie e la connettività locale $k$-NN senza consumare coordinate assolute.
• Questi embedding congelati ($\Psi$) fungono da un "vocabolario spaziale", permettendo al modello a valle di generalizzare a nuove istanze di domanda sulla stessa mappa senza dover riapprendere la geometria.

2. Fase 1: Generazione dei Semi

Un Trasformatore dei Semi (ST) identifica un sottoinsieme di nodi da servire come centri iniziali dei cluster ("semi").

• Predice le probabilità marginali per i nodi che agiscono come semi e apprende rappresentazioni contrastive per raggruppare nodi simili.
• Una strategia di Decodifica Greedy Consapevole della Capacità seleziona $K$ semi (dove $K$ è la dimensione stimata della flotta) e impacchetta avidamente i nodi vicini in questi semi basandosi sulla similarità contrastiva, garantendo dispersione spaziale e fattibilità della capacità.

3. Fase 2: Assegnazione Globale tramite Trasporto Ottimo Differenziabile

Un Trasformatore di Clustering (CT) calcola le distanze latenti ($\Delta_{ij}$) tra i clienti e i semi selezionati.

• Rilassamento Differenziabile: Per imporre vincoli di capacità globali end-to-end, il Problema di Assegnazione Capacitato (CAP) discreto viene rilassato in un problema di Trasporto Ottimo (OT) continuo.
• Algoritmo Sinkhorn-Knopp (SK): Il modello minimizza un obiettivo OT regolarizzato entropicamente, producendo un piano di trasporto continuo ($\hat{Y}$) che soddisfa i vincoli di capacità. Questo piano funge da surrogato differenziabile per la matrice di assegnazione discreta.

4. Fase 3: Decodifica OR

Il piano di trasporto continuo $\hat{Y}$ guida un solver esatto di Programmazione Lineare Intera Mista (MIP) per recuperare i cluster finali discreti.

• Sparsificazione: Il modello utilizza soglie di confidenza per fissare assegnazioni ad alta confidenza (Assegnazione Rigida) o potare gli archi a bassa probabilità (Sparsificazione Guidata da Sinkhorn).
• Ciò riduce drasticamente lo spazio di ricerca per il solver esatto, che risolve quindi i sottoproblemi rimanenti come TSP indipendenti utilizzando solver pronti all'uso (ad esempio, LKH-3).

Contributi Chiave

1. Framework Non Autoregressivo: Introduce il primo solver neurale puramente NAR per il CVRP che aggira i colli di bottiglia della decodifica sequenziale inquadrando il problema come un compito di partizionamento globale.
2. Vincoli di Capacità Differenziabili: Sviluppa un nuovo strato differenziabile end-to-end utilizzando il Trasporto Ottimo regolarizzato entropicamente per imporre i vincoli di capacità della flotta, colmando il divario tra assegnazione neurale e programmazione intera esatta.
3. Astrazione della Simmetria: Fornisce garanzie teoriche formali che l'architettura astrae intrinsecamente le simmetrie spaziali $E(2)$, la permutazione tra rotte e le simmetrie di attraversamento all'interno delle rotte per costruzione, eliminando la necessità di costosi aumenti dei dati.
4. Priorità del Supporto Spaziale: Dimostra che sfruttare un vocabolario spaziale pre-addestrato su una geografia fissa permette un'efficienza parametrica estrema e un'escalation zero-shot a dimensioni di problemi elevate.

Risultati Sperimentali

Il framework è stato valutato sia su impostazioni operative a capacità costante (geografia fissa) che su benchmark standard (coordinate i.i.d.).

• Generalizzazione Zero-Shot: Neural CFRS scala in modo robusto a istanze fuori distribuzione fino a $N=1000$ clienti.
  • In un'impostazione a capacità costante ($Q=50$), raggiunge un gap di ottimalità di < 4% su istanze $N=1000$ in meno di 30 secondi.
  • Notevolmente, un'architettura ultra-leggera a singolo strato (682K parametri) mantiene un gap approssimativo del 5% a questa scala, sfidando la nozione secondo cui sono necessarie architetture profonde per l'instradamento su larga scala.
• Benchmark Standard: Sul benchmark CVRP100 standard, la variante di decodifica esatta raggiunge un gap di ottimalità del 2,73%, superando le baseline autoregressive greedy (ad esempio, POMO, BQ, LEHD) e competendo con le euristiche classiche.
• Efficienza: Il metodo elimina completamente la dipendenza dalla ricerca locale post-hoc per il clustering iniziale, affidandosi invece alla capacità del modello neurale di guidare il solver esatto.

Significato e Affermazioni

Il documento sostiene che Neural CFRS rappresenta un cambiamento strutturale nell'NCO per i problemi di instradamento:

• Allineamento con i Punti di Forza del Deep Learning: Sfrutta la capacità del deep learning di apprendere similarità e assegnazioni su un contesto globale, piuttosto che costringerlo a costruire tour sequenziali lunghi.
• Fattibilità nel Mondo Reale: Rispettando i supporti spaziali fissi e le capacità costanti, il framework si allinea al regime ammortizzato e sensibile alla latenza della logistica reale, offrendo una via praticabile per l'instradamento quotidiano in aree di servizio statiche.
• Cambiamento di Paradigma: I risultati suggeriscono che l'adattamento specifico al compito (ad esempio, il pre-addestramento sul supporto spaziale) può produrre risultati all'avanguardia senza un esteso fine-tuning, e che architetture semplici e superficiali possono essere altamente efficaci se abbinate ai corretti bias induttivi (decomposizione CFRS e priori spaziali).

Gli autori concludono che, sebbene il framework si esibisca in modo competitivo, il lavoro futuro dovrebbe concentrarsi sul migliorare l'escalation zero-shot a istanze ancora più grandi e sul perfezionare la capacità del modello di bilanciare l'utilizzo della capacità con l'efficienza spaziale nei casi limite.