🤖 machine learning

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

Questo articolo introduce la piattaforma "Smart Routes" per sviluppare e confrontare algoritmi volti a risolvere il Problema del Veicolo Singolo con Capacità e Finestre Temporali, dimostrando che il deep learning e i metodi euristici classici ottengono risultati quasi ottimali con costi computazionali significativamente inferiori rispetto ai solver esatti come SCIP, specialmente all'aumentare delle dimensioni del problema.

Autori originali: Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov

Pubblicato 2026-08-17

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate di essere il capitano di una flotta di consegne, incaricato di consegnare centinaia di pacchi in una città frenetica. Avete una mappa, un elenco di clienti e un insieme rigoroso di regole: i vostri camion possono trasportare solo una certa quantità di peso e alcuni clienti desiderano ricevere i loro pacchi solo tra le 9:00 e le 11:00. Il vostro obiettivo è semplice: visitare tutti, rispettare le regole e spendere il minor tempo e carburante possibile. Questo è il "Problema del Giro del Veicolo" (Vehicle Routing Problem), un classico enigma che ha tenuto impegnati per decenni logisti e matematici.

Per anni, gli scienziati hanno cercato di risolverlo usando due strumenti principali. Il primo è la "Calcolatrice Perfetta", un metodo che cerca di controllare ogni singola combinazione possibile per trovare quella assolutamente migliore. È come cercare di assaggiare ogni singolo piatto in un enorme buffet per trovare il boccone perfetto. Funziona molto bene per piccoli pasti, ma se il buffet diventa troppo grande, avrete fame per sempre prima di aver finito. Il secondo strumento è la "Scommessa Intelligente", o euristica. Questo è come uno chef esperto che conosce bene la cucina; non controlla ogni piatto, ma usa l'esperienza e trucchi rapidi per trovare un pasto delizioso molto velocemente. Recentemente, un nuovo contendente è entrato nell'arena: il "Deep Learning". Pensate a questo come a uno chef robotico che guarda migliaia di video di cucina, impara i pattern e poi prova a indovinare il percorso migliore istantaneamente, migliorandosi man mano che si esercita.

Questo articolo, intitolato "Smart Routes", è un torneo testa a testa tra questi tre chef. Gli autori hanno costruito un nuovo parco giochi digitale chiamato "Smart Routes" per testarli equamente. Non si sono limitati a guardare piccoli e semplici enigmi; hanno testato gli algoritmi su problemi con 50 e 100 fermate, il che è come passare da un piccolo quartiere a un'intera città. Volevano vedere chi riusciva a trovare un buon percorso nel modo più veloce possibile senza infrangere le regole del gioco.

La Grande Corsa: Perfetto vs. Veloce vs. Intelligente

I ricercatori hanno organizzato una gara utilizzando la loro nuova piattaforma "Smart Routes". Questa piattaforma è come un campo di prova universale dove è possibile collegare qualsiasi algoritmo — che sia un classico trucco matematico, un potente risolutore informatico o un robot che impara — e guardarlo all'opera. Hanno testato tre tipi principali di concorrenti:

Il Solutore Esatto (SCIP): La "Calcolatrice Perfetta" che promette la risposta migliore, ma richiede molto tempo.
Le Euristiche Classiche (LKH, 2-OPT, 3-OPT, OR-Tools): Le "Scommesse Intelligenti" che usano scorciatoie ingegnose per trovare buone risposte rapidamente.
Il Modello di Deep Learning (JAMPR): Lo "Chef Robot" addestrato per imparare i pattern e fare ipotesi veloci e di alta qualità.

Hanno messo alla prova questi concorrenti su due tipi di sfide: una città più piccola con 50 fermate di consegna e una città più grande con 100 fermate. Hanno dato alla "Calcolatrice Perfetta" un enorme vantaggio temporale (1.000 secondi per la città piccola e 2.000 secondi per quella grande) perché ha bisogno di riflettere profondamente. Gli altri hanno ricevuto molto meno tempo (rispettivamente 100 e 200 secondi).

I Risultati: La Velocità Vince, ma le Dimensioni Contano

La Sfida delle 50 Fermate (La Città Piccola)
Nella città più piccola, la gara è stata sorprendentemente vicina. La "Calcolatrice Perfetta" (SCIP) alla fine ha trovato il percorso assoluto migliore, ma ci è voluto molto tempo per arrivarci. Nel frattempo, le "Scommesse Intelligenti" e lo "Chef Robot" hanno trovato percorsi quasi altrettanto buoni — solo circa il 5% peggiori rispetto a quello perfetto — ma lo hanno fatto in una frazione del tempo.

