Découvrez les secrets des algorithmes TSP : un guide visuel

Principales méthodes heuristiques pour résoudre le problème du voyageur de commerce (TSP)

Heuristique du plus proche voisin : Une approche simple et gloutonne qui consiste à visiter la ville non visitée la plus proche à chaque étape.
Heuristique d’insertion la moins chère : Commence avec un sous-circuit et insère de façon incrémentale des villes à des positions qui minimisent l’augmentation de la longueur du trajet.
Heuristique 2-opt : Une méthode d’amélioration locale qui supprime deux arêtes d’un trajet et les reconnecte d’une autre façon, si cela raccourcit le trajet.

Comprendre le problème du voyageur de commerce (TSP)

Le problème du voyageur de commerce (TSP) est un problème classique d’optimisation combinatoire qui vise à trouver le trajet le plus court possible qui visite chaque ville d’une liste une seule fois et revient à la ville de départ. Il s’agit d’un problème NP-difficile, ce qui signifie qu’il n’existe pas d’algorithme connu qui puisse le résoudre en temps polynomial. À mesure que le nombre de villes augmente, la complexité du problème croît de façon exponentielle, ce qui rend la recherche d’une solution optimale difficile pour les instances à grande échelle.

Le TSP peut être modélisé sous forme de graphe où les villes représentent les nœuds et les distances entre les villes représentent les arêtes. L’objectif est de trouver un cycle hamiltonien (un trajet qui visite chaque nœud exactement une fois et revient au nœud de départ) avec le poids minimal.

L’importance du TSP

Le TSP n’est pas seulement un problème mathématique théorique ; il a de nombreuses applications pratiques dans divers domaines, tels que :

Logistique et transport : Optimiser les itinéraires de livraison, les itinéraires de transport et les itinéraires des véhicules.
Fabrication : Ordonner les tâches pour minimiser le temps de déplacement d’une machine.
Robotique : Planifier les mouvements d’un robot pour effectuer des tâches de la manière la plus efficace.
Génétique : Mettre en ordre les gènes dans un génome.

En raison de sa large applicabilité, le TSP est un point de référence pour le développement et l’évaluation des algorithmes d’optimisation.

Méthodes heuristiques pour le TSP

Étant donné que le TSP est un problème NP-difficile, il est souvent impossible de trouver la solution optimale pour les instances à grande échelle dans un délai raisonnable. Par conséquent, les méthodes heuristiques sont utilisées pour trouver des solutions « assez bonnes » qui ne sont pas nécessairement optimales, mais qui sont obtenues en un temps de calcul raisonnable. Les heuristiques peuvent être classées en différentes catégories, notamment les heuristiques constructives, les heuristiques d’amélioration locale et les métaheuristiques.

1. Heuristique du plus proche voisin (NN)

L’algorithme du plus proche voisin est l’une des heuristiques les plus simples pour le TSP. Il s’agit d’un algorithme glouton qui commence dans une ville aléatoire et visite de façon itérative la ville non visitée la plus proche jusqu’à ce que toutes les villes aient été visitées. Enfin, il revient à la ville de départ.

Étapes de l’algorithme NN :

Sélectionnez une ville de départ aléatoire.
Trouvez la ville non visitée la plus proche de la ville actuelle.
Visitez cette ville et marquez-la comme visitée.
Répétez les étapes 2 et 3 jusqu’à ce que toutes les villes aient été visitées.
Retournez à la ville de départ.

L’heuristique NN est facile à implémenter et rapide, mais elle ne donne souvent pas de bons résultats. Sa nature gloutonne peut conduire à de mauvaises décisions au début qui ne peuvent pas être corrigées plus tard.

2. Heuristique d’insertion la moins chère

L’heuristique d’insertion la moins chère commence par un sous-trajet (généralement un trajet composé de deux villes) et insère de façon incrémentale les villes restantes dans le trajet. À chaque étape, elle choisit la ville et la position d’insertion qui minimisent l’augmentation de la longueur du trajet.

Étapes de l’algorithme d’insertion la moins chère :

Commencez avec un sous-trajet composé de deux villes.
Pour chaque ville non visitée, trouvez la position d’insertion qui minimise l’augmentation de la longueur du trajet.
Insérez la ville qui donne la plus petite augmentation dans le trajet.
Répétez les étapes 2 et 3 jusqu’à ce que toutes les villes aient été insérées.

L’heuristique d’insertion la moins chère est généralement meilleure que l’heuristique NN, mais elle est aussi plus lente. Elle prend en compte l’impact de l’insertion de chaque ville, ce qui permet d’éviter de mauvaises décisions au début.

