Le problème du voyageur de commerce (souvent appelé TSP) est un problème algorithmique classique dans le domaine de l'informatique et de la recherche opérationnelle. Il est axé sur l'optimisation. Dans ce contexte, une meilleure solution signifie souvent une solution moins chère, plus courte ou plus rapide. Le TSP est un problème mathématique. Il s'exprime le plus facilement sous la forme d'un graphe décrivant les emplacements d'un ensemble de nœuds.
Le problème du voyageur de commerce a été défini dans les années 1800 par le mathématicien irlandais W. R. Hamilton et par le mathématicien britannique Thomas Kirkman. Le jeu Icosian de Hamilton était un puzzle récréatif basé sur la découverte d'un cycle hamiltonien. La forme générale du TSP semble avoir été étudiée pour la première fois par des mathématiciens dans les années 1930 à Vienne et à Harvard, notamment par Karl Menger. Menger définit le problème, considère l'algorithme de force brute évident et observe la non-optimalité de l'heuristique du plus proche voisin :
Nous désignons par problème de messagerie (puisque dans la pratique cette question devrait être résolue par chaque facteur, de toute façon aussi par de nombreux voyageurs) la tâche de trouver, pour finitely de nombreux points dont les distances par paires sont connues, le chemin le plus court reliant les points. Bien entendu, ce problème peut être résolu par de nombreux essais. On ne connaît pas de règles qui feraient passer le nombre d'essais en dessous du nombre de permutations des points donnés. La règle selon laquelle il faut d'abord aller du point de départ au point le plus proche, puis au point le plus proche de celui-ci, etc. ne permet généralement pas d'obtenir l'itinéraire le plus court.
Hassler Whitney, de l'université de Princeton, a introduit peu après le problème des vendeurs itinérants de noms.