Il Punto Chiave: Per problemi più piccoli, non è necessario aspettare la risposta perfetta. I metodi veloci sono così vicini al meglio che sono un affare molto più vantaggioso, perché vi risparmiano ore di attesa.

La Sfida delle 100 Fermate (La Città Grande)
Quando la città è raddoppiata nelle dimensioni a 100 fermate, le regole del gioco sono cambiate drasticamente. La "Calcolatrice Perfetta" ha iniziato a faticare. Ha impiegato circa 13 volte più tempo solo per trovare il suo primo percorso valido rispetto agli altri metodi. Peggio ancora, nel momento in cui ha finalmente trovato un percorso, quel percorso era circa il 50% più costoso (più lungo e lento) rispetto ai percorsi trovati istantaneamente dallo "Chef Robot" e dalle "Scommesse Intelligenti" avanzate.

Il Punto Chiave: Man mano che la città diventa più grande, la "Calcolatrice Perfetta" diventa troppo lenta per essere utile. Passa così tanto tempo a cercare che non riesce nemmeno a trovare una buona soluzione in tempo. Lo "Chef Robot" (JAMPR) e le "Scommesse Intelligenti" avanzate (come OR-Tools) sono rimasti veloci e hanno trovato percorsi di alta qualità, dimostrando che per i grandi problemi, la velocità e la scommessa intelligente battono la ricerca della perfezione.

Il Verdetto

L'articolo conclude che, sebbene la "Calcolatrice Perfetta" sia ottima per piccoli enigmi, incontra un limite quando il problema diventa troppo grande. La piattaforma "Smart Routes" ha dimostrato che per problemi di consegna su larga scala e realistici (come 100 fermate), affidarsi a soluzioni esatte e perfette è spesso una cattiva idea perché richiedono troppo tempo e non garantiscono nemmeno un ottimo risultato entro un tempo ragionevole.

Invece, gli autori suggeriscono che un mix di euristiche classiche (le scorciatoie esperte) e deep learning (il robot addestrato) sia la strategia vincente. Questi metodi possono trovare percorsi quasi uguali a quelli perfetti, ma lo fanno così velocemente da essere effettivamente utili nella logistica del mondo reale. Il sistema "Smart Routes" stesso viene evidenziato come uno strumento prezioso perché permette a chiunque di testare facilmente questi diversi metodi, visualizzare i percorsi su una mappa e persino aggiungere le proprie nuove idee al mix senza dover ricostruire l'intero sistema.

In breve, se state cercando di consegnare pacchi in una città in crescita, non aspettate il piano perfetto. Usate gli strumenti intelligenti e veloci che imparano dall'esperienza, perché nel mondo reale, un buon percorso trovato ora è meglio di un percorso perfetto trovato la prossima settimana.

Sintesi Tecnica: Smart Routes – Un sistema per lo sviluppo e il confronto di algoritmi per la risoluzione di problemi di routing dei veicoli con vincoli realistici

Definizione del Problema
Il documento affronta il Problema del Routing dei Veicoli con Capacità e Finestre Temporali (CVRPTW), una sfida critica nella logistica dei trasporti che riguarda l'ottimizzazione dei percorsi per una flotta di veicoli destinata a servire clienti con specifici limiti di capacità e finestre temporali di consegna. Gli autori evidenziano come, sebbene gli approcci matematici esatti forniscano teoricamente soluzioni ottimali, la loro applicazione sia severamente limitata dalla complessità esponenziale all'aumentare delle dimensioni del problema. Di conseguenza, è necessario bilanciare la qualità della soluzione rispetto al tempo di ricerca, particolarmente per scenari del mondo reale che coinvolgono una crescente popolazione urbana e vincoli complessi. Inoltre, gli autori identificano una mancanza di piattaforme unificate che permettano ai ricercatori di integrare, confrontare e visualizzare in modo fluido e senza alterare l'architettura del sistema diversi approcci algoritmici (esatti, euristici e di deep learning).

Metodologia
Lo studio impiega un'analisi comparativa di tre distinte classi di algoritmi applicati a istanze CVRPTW:

Metodi Esatti: Gli autori utilizzano la suite di ottimizzazione SCIP, che impiega algoritmi di Branch&Bound, Cutting Plane e Branch&Cut per trovare soluzioni ottimali.
Euristiche Classiche: Lo studio valuta approcci costruttivi e metaeuristici, nello specifico l'euristica Lin-Kernighan (LKH), i metodi di ricerca locale 2-OPT e 3-OPT, nonché il framework OR-Tools di Google.
Deep Reinforcement Learning (DRL): Gli autori utilizzano una versione modificata del modello JAMPR (Joint Attention Model for Pickup and Delivery with Time Windows). Questa architettura adatta l'Attention Model (AM) aggiungendo matrici addestrabili ( $M+$ ) all'output del decoder per gestire vincoli specifici. Il modello tratta la costruzione del percorso come un processo decisionale sequenziale (Processo Decisionale di Markov), dove lo stato include il percorso corrente e i nodi non visitati, e le azioni consistono nella selezione del nodo successivo.

