Ricordo ancora la lezione di informatica dell’università in cui il professore ci parlò della complessità computazionale e dell’esistenza di problemi per i quali il computer non è in grado di trovare una soluzione in tempi accettabili (problemi di tipo NP).
In particolare il professore ci illustrò come esempio di problema NP quello del commesso viaggiatore. Dato un insieme di città e note le distanze tra ciascuna coppia di esse, trovare il tragitto di minima percorrenza da seguire affinché il commesso visiti tutte le città una ed una sola volta e ritorni alla fine alla città di partenza.
Ora, se il problema non è risolvibile in tempi umani per un singolo commesso viaggiatore immagina come deve essere risolverlo per una compagnia come UPS che ha una flotta di oltre 100 milla veicoli!
Appurato che calcolare una soluzione “ottima” non è praticabile, gli ingegneri di UPS hanno scoperto che è possibile ottimizzare il percorso dei corrieri evitando le svolte a sinistra in modo da evitare il più possibile di dover attraversare il traffico proveniente dalla direzione opposta. Quindi sebbene il percorso diretto possa sembrare il più conveniente in realtà svoltando sempre a sinistra i dati hanno rivelato una riduzione notevole degli incidenti e del consumo di carburante “sprecato” attendendo di poter attraversare la strada.
Personalmente trovo interessantissimo il fatto che gli ingegneri di UPS si trovino a combattere quotidianamente con il problema del commesso viaggiatore che ai tempi dell’università mi sembrava inventato appositamente per dimostrare teoremi. Inoltre apprezzo molto come seguendo un approccio data-driven sia possibile ottenere comunque un miglioramento dell’efficienza del sistema di trasporto permettendo all’azienda di abbattere i costi e risparmiando qualche arrabbiatura agli autisti fermi nel traffico cittadino.
E tu che ne pensi?
Grazie per aver letto questo articolo della rubrica Input/Output. Ad ogni input, tipicamente, corrisponde un output. E solo esponendosi ad input diversi si possono tirare fuori idee non convenzionali. Proprio per questo ogni martedì prendo in input una curiosità legata al mondo tecnologico per ragionare su nuove idee da tirare fuori in output.