Te presentamos 

Prezi AI.

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.

Cargando…
Transcripción

Problème de voyageur de commerce

Notre équipe

L'algorithme des plus proches vousins

Algorithmes existants

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é

La méthode d’insertion

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

La recherche tabou

L'algorithme de descente locale

Merci pour votre attention

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

Introduction

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 .

L'application dans la vie réelle

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.

Problématique

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 ?

Plan

Étude de cas

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.

Procédure par séparation évaluation

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

Mais !!!

- 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

Descubre cómo crear presentaciones más dinámicas e interesantes con Prezi