Il Travelling Salesman Problem (TSP) è uno dei problemi più studiati in informatica: visitare N città col percorso più breve, tornando al punto di partenza. Sembra semplice, ma con 20 città i percorsi possibili superano gli atomi nell'universo. Il Vehicle Routing Problem (VRP) generalizza il TSP a flotte di veicoli con vincoli reali: capacità, orari, tipi di merce.
L'esplosione combinatoria
Il numero di percorsi possibili cresce come (n-1)!/2. Con 10 città: 181.440 percorsi. Con 20 città: oltre 10^16. Con 50 città: più che atomi nell'universo osservabile. I computer classici usano euristiche che trovano soluzioni 'buone' ma non garantiscono l'ottimo.
Vehicle Routing Problem (VRP)
Nel mondo reale non c'è un solo commesso viaggiatore, ma flotte di veicoli. Il VRP aggiunge vincoli: capacità di carico, finestre temporali per le consegne, tipi di merce (refrigerata, fragile), autonomia dei veicoli elettrici. Ogni vincolo moltiplica la complessità.
L'approccio quantistico
Il TSP può essere formulato come problema QUBO e risolto con quantum annealing o QAOA. Il quantum annealer esplora simultaneamente molte configurazioni grazie alla sovrapposizione quantistica e usa il tunneling quantistico per uscire da minimi locali dove gli algoritmi classici restano intrappolati.
Caso reale: Volkswagen Lisbona 2019
Al Web Summit 2019, Volkswagen ha dimostrato l'ottimizzazione del traffico di taxi a Lisbona usando D-Wave. Non una simulazione: taxi reali, strade reali. È ancora un proof-of-concept, non produzione, ma dimostra che l'approccio funziona su problemi concreti.
