Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Sintesi Tecnica: Modello Fondazionale Assistito dalla Visione per la Risoluzione di Problemi di Routing Veicolare Multi-Task

Definizione del Problema
I problemi di Vehicle Routing (VRP) multi-task coinvolgono l'ottimizzazione dei costi di routing soddisfacendo diversi vincoli dei clienti, come le richieste di backhaul (B), i percorsi aperti (O), i limiti di durata (L) e le finestre temporali (TW). La combinazione di questi vincoli crea un numero esponenziale di varianti VRP (ad esempio, 16 varianti da quattro vincoli). Gli attuali solver neurali si affidano tipicamente a modalità basate su grafi, codificando i vincoli come attributi dei nodi. Tuttavia, questi approcci affrontano limitazioni: faticano a apprendere complesse relazioni spaziali e interazioni tra i vincoli man mano che i task diventano più intricati, e l'addestramento di modelli separati per ogni variante è computazionalmente proibitivo. Inoltre, i metodi basati sulla visione esistenti per l'ottimizzazione combinatoria sono stati limitati a scenari single-task (ad esempio, TSP) e spesso non riescono a codificare attributi specifici del task cruciali, come le domande o le finestre temporali, all'interno della rappresentazione visiva.

Metodologia: Modello Fondazionale Assistito dalla Visione (VaFM)
Gli autori propongono VaFM, un modello fondazionale che integra modalità di visione e grafi per risolvere simultaneamente 1e 16 diverse varianti di VRP. L'architettura è composta da tre componenti primarie:

1. Generazione di Immagini VRP Multi-Task: Per affrontare la mancanza di rappresentazione dei vincoli nelle immagini VRP esistenti, gli autori progettano due immagini di input per ogni istanza: un'immagine "di domanda" (demand image) e un'immagine "di finestra temporale" (time window - TW).

   • Codifica Visiva: Le coordinate dei clienti sono mappate sugli indici dei pixel. L'intensità del colore del nodo rappresenta variabili continue (magnitudo della domanda o durata della finestra temporale).
   • Rappresentazione dei Vincoli: I vincoli discreti sono codificati tramite segnali visivi: i percorsi aperti (O) sono indicati dall'inversione del colore dello sfondo; i limiti di durata (L) sono mostrati cambiando la forma dei nodi (da rettangoli a segni più); le richieste di backhaul (B) utilizzano colori dei nodi distinti (verde per il linehaul, blu per il backhaul).
   • Input: Le due immagini vengono concatenate e processate da un encoder di visione basato su CNN (ResNet-18).

2. Modulo di Fusione Hybrid Cross-Attention: Per superare il campo recettivo fisso dei classici patch embeddings e adattarsi a requisiti di task variabili, VaFM impiega un meccanismo di fusione ibrido.

   • Meccanismo: Le mappe di caratteristiche dagli ultimi due strati dell'encoder di visione vengono estratte. I patch embeddings vengono derivati da queste mappe e allineati con gli embedding dei nodi del grafo.
   • Campo Recettivo Adattivo: Viene utilizzato un meccanismo di cross-attention in cui gli embedding dei nodi fungono da query e le mappe di caratteristiche appiattite dallo strato più profondo fungono da chiavi (keys) e valori (values). Ciò consente al modello di aggregare informazioni globali rilevanti (dagli strati profondi) pur mantenendo un contesto locale fine (dagoli strati superficiali), creando efficacemente campi recettivi adattivi per diversi vincoli.

3. Task Ausiliario Sensibile ai Vincoli: Per mitigare il problema della distribuzione sbilanciata dei pixel (dove vincoli come O o L occupano più pixel rispetto a B o TW, rischiando di far trascurare questi ultimi dal modello), viene introdotto un task ausiliario.

   • Implementazione: Un classificatore è collegato all'encoder di visione per predire la presenza di ciascuno dei quattro vincoli (O, L, B, TW).
   • Funzione di Perdita: La perdita Binary Cross-Entropy (BCE) è applicata a questo task ausiliario, garantendo che il modello apprenda rappresentazioni bilanciate per tutti i vincoli indipendentemente dalla loro prominenza visiva.
   • Obiettivo di Addestramento: La perdita totale è una somma pesata della perdita di Reinforcement Learning (RL) per la minimizzazione del costo di routing e della perdita di classificazione ausiliaria.

Contributi Chiave

• Primo Modello Fondazionale per VRP Multi-Task Assistito dalla Visione: Il lavoro introduce il primo framework che combina modalità di grafo e visione per gestire molteplici varianti VRP simultaneamente, andando oltre i solver visivi single-task.
• Nuova Codifica Visiva e Fusione: Il documento propone design di immagini specifici per codificare diversi vincoli e un modulo di fusione hybrid cross-attention che consente campi recettivi adattivi, affrontando i limiti delle dimensioni fisse dei patch nei contesti multi-task.
• Apprendimento Bilanciato dei Vincoli: L'introduzione di un task ausiliario sensibile ai vincoli con perdita BCE previene efficacementamente il fatto che il modello possa trascurare i vincoli con meno pixel visivi.

Risultati Sperimentali
Il modello è stato valutato su 16 varianti VRP con 50 e 100 nodi cliente, confrontandolo con metodi State-of-the-Art (SOTA) inclusi HGS-PyVRP, OR-Tools e vari solver neurali (MTPOMO, MVMoE, RF-MoE-L).

• Performance: VaFM (specificamente la variante VaFM-MoE-L) ha ottenuto le migliori prestazioni in 15 casi su 16 per N=50 e 12 casi su 16 per N=100.
• Vincoli Complessi: Il divario di performance tra VaFM e i baseline basati solo su grafi si è ampliato all'aumentare del numero di vincoli. Ad esempio, su task con 3 o 4 vincoli, VaFM ha mostrato miglioramenti significativi nel gap di ottimalità rispetto al baseline RF-MoE-L.
• Generalizzazione: Sebbene VaFM abbia mostrato una forte generalizzazione zero-shot a scale maggiori (N=200) e combinazioni di vincoli non viste (backhaul misto), ha mostrato una certa instabilità su dataset reali e su task specifici con forte prevalenza di finestre temporali, suggerendo limitazioni nella discriminazione basata sul colore a scale più ampie.
• Efficienza: VaFM richiede un tempo di inferenza leggermente superiore rispetto ai baseline basati solo su grafi a causa della branca di visione, ma rimane significativamente più veloce dei solver euristici come HGS-PyVRP.

Significatività e Rivendicazioni
Il documento afferma che VaFM dimostra il potenziale dell'integrazione di modalità di visione nei solver neurali basati su grafi per migliorare la rappresentazione di problemi di ottimizzazione complessi e multi-vincolo. Gli autori sostengono che il loro approccio cattura con successo la semantica a livello di patch (distribuzioni spaziali della domanda e pattern di tempo di servizio) che sono difficili da apprendere per i modelli puramente grafici. I risultati suggeriscono che i modelli assistiti dalla visione sono particolarmente superiori per le varianti VRP con vincoli complessi e interagenti. Tuttavia, gli autori riconoscono con modestia alcune limitazioni, notando che la attuale codifica visiva (che si basa sull'intensità di un singolo colore) potrebbe avere difficoltà con la discriminazione fine in istanze su larga scala e che è necessario ulteriore lavoro per migliorare la generalizzazione su dataset reali e vincoli non visti, potenzialmente attraverso modelli linguistici di grandi dimensioni multimodali.