Un migliore approccio al “problema del commesso viaggiatore” potrebbe migliorare i settori della logistica e dei trasporti
Un nuovo approccio per risolvere il “problema del commesso viaggiatore”, una delle questioni più difficili nell’informatica, supera significativamente gli approcci attuali.
Una famigerata domanda teorica che ha lasciato perplessi i ricercatori per 90 anni, il problema del commesso viaggiatore ha anche una reale rilevanza per l’industria di oggi. Essenzialmente una domanda su come combinare al meglio una serie di compiti in modo che possano essere eseguiti nel modo più rapido ed efficiente, trovare buone soluzioni al problema può aiutare notevolmente a migliorare settori come i trasporti e la logistica.
I ricercatori dell’Università di Cambridge hanno sviluppato un approccio ibrido e basato sui dati al problema che non solo produce soluzioni di alta qualità, ma a un ritmo più rapido rispetto ad altri approcci all’avanguardia. I loro risultati sono presentati questa settimana alla Conferenza internazionale sulle rappresentazioni dell’apprendimento .
“L’importanza del sistema logistico globale ci è stata ricordata durante la pandemia”, ha affermato la professoressa Amanda Prorok del Dipartimento di Informatica e Tecnologia di Cambridge, che ha guidato la ricerca. “Facciamo molto affidamento su questo tipo di infrastruttura per essere più efficienti e la nostra soluzione potrebbe essere d’aiuto in quanto si rivolge sia alla logistica interna, come l’instradamento dei robot intorno a un magazzino per raccogliere le merci per la consegna, sia a quelle esterne esso, come l’instradamento delle merci alle persone”.
Il problema del commesso viaggiatore coinvolge un autista di consegna fittizio che deve chiamare un determinato numero di città – diciamo, 20, 50 o 100 – che sono collegate da autostrade tutto in un viaggio. La sfida è trovare il percorso più breve possibile che fa scalo a ciascuna destinazione una volta e trovarlo rapidamente.
“Ci sono due componenti chiave del problema. Vogliamo ordinare le fermate e vogliamo anche conoscere il costo, in termini di tempo o distanza, per andare da una fermata all’altra in quell’ordine”, ha affermato Prorok.
Vent’anni fa il percorso dal magazzino alle destinazioni potrebbe essere stato fissato in anticipo. Ma con la disponibilità odierna di informazioni sul traffico in tempo reale e la possibilità di inviare messaggi all’autista per aggiungere o rimuovere al volo le località di consegna, il percorso potrebbe ora cambiare durante il viaggio. Ma ridurre al minimo la sua lunghezza o durata rimane ancora fondamentale.
Spesso c’è un costo attribuito all’attesa di una soluzione ottimale oa scadenze difficili in cui devono essere prese le decisioni. Ad esempio, l’autista non vede l’ora che venga calcolata una nuova soluzione: potrebbe perdere le consegne o le condizioni del traffico potrebbero cambiare di nuovo.
Ed è per questo che sono necessari algoritmi di ottimizzazione combinatoria generale, in qualsiasi momento, che producano soluzioni di alta qualità in tempi di calcolo limitati.
L’approccio ibrido sviluppato da Cambridge lo fa combinando un modello di apprendimento automatico che fornisce informazioni su quali sono stati i percorsi migliori precedenti e uno strumento “metaeuristico” che utilizza queste informazioni per assemblare il nuovo percorso.
“Vogliamo trovare più velocemente le buone soluzioni”, ha affermato Ben Hudson, il primo autore del documento. “Se sono un autista per una ditta di corriere, devo decidere quale sarà la mia prossima destinazione mentre guido. Non posso permettermi di aspettare una soluzione migliore. Ecco perché nella nostra ricerca ci siamo concentrati sul compromesso tra il tempo di calcolo necessario e la qualità della soluzione che abbiamo ottenuto”.
Per fare ciò, Hudson ha escogitato un algoritmo di ricerca locale guidata in grado di differenziare i percorsi da una città all’altra che sarebbero costosi, in termini di tempo o distanza, da percorsi che sarebbero meno costosi da includere nel viaggio. Ciò ha consentito ai ricercatori di identificare rapidamente soluzioni di alta qualità, anziché ottimali.
Lo hanno fatto utilizzando una misura di quello che chiamano il “rimpianto globale” – il costo di far rispettare una decisione relativa al costo di una soluzione ottimale – di ogni percorso da città a città nell’algoritmo di ricerca locale guidata. Hanno usato l’apprendimento automatico per ottenere un’approssimazione di questo “rimpianto”.
“Conosciamo già la soluzione corretta a una serie di questi problemi”, ha affermato Hudson. “Quindi abbiamo utilizzato alcune tecniche di apprendimento automatico per cercare di imparare da quelle soluzioni. Sulla base di ciò, cerchiamo di imparare per un nuovo problema – per un nuovo insieme di città in luoghi diversi – quali percorsi tra le città siano promettenti.
“Quando abbiamo queste informazioni, le alimentano nella parte successiva dell’algoritmo, la parte che disegna effettivamente i percorsi. Usa quelle informazioni extra su quali potrebbero essere i buoni percorsi per costruire una buona soluzione molto più rapidamente di quanto avrebbe potuto fare altrimenti.
I risultati che hanno ottenuto sono stati impressionanti. I loro esperimenti hanno dimostrato che l’approccio ibrido, basato sui dati, converge a soluzioni ottimali a una velocità maggiore rispetto a tre recenti approcci basati sull’apprendimento per il problema del commesso viaggiatore.
In particolare, quando si cercava di risolvere il problema quando aveva un percorso di 100 città, il metodo Cambridge ha ridotto il divario di ottimalità medio dall’1,534% allo 0,705%, un duplice miglioramento. Quando si generalizza dal percorso problematico di 20 città al percorso problematico di 100 città, il metodo ha ridotto il divario di ottimalità dal 18,845% al 2,622%, un miglioramento di sette volte.
“Molte società di logistica utilizzano metodi di routing nella vita reale”, ha affermato Hudson. “Il nostro obiettivo con questa ricerca è quello di migliorare tali metodi in modo che producano soluzioni migliori, soluzioni che si traducano in minori distanze percorse e quindi minori emissioni di carbonio e ridotto impatto sull’ambiente”.
