Remerciez-le!

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

Voyageur de commerce recuit simule

nnnnnnn nnnn nnnnnn Université de Tunis El Manar nnnnnnnn nnnnnnnnn nnnnn nnnnnnnn Ecole nationale d ? ingénieurs de Tunis Département Génie Industriel Projet en méta heuristique Résolution d'un problème de voyageur de commerce avec le recuit simulé Réalisé par ABIDI Oussama BEN BRAHIM Ali Classe AGI Année universiaire Sommaire Chapitre Revue de littérature Problème de voyageur de commerce Définition du problème Formulation par un programme linéaire binaire Formulation Formulation Applications Caractéristique Résolution Exemples Recherche d ? une solution approchée Le recuit simulé Historique Définition Principes du recuit simulé Analogie entre recuit thermique et recuit simulé L ? algorithme du recuit simulé Etat initial de l ? algorithme Paramètre de température Application du recuit simulé au problème de voyageur de commerce Avantages et inconvénients Chapitre Algorithme et Implémentation Introduction Les éléments de l ? algorithme de recuit simulé Solution initiale INITIAL ? Voisinage VOISIN ? Algorithme principale MAIN RECUIT Définition du problème et Résolution Définition de problème Résolution Résolution approché recuit simulé Résolution exacte Liste des figures Figure Blocage d ? une heuristique classique dans un minima local Figure Diagramme de modélisation du recuit simulé Figure Un ensemble de villes n ?uds reliés entre eux par des routes arcs Figure trajet de la solution initiale Figure trajet de la meilleure solution trouvée Figure Code Cplex Figure donné du problème Figure La solution optimale fournie par Cplex pour la ? Instance n Liste des tableaux Tableau coordonnée des points Tableau distances entre les différents points Chapitre Revue de littérature Problème de voyageur de commerce Définition du problème Le nom du problème du voyageur de commerce vient de la situation fictive d ? un vendeur qui désire visiter un certain nombre de villes débutant et finissant son parcours dans la même ville en visitant chacune des autres villes une et une seule fois A l ? échelle d ? un pays comme les États-Unis le coût en argent et en temps d ? un tel voyage peut devenir prohibitif si l ? on ne prévoit pas un trajet optimal à l ? avance Donc le défi du problème est que le voyageur de commerce veut minimiser la durée totale du voyage Formulation par un programme linéaire binaire Formulation Variables de décision xij si le client j est visité immédiatement après le client i sinon Fonction objectif La fonction objective consiste à minimiser distance parcourue par le voyageur nn ? ? Min x d i j ij ij Sc n ? x i eti j ij j n n ? x ij j et i j i n n ? x ij ? S - S n N tq ? S ?Ú N - j n S et i n S xij ou Et traduit le faite que le voyageur de commerce doit passer par toutes les villes et une seule fois oblige de ne pas avoir deux cycles ou plus qui ne sont pas lié contraintes d ? intégrités Formulation Variables de décision xij si le client j est visité immédiatement après le