Per facilitare tali confronti, gli autori hanno sviluppato Smart Routes, una piattaforma software personalizzata. Questo sistema presenta:

Architettura Modulare: Composta da un modulo Dataset (per la generazione e il caricamento dei dati), un modulo Algorithm (per l'addestramento e la valutazione di modelli definiti dall'utente o predefiniti) e un modulo Solution (per la generazione di metriche e la visualizzazione).
Estensibilità: Gli utenti possono integrare algoritmi personalizzati ereditando dalle classi base, consentendo il test di nuove idee senza modificare il sistema centrale.
Visualizzazione: La piattaforma fornisce interfacce web interattive per visualizzare i percorsi e generare grafici di performance che confrontano i costi dei percorsi nel tempo.

Configurazione Sperimentale
Gli esperimenti sono stati condotti su dataset artificiali generati sulla base del set di benchmark Solomon R201, concentrandosi su dimensioni del problema di 50 e 100 nodi.

Vincoli: Il problema è stato risolto in impostazioni "soft", che consentono di saltare i clienti non visitati con un costo di penalità.
Hardware: I test sono stati eseguiti su un server equipaggiato con una GPU NVIDIA Tesla A40 e una CPU Intel Xeon Gold.
Limiti di Tempo: Ai metodi euristici e DRL sono stati concessi 100s (per 50 nodi) e 200s (per 100 nodi). Ai metodi esatti (SCIP) è stato allocato un tempo significativamente maggiore (1000s e 2000s, rispettivamente) per tentare di trovare soluzioni ottimali.

Risultati Chiave
L'analisi comparativa ha prodotto le seguenti scoperte:

Istanze a 50 Nodi: Sia le euristiche classiche (LK H, OR-Tools) che il modello di deep reinforcement learning (JAMPR) hanno prodotto rapidamente soluzioni subottimali. Entro i primi 10 secondi, la qualità della soluzione di SCIP era inferiore a quella di questi metodi. Sebbene SCIP abbia infine superato tali metodi dopo circa 100 secondi, il divario finale tra il modello DRL e la soluzione esatta è rimasto inferiore al 5%.
Istanze a 100 Nodi: I limiti dei metodi esatti sono diventati pronunciati. SCIP ha richiesto circa 13 volte più tempo rispetto ai metodi euristici e DRL per raggiungere lo stesso costo del percorso. Inoltre, entro il tempo allocato, SCIP non è riuscito a trovare una soluzione ottima, e la sua prima soluzione ammissibile è stata circa il 50% più costosa di quelle fornite da OR-Tools e JAMPR.
Scalabilità: Al raddoppiare della dimensionalità del problema, il tempo richiesto a SCIP per trovare una soluzione è aumentato di circa 14 volte, mentre le prestazioni degli approcci euristici e neurali sono rimaste relativamente stabili, suggerendo che i metodi esatti diventano impraticabili per problemi di 100 nodi o superiori.

Significatività e Rivendicazioni
Il documento rivendica due contributi primari:

La Piattaforma Smart Routes: Un ambiente unificato ed estensibile che integra approcci esatti, euristici e di deep learning per il VRP. Gli autori sostengono che questo sistema offra un vantaggio significativo rispetto ai framework esistenti (come OR-Tools, Gumbi e SCIP) supportando il deep reinforcement learning, fornendo visualizzazione integrata e permettendo l'integrazione facile di algoritmi personalizzati.
Validazione Empirica degli Approcci: Lo studio fornisce un confronto completo dimostrando che, per problemi di dimensioni moderate (50 nodi), le euristiche classiche e il deep reinforcement learning offrono un compromesso superiore tra qualità della soluzione e tempo di calcolo rispetto ai solver esatti. Per istanze più grandi (100 nodi), il documento conclude che i metodi esatti sono praticamente impraticabili a causa della crescita esponenziale del tempo, mentre il deep reinforcement learning e le euristiche avanzate forniscono soluzioni subottimali rapide e di alta qualità.

Gli autori posizionano il loro lavoro come un passo verso un'ottimizzazione dei percorsi più efficiente di fronte alla crescita urbana globale, sottolineando come la loro piattaforma faciliti il rapido test e il confronto di nuove idee algoritmiche nella logistica.

La Grande Corsa: Perfetto vs. Veloce vs. Intelligente

I Risultati: La Velocità Vince, ma le Dimensioni Contano

Il Verdetto

Articoli simili