Naviguer dans le labyrinthe du TSP : Un guide des heuristiques et des algorithmes

Principaux points à retenir sur les algorithmes TSP

• Heuristiques et algorithmes : Comprendre le rôle des heuristiques (par exemple, le voisin le plus proche, l'insertion de coque convexe) et des algorithmes plus complexes (par exemple, le recuit simulé, les algorithmes génétiques) dans la recherche de solutions quasi optimales au TSP.
• Compromis entre précision et efficacité : Reconnaître le compromis inhérent entre la recherche de la solution optimale (qui peut prendre un temps exponentiel) et l'utilisation d'heuristiques qui fournissent des solutions « suffisamment bonnes » rapidement.
• Techniques d'optimisation : Découvrez diverses techniques d'amélioration de tour, telles que l'heuristique 2-opt, qui peuvent être appliquées pour affiner davantage les solutions obtenues à partir d'autres méthodes.

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

Le problème du voyageur de commerce (TSP) est un problème d'optimisation combinatoire classique qui vise à trouver le trajet le plus court possible qui visite chaque ville d'une liste donnée exactement une fois et revient à la ville d'origine. Étant donné une liste de villes et les distances entre chaque paire de villes, le TSP consiste à trouver le chemin le plus court possible qui visite chaque ville une seule fois et revient à la ville d'origine.

Le TSP est un problème NP-difficile, ce qui signifie qu'il n'existe pas d'algorithme en temps polynomial connu qui puisse résoudre toutes les instances du problème. Le nombre de solutions possibles augmente de façon factorielle avec le nombre de villes, ce qui rend impossible la recherche exhaustive de la solution optimale pour les grandes instances. Pour les problèmes de voyageur de commerce du monde réel plus importants, lorsque les méthodes manuelles telles que Google Maps Route Planner ou Excel route planner ne suffisent plus, les entreprises s'appuient sur des solutions approximatives suffisamment optimisées en utilisant des algorithmes tsp rapides qui reposent sur des heuristiques.

Par conséquent, les heuristiques et les algorithmes d'approximation sont utilisés pour trouver des solutions « suffisamment bonnes » dans un délai raisonnable. Ces méthodes ne garantissent pas la solution optimale, mais elles peuvent souvent fournir des solutions proches de l'optimum qui sont acceptables pour les applications pratiques.

Une pléthore d'heuristiques et d'algorithmes TSP

Voici un aperçu de diverses heuristiques et algorithmes utilisés pour résoudre le TSP :

Heuristiques de construction

Ces heuristiques construisent une solution du début à la fin, ajoutant progressivement des villes au tour jusqu'à ce que toutes les villes soient incluses.

Tour aléatoire

Cette méthode crée simplement un tour en sélectionnant les villes dans un ordre aléatoire. Elle sert de base à la comparaison avec d'autres algorithmes plus sophistiqués. Bien qu'elle soit simple à mettre en œuvre, elle donne généralement des résultats médiocres.

Voisin le plus proche (NN)

L'heuristique du voisin le plus proche commence par une ville aléatoire et visite ensuite à plusieurs reprises la ville voisine la plus proche qui n'a pas encore été visitée. Cette méthode est gourmande et simple à mettre en œuvre, mais elle peut souvent conduire à des solutions sous-optimales, en particulier dans les derniers stades, où elle peut être forcée de faire des sauts longs pour visiter les villes restantes.

Insertion par coque convexe

Cette heuristique commence par la coque convexe des villes (l'ensemble de villes le plus petit convexe qui contient toutes les villes). Elle insère ensuite les villes restantes une par une dans le tour, à l'endroit qui entraîne l'augmentation la plus faible de la longueur du tour. Cette méthode tend à bien fonctionner lorsque les villes sont regroupées près de la coque convexe.

Insertion la moins chère

Semblable à l'insertion de coque convexe, l'insertion la moins chère insère itérativement des villes dans le tour. Cependant, elle sélectionne la ville à insérer et son emplacement dans le tour en fonction de l'augmentation la plus faible possible de la longueur du tour. Cette méthode est généralement plus précise que le voisin le plus proche, mais elle prend plus de temps.

Arbre en forme d’anneau

L'heuristique de l'arbre en forme d'anneau construit un arbre en forme d'anneau des villes et traverse ensuite l'arbre pour créer un tour. La forme de l'anneau peut être générée à l'aide d'un algorithme de graphe minimum. Cela implique de trouver un arbre couvrant minimum (MST) du graphe, puis d'ajouter des arêtes pour créer un cycle eulérien, qui peut ensuite être transformé en un tour TSP en utilisant des raccourcis.

Tournée bitonique

Une tournée bitonique est une tournée qui augmente puis diminue (ou diminue puis augmente) l'itinéraire. L'heuristique de la tournée bitonique commence par trier les villes selon leur coordonnée x, puis construit une tournée bitonique en ajoutant les villes une par une dans l'ordre trié. Cette méthode est simple à mettre en œuvre et fonctionne raisonnablement bien lorsque les villes sont distribuées le long d'une ligne.

Heuristique de Clarke et Wright (algorithme d'épargne)

L'algorithme de Clarke et Wright, également connu sous le nom d'algorithme d'épargne, est une méthode gourmande qui commence par un ensemble de circuits à un nœud (chaque ville est son propre circuit). Il fusionne ensuite itérativement les circuits en fonction de l'épargne réalisée en les fusionnant. L'épargne entre deux villes i et j est définie comme la distance (du dépôt à i) + la distance (du dépôt à j) - la distance (i à j). L'algorithme fusionne les circuits qui offrent la plus grande épargne jusqu'à ce que tous les circuits soient fusionnés en un seul tour.

Métaheuristiques

Les métaheuristiques sont des algorithmes d'optimisation de niveau supérieur qui guident d'autres heuristiques pour rechercher de meilleures solutions. Ils peuvent s'échapper des optima locaux et explorer un plus grand espace de solutions.

Recuit simulé (SA)

Le recuit simulé est une métaheuristique probabiliste inspirée du processus de recuit en métallurgie. Il commence par une solution initiale (par exemple, un tour aléatoire) et l'améliore ensuite itérativement en apportant de petits changements aléatoires. Si le changement améliore la solution, il est toujours accepté. Cependant, si le changement détériore la solution, il est accepté avec une certaine probabilité, qui diminue à mesure que la température (un paramètre) diminue au cours du temps. Cette probabilité d'accepter des solutions plus mauvaises permet à l'algorithme d'échapper des optima locaux et d'explorer un plus grand espace de solutions.

Carte de Kohonen (réseaux de neurones auto-organisés)

Une carte de Kohonen, également appelée réseau de neurones auto-organisé (SOM), est une technique d'apprentissage non supervisée qui peut être utilisée pour résoudre le TSP. La carte est un réseau de neurones disposés en un treillis. Chaque neurone représente une ville. L'algorithme commence par initialiser les poids des neurones de manière aléatoire. Il présente ensuite itérativement au réseau un ensemble aléatoire de villes. Pour chaque ville, l'algorithme trouve le neurone le plus proche (le neurone avec les poids les plus similaires à la ville). Il met ensuite à jour les poids du neurone le plus proche et de ses voisins pour qu'ils soient plus similaires à la ville. Au fil du temps, les neurones s'auto-organisent pour représenter la structure des données. Une fois le réseau entraîné, le tour TSP peut être obtenu en traversant les neurones dans l'ordre de leur position dans le réseau.

Algorithme des abeilles (optimisation de la colonie d'abeilles artificielles)

L'algorithme des abeilles, ou optimisation de la colonie d'abeilles artificielles (ABC), est une métaheuristique basée sur la population inspirée du comportement de recherche de nourriture des colonies d'abeilles. Dans l'ABC, la solution au problème du TSP est représentée par la position d'une abeille dans l'espace de recherche. La population d'abeilles est divisée en trois groupes : les abeilles employées, les abeilles spectatrices et les abeilles éclaireuses. Les abeilles employées recherchent des sources de nourriture (solutions) dans le voisinage de leur position actuelle. Les abeilles spectatrices attendent dans la ruche et sélectionnent une source de nourriture à suivre en fonction de la qualité de la source de nourriture. Les abeilles éclaireuses recherchent de nouvelles sources de nourriture de manière aléatoire. L'algorithme itère par ces étapes, les abeilles partageant des informations sur les sources de nourriture et ajustant leurs positions jusqu'à ce qu'une solution satisfaisante soit trouvée.

Système de fourmis (optimisation de la colonie de fourmis)

L'optimisation de la colonie de fourmis (ACO) est une métaheuristique probabiliste inspirée du comportement des fourmis à la recherche de nourriture. Dans l'ACO, un ensemble de fourmis construisent des solutions au TSP en parcourant le graphe des villes. Chaque fourmi choisit de visiter la ville suivante en fonction d'une combinaison de la distance à la ville et de la quantité de phéromone déposée sur l'arête menant à la ville. Les fourmis déposent des phéromones sur les arêtes qu'elles parcourent, et la quantité de phéromone déposée est proportionnelle à la qualité de la solution de la fourmi. Au fil du temps, les fourmis ont tendance à suivre les arêtes avec plus de phéromones, ce qui conduit à la découverte de bonnes solutions.

Algorithme génétique (GA)

Un algorithme génétique (GA) est une métaheuristique basée sur la population inspirée du processus de sélection naturelle. Dans un GA, une population de solutions (appelées individus) est maintenue. Chaque individu représente un tour TSP. L'algorithme itère par les étapes suivantes :

1. Sélection : Les individus sont sélectionnés dans la population pour se reproduire en fonction de leur aptitude (qualité de leur solution).
2. Croisement : Les individus sélectionnés sont croisés pour produire de nouveaux descendants.
3. Mutation : Les descendants sont mutés (de petits changements aléatoires sont apportés à leur tour).
4. Remplacement : Les nouveaux descendants remplacent certains des individus de la population.

Algorithme du trou noir

L'algorithme du trou noir est une métaheuristique basée sur la population inspirée du comportement des trous noirs dans l'espace. Dans l'algorithme du trou noir, la solution au problème du TSP est représentée par la position d'une étoile dans l'espace. La population d'étoiles est attirée par un trou noir, qui représente la meilleure solution trouvée jusqu'à présent. La force d'attraction du trou noir est proportionnelle à sa masse (qualité de la solution). Au fur et à mesure que les étoiles se rapprochent du trou noir, elles peuvent être absorbées par lui, ce qui signifie que leur position est mise à jour avec la position du trou noir. L'algorithme itère par ces étapes, les étoiles se déplaçant vers le trou noir jusqu'à ce qu'une solution satisfaisante soit trouvée.

Recherche tabou

La recherche tabou est une métaheuristique de recherche locale qui utilise une liste tabou pour empêcher l'algorithme de revenir à des solutions récemment visitées. L'algorithme commence par une solution initiale et l'améliore ensuite itérativement en apportant de petits changements. Cependant, l'algorithme ne peut pas revenir à une solution qui se trouve dans la liste tabou. La liste tabou est une liste des solutions récemment visitées. La taille de la liste tabou est un paramètre de l'algorithme. La recherche tabou permet à l'algorithme d'échapper des optima locaux et d'explorer un plus grand espace de solutions.

Heuristiques d'amélioration de tour

Ces heuristiques commencent par une solution réalisable et tentent ensuite de l'améliorer en apportant de petits changements au tour.

Heuristique 2-opt

L'heuristique 2-opt est une simple heuristique d'amélioration de tour qui fonctionne en supprimant deux arêtes du tour et en les remplaçant par deux arêtes différentes. L'algorithme vérifie toutes les paires possibles d'arêtes et, si le remplacement des arêtes raccourcit le tour, le remplacement est effectué. Ce processus est répété jusqu'à ce qu'il n'y ait plus de remplacements améliorant le tour. L'heuristique 2-opt peut être appliquée au résultat de l'une des méthodes susmentionnées pour améliorer davantage la solution.

Pour illustrer l'heuristique 2-opt, considérez un tour représenté par la séquence de villes A-B-C-D-E-A. Supposons que le remplacement des arêtes A-B et D-E par A-D et B-E raccourcit le tour. Le nouveau tour serait A-D-C-B-E-A.

Voici une représentation schématique de l'heuristique 2-opt :

Améliorer la compréhension du TSP avec des images

Les algorithmes TSP peuvent être difficiles à visualiser. Cette section vise à aider les lecteurs à visualiser les algorithmes TSP et à acquérir une compréhension plus approfondie du fonctionnement des algorithmes TSP.

La première image illustre la complexité du problème du voyageur de commerce et les économies potentielles qui peuvent être réalisées en optimisant l'itinéraire. La deuxième image montre comment un outil d'optimisation d'itinéraire peut être utilisé pour résoudre le problème du voyageur de commerce. La troisième image montre comment l'algorithme d'optimisation de la colonie de fourmis peut être utilisé pour résoudre le problème du voyageur de commerce.

Visualiser les algorithmes TSP

Pour mieux comprendre la mise en œuvre et l'efficacité des algorithmes de voyageur de commerce, regardez cette vidéo qui explique les algorithmes d'approximation de voyageur de commerce :

FAQ sur le TSP

Références

• Heuristic Algorithms for the Traveling Salesman Problem - Opex Analytics
• Travelling salesman problem - Wikipedia
• 11 Animated Algorithms for the Traveling Salesman Problem - STEM Lounge
• Best Algorithms for the Traveling Salesman Problem - NextBillion.ai
• Algorithms for the Travelling Salesman Problem - Routific