Le problème du vendeur voyageur

Le problème des vendeurs de voyages est un problème classique dans l'étude des opérations impliquant un vendeur itinérant qui doit visiter le nombre N de villes. Nous sommes ici confrontés au problème de définir le chemin le plus court qu'il souhaite emprunter. Ce problème n'a pas de solution temporelle polynomiale car la complexité de la détermination du chemin le plus court augmente en fonction du facteur N pour les grandes valeurs N.

Un ordinateur chargé de découvrir l'itinéraire le plus court à partir d'un ensemble de différents trajets possibles ne sera pas en mesure de calculer l'itinéraire le plus court pour de très grandes valeurs du nombre de villes. La complexité des algorithmes est classée comme exponentielle, polynomiale, logarithmique, etc., la complexité du TSP est fonction du facteur (n).

Illustrons-le par un exemple. Pour un tournoi dans 3 villes, aucune des combinaisons possibles n'est 6. Voici une liste des villes possibles et non-tournois dans la liste ci-dessous.

4 visites de la ville = non. des tournois possibles est de 24

5 visites de la ville = non. des tournois possibles est de 120

6 visites de la ville = non. des tournois possibles est 720

7 visites de la ville = non. des tournois possibles est 5040

8 tours de ville = nombre de tournois possibles: 40320

9 tours de ville = le nombre de tournois possibles est 362880

10 tours de ville = le nombre de tournois possibles est de 3628800

Comme on peut le voir facilement, le nombre de calculs requis par un ordinateur pour déterminer l'itinéraire le plus court augmente à 362880 pour un tour de seulement 9 villes et pour un tour de 50 villes, la complexité augmente à 3,04141E + 64.

Ainsi, un ordinateur ne peut tout simplement pas traiter autant d'instructions dans le temps limité pour des besoins plus grands et réels. La puissance de traitement disponible sur les ordinateurs modernes prendrait des milliards d'années pour trouver une solution à un problème de vendeurs pour une valeur d'entrée (aucune des villes) qui serait égale à 100.

Le TSP peut être résolu en utilisant des formules de programmation linéaire / programmation linéaire d'intérêt et en utilisant des méthodes Simplex ou Plan de coupe.

Au lieu d'utiliser une technique de force brute, vous pouvez réduire le nombre de tours possibles en utilisant la programmation dynamique. On peut résoudre le TSP en utilisant des heuristiques.

Le TSP est considéré comme NP-Difficile ou en d'autres termes, il n'y a pas de solution générale à ce problème à moins qu'il ne soit prouvé que P = NP.