Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

IFT1575 Modèles de recherche opérationnelle Problème du voyageur de commerce He

IFT1575 Modèles de recherche opérationnelle Problème du voyageur de commerce Heuristiques Une heuristique permet d’identifier au moins une solution réalisable à un problème d’optimisation, mais sans garantir que cette solution soit optimale Voyageur de commerce 2 d’optimisation, mais sans garantir que cette solution soit optimale Problème du voyageur de commerce Un voyageur de commerce doit visiter un certain nombre de villes Il doit visiter chaque ville une et une seule fois La distance étant connue entre chaque paire de Voyageur de commerce 3 La distance étant connue entre chaque paire de villes, il s’agit de minimiser la distance totale parcourue On peut représenter ce problème par un graphe où chaque ville correspond à un sommet et où chaque arête lie une paire de villes Formellement, le problème consiste à trouver un cycle Hamiltonien de longueur minimale dans un graphe complet Problème du voyageur de commerce Dans un graphe complet avec n sommets, il y a (n-1)!/2 tours possibles. On voit donc que le nombre de tours augmente rapidement avec la taille du Voyageur de commerce 4 de tours augmente rapidement avec la taille du problème. Parmi tous les tours possibles, on en cherche un qui est de longueur minimale. Méthodes heuristiques Il faut être conscient que les méthodes exactes peuvent prendre beaucoup de temps, surtout lorsque les problèmes sont de grande taille Une autre approche consiste à utiliser des méthodes heuristiques visant à identifier rapidement de bonnes Voyageur de commerce 5 Une autre approche consiste à utiliser des méthodes heuristiques visant à identifier rapidement de bonnes solutions On les classe souvent en deux catégories : Méthodes constructives : permettent de construire une solution réalisable Méthodes d’amélioration : permettent de considérer plusieurs solutions réalisables différentes tout en tentant d’améliorer la valeur de l’objectif. Méthode de descente Étant donné une solution réalisable initiale, on tente de l’améliorer par une modification d’un certain type. Voyageur de commerce 6 Dans l’ensemble de toutes les modifications d’un certain type, on choisit celle qui améliore le plus la valeur de l’objectif (s’il y en a une!). Cette approche est appelée méthode de descente (quand on minimise). Modification: 2-opt (inversion) Pour le problème du voyageur de commerce, on peut définir plusieurs types de modifications. Un type possible consiste à éliminer deux arêtes dans Voyageur de commerce 7 Un type possible consiste à éliminer deux arêtes dans le tour pour les remplacer par deux nouvelles arêtes (2-opt). 2-opt : exemple Voyageur de commerce 8 Méthode de descente avec 2-opt Identifier une solution réalisable initiale Considérer tous les échanges 2-opt possibles et choisir celui qui améliore le plus la distance totale Arrêter s’il n’y a aucun échange 2-opt qui permette Voyageur de commerce 9 Arrêter s’il n’y a aucun échange 2-opt qui permette d’améliorer la distance totale Cette méthode est intéressante, mais elle ne garantit pas de trouver une solution optimale Elle identifie plutôt un optimum local (par rapport au type de modification utilisé, ici les échanges 2-opt) uploads/Voyage/ ift1575-doc-tsp-1.pdf