Il problema del commesso viaggiatore nell'era moderna

Formulato per la prima volta nell'Ottocento, lo studio del problema del commesso viaggiatore (TSP, dall'inglese Travelling Salesman Problem) ha fatto notevoli passi avanti grazie al matematico statunitense Merrill M. Flood negli anni Trenta, quando cercò di risolvere un problema di percorsi degli scuolabus. Il TSP è un problema matematico in cui bisogna trovare il percorso più breve possibile che tocchi un insieme di punti (in questo caso, le fermate degli autobus). Il percorso deve passare per ogni punto una sola volta prima di tornare al punto di partenza.

In generale l'ordine in cui vengono visitati i punti non è un fattore principale, purché il commesso li visiti tutti una volta. Nonostante la straordinaria semplicità della formulazione, il TSP è un problema NP-difficile di ottimizzazione combinatoria e può essere usato come modello per testare tecniche di ottimizzazione applicate a problemi molto diversi, compreso il dispatching dinamico di veicoli condivisi.

A un livello più astratto, il TSP può essere descritto con la teoria dei grafi come una rete pesata non orientata, i cui nodi rappresentano città e i cui collegamenti hanno pesi che indicano le distanze tra le città. In questo contesto, trovare la soluzione ottimale del TSP significa trovare il percorso minimo che colleghi tutti i nodi della rete. In letteratura esistono diversi algoritmi che analizzano le proprietà strutturali di una rete cercandone i percorsi minimi, e sono al centro della teoria dei grafi tradizionale. L'applicazione di questi algoritmi alle reti complesse si ritrova in campi consolidati come matematica, biologia e scienze sociali.

È sorprendente che, pur basandosi su un problema relativamente semplice e pur essendo nati per risolverlo, oggi questi algoritmi vengano sfruttati per la loro capacità predittiva anche in operazioni industriali complesse. Settori fondamentali nella nostra vita quotidiana, come la consegna di merci su scala locale, nazionale e internazionale, il trasporto marittimo, le reti aeroportuali o le reti di trasporto pubblico delle grandi aree metropolitane, sono solo alcuni esempi che usano varianti degli algoritmi TSP per semplificarci la vita.

Il percorso minimo in una variante del TSP si può trovare calcolando tutte le possibili combinazioni di percorso. Questo approccio a forza bruta funziona quando N è abbastanza piccolo, ma è praticamente irrealizzabile per N grandi. In quest'ultimo caso gli algoritmi di ricerca euristica offrono ottime soluzioni approssimate. Il loro vantaggio principale è la capacità di ottenere soluzioni della variante TSP che, pur non essendo esatte, sono molto più pratiche e soprattutto si ottengono rapidamente e con un basso costo computazionale. Questo rende gli algoritmi di ricerca euristica diffusi e adatti a servizi software in cui le risorse di calcolo sono limitate e la risposta in tempo reale è cruciale, soprattutto quando la domanda cresce.

La tecnologia di Shotl usa metodi scientifici moderni che permettono di sfruttare la ricerca passata e presente su reti complesse e algoritmi di ottimizzazione. Il servizio, supportato da una progettazione ingegneristica agile, si basa su un solido nucleo algoritmico che trova soluzioni ottimali per una variante del TSP formulata secondo i vincoli di ogni situazione specifica.

La nostra soluzione algoritmica abbina più passeggeri diretti nella stessa direzione a un veicolo in movimento, riducendo al minimo distanze percorse e tempi di attesa e offrendo così un servizio e un'esperienza di trasporto migliori.