La méthode de recherche tabou est également couramment utilisée pour résoudre le

problème du voyageur de commerce (TSP - Traveling Salesman Problem), qui est un

problème classique de recherche opérationnelle. Le TSP consiste à trouver le chemin
le plus court qui permet à un voyageur de visiter un ensemble de villes une seule
fois et de retourner à la ville de départ. L'application de la méthode de recherche
tabou au TSP suit une structure similaire à celle décrite précédemment. Voici
comment vous pouvez l'appliquer
B. Application de la méthode de recherche tabou au TSP :
1. Définition de la structure de voisinage : Pour le TSP, la structure de
voisinage peut être définie par des opérations telles que l'échange de villes entre
deux itinéraires, l’inversion de sous-chemins, etc.
2. Initialisation : Commencez par une solution initiale qui peut être générée de
manière aléatoire ou en utilisant une heuristique, par exemple, la méthode de
l'insertion la plus proche.
3. Fonction objectif : La fonction objectif mesure la longueur totale de
l'itinéraire, c'est-à-dire la distance totale parcourue par le voyageur. L'objectif
est de minimiser cette fonction en modifiant la solution actuelle.
4. Recherche locale : Effectuez une recherche locale pour explorer les solutions
voisines. À chaque itération, choisissez une solution voisine avec une longueur
d'itinéraire améliorée, tout en évitant les solutions taboues.
5. Critères d'arrêt : La recherche se poursuit jusqu'à ce qu'un certain critère
d'arrêt soit atteint, comme un nombre maximum d'itérations, un temps limite ou une
solution satisfaisante.
6. Mise à jour des solutions taboues : Les solutions taboues, qui sont des
itinéraires interdits temporairement pour éviter de revenir en arrière, sont mises
à jour à chaque itération pour permettre une exploration plus large de l'espace de
recherche.
7. Solution finale : La meilleure solution trouvée après plusieurs itérations
est considérée comme la solution finale au problème.
8. Validation : La solution finale est validée pour s'assurer qu'elle respecte
les contraintes du problème, c'est-à-dire que toutes les villes sont visitées
exactement une fois.

C. Une application de la recherche Tabou au problème TSP :

(1) Une représentation de la solution :
Une solution réalisable est représentée comme une séquence de nœuds,
codé par un tableau des entiers qui représente le successeur et le prédécesseur de
chaque ville.
6 2 4 1 5 8 3 7
Ainsi, le tableau représente le circuit suivant :
le point de départ est la ville 6 qui est aussi la ville d’arrivée, en passant par
les villes selon leur ordre d’apparition dans le tableau
6241583
(2) Solution initiale :
Une bonne solution possible mais non optimale pour le TSP
peut être trouvé rapidement en utilisant une approche heuristique. En commençant
par le premier nœud dans la tournée, et trouver le nœud le plus proche. Chaque fois
trouver le nœud le plus proche non visitée á partir du nœud courant jusqu’il ce que
tous les nœuds soient visitées.

(3) Voisinage :
Un voisinage pour une solution donnée est définie comme toute autre solution qui
est obtenue par un échange par paire de deux nœuds de la solution. Ceci garantit
toujours que
tout voisinage d’une solution réalisable est toujours une solution réalisable (c-a-
d, ne forme

pas de sous-tour). Si nous fixons le nœud 1 comme point de départ et la fin de

nœud, pour un
Problème de n nœuds, il y a C voisinages. A chaque itération, le voisinage est
sélectionné par rapport à une fonction objective (distance minimale). Nous avons
l’exemple ci-dessous :

Solution de voisinage obtenue en échangeant les ordres de visite des

villes 2 et 5.
(4) Critères d’arrêts :
Des critères d’arrêts possible sont :
-Si une solution prouvé optimal a été trouvé.
- Un nombre maximal prédéfini a été attient ou un temps à ne pas dépasser.
- Si la recherche semble stagnée sans amélioration de la meilleure solution
trouvée.
 Représentation de problème :
Le problème du voyageur de commerce peut être
modélisé à l’aide d’un graphe constitué d’un ensemble de sommets et d’un ensemble
d’arêtes. Chaque sommet représente une ville, une arête symbolise le passage d’une
ville à une autre, et on lui associe un poids pouvant représenter une distance, un
temps de parcours ou encore un coût. Ci-contre, un exemple de graphe à 4 sommets.

Exemple de graphe à
4 sommets.
Résoudre le problème du voyageur de commerce revient à trouver dans ce
graphe un cycle passant par tous les sommets une unique fois (un tel cycle est dit
« hamiltonien ») et qui soit de longueur minimale. Pour le graphe ci-contre, une
solution à ce problème serait le cycle 1, 2, 3, 4 et 1, correspondant à une
distance totale de 23. Cette solution est optimale, il n’en existe pas de
meilleure.
Comme il existe une arête entre chaque paire de sommets, on dit que
ce graphe est « complet ». Pour tout graphe, une matrice de poids peut être
établie. En lignes figurent les sommets d’origine des arêtes et en colonnes les
sommets de destination ; le poids sur chaque arête apparaît à l’intersection de la
ligne et de la colonne correspondantes. Pour notre exemple, cette matrice est la
suivante :
0 5 8 7
5 0 6 7
8 6 0 5
7 7 5 0

Dans cet exemple, le graphe est « non orienté », c’est-à-dire

qu’une arête peut être parcourue indifféremment dans les deux sens, cela explique
que la matrice soit symétrique. Cette symétrie n’est pas forcément respectée dans
le cas d’un graphe orienté. Il existe alors deux catégories de problèmes : le cas
symétrique (le poids de l’arc du sommet X vers Y est égal au poids de l’arc du
sommet Y vers X) et le cas asymétrique (le poids de l’arc du sommet X vers Y peut
être différent du poids de l’arc du sommet Y vers X)

 Méthodes de résolution :
 Comme pour le problème du sac à dos (un autre des problèmes les
plus connus dans le domaine de l’optimisation combinatoire et de la recherche
opérationnelle), il existe deux grandes catégories de méthodes de résolution : les
méthodes exactes et les méthodes approchées. Les méthodes exactes permettent
d’obtenir une solution optimale à chaque fois, mais le temps de calcul peut être
long si le problème est compliqué à résoudre. Les méthodes approchées, encore
appelées heuristiques, permettent quant à elles d’obtenir rapidement une solution
approchée, mais qui n’est donc pas toujours optimale.