4.2 État de l'art
Le GTSP fut introduit en premier par Srivastava et al.
(1969) et Henry-Labordere (1969), qui ont proposé chacun une
résolution par un algorithme de programmation dynamique. Laporte et
Nobert (1984) et Laporte et al. (1984) ont proposé une approche
par programmation en nombres entiers afin de résoudre le GTSP de
manière exacte. Plus récemment, Fischetti et al. (1997)
ont proposé une résolution efficace basée sur une
procédure de séparation et génération de coupes,
qui a permis de fournir des résultats optimaux pour des instances
contenant jusqu'à 442 noeuds.
4.2. État de l'art
Plusieurs travaux ont été menés pour
transformer le GTSP en TSP (Lien et al., 1993; Noon et Bean, 1993;
Dimitrijevic et Saric, 1997; Laporte et Semet, 1999; Ben-Arieh et al.,
2003). Certaines des instances de TSP issues de ces transformations ont un
nombre similaire de noeuds comparé au nombre de noeuds de l'instance de
GTSP initiale. De plus, certaines transformations de GTSP en TSP (Noon et Bean,
1993) ont une propriété importante : une solution optimale du TSP
créé peut être transformée en une solution optimale
du GTSP. Malheureusement, une solution réalisable non optimale pour le
TSP créé peut ne pas être réalisable pour le GTSP.
De plus, certaines heuristiques très efficaces pour le TSP ont eu des
résultats peu convaincants pour le GTSP (Slavík, 1997; Dror et
Haouari, 2000)
Deux algorithmes d'approximations ont été
proposés pour le GTSP. Slavík (1997) a présenté une
approximation en 3p/2, pour laquelle p est le nombre de
villes dans le plus grand groupe (p = max (|Vm|)).
Cependant, la borne dans le pire cas peut être de
i=1,...,m
piètre qualité, la borne supérieure de
p étant égale au nombre de noeuds. Garg et Konjevod
(2000) ont proposé un algorithme d'approximation pour le problème
d'arbre de Steiner, amenant à un algorithme d'approximation en
O(log2(|V|) log log(|V|))
log(m)) pour le GTSP. Dans les deux cas, les inégalités
triangulaires doivent être respectées.
Noon et Bean (1991) ont proposé plusieurs heuristiques,
en particulier une adaptation de l'heuristique du plus proche voisin
utilisée pour le TSP. Des adaptations similaires ont été
proposées par Fischetti et al. (1997), telles que la plus
lointaine insertion, la plus proche insertion ou encore l'insertion à
plus faible coût. Plus récemment, Renaud et Boctor (1998a) ont
proposé l'heuristique GI3 (Generalized Initialization,
Insertion and Improvement), qui est une généralisation de
l'heuristique I3, présentée dans (Renaud et
al., 1996). Cette heuristique se déroule en trois phases : une
phase d'initialisation du-rant laquelle on construit un tour qui peut ne pas
être valide, une phase d'insertion qui complète les tours
incomplets en insérant au plus faible coût les villes provenant de
groupes non visités et une phase d'amélioration qui utilise des
modifications de voisinages de type 2-opt et 3-opt, appelées ici G2-opt
et G3-opt. Cet article présente aussi l'algorithme ST (pour Shortest
Tour). Cet algorithme détermine la séquence de villes de plus
petit coût qui visite les groupes dans un ordre fixé. Ils montrent
que ce problème peut être résolu en un temps polynomial.
Snyder et Daskin (2006) ont proposé récemment
une résolution par un algorithme génétique utilisant un
encodage par clé aléatoire, encodage qui assure que les solutions
construites par croisement ou mutation sont des solutions valides. Cet
algorithme génétique est couplé avec des
améliorations par recherche locale, définissant un algorithme
mémétique, une procédure d'échange et un voisinage
de type 2-opt (voir (Moscato et Cotta, 2005) pour plus de détails sur
les algorithmes mémétiques). Leurs résultats
expérimentaux montrent que leur algorithme est performant, que ce soit
en terme de qualité de solution ou de temps de calcul. Un algorithme
basé sur l'optimisation par essaims particulaires a été
récemment présenté par Shi et al. (2007). Une
procédure pour supprimer les croisements dans les tours a
été utilisée pour accélérer la vitesse de
convergence, appuyée par deux techniques de recherche locale.
Malgré cela, les résultats présentés ne parviennent
pas à dépasser les meilleures heuristiques connues.
Enfin, Silberholz et Golden (2007) ont proposé un
algorithme génétique avec plusieurs nouvelles techniques, entre
autres, des populations initiales isolées, ainsi qu'une nouvelle
procédure de reproduction, basé sur l'opérateur de
croisement ordonné pour le TSP. Cette nouvelle procédure est
appelée mrOX, pour croisement ordonné de rotation
modifié (modified rotational ordered crossover). Les
procédures d'améliorations locales associées à cet
opérateur de croisement, définissant un algorithme
mémétique, ont permis d'obtenir de très bons
résultats sur de nouvelles instances de taille importante et de
dépasser les autres solutions heuristiques en ce qui concerne la
qualité des solutions obtenues. L'algorithme proposé par
Silberholz et Golden (2007) peut être considéré comme
l'algorithme le plus compétitif publié à ce jour.
| 
