Recherche locale a mémoire adaptative parallèle pour le problème de voyageur de commerce

  Dans ce chapitre on va parler sur un problème d’optimisation combinatoire, c’est le problème de voyageur de commerce, c’est un problème typique de la classe NP-complet, il nous aide comme une pierre de test de la méthode implémenté par nous même, cette méthode base sur la méthode de recherche locale à mémoire adaptativela méthode de base sera représentée en second lieu, en suite on va introduire la méthode parallèle proposée, puis les détails de l’implémentation, tests et résultats et finalement les discutions et la conclusion. 

Le problème de voyageur de commerce

Le problème du voyageur commerce (PVC) est l’un des problèmes les plus connus dans le domaine de l’optimisation combinatoire car en plus de sa simplicité il est typiquement NP-complet, donc il est largement utilise pour juger l’efficacité des méthodes proposées pour résoudre un tel type des problèmes, il s’agit de trouver le chemin le plus court qui relie n villes données, chaque ville ne doit être visitée qu’une et une seule fois, et revenir à la ville de départ. Le PVC peut être appliqué à résoudre un grand nombre des problèmes pratiques dans notre vie quotidienne. 

Définition

 Le problème du voyageur de commerce », est le suivant : un représentant de commerce ayant n villes à visiter souhaite établir une tournée qui lui permet de passer exactement une fois par chaque ville et de revenir à son point de départ pour un moindre coût, c’est-à-dire en parcourant la plus courte distance possible. Si on utilise les notions des graphes. Soit G = (X,U), un graphe dans lequel l’ensemble X des sommets représente les villes à visiter, ainsi que la ville de départ de la tournée, et U, l’ensemble des arcs de G, représente les parcours possibles entre les villes. A tout arc (i,j) U, on associe la distance de parcours di j de la ville i à la ville j. La longueur d’un chemin dans G est la somme des distances associées aux arcs de ce chemin. Le PVC se ramène alors à la recherche d’un circuit hamiltonien (un chemin fermé passant exactement une fois par chacun des sommets du graphe G) et de longueur minimale[HW85].   Plus formellement, le problème du voyageur de commerce peut s’écrire comme un programme linéaire. Ci -dessous, V est l’ensemble des n sommets du graphe. X désigne l’arc (i, j) et vaut 1 s’il fait partie de la solution, 0 si non .di j représente le poids l’arc (i,j). { ∑∑ ∑ ∈ ∑ ∈ ∑ | | ∈ ∈ { } ∈ (1) Chaque sommet i ne peut accepter qu’un arc sortant vers un autre sommet j. (2) Chaque sommet j ne peut accepter qu’un arc entrant d’un autre sommet i. (3) Dans tout sous ensemble P de sommets, sélectionner |P| arcs permettrait de former des circuits hamiltoniens. On interdit cela. 

Historique

 Des problèmes mathématiques liés au problème de voyager de commerce (en anglais, TSP : Traveling Salesman Problem) ont été étudiés dans les 1800’s par le mathématicien Irlandai Sir William Rowan Hamilton et par le mathématicien Britannique Thomas PenyngtonKirkman. Hamilton a créé le jeu Icosian en 1857qui nécessite un lecteur de terminer une tournée en utilisant seulement connecteurs spécifiés par 20 points [CT03]. Dans les années 1930 le PVC est traité plus en profondeur par Karl Menger à Harvard. Il est ensuite développé à Princeton par les mathématiciens Hassler Whitney et Merril Flood[Sch60]. 1954 Solution du PVC pour 49 villes par Dantzig, Fulkerson et Johnson par la méthode du cutting-plane [DFJ54], les villes représentent 48 capitale état d’ETATS-UNIS plus Washington.   1975 Solution pour 100 villes par Camerini, Fratta and Maffioli 1987 Solution pour 532, puis 2392 villes par Padberg et Rinaldi 1998 Solution pour les 13 509 villes des Etats-Unis. 2001 Allemagne par Applegate, Bixby, Chvàtal et Cook des universités de Rice et Princeton appliquent une version parallèle de la méthode de Danzig, Fulkerson et de Johnson sur une grande instance de PVC, Ils ont obtenu la solution optimale du PVC qui a 15.112 villes (nœuds) en Allemagne, Le calcul a été exécuté sur un réseau de 110 processeurs situés et ils ont estimé tout le temps de calcul étaient de 22,6 ans, mesurés à un processeur d’alpha de Compaq EV6(21264) fonctionnant à 500MH[FKTY03]. En mai 2004, le problème de représentant de commerce de visiter chacune des 24.978 villes en Suède a été résolu: une excursion de longueur approximativement 72.500 kilomètres a été trouvée et on l’a montrée qu’aucune excursion plus courte n’existe. En mars 2005, le problème de représentant de commerce de visiter chacun des 33.810 points dans une carte a été résolu en utilisant CONCORDE une excursion des unités de la longueur 66.048.945 a été trouvée et on l’a montrée qu’aucune excursion plus courte n’existe. Le calcul a pris approximativement 15,7 années d’unité centrale de traitement (Cook et al. 2006). 

Complexité du problème

 Ce problème appartient à la classe NP-difficile et pour montrer la difficulté de ce problème supposant qu’on a 50 villes ; donc ils existent 49! Solutions (tourne) possibles, i.e. 6,08.1062 tournées possible. Prenons un ordinateur de π Millimètres calculant un milliard de solutions par seconde. Sachant que le diamètre équatorial de la terre est de 12756 kilomètres, mettons 12756000000 de ces ordinateurs les uns à la suite des autres sur l’équateur. On peut ainsi calculer 12576000000000000000 solutions par seconde Pour être certain de trouver la tournée la plus courte, il faut considérer toutes les tournées possibles. Il nous faudra alors 4,766*1043 secondes avec le super ordinateur que l’on vient de présenter. Note : 4,766.1043 est l’équivalent de 1,51*1034 siècle. D’une manière formelle pour démontrer que PVC est NP-complet nous emploierons la méthode populaire de la réduction. Nous prendrons un problème, l’appelons H, on s’est déjà   avéré qu’il est NP-complet. Puis, nous prouverons que vous pouvez résoudre H en le ramenant au PVC. Une fois que nous avons montré ceci, nous pouvons dire que si PVC est soluble dans un temps polynôme, alors nous pouvons résoudre H dans un temps polynôme. À quel point nous atteignons une contradiction nous concluons alors que PVC ne peut pas être résolu dans un temps polynôme parce qu’on l’a déjà montré que H ne peut pas être résolu dans le temps polynôme. D’ailleurs, PVC doit être NP-complet parce que H est NPcomplet[Zam06]. En montrant que PVC est NP-complet, nous choisirons H pour être le problème populaire de cycle hamiltonien, qui est connu pour être NP-complet. À un regard étroit, il est évident que le problème de cycle hamiltonien soit un cas spécial de PVC. Tous simplement en modifiant le graphe d’entrée selon l’algorithme de PVC en plaçant les coûts de tous les bords existants pour être une certaine constante finie fixe. Puis, si n’importe quelle excursion est trouvée, cette excursion est un cycle hamiltonien. Ainsi, le PVC doit être NP-complet parce qu’on l’a montré que le problème de cycle hamiltonien est NP-complet[Zam06].