Il problema del venditore ambulante (TSP) è un problema algoritmico incaricato di trovare il percorso più breve tra un insieme di punti e luoghi che devono essere visitati. Nella dichiarazione del problema, i punti sono le città che un venditore potrebbe visitare. L'obiettivo del venditore è mantenere i costi di viaggio e la distanza percorsa il più bassi possibile.
Incentrato sull'ottimizzazione, il TSP viene spesso utilizzato nell'informatica per trovare il percorso più efficiente per il viaggio dei dati tra i vari nodi. Le applicazioni includono l'identificazione dei metodi di ottimizzazione della rete o dell'hardware. Fu descritto per la prima volta dal matematico irlandese WR Hamilton e dal matematico britannico Thomas Kirkman nel 1800 attraverso la creazione di un gioco risolvibile trovando un ciclo di Hamilton, che è un percorso non sovrapposto tra tutti i nodi.
Il TSP è stato studiato per decenni e sono state teorizzate diverse soluzioni. La soluzione più semplice è provare tutte le possibilità, ma questo è anche il metodo più dispendioso in termini di tempo e denaro. Molte soluzioni utilizzano l'euristica, che fornisce risultati probabilistici. Tuttavia, i risultati sono approssimativi e non sempre ottimali. Altre soluzioni includono algoritmi branch and bound, Monte Carlo e Las Vegas.
Piuttosto che concentrarsi sulla ricerca del percorso più efficace, TSP si occupa spesso di trovare la soluzione più economica. Nei TSP, la grande quantità di variabili crea una sfida quando si trova il percorso più breve, il che rende le soluzioni approssimative, veloci ed economiche ancora più attraenti.