Te presentamos
Tu nuevo asistente de presentaciones.
Perfecciona, mejora y adapta tus contenidos, busca imágenes relevantes y edita elementos visuales más rápido que nunca.
Búsquedas populares
Problème de voyageur de commerce
La première idée consiste à se rendre systématiquement dans la ville la plus proche de celle où l’on se trouve
Algorithme exacte
Algorithme approché
Feres Foudhaili
Takwa Ben Ahmed
Méthode par insertion
Procédure par séparation évaluation.
Il s'agit de construire le parcours ville par ville, en insérant dans le parcours la ville qui le rallonge le moins
L'algorithme du plus proche voisin
La méthode de élastique
L'algorithme de descente locale
L'algorithme du recuit simulé
La recherche Tabou
Il est essentiel de noter que cette opération peut conduire à augmenter la valeur de la fonction (dans un problème de minimisation) : c'est le cas lorsque tous les points du voisinage ont une valeur plus élevée.
Iheb Zmerli
Med Amine Bouzid
Le problème de voyageur de commerce(PVC), étudié depuis le 19 ème siècle,est l'un des plus connus dans le domaine de la recherche opérationnelle.
C'est déja sous forme de jeu que "William Rowan Hamilton" a posé pour la première fois ce problème dés 1895.
Ce problème d'optimisation combinatoire appartient à la classe des problèmes NP-Complets .
Les domaines d’application sont nombreux :
problèmes de logistique
problèmes de transport
problèmes de marchandises
problèmes de personnes
Toutes sortes de problèmes d’ordonnancement.
Certains problèmes rencontrés dans l’industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l’optimisation de trajectoires de machines outils.
Un voyageur de commerce doit visiter n villes données en passant par chaque ville exactement une fois et revenir à son point d'origine
Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ?
Introduction
Problématique
Etude de cas
L'application dans la vie réelle
Conclusion
Tout en minimisant :
-Le nombre de routes.
-La distance totale parcourue.
Est une méthode générique de résolution de problèmes d'optimisation combinatoire.
L'optimisation combinatoire consiste à trouver un point minimisant une fonction
design by Dóri Sirály for Prezi
- Minimiser la distance totale parcourue
-Passer au moins une seule fois par chaque arrête (rue) du graphe (non orienté)
-Revenir à la case de départ