RELAGRAM: modello ricorsivo a grafo latente per il problema di instradamento dei veicoli con vincoli di capacità

Abstract degli autori

La ricorsione latente elabora ripetutamente le rappresentazioni interne attraverso la stessa rete neurale. Lavori recenti hanno mostrato che questo approccio è efficace in compiti di ragionamento strutturato come il Sudoku e la risoluzione di labirinti. Tuttavia, non è ancora chiaro se la ricorsione latente possa supportare l’instradamento neurale. Presentiamo RELAGRAM (Recursive Latent Graph Model), un nuovo approccio che porta la ricorsione latente nell’ottimizzazione combinatoria su grafi. RELAGRAM codifica un’istanza del problema di instradamento dei veicoli con vincoli di capacità (CVRP) come token di arco; un transformer compatto aggiorna ricorrentemente le rappresentazioni latenti di questi token. Una testa di output mappa lo stato della risposta in una mappa di calore degli archi, dalla quale un decoder autoregressivo costruisce una soluzione ammissibile. Sulle istanze CVRP-100, RELAGRAM, con 0,53 milioni di parametri, raggiunge scarti rispetto a un riferimento PyVRP pari al 13,4%, al 9,8% e all’8,3%, rispettivamente con decodifica greedy, augmentation basata sulle otto simmetrie e ricerca tra 256 candidati. Addestrato soltanto su CVRP-100, RELAGRAM generalizza in modalità zero-shot a CVRP-500 e CVRP-1000, raggiungendo scarti del 15,6% e del 21,7% con la ricerca tra 256 candidati. Nel complesso, questi risultati dimostrano che la ricorsione latente è un approccio promettente all’instradamento neurale.