Risoluzione del problema multi-deposito con percorsi chiusi per più agenti viaggiatori usando clustering gerarchico k-means++ e reti neurali combinatorie

Percorsi più intelligenti per molti autisti

Dai furgoni per pacchi ai droni per consegne fino ai convogli per soccorsi in caso di disastro, i pianificatori si trovano spesso davanti a un enigma: come possono diversi veicoli che partono da posizioni diverse condividere il lavoro di visitare centinaia o migliaia di fermate senza sprecare carburante o tempo? Questo articolo presenta un nuovo modo di dividere e vincere l’enigma, combinando un trucco classico di clustering con una rete neurale moderna in modo che i computer possano tracciare percorsi efficienti in pochi secondi invece che in minuti o ore.

La sfida di molti depositi e molti conducenti

Lo studio affronta una versione impegnativa del famoso problema del commesso viaggiatore, in cui invece di un singolo viaggiatore ce ne sono molti, ciascuno con punto di partenza e di arrivo nel proprio deposito. Insieme devono visitare ogni città esattamente una volta mantenendo la distanza totale il più breve possibile. Questa impostazione riproduce compiti come il coordinamento di flotte di camion, gruppi di robot o droni aerei che condividono il lavoro su una regione. Poiché il numero di combinazioni possibili di percorsi esplode al crescere delle città e dei conducenti, i metodi esatti diventano troppo lenti e i metodi tradizionali di ricerca per tentativi spesso arrancano o devono scambiare qualità della soluzione per velocità.

Limiti della ricerca classica e della semplice divisione

Per anni gli ingegneri hanno fatto affidamento su “metaeuristiche” come algoritmi genetici, ricerca ispirata alle colonie di formiche e sciami di particelle. Queste imitano processi naturali per esplorare molte soluzioni candidate e migliorarle gradualmente. Possono essere flessibili ma presentano due grandi svantaggi: non offrono garanzie nette sulla bontà della soluzione e possono essere molto lente per mappe grandi, specialmente quando ogni nuovo problema richiede di ricominciare la ricerca da capo. Un’accelerazione popolare è prima raggruppare le città in regioni usando strumenti come k-means e poi risolvere un sotto-problema più piccolo all’interno di ciascun cluster. Sebbene questa strategia divide-e-risolve aiuti, la qualità finale è comunque limitata dal metodo di ricerca sottostante e puntare a percorsi migliori di solito significa pagare con tempi di esecuzione ancora più lunghi.

Insegnare a una rete a instradare, poi aiutarla a scalare

Negli ultimi anni è emersa un’idea diversa: addestrare una rete neurale a generare direttamente buoni percorsi. Dopo aver appreso da molti esempi di disposizioni di città, una rete del genere può proporre un tour completo in un singolo passaggio in avanti, proprio come un modello linguistico genera una frase. Questi risolutori neurali funzionano sorprendentemente bene per problemi con un unico conducente di dimensione modesta, ma incontrano difficoltà quando devono coordinare molti conducenti o quando l’insieme di città è molto più grande di quanto visto in allenamento. La mossa chiave degli autori è incapsulare tale risolutore neurale in un processo a due fasi che rimodella un compito multi-conducente enorme in molti sotto-problemi più piccoli e familiari che la rete può gestire agevolmente.

Come funziona il metodo in due fasi

Il metodo proposto, chiamato KHC-NCN, inizia usando una versione migliorata del clustering k-means per assegnare le città ai diversi depositi e conducenti. Se una regione risultante contiene troppe città perché il risolutore neurale la gestisca in modo affidabile, il metodo la suddivide automaticamente in pezzi più piccoli, ciascuno di dimensione vicina a quella vista durante l’addestramento della rete. Le coordinate in ogni pezzo vengono riscalate all’interno di un quadrato standard in modo che somiglino ancora di più ai dati di training. La rete neurale produce quindi un percorso per ciascun piccolo pezzo. Infine, un passo di fusione cuce insieme questi sotto-percorsi in un unico anello per ciascun conducente, usando regole geometriche semplici per connettere i pezzi dove farlo aggiunge la minima distanza extra.

Velocità e qualità su mappe benchmark reali

Gli autori testano il loro metodo su una vasta raccolta di mappe standard da un set di benchmark pubblico ampiamente usato nella ricerca sul routing. Confrontano con molte tecniche di ricerca consolidate e sia con un risolutore di punta artigianale sia con un altro approccio neurale. Su 44 casi di test con diverse dimensioni delle mappe e numeri di conducenti, il loro metodo trova percorsi totali più brevi in quasi tre quarti dei casi risultando allo stesso tempo drasticamente più rapido, spesso di ordini di grandezza. Si comporta particolarmente bene quando il numero di città sale nelle centinaia o migliaia, dove molti approcci classici rallentano o forniscono percorsi meno efficaci.

Cosa significa per il routing nel mondo reale

In termini semplici, lo studio mostra che lasciare che una rete neurale veloce gestisca molti piccoli problemi ben strutturati può essere meglio che impiegare molto tempo su un unico enorme problema. Raggruppando le città in modo che rispettino la zona di comfort della rete e poi combinando astutamente le risposte parziali, il metodo fornisce percorsi sia brevi sia rapidi da calcolare. Per applicazioni come la logistica, la pianificazione multi-robot e la risposta alle emergenze, questo indica un modo pratico per ottenere piani di percorso quasi in tempo reale che sfruttano meglio veicoli ed energia rispetto a molti strumenti esistenti.

Citazione: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Parole chiave: instradamento veicoli, reti neurali, clustering, ottimizzazione, logistica