Nuovo algoritmo ottimizza le rotte per veicoli elettrici
Nel panorama della logistica moderna, dove l’efficienza operativa e la sostenibilità ambientale sono diventate priorità assolute, un nuovo balzo in avanti nel campo della pianificazione intelligente delle flotte sta attirando l’attenzione dei principali operatori del settore automobilistico. Un team di ricercatori dell’Università di Anhui, guidato da Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao, ha sviluppato un innovativo algoritmo di calcolo che promette di rivoluzionare la gestione delle rotte per i veicoli elettrici (EV), affrontando una delle sfide più complesse nella transizione verso un trasporto urbano a zero emissioni.
Il problema, noto nella letteratura scientifica come il Problema di Routing del Veicolo Elettrico (EVRP), è di per sé estremamente arduo. A differenza dei veicoli a combustione interna, la cui unica limitazione primaria è la capacità di carico, i veicoli elettrici introducono una seconda e critica restrizione: l’autonomia della batteria. Questo significa che un pianificatore non deve semplicemente determinare il percorso più efficiente per visitare tutti i clienti, ma deve anche decidere con precisione quando, dove e per quanto tempo ricaricare. Questa doppia ottimizzazione – della traiettoria e della ricarica – espande esponenzialmente lo spazio delle possibili soluzioni, trasformando un problema già complesso in una sfida computazionale di enorme portata.
I metodi tradizionali per risolvere l’EVRP si sono basati principalmente su due approcci distinti. Da un lato, gli algoritmi esatti, come la programmazione lineare intera mista, possono garantire la soluzione ottimale, ma il loro tempo di calcolo cresce in modo esponenziale con il numero di clienti, rendendoli impraticabili per le operazioni del mondo reale che coinvolgono centinaia o migliaia di consegne. Dall’altro lato, gli algoritmi euristici e metaeuristici, come la ricerca tabù o la ricerca adattativa di grandi vicinanze (ALNS), possono trovare soluzioni accettabili in tempi ragionevoli, ma spesso rischiano di rimanere intrappolati in ottimi locali, ovvero soluzioni che sono buone in una piccola area dello spazio delle soluzioni, ma distanti dal vero ottimo globale.
Gli algoritmi evolutivi, ispirati al processo di selezione naturale, sono emersi come un’alternativa promettente. Questi algoritmi operano con una “popolazione” di soluzioni candidate che “evolvono” nel tempo attraverso processi di selezione, crossover e mutazione. La loro natura basata su popolazioni consente di esplorare simultaneamente diverse regioni dello spazio delle soluzioni, riducendo il rischio di rimanere bloccati in ottimi locali. Tuttavia, anche questi sofisticati metodi hanno incontrato difficoltà nel gestire la complessità intrinseca dell’EVRP, specialmente quando si tratta di trovare un equilibrio tra la minimizzazione della distanza totale percorsa, la riduzione del numero di veicoli utilizzati e la garanzia che nessun veicolo si esaurisca a metà percorso.
È in questo contesto che il lavoro di Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao rappresenta un punto di svolta significativo. Il loro approccio, un algoritmo evolutivo cooperativo a doppia popolazione (COEA), segna un cambiamento di paradigma nel modo in cui vengono affrontati i problemi di ottimizzazione complessi. Invece di tentare di risolvere direttamente l’intricato problema dell’EVRP, i ricercatori hanno adottato una strategia basata su un “problema ausiliario”. L’idea centrale è quella di creare un problema più semplice, strettamente correlato a quello originale, che possa essere risolto rapidamente e la cui soluzione possa essere utilizzata per accelerare la risoluzione del problema principale.
Il problema ausiliario scelto è una versione semplificata del classico problema di routing del veicolo, noto come CVRP (Problema di Routing del Veicolo con Capacità). Il CVRP considera le restrizioni di capacità di carico dei veicoli e la necessità di visitare tutti i clienti, ma ignora completamente il vincolo energetico. Eliminando questa variabile, il CVRP diventa molto più facile da risolvere, e la sua popolazione di soluzioni può convergere verso soluzioni di alta qualità in un numero di iterazioni significativamente inferiore.
La vera genialità del COEA risiede nel modo in cui il sapere viene trasferito tra queste due popolazioni: quella del problema semplice (CVRP) e quella del problema complesso (EVRP). Uno scambio diretto di soluzioni sarebbe inutile, poiché un percorso ottimale per un veicolo a combustione non tiene conto dei punti di ricarica. Per superare questo ostacolo, i ricercatori hanno implementato due innovazioni chiave: un nuovo metodo per rappresentare le soluzioni e un meccanismo di traduzione intelligente.
La prima innovazione è una matrice di adiacenza delle distanze migliorata. Invece di rappresentare un percorso semplicemente come una sequenza di numeri (ad esempio, 1-3-2-0, dove 0 è il deposito), il COEA utilizza una matrice che codifica informazioni molto più ricche. Ogni cella di questa matrice non contiene solo la distanza fisica tra due punti, ma incorpora anche un valore relativo che indica l'”affinità” tra di essi all’interno della soluzione. Ad esempio, se due clienti sono serviti dallo stesso veicolo, la “distanza” tra di loro in questa matrice è artificialmente ridotta. Se appartengono a percorsi diversi, questa “distanza” è amplificata. Questo accorgimento permette alla matrice di catturare implicitamente la struttura di raggruppamento dei clienti per veicolo, un’informazione cruciale che un algoritmo di apprendimento può utilizzare.
La seconda e più rivoluzionaria innovazione è l’uso di un codificatore automatico per la rimozione del rumore (DAE), una tecnica di apprendimento automatico. Il DAE agisce come un traduttore tra i due “linguaggi” dei problemi. Durante il processo evolutivo, le migliori soluzioni di entrambe le popolazioni vengono convertite nelle loro rappresentazioni matriciali e utilizzate per addestrare il DAE. Il DAE impara così la mappatura tra la struttura di una soluzione CVRP (ottimale in termini di distanza e capacità) e come quella stessa struttura potrebbe essere trasformata in una soluzione EVRP fattibile (che tenga conto anche delle batterie e delle stazioni di ricarica).
Una volta addestrato, questo DAE diventa un motore di trasferimento della conoscenza. Prende le soluzioni di élite della popolazione CVRP, che è convergente rapidamente verso modelli di raggruppamento efficienti, e le “traduce” in soluzioni iniziali per la popolazione EVRP. Questo è cruciale: invece di iniziare la ricerca per l’EVRP con soluzioni casuali, la popolazione complessa riceve continuamente “semi” di alta qualità che già contengono una logica di raggruppamento dei clienti ben ottimizzata. Ciò accelera in modo drammatico il processo di convergenza, poiché l’algoritmo EVRP non deve perdere tempo a scoprire come raggruppare i clienti in modo efficiente; quella conoscenza è già stata trasferita.
Il processo è bidirezionale. Non solo vengono inviate soluzioni dal CVRP all’EVRP, ma anche soluzioni di élite dall’EVRP vengono inviate indietro al CVRP. Questo feedback è vitale perché guida l’evoluzione del problema semplice verso strutture che sono più utili e rilevanti per il problema complesso. Si tratta di un ciclo di miglioramento continuo, in cui ogni popolazione aiuta l’altra a evolvere verso un obiettivo comune.
Per validare l’efficacia del loro algoritmo, il team dell’Università di Anhui ha condotto una serie di test esaustivi utilizzando un insieme di test standard per l’EVRP che include istanze di medie e grandi dimensioni, con fino a 400 clienti. Hanno confrontato il COEA con cinque degli algoritmi più avanzati del momento: BACO, KBEA, HVNS, ALNS e TS-MCWS. I risultati sono stati conclusivi.
Il COEA ha dimostrato una velocità di convergenza significativamente più rapida. Nei grafici che mostrano il costo medio della soluzione in funzione del numero di iterazioni, la curva del COEA scendeva molto più velocemente rispetto a quella dei suoi concorrenti, raggiungendo soluzioni di migliore qualità in meno tempo. In termini di risultati finali, il COEA ha ottenuto le migliori soluzioni conosciute in 11 delle 18 istanze di test, un risultato particolarmente notevole nei problemi di grandi dimensioni, che sono i più rilevanti per le operazioni logistiche reali.
In confronto diretto, il COEA ha superato costantemente BACO, HVNS e TS-MCWS, con miglioramenti nel costo totale che spesso superavano il 20%. Anche rispetto al KBEA, un algoritmo evolutivo avanzato che utilizza informazioni storiche della popolazione per guidare la sua ricerca, il COEA ha ottenuto risultati superiori nella maggior parte dei casi. Questo dimostra che la strategia di trasferimento della conoscenza tra problemi è più efficace dei metodi di apprendimento intra-popolazione.
Gli studi di ablazione, in cui i ricercatori hanno disattivato componenti chiave del COEA, hanno confermato l’importanza di ogni parte del design. Disattivando la matrice di distanza migliorata, l’algoritmo ha perso la capacità di catturare la struttura di raggruppamento, rallentando la convergenza. Disattivando il DAE e sostituendolo con uno scambio diretto di soluzioni, le prestazioni si sono degradate severamente, confermando che il meccanismo di traduzione è essenziale per un trasferimento efficace della conoscenza. Questi esperimenti hanno dimostrato che il COEA non è semplicemente la somma delle sue parti, ma un sistema integrato in cui l’interazione tra la rappresentazione della soluzione, il DAE e l’evoluzione cooperativa delle popolazioni crea un effetto sinergico.
Le implicazioni pratiche di questa ricerca sono profonde. Per le aziende di logistica, un algoritmo come il COEA significa la capacità di gestire flotte di veicoli elettrici in modo più efficiente, riducendo i costi operativi, estendendo l’autonomia dei veicoli e migliorando la puntualità delle consegne. Questo può essere la differenza tra un’operazione redditizia e una che fatica a coprire i propri costi.
Per le città e i pianificatori urbani, questa tecnologia offre uno strumento potente per simulare il comportamento delle flotte elettriche e ottimizzare il posizionamento dell’infrastruttura di ricarica. Invece di installare stazioni di ricarica basandosi su supposizioni, i comuni possono utilizzare modelli come questo per prevedere con precisione dove saranno necessari i punti di ricarica, massimizzandone l’utilizzo e minimizzando il costo della rete.
Oltre la logistica, questo lavoro apre una nuova strada per la risoluzione di problemi di ottimizzazione complessi in diversi settori. Il concetto di utilizzare un problema ausiliario più semplice per guidare la soluzione di uno più complesso, facilitato da tecniche di apprendimento automatico, potrebbe essere applicato alla pianificazione di reti di droni, alla gestione di flotte ibride o all’ottimizzazione di sistemi di trasporto multimodale.
In un momento in cui la pressione per raggiungere la neutralità del carbonio è sempre maggiore, l’intelligenza del software che governa la logistica verde è tanto importante quanto la tecnologia dei veicoli. L’algoritmo COEA, sviluppato da Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao, non è solo un avanzamento tecnico; è un passo cruciale verso un sistema di trasporto più intelligente, più efficiente e veramente sostenibile.
Nuovo algoritmo ottimizza le rotte per veicoli elettrici
Wang Chao, Qin Fang, Liu Rongrong, Jiang Hao, Scuola di Intelligenza Artificiale, Università di Anhui, CAAI Transactions on Intelligent Systems, DOI: 10.11992/tis.202209007