Introduction
Le célèbre problème dit du "voyageur de commerce", problème étudié par Dantzig dès 1954.
Ce problème consiste à trouver un parcours passant par les 33 villes figurant sur une carte et le plus court possible.
Le graphe ci-dessous correspond à un problème avec 5 villes en supposant que toutes les liaisons sont possibles. Les distances sont mises arbitrairement.
Il s’agit de partir d’un sommet et d’y revenir en parcourant une fois et une seule chaque sommet avec l’itinéraire le plus court.
Cet itinéraire est indépendant de la ville de départ.
Par exemple, la longueur de l’itinéraire a b c d e a est égale à 38 alors que celle de a b e c d a vaut 40.
Le problème
Définition d'un cycle ou d'un circuit hamiltonien
Un cycle hamiltonien est un cycle qui passe une fois et une seule par chaque sommet du graphe.
On dit aussi tournée ou tour.
Si le graphe est orienté, on définit de la même manière un circuit hamiltonien.
Dans un graphe de n sommets, le nombre de tournées est égal à (n-1)!, qui correspond aux nombres de permutations de n-1 éléments. ((n-1)! et non n! car on peut partir d'un sommet quelconque).
A chaque arête (ou arc si le graphe est orienté) on affecte un nombre cij qui peut, par exemple, représenter un coût, un temps ou… une longueur. On l’appelle longueur de l’arête (ou de l'arc).
Définitions
Cas non orienté ou symétrique cij = cji
Il s'agit de déterminer parmi tous les cycles hamiltoniens, celui (ou ceux) de longueur minimale.
Cas orienté (ou non symétrique) cij ≠ cji
Il s'agit de déterminer parmi tous les circuits hamiltoniens, celui (ou ceux) de longueur minimale.
Le problème du voyageur de commerce est le cas le plus simple du problème d’organisation de tournées de livraisons.
Exemple de problème modélisable par un problème de voyageur de commerce
Le processus de peinture des carrosseries automobiles est complexe et, dans certains cas, il comprend le passage des carrosseries dans une cuve de peinture. Après une série d’une peinture donnée, on change de peinture.
Le passage d'une peinture à une autre génère un coût fixe, dû au temps d’arrêt pour le nettoyage de la cuve ainsi qu'à la perte des matières premières résiduelles.
Le coût qui en découle dépend des peintures qui se succèdent.
Le problème est de déterminer l’ordre de passage des différentes peintures de manière à minimiser tous les coûts de changement.
Ce problème est modélisé par un problème de voyageur de commerce. On définit un graphe dont les sommets sont associés aux différents coloris. Chaque arc (le problème est non symétrique car passer de i à j n’a pas le même coût que passer de j à i), représente le passage d'une peinture à la suivante. La longueur correspond au coût de changement de coloris.
Solutions
Le problème de voyageur de commerce appartient à une catégorie de problème pour lequel on ne possède actuellement pas d'algorithme dont le temps de calcul croit de manière raisonnable, c'est-à-dire polynomiale, avec la taille du problème.
Lorsque la taille du problème devient élevée (selon les données cela peut être quelques centaines de villes) on se contente de petits problèmes ou l'on abandonne l'idée d'obtenir une solution optimale.
Face à ce challenge, on va se contenter de méthodes approchées encore appelées "heuristiques" qui vont permettre de trouver rapidement une solution que l’on n’espère pas trop éloignée de la solution optimale.
Heuristique du plus proche voisin
Principe
On part d'une ville quelconque et l'on se dirige vers la ville la plus proche sans repasser par une ville déjà visitée.
Partir d'un sommet
TANT QUE la tournée n'est pas complète
Aller à la ville la plus proche non encore visitée
FINTANTQUE
Cette heuristique très simple peut donner des résultats arbitrairement mauvais.
Si la longueur de l'arête (a, e) est égale à M, nombre arbitrairement grand, l'heuristique du plus proche voisin donnera toujours la tournée a b c d e a dont la longueur (28 + M) peut être aussi éloignée que l'on veut de la solution optimale qui est en fait, dès que la longueur de (a, e) dépasse 11, le tour a b c e d a de longueur 39.