Remerciez-le!

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

Problème de voyage de commerce Histoire: le problème de voyageur de commerce à

Problème de voyage de commerce Histoire: le problème de voyageur de commerce à été évoqué pour la première fois en 1930 par le mathématicien viennos Karl Menger il a intrigué bon nombre de chercheurs depuis ce temps : Sans doute par ce qu’il est facile à énoncer mais difficile à résoudre. Ce problème cache de nombreuses finesses et difficultés qui nous emmènerons dans les développements récents de la théorie des recherches. Domaines d’application:  le domaine de logistique : la livraison des marchandises.  optimisation de trajectoires de machines outil. Problème de filage d’ordinateur. Problème de coupage et de perçage. Développement algorithmiques et théories importantes. ◎L’objectif principal: ◎Le problème de voyageur de commerce asymétrique consiste à trouver un circuit C passant une et une seule fois par chaque sommet du graphe G (circuit hamiltonien) dont le coût total cij est minimal. dépôt 2 1 3 4 dépôt 1 4 3 2 2 3 4 1 dépôt Algorithme de colonie de fourmi pour le problème de voyageur de commerce On considère un problème de voyageur de commerce à N villes. pour chaque fourmi k le trajet d’une ville i à une ville j dépend de:  La liste des villes déjà visitées  La visibilité qui est l’inverse de la distance entre les villes nij.  La quantité de phéromone déposée sur l’arête reliant deux villes Ƭij(t) appelée l’intensité de la piste. ◎ ◎Pour chaque fourmi k ,le trajet d’une ville i à une ville j dépend de: sont les parametres qui controllent l’importance relatives entre phéromones et visibilité. La formule 1 Algorithme de colonie de fourmi pour le problème de voyageur de commerce ◎Si 2 et 5 ont la même quantité de phéromones Donc la probabilité de choisir 5 et plus grande que celle de 2. 5 2 1 4 3 ◎Après un tour complet , chaque fourmi dépose une quantité de phéromone . Cette quantité dépend de la qualité du solution trouvée qui est: ◎ est la tournée fait par le fourmi k à l’itération t , la longueur du trajet et Q un paramètre de réglage. La formule 2 La formule 3 4 5 1 3 2 5 4 3 2 3 1 2 4 1 5 Les arcs 2-5, 3-4 et 5-1 est un chemin commun entre les deux graphes ◎A partir de 1, 5 est plus probable en raison de la distance et la quantité de phéromone. A partir de 5, 2 peut être sélectionnés en raison de la Phéromone et 4 en raison de La distance. 1 2 3 4 5 ◎Si l’une des fourmis choisit 1-5 puis 4, par la suite elle va Choisir 3 en raison de la Distance et de la phéromone La plus élevée. Le meilleur trajet est: 1—5—4—3—2 5 3 2 1 4 Fonctionnement de l’algorithme ◎Tant le critère d’ arrêt n’est pas atteint faire ◎ pour k=1 à m faire ◎ choisir une ville au hasard ◎ pour chaque ville non visitée faire ◎ choisir une ville j , dans la liste des villes restantes ◎ selon la formule 1 ◎ fin pour déposer une piste sur le trajet t conformément à la formule 2 fin pour évaporer les pistes selon la formule 3. fin tant que merci pour votre attention uploads/Geographie/ probleme-de-voyage-de-commerce-asymetrique.pdf