Il problema del venditore viaggiatore (TSP) è una delle sfide più durevoli nell'ottimizzazione combinatoria. Al suo centro, il TSP pone una domanda ingannevole: data una serie di città e le distanze tra ogni coppia, qual è il più breve percorso possibile che visita ogni città esattamente una volta e ritorna al punto di origine? Questo apparentemente semplice puzzle ha affascinato matematici, scienziati del computer e ricercatori di operazioni per decenni, perché la sua complessità cresce

Le origini e l'evoluzione del problema del venditore viaggiatore

Il TSP è stato formulato per la prima volta nel 1800 da parte di matematici come William Rowan Hamilton e Thomas Kirkman, ma ha guadagnato una vasta attenzione nella metà del XX secolo come potenza di calcolo ha cominciato a crescere. Nel 1954, un team di RAND Corporation ha pubblicato la prima soluzione TSP “grande” per 49 città, utilizzando tecniche di programmazione lineare all’avanguardia.

Per esempio, l’Università di Chicago VIGRE carta sul TSP offre una rigorosa introduzione, mentre NEOS Guida’s TSP spiega il suo stato computazionale.

Mapping del TSP alle operazioni di logistica moderne

In una tipica operazione di consegna, un veicolo parte da un deposito, deve visitare una serie di sedi dei clienti, e poi tornare al deposito. Questo rispecchia il classico TSP simmetrico. Tuttavia, la logistica del mondo reale raramente incontra la forma pura del problema.

  • Tempo finestre:[] I clienti si aspettano consegne entro ore specifiche, trasformando il TSP nel problema del venditore viaggiante con Windows (TSPTW).
  • Capacità di veicolo:[] I veicoli multipli, ciascuno con spazio di carico finito, danno luogo al problema di routing del veicolo (VRP), una generalizzazione di TSP.
  • Aggiornamenti dinamici:[ Nuovi ordini arrivano per tutta la giornata, richiedendo in tempo reale la deviazione piuttosto che un piano statico.
  • Reti stradali e stradali:[ Le distanze euclidee sono sostituite da tempi di viaggio reali che variano con congestione, chiusure stradali e tempo.

Nonostante queste complessità, la logica TSP principale rimane incorporata all'interno dei risolutori VRP. La maggior parte dei moderni motori di ottimizzazione dei percorsi decompongono il problema multi-veicolo, multi-constraint in una serie di sottoproblemi TSP-like per le singole rotte.

Il TSP in consegna a un miglio

L’ultima corsa di circa 1 milione di secondi, che rappresenta la parte più costosa di molte catene di approvvigionamento. Secondo le stime del settore, il trasporto di ultima miglia rappresenta il 30% al 50% dei costi complessivi della logistica.

Tecniche avanzate di algoritmica per TSP in Logistica

Mentre i risolutori esatti (ad esempio, ramo-and-bound o ramo-and-cut) possono gestire problemi di piccole e medie dimensioni, le aziende logistiche affrontano regolarmente istanze con centinaia o migliaia di fermate per percorso.

  • Algoritmi genetici:[] Selezione naturale mimicking, questi evolvono una popolazione di percorsi su molte generazioni, attraversando e mutando buone soluzioni per convergere su percorsi quasi ottimali.
  • ricottura simulata:[] Ispirata dalla metallurgia, questa tecnica probabilistica accetta occasionalmente soluzioni peggiori all'inizio della ricerca per sfuggire all'optima locale, quindi riduce gradualmente la “temperatura” per ottimizzare il percorso migliore.
  • Ottimizzazione della colonia:[] Simulando il comportamento di remissione del feromone delle formiche, questo metodo costruisce percorsi incrementalmente e rafforza segmenti di percorso che appaiono in tour più brevi.
  • Algoritmi di vicinato e risparmio più vicini:[ Euristica di costruzione veloce che forniscono un percorso iniziale decente, che può poi essere migliorato dalla ricerca locale.

Il software moderno spesso combina questi metodi. Ad esempio, un algoritmo genetico può produrre un insieme di percorsi candidati, che vengono poi lucidati utilizzando la ricerca locale a 3 opzioni e convalidati contro i dati di traffico in tempo reale da API come Google Maps o QUI. Il risultato è una raccomandazione di routing dinamica che può adattarsi quando un cliente cancella un ordine o un nuovo drop-in si presenta.

Dati in tempo reale e TSP

Il TSP statico assume distanze fisse e un insieme noto di destinazioni. In logistica, la realtà è fluida. I ping gps dai veicoli di consegna, i feed di traffico dal vivo e l'ordine cancella flusso in costante. I moderni sistemi basati su TSP trattano il problema come un orizzonte di rotolamento: un piano viene generato per le prossime fermate N, eseguito in parte, e poi ri-ottimizzato come nuove informazioni arriva.

Per un'analisi approfondita di come le aziende utilizzano dati in tempo reale per migliorare le soluzioni TSP, vedere il sorvegliare su routing dinamico del veicolo da Pillac et al. (2019).

Case Studies: TSP in azione presso le principali società di logistica

Ecosistema di ottimizzazione della rotta Amazon Prime

Amazon gestisce una delle reti di consegna più complesse del mondo, con milioni di pacchetti che si muovono attraverso decine di centri di smistamento e stazioni di consegna ogni giorno. L'azienda utilizza algoritmi proprietari che risolvono varianti di TSP e VRP su più onde. Il loro sistema deve tenere conto delle finestre di tempo di consegna (ad esempio, Prime Now slot di un'ora), dimensioni di pacchetto variabili, e la capacità dei furgoni dei driver.

UPS e il sistema ORION

Il sistema ORION (On-Road Integrated Optimization and Navigation) è forse il più pubblicizzato di grande ottimizzazione basata su TSP.

Ottimizzazione globale della catena di fornitura di DHL

DHL applica i concetti TSP non solo alla consegna locale ma anche alle sue reti di trasporto internazionali. Per i servizi di corriere espresso, DHL utilizza un modello di routing multi-echelon dove i pacchi sono consolidati a mozzi, volati tra continenti e poi distribuiti localmente. Il passaggio di distribuzione locale è essenzialmente un grande TSP con finestre di tempo e vincoli di capacità.

Oltre il classico TSP: Varianti che risolvono i problemi moderni

Poiché la logistica è cresciuta più sofisticata, i ricercatori hanno proposto dozzine di varianti TSP su misura per specifici vincoli operativi:

  • Prize-collecting TSP:[ Il corriere può saltare alcune destinazioni ma paga una penalità, utile quando non tutte le fermate sono obbligatorie.
  • Moltiple travel salesmen (mTSP): Diversi driver iniziano e finiscono in un deposito, ognuno visita un sottoinsieme di clienti, un modello diretto per il routing della flotta.
  • TSP con backhauls: Alcune fermate richiedono la raccolta di merci (ad esempio, ritorni) piuttosto che la consegna, alterando la sequenza di carico del percorso.
  • TSP asimmetrico:[] I costi di viaggio differiscono in base alla direzione (ad esempio, a causa di strade a senso unico o di diversi pedaggi), rispecchiando le reti urbane reali.

Ogni variante richiede adattamenti algoritmici specializzati, ma la logica TSP sottostante – fingendo il ciclo Hamiltoniano più breve – rimane un potente ancoraggio concettuale.Per i manager logistici, la comprensione quale variante mappa alle loro operazioni quotidiane è il primo passo verso un'ottimizzazione efficace del percorso.

Indicazioni future: Autonoma Veicoli, Drones e AI

I veicoli di consegna autonome e i droni possono trasformare la logistica di ultima generazione, ma anche introdurre nuove sfide legate al TSP. Un furgone autoguida potrebbe essere necessario risolvere un TSP-time non solo per il suo percorso, ma anche coordinare con un piccolo drone che lancia dal furgone per fare consegne in algoritmo di generazione di forza maggiore mentre il furgone continua su una strada principale.

Per uno sguardo in un approccio all'avanguardia, leggere learning per risolvere TSP con reti neurali di grafo[].

Pratiche fasi per i gestori di logistica

Per le organizzazioni che cercano di applicare i principi TSP alle proprie operazioni di consegna, il percorso prevede tipicamente quattro fasi:

  1. aggregazione dati:[] Raccogliere indirizzi accurati, tempi di viaggio (utilizzando un'API di routing), previsioni di domanda e vincoli del driver.
  2. Selezione algoritmica:[] Scegli tra i risolutori open source (ad esempio OR‐Tools from Google, LKH) o piattaforme commerciali (ad esempio, Routific, Route4Me, OptimoRoute) che incorporano l'euristica TSP.
  3. Integrazione con i sistemi di spedizione:[ Collegare l'ottimizzatore ad un'app per driver mobile e un sistema di gestione degli ordini di backend per spingere le rotte e ricevere aggiornamenti di stato in tempo reale.
  4. Miglioramento continuo:[] Misurare gli indicatori di performance chiave (fermi all'ora, miglia per fermata, percentuale di tempo) e ottimizzare i parametri o i vincoli del risolutore in quanto le operazioni si evolvono.

Anche le piccole imprese con dieci o meno percorsi possono realizzare notevoli risparmi, spesso con una riduzione del 10-20% della distanza, adottando uno strumento di routing basato su TSP, che l'investimento nel software e nella formazione tipicamente ripaga entro mesi attraverso costi ridotti di carburante, manutenzione e straordinario.

Conclusione: L'importanza duratura di un problema classico

Il problema del venditore viaggiante è emerso in prima persona nelle sale tranquille della matematica del XIX secolo, ma ora guida gli algoritmi che forniscono pacchetti a porte chiuse in tutto il mondo. Dai centri di smistamento di Amazon ad un forno a un solo strumento di cucina in una città rurale, l'ottimizzazione di percorsi ispirata a TSP taglia i rifiuti, salva i soldi, e riduce l'impatto ambientale.