3. Heuristique 2-opt

L’heuristique 2-opt est une méthode d’amélioration locale qui commence par un trajet valide et améliore de façon itérative en effectuant des 2-opt. Un 2-opt consiste à supprimer deux arêtes du trajet et à les reconnecter d’une autre façon. L’objectif est de trouver une paire d’arêtes qui, lorsqu’elles sont reconnectées, raccourcissent la longueur du trajet.

Étapes de l’algorithme 2-opt :

Commencez par un trajet valide.
Pour chaque paire d’arêtes dans le trajet, vérifiez si la suppression et la reconnexion des arêtes raccourcissent la longueur du trajet.
Si une amélioration est trouvée, effectuez le 2-opt et répétez l’étape 2.
Sinon, arrêtez-vous.

L’heuristique 2-opt est une heuristique simple mais efficace qui peut améliorer de façon significative la qualité des solutions TSP. Elle peut être appliquée à n’importe quel trajet initial, tel que celui obtenu à l’aide des heuristiques NN ou d’insertion la moins chère.

Voici une vidéo qui explique comment fonctionne l’heuristique 2-opt pour le TSP :

Cette vidéo fournit une explication claire et visuelle de la façon dont l’heuristique 2-opt optimise un trajet TSP en échangeant des arêtes pour réduire la distance totale. Elle montre les étapes itératives du processus 2-opt et l’explique clairement, ce qui la rend accessible et facile à comprendre. Cette heuristique est particulièrement utile, car elle peut être appliquée à n’importe quelle solution TSP initiale pour l’améliorer.

4. Autres heuristiques

Voici d’autres heuristiques pour le TSP :

Heuristique de l’arbre couvrant minimal (MST) : Construit un MST de toutes les villes, puis parcourt l’arbre pour créer un trajet.
Heuristique de Christofides : Améliore l’heuristique MST en ajoutant une correspondance parfaite de poids minimal aux nœuds impairs du MST.
Algorithme de Clarke et Wright (heuristique d’épargne) : Commence par un ensemble de trajets vers et depuis un dépôt et fusionne de façon itérative les trajets en fonction de leur valeur d’épargne.
Système de colonies de fourmis (ACO) : Une métaheuristique inspirée du comportement de recherche de nourriture des fourmis.

Comparaison des heuristiques TSP

Le tableau suivant compare les heuristiques TSP discutées ci-dessus en fonction de leur complexité temporelle, de leur qualité de solution et de leur facilité d’implémentation.

Heuristique	Complexité temporelle	Qualité de la solution	Facilité d’implémentation
Plus proche voisin	\(O(n^2)\)	Médiocre	Facile
Insertion la moins chère	\(O(n^3)\)	Bon	Moyenne
2-opt	\(O(n^3)\)	Bon	Moyenne
Arbre couvrant minimal	\(O(n^2)\) ou \(O(n \log n)\)	Moyenne	Moyenne
Christofides	\(O(n^3)\)	Bon	Difficile
Clarke et Wright	\(O(n^2 \log n)\)	Moyenne	Moyenne
Colonie de fourmis	\(O(n^2 m)\) (où m est le nombre de fourmis)	Bon	Difficile

Où \(n\) est le nombre de villes.

Illustrations visuelles des heuristiques TSP

Voici des illustrations visuelles de différentes heuristiques TSP appliquées au même ensemble de villes. Ces images montrent comment chaque algorithme construit un trajet différent et comment la qualité des solutions peut varier.

Figure 1 : Une illustration de l’heuristique 2-opt, qui échange des arêtes pour améliorer la longueur du trajet. Cet algorithme consiste à supprimer deux arêtes et à les reconnecter d’une nouvelle façon, de façon itérative, afin d’obtenir un trajet plus court.

Figure 2 : Un exemple de l’algorithme d’optimisation par colonies de fourmis, inspiré du comportement des fourmis lorsqu’elles trouvent le meilleur trajet vers une source de nourriture. Les fourmis déposent des phéromones, qui guident les futures fourmis vers les trajets les plus courts.

Heuristic Smoothing Ant Colony Optimization

Figure 3 : Une visualisation de l’optimisation par colonies de fourmis lissée par heuristique, une approche plus avancée. Cette méthode améliore le processus standard ACO en intégrant des techniques de lissage heuristique pour trouver des solutions plus optimales.

Figure 4 : Cette image illustre l’adaptation de la visibilité dans l’optimisation par colonies de fourmis, ce qui améliore la façon dont les fourmis perçoivent et utilisent les informations pour trouver des trajets optimaux. Cette adaptation peut conduire à des solutions plus efficaces dans le TSP.