Un veicolo, senza capacità, ritorno all'origine: trovare il tour chiuso di distanza minima che visita ciascuno degli N nodi esattamente una volta. Il problema fondante dell'ottimizzazione combinatoria — tutte le varianti VRP ne ereditano l'ossatura (nome accademico: TSP).
In breve
Ti suona familiare?
- Abbiamo un servizio di campo mono-veicolo — un tecnico visita 8-15 clienti al giorno e la sequenza la decide il tecnico per intuito.
- Nella nostra manifattura media un commerciale fa un giro regionale una volta a settimana (15-40 visite a fornitori o clienti); un veicolo, nessun vincolo di capacità, l'ordine non è ottimo.
- Operiamo una foratrice PCB o una macchina pick-and-place automatica — la testa visita 500-5.000 punti, la sequenza la decide il programmatore della macchina.
- Pianifichiamo un tracciato di posa cavi o una sequenza di posa tubazioni — una squadra, un tour, nessun vincolo di capacità.
- Un robot di magazzino (AS/RS a singolo prelievo) costruisce tour per scaffalature — il robot non ha vincolo di capacità o trasporta un solo oggetto.
- Giro urbano fornitori in catena del freddo (un veicolo, carico piccolo); l'ordine è impostato dall'abitudine dell'autista.
- Il nostro numero di nodi è 50-500 — scala gestibile da un MIP esatto, ma l'intuito 'TSP è NP-difficile, bisogna usare un'euristica' ci tiene fermi sull'euristica.
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Costruisci prima la matrice di distanze pairwise (distanza stradale reale, simmetrica o asimmetrica), poi a seconda della scala — sotto i 1.000 nodi: solver MIP esatto; oltre: ricerca locale k-opt (famiglia Lin-Kernighan) — ottieni la tour in minuti.
In letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business) il problema si chiama Travelling Salesman Problem (TSP — problema del commesso viaggiatore), studiato da oltre 70 anni come problema fondante dell’ottimizzazione combinatoria moderna. Enunciato canonico: dati N nodi (città, clienti, punti di foratura, giunzioni di cavo) e una matrice di distanze pairwise (o tempo, o costo), trovare il tour hamiltoniano (tour chiuso che visita ogni nodo una volta) di costo totale minimo che visita ogni nodo esattamente una volta e torna al punto di partenza. Un veicolo, nessuna capacità, nessuna finestra temporale, il deposito coincide sempre con il nodo di partenza. Soluzione in tre fasi:
1. Modellazione. Dati di input: elenco dei nodi (per ogni nodo posizione o etichetta identificativa), matrice delle distanze pairwise (euclidea, distanza stradale reale o tempo — basata su rete viaria per i tour urbani, Manhattan per la testa di una macchina), simmetria (se la distanza A→B = B→A, TSP simmetrico; altrimenti — es. sensi unici — TSP asimmetrico / ATSP), proprietà metrica (se vale la disuguaglianza triangolare, TSP metrico e si applica un’euristica di 3/2-approssimazione con garanzia). Obiettivo: costo totale del tour minimo. Vincoli: ogni nodo visitato esattamente una volta + un unico tour chiuso (sub-tour vietati).
2. Decisione con il solver. Tre approcci accademici principali: (i) Branch-and-cut MIP esatto (ramificazione-e-taglio — ricerca ad albero con piani di taglio) — il metodo dei piani di taglio è stato introdotto negli anni 1950; solver maturi hanno risolto istanze TSP fino a 85K+ nodi in modo esatto. Per scala di campo (50-500 nodi), i solver MIP commerciali o open-source maturi (Mixed-Integer Linear Programming — ottimizzazione con alcune variabili 0/1 e altre continue) finiscono in minuti. (ii) Programmazione dinamica (Held-Karp) — la formulazione DP O(n²·2^n) degli anni 1960; pratico per n < 25, riferimento didattico. (iii) Euristica — famiglia Lin-Kernighan — ricerca locale k-opt (rimuove k archi dal tour e riconnette in modo ottimo); l’implementazione moderna LKH (Lin-Kernighan-Helsgaun) resta entro lo 0,1-1% dall’ottimo fino a scala di milioni di nodi ed è l’euristica di riferimento per istanze di campo dai 1.000 nodi in su. Euristiche mattone: nearest-neighbor, Christofides 3/2 (TSP metrico), savings, ricerca locale 2-opt e 3-opt.
3. Integrazione in campo. Output a tre strati a seconda dell’uso: (a) operazione di servizio di campo — elenco di fermate ordinate + navigazione nell’app mobile dell’autista, assegnato a inizio giornata, di norma non ri-ottimizzato intra-day; (b) programmazione macchina — sequenza di foratura o di posa incorporata nel programma NC di una foratrice PCB o di un pick-and-place, calcolata una volta per lotto di pezzi; (c) tracciato cavi o tubi — il piano di rotta del progettista, decisione unica prima della prova. Il modulo TSP è generalmente incastonato in un software di routing o in un pacchetto di programmazione di linea — raramente venduto come prodotto autonomo. Comitato trimestrale di operazioni: distanza reale del tour vs piano, deriva del tempo dell’autista, numero di tour extra.
Alternative
Sequenziamento intuitivo + spreadsheet
GratuitoNessuna licenza
Per chi: Molto piccola scala (sotto 10 fermate/giorno), quanto il pianificatore tiene in testa
- + Nessun costo software
- + Conta la conoscenza di campo del pianificatore
- + Risposta telefonica ai cambi di ETA
- − Oltre le 20 fermate la mente devia 20-40% dall'ottimo
- − Incoerente — la sequenza cambia di giorno in giorno
- − Nessuna misura — le distanze non sono registrate
- − Crolla rapido se serve multi-veicolo o capacità (diventa VRP)
Software generale di routing / servizio di campo (modulo TSP incorporato)
Aziendale100-400 TRY/veicolo/mese in abbonamento o 200K-800K TRY licenza una tantum
Per chi: Operazione di servizio di campo (10-50 veicoli), tour mono-veicolo, senza capacità
- + Motore di ordinamento del tour presente — nearest-neighbor + miglioramento locale è tipico
- + App mobile per autista, navigazione, info cliente integrate
- + Mappe e dati di traffico locali
- − Trasparenza dell'algoritmo bassa — 'quale metodo viene usato' raramente con risposta chiara
- − Un solver con garanzia di ottimo in genere assente, solo approssimazione rapida
- − Oltre le 500 fermate il gap dal tour migliore cresce
Solver open-source + modulo TSP su misura
Open SourceLicenza gratuita; sviluppo interno 8-16 settimane o 200K-800K TRY di consulenza
Per chi: Operazione con un team tech, programmazione macchina (PCB, CNC), rotta di campo specializzata
- + Solver con garanzia di ottimo disponibili in open source
- + Strumenti euristici standard di settore che restano vicini all'ottimo fino a scala di milioni di fermate sono open source
- + Varianti come tour su sensi unici o con profitti possono essere adattate
- − Servono uno specialista di ottimizzazione interno + team di integrazione
- − Dal primo prototipo al sistema di campo 3-6 mesi
- − La manutenzione resta in casa
Pacchetto di programmazione macchina industry-specific (PCB / CNC)
Aziendale500K-3M TRY incorporato nel pacchetto software della macchina
Per chi: Foratrice PCB automatica, pick-and-place, taglio laser — pacchetto del costruttore
- + Sequenza di testa di foratura/posa calibrata dal costruttore
- + Output del programma di macchina carica direttamente sull'impianto
- + Formazione operatore inclusa dal costruttore
- − Legato al costruttore — riacquisto se si cambia macchina
- − Algoritmo opaco, gap dal tour migliore non misurabile
- − Personalizzazione (es. penalità di cambio utensile) difficile
Raccomandazione
Chiedi nell'incontro
- Quale approccio usa il motore di ordinamento del tour — solver con garanzia di ottimo, nearest-neighbor + miglioramento locale, euristica standard di settore, oppure solo nearest-neighbor?
- La matrice delle distanze supporta sensi unici e tempo dipendente dalla direzione, oppure A→B e B→A sono sempre assunti uguali?
- Come si genera la matrice delle distanze — linea retta, basata su strada reale, o matrice tempo dipendente dal traffico? Cadenza di aggiornamento?
- Qual è il tempo di soluzione per dimensioni tipiche dell'istanza — 100, 500, 1.000 fermate?
- La percentuale di scostamento dal tour migliore possibile viene riportata dal modulo?
- Quando il problema cresce da un solo veicolo a routing capacitato multi-veicolo (capacità, più tour, ritorno al deposito), si può riutilizzare la stessa infrastruttura, o è un modulo a parte?
- Se il contratto termina, in quale formato si possono esportare i dati di tour (posizioni delle fermate, tour generati, matrici di distanze)?
Dettagli tecnici
Nota editoriale
Questo problema si chiama in officina “pianificazione del tour”, “ordine delle visite” o “sequenza di rotta”. Il nome accademico è chiaro: Travelling Salesman Problem (TSP). TSP è il problema fondante della ricerca operativa — VRP (#002), PDPTW (#046), Berth Allocation (#026) e decine di altri problemi di routing / scheduling sono estensioni strutturali del TSP. La distinzione strutturale è netta: TSP è un solo veicolo, un tour chiuso, senza capacità, ritorno alla partenza, senza finestre temporali. VRP aggiunge multi-veicolo + deposito + capacità; VRPTW aggiunge le finestre; PDPTW aggiunge la coppia origine-destinazione e la precedenza. Acquistare il “modulo di routing” di un fornitore senza verificare quale di queste strutture risolve davvero significa scoprire mesi dopo — quando arriva la necessità multi-veicolo — che l’infrastruttura non basta.
Punto più spesso omesso nel settore: la soglia pratica di applicabilità dei solver esatti moderni. L’intuito pratico è spesso ‘TSP è NP-difficile (classe di problemi il cui tempo di risoluzione esplode con la dimensione), esatto impossibile, serve un’euristica’. La realtà: solver branch-and-cut maturi hanno risolto istanze da 85K+ nodi in modo esatto; un’istanza di campo da 100-500 nodi raggiunge l’ottimo in minuti su un MIP moderno. Le euristiche (nearest-neighbor + 2-opt) sono il default nella maggior parte dei prodotti — deviano 15-30% dall’ottimo su dati reali. Regola pratica: sotto i 1.000 nodi il TSP operativo è MIP-esatto; nell’intervallo 1.000-100K l’euristica LKH resta entro lo 0,1-1% dall’ottimo. L’intuito ‘serve un’euristica’ non è corretto; non si può decidere senza conoscere la scala.
Secondo punto omesso: distinzione simmetrico vs asimmetrico. Le rotte urbane con sensi unici, ingressi e uscite di tangenziale o tempi di percorrenza dipendenti dalla direzione producono una matrice di distanze asimmetrica — A→B differisce da B→A. La maggior parte dei moduli TSP dei prodotti assume simmetria; alimentati con dati asimmetrici producono un ottimo sbagliato. TSP asimmetrico (ATSP) richiede una formulazione differente.
Passo a passo — per la PMI
Fase 1 — Misurare prima, pianificare poi. Almeno 8-12 settimane di dati di tour: per tour — numero di fermate, posizioni delle fermate, distanza reale (contachilometri), durata, identità dell’autista, se la sequenza è stata modificata in giornata, se le finestre cliente sono state rispettate. Matrice delle distanze: distanza e tempo tipici tra ogni coppia di nodi visitati (traffico fluido vs ora di punta). Senza questo inventario non si sa quale software porterà quale risultato.
Fase 2 — Estrarre il capitale di conoscenza. Stimare il gap della sequenza intuitiva attuale dall’ottimo: su un set di 30-50 nodi di una giornata, calcolare il tour esatto con un solver MIP open-source e confrontarlo con il tour reale dell’autista. Gap tipico 15-30%. Questo gap è la pietra angolare del business case. Se il numero di nodi varia giornalmente, separare medie per giorni tipici e di punta.
Fase 3 — Pilota. 6-10 settimane. Per un veicolo o una macchina, far girare il modulo TSP in parallelo alla sequenza intuitiva attuale. La decisione resta in mano all’autista / operatore; il sistema suggerisce. Criteri di successo scritti prima del pilota: distanza media del tour -10% minimo, durata -8%, soddisfazione dell’autista neutra o positiva.
Fase 4 — Roll-out. 4-9 mesi per l’intera flotta o il parco macchine. Comitato trimestrale operativo: distanza reale vs piano, deriva del tempo dell’autista, report sull’impatto sulle finestre cliente, report tempo testa.
Rischi — cosa può andare storto
- Tempo di percorrenza ipotizzato statico. Una matrice di distanze costruita su tempi medi di singolo punto devia 50-100% rispetto al tempo reale nelle ore di punta. È necessaria una matrice di tempi a bande orarie (es. profilo di tempo di arco a 30 minuti); durante il pilota vanno confrontati tempi pianificati vs reali.
- Il tempo di servizio è nel modello? Un tecnico di campo passa 30-90 minuti su ogni fermata; se questo tempo di servizio non è nel piano del tour, la sequenza è matematicamente ottima ma operativamente non praticabile. Tempo di servizio per nodo va modellato come valore fisso o probabilistico.
- Il numero di nodi cresce, l’euristica si allontana dall’ottimo. A 50 nodi nearest-neighbor + 2-opt è entro 5-10% dall’ottimo; a 500 nodi 15-25%; a 5.000 nodi 30%+. Crescendo la scala serve il passaggio a LKH o MIP esatto; congelare l’euristica accumula perdite con la crescita.
- Lock-in con un unico fornitore di software di routing. Senza clausola contrattuale di ’esportazione annuale dei dati di tour, delle matrici di distanze e dello storico delle soluzioni in formato standard’, uscire dal sistema significa perdere la memoria di tour dell’operazione. Posizioni dei clienti e finestre di visita sono il nucleo di tale memoria.
Visione tecnica del metodo risolutivo
| Approccio | Scala tipica | Tempo di soluzione | Ottimo garantito? |
|---|---|---|---|
| Sequenziamento intuitivo (pianificatore + testa) | <20 nodi | istantaneo | No, 60-80% ottimo |
| Nearest-neighbor + 2-opt | 20-200 nodi | secondi | No, 85-95% ottimo |
| Christofides 3/2 (TSP metrico) | 50-500 nodi | secondi | Garanzia 3/2 |
| Programmazione dinamica (Held-Karp) | <25 nodi | minuti | Sì (esatto) |
| Branch-and-cut MIP | 50-100K nodi | minuti-ore | Sì (entro bound) |
| Lin-Kernighan / LKH | 1K-1M+ nodi | minuti-ore | No, 0,1-1% dall’ottimo |
| Metaeuristica (tabù, genetica, ant colony) | flessibile | flessibile | No, buona qualità pratica |
Varianti TSP — scegliere in base al campo:
- TSP simmetrico: distanza A→B = B→A. Strade extraurbane, distanza aerea, foratura PCB. Variante più semplice e più studiata.
- TSP asimmetrico (ATSP): distanza dipendente dalla direzione. Sensi unici, tempo dipendente dalla direzione. Modellazione un po’ più complessa, branch-and-cut comunque applicabile.
- TSP euclideo: nodi nel piano, distanza in linea retta. Foratura PCB, operazioni in linea.
- TSP metrico: vale la disuguaglianza triangolare (A→C ≤ A→B + B→C). Garanzia di Christofides 3/2 valida.
- TSP con profitti / OP: i nodi hanno un valore (profitto); non è obbligatorio visitarli tutti. Variante ‘cliente prioritario’ per il servizio di campo.
Funzione obiettivo — scelta:
- Obiettivo 1 — Distanza / carburante minimi: Focalizzazione carburante + tempo dell’autista.
- Obiettivo 2 — Tempo totale minimo: Focalizzazione tempo dell’autista / ciclo macchina.
- Obiettivo 3 — Tempo massimo di fermata minimo (min-max TSP): Distribuzione equa o sicurezza.
Riferimenti accademici
Elencati nel blocco sources del frontmatter di questa pagina.
Fonti
- Dantzig, G., Fulkerson, R. e Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410. Lavoro fondante dei piani di taglio.
- Lin, S. e Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. Base della famiglia euristica moderna.
- Applegate, D., Bixby, R., Chvátal, V. e Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. Libro canonico del solver esatto branch-and-cut del gruppo Princeton-Georgia Tech.
- Held, M. e Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. La formulazione DP O(n²·2^n).
- Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. LKH — entro lo 0,1-1% dall’ottimo fino a scala di milioni.
- YÖK Tez Merkezi — parola chiave: ‘gezgin satıcı’ o ‘TSP’ o ‘ottimizzazione del tour’ — 30+ tesi dell’accademia turca. tez.yok.gov.tr
Glossario
- Travelling Salesman Problem
- Il problema fondante dell'ottimizzazione combinatoria: trovare in un grafo il tour hamiltoniano di costo minimo che visita ogni nodo esattamente una volta e torna al punto di partenza.
- Branch-and-Cut
- Il framework di risoluzione MIP esatto che combina branch-and-bound con i metodi dei piani di taglio — in ogni nodo dell'albero di ricerca disuguaglianze valide (tagli) restringono il rilassamento LP prima del branching.
- MIP
- Modello di ottimizzazione in cui alcune variabili decisionali devono essere numeri interi (es. numero di camion, numero di turni).
- VRP
- La decisione su quali veicoli, partendo da uno o più depositi, visitano quali clienti e in che ordine.
Problemi correlati
Cosa entra in un camion o container, e in che ordine si carica?
Dato un camion, container o veicolo merci di dimensioni fisse, quale disposizione di scatole (o pallet) con dimensioni, pesi e regole di impilamento diversi dà il più alto tasso di utilizzo? Il nome matematico è Three-Dimensional Bin Packing Problem (3D-BPP), oppure nella variante pratica Container Loading Problem (CLP). I metodi che risolvono contemporaneamente volume, limiti di peso, regole di impilamento, distribuzione del peso (bilanciamento) e sequenza di consegna (multi-drop) sono studiati dagli anni '90. Anche un miglioramento del 5% nell'utilizzo aumenta in modo concreto le consegne per veicolo per una PMI.
Da un nodo all'altro — come calcolo il cammino minimo su un grafo pesato?
Per PMI che devono calcolare il percorso più rapido o più breve tra due punti: squadre di servizio sul campo con 10-50 veicoli (idraulici, elettricisti, riparazione elettrodomestici), operatori urbani di corriere/pacchi o centrali operative che coordinano interventi di emergenza. Ogni giorno arrivano centinaia di domande 'come vado adesso più veloce da A a B?'; la risposta cambia con traffico, chiusure stradali e tipo di mezzo. Un percorso sbagliato costa al tecnico uno-due interventi saltati nella giornata, al corriere una consegna in ritardo e all'azienda un cliente. Una pianificazione manuale o a occhio lascia tipicamente 20-60 minuti sprecati per veicolo al giorno rispetto a un calcolo basato sulla rete.
Dove Apro il Nuovo Magazzino?
Un distributore, un operatore di e-commerce o un produttore pmi prevede di aprire 1–5 nuovi magazzini, filiali o centri di distribuzione nei prossimi 2–5 anni. La decisione: in quale città o regione, quanti siti, di quali dimensioni, e quali magazzini esistenti trasferiscono quale volume di clienti o ordini al nuovo sito. Una localizzazione sbagliata significa 5–10 anni di alti costi di trasporto, consegne in ritardo e perdita di clienti; una buona localizzazione vale 300.000–1,5 milioni di EUR di risparmio annuo nello stesso periodo. Quando la decisione viene presa a sensazione (per esempio 'accanto allo stabilimento, gli operai abitano vicino'), raramente colpisce l'ottimo — perché costo di trasporto, affitto, tasse, costo del lavoro e tempo di servizio sono vincoli da bilanciare insieme.