Chapitre 4
Application au Problème du
Voyageur de Commerce
Généralisé
4.1 Introduction au Problème du Voyageur de
Commerce Généralisé
Nous proposons une solution pour le problème du
Voyageur de Commerce Généralisé (Generalized Traveling
Salesman Problem ou GTSP) basée sur un algorithme
mémétique (dans notre cas, un algorithme génétique
combiné avec de la recherche locale, voir (Hart et al., 2005)
ou (Moscato et Cotta, 2005) pour plus de détails). Le problème du
Voyageur de Commerce Généralisé est une
généralisation du classique problème du Voyageur de
Commerce (Traveling Salesman Problem ou TSP). Ma principale
contribution réside dans l'opérateur de croisement basé
sur l'exploration d'un voisinage étendu autour de l'individu père
et de l'individu mère.
Le GTSP peut être décrit de la façon
suivante. Soit G = (V, E) un graphe complet non
orienté, V = {v1, . . . , vn} un
ensemble de villes, W = {W1, . . . , Wm}
un ensemble de groupes, avec 0 < m = n. Chaque ville
vi E V appartient à un et un seul groupe (les groupes
sont disjoints deux à deux, i.e. pour i =6 j, Wi
fl Wj = 0 et W1 U ... U Wm =
V). Les coûts de transports sont notés
cij pour (vi, vj) E V.
L'objectif est de construire un tour qui visite exactement une fois chaque
groupe tout en minimisant la somme des coûts de transport. Dans notre
travail, nous n'avons considéré que le cas pour lequel les
matrices de coûts sont symétriques (cij = cji),
mais l'algorithme peut être facilement généralisé
pour les cas asymétriques. En particulier, l'opérateur de
croisement peut être aussi bien appliqué pour les cas
symétriques que pour les cas asymétriques.
Le GTSP est un problème NP-difficile au sens fort,
puisque ce problème est une généralisation du TSP. En
effet, le cas spécial dans lequel m = n (une ville par
groupe) est un problème de Voyageur de Commerce : le problème est
de trouver un tour qui visite chaque ville en minimisant les coûts de
transports.
Dans la section 4.2, nous présentons un état de
l'art sur le GTSP. La section 4.3 présente un nouvel algorithme
mémétique développé pour la résolution du
GTSP. La principale caractéristique de cet algorithme réside dans
la procédure de croisement basée sur une recherche à grand
voisinage (voir (Ahuja et al., 2002) pour un travail récent sur
les recherches à grand voisinage). La section 4.4 évalue
expérimentalement notre algorithme à l'aide de benchmarks issus
de la librairie GTSPLIB (Reinelt, 1991).
| 
