2.3.2 Autres variantes de Problèmes de
Tournées à Couverture Partielle
On trouve d'autres variantes du problème du Voyageur de
Commerce relativement proches des problèmes présentés :
- Traveling Purchaser Problem (Ramesh, 1981) : dans ce
problème, les villes sont remplacées par des marchés.
Chaque marché fournit un sous-ensemble de produits. Le prix de vente de
chaque produit est connu et les prix des produits sont dépendants du
marché à partir duquel ils sont achetés. L'objectif
consiste à trouver un tour qui part d'un dépôt, connectant
un sous-ensemble de marchés, de telle sorte que l'ensemble des produits
soit acheté et que la somme des coûts de transport et des
coûts d'achat des produits soit minimisée (voir le chapitre 3 pour
plus de détails sur ce problème).
- Covering Tour Problem (Gendreau et al., 1997) :
dans ce problème, un ensemble T de sommets doit être
visité et un ensemble W de sommets doit être couvert.
L'objectif est de trouver un cycle hamiltonien de longueur minimale qui visite
l'ensemble des sommets de T de telle sorte que chaque sommet de W
ait une distance inférieure à une longueur
prédéterminée avec au moins un sommet du cycle.
- Generalized Traveling Salesman Problem (Henry-Labordere,
1969) : dans ce problème, les sommets appartiennent à des
groupes. L'objectif est de construire un tour qui visite exactement une fois
chaque groupe tout en minimisant les coûts de transport (voir le chapitre
4 pour plus de détails sur ce problème).
2.3.3 Complexité des Problèmes de
Tournées avec Couverture Partielle
L'ensemble des problèmes présentés, aussi
bien dans leurs versions mono-véhicule que dans les versions avec une
flotte de véhicules, sont NP-difficiles. Ceci est
généralement facile à prouver : dans la plupart des cas,
on peut se ramener à un problème de type Voyageur de Commerce qui
est NP-difficile au sens fort.
2.3.4 Quelques opérateurs de recherche locale pour
les Problèmes de Tournées avec Couverture Partielle
Il existe un certain nombre d'opérateurs de recherche
locale, utilisés entre autres pour les problèmes de
Tournées avec Gains. On peut classer les opérateurs de recherche
locale en deux sous catégories:
- sans changement des sommets visités : ces
opérateurs modifient l'ordre de visite des sommets dans un tour dans le
cas où un seul véhicule est disponible (2-opt (Croes, 1958),
heuristique de Lin et Kernighan (1973), ...) ou changent l'affection des
sommets entre les tournées (croisement (Montané et Galvão,
2006), échange (Tan et al., 2001), repositionnement
(Montané et Galvão, 2006), ...);
- avec changement des sommets visités : ces
opérateurs tirent partie du fait que l'ensemble des sommets n'est pas
visité (insertion d'un sommet -ou d'une chaîne de sommets- dans la
tournée (Riera-Ledesma et Salazar-González, 2005), suppression
d'un sommet (Pisinger et Ropke, 2007) ou d'une chaîne de sommets
(RieraLedesma et Salazar-González, 2005)).
Nous nous sommes intéressés plus
particulièrement à cette dernière catégorie de
voisinages. Les quelques exemples qui suivent (figures 2.1-2.5)
présentent un aperçu d'opérateurs connus.
9
6
8
5
2
10
3
7
0 4 1
2
1
3
0
4
5
6
FIGURE 2.1 - Exemple de solution
initiale
FIGURE 2.2 - Application d'un
échange entre les sommets 2 et 6
1
2
3
0
4
5
6
FIGURE 2.3 - Application de
l'opérateur insertion
Chapitre 2. La recherche à grand voisinage : un nouvel
opérateur
2
3
0
4
5
1
6
6
1
2
3
0
4
5
FIGURE 2.4 - Application de
l'opérateur suppression
FIGURE 2.5 - Application d'un
2-opt entre les sommets 2 et 5 : le chemin entre ces
sommets est inversé
2.4 Dropstar : une nouvelle structure de grand
voisinage
2.4.1 Des opérateurs existants : drop,
l-ConsecutiveDrop
Afin de présenter l'intérêt du nouvel
opérateur de voisinage que nous proposons, nous nous appuierons sur un
exemple simpliste du problème de Tour avec Profits (Profitable Tour
Problem ou PTP). On définit le Profitable Tour Problem de la
manière suivante. Soit G = (V, E) un graphe
non orienté avec V = {v1, . . . ,
vn} un ensemble de sommets pour lequel v1 est le
dépôt. On note cij le coût de l'arc
(vi, vj). On associe à chaque sommet vi un
gain supposé positif. L'objectif est de minimiser la différence
entre la somme des distances parcourues et la somme des gains
récoltés. Les chiffres situés sur les sommets de la figure
2.6 représentent le gain associé à chaque sommet et les
chiffres situés sur les arcs, la distance entre deux sommets. Dans le
cas où toutes les villes ne doivent pas être visitées,
comme c'est le cas ici, on peut appliquer la procédure DROP
utilisée par de nombreux chercheurs sur ces classes de problèmes
(Ramesh et Brown, 1991; Mittenthal et Noon, 1992; Voß, 1996). Cet
opérateur retire un sommet d'une solution initiale dans le cas où
ce retrait permettrait de diminuer le coût de la fonction objectif.
Posons la solution initiale (Fig. 2.7), de coût
égal à --1. Lorsqu'on applique la procédure DROP, la seule
suppression qui permet de diminuer le coût de la fonction objectif est la
suppression du sommet 4. On a alors la solution 0 1 2 3 0 de coût
égal à --2, présentée dans la figure 2.8. Le but
étant de minimiser la fonction objectif, on se rend compte que cette
solution est un optimum local relativement à la procédure DROP.
En effet, si l'on se limite à la suppression d'une seule ville de cette
solution, on ne peut améliorer la solution courante.
Devant la limitation de la taille de l'espace de recherche
défini par ce voisinage, Riera-Ledesma et Salazar-González (2005)
ont proposé une extension de ce voisinage qu'ils ont appliquée au
problème de l'Acheteur Itinérant. Ils ont nommé ce nouveau
voisinage : l-ConsecutiveDrop. Ce voisinage peut se retrouver sous des
formes similaires pour ces classes de problèmes (Keller, 1989; Renaud et
Boctor, 1998b; Hachicha et al., 2000; Dell'Amico et al.,
1998). Ce voisinage essaie de réduire la longueur d'un cycle initial en
supprimant l sommets consécutifs. Si on applique cette
procédure à la solution présentée dans la figure
2.8, en choisissant l = 2, on améliore la solution courante en
obtenant la solution présentée dans la figure 2.9, de coût
égal à --4. Cette solution aurait aussi pu être obtenue en
supprimant dans un premier temps les sommets 1 et 2 de la solution initiale (la
solution ainsi obtenue serait 0 3 4 0 de coût égal à -3),
puis en supprimant de cette solution le sommet 4.
Néanmoins, cette procédure présente des
limitations. Considérons l'exemple présenté dans la figure
2.10. Nous posons alors la solution initiale 0 1 2 3 4 5 0 de coût
égal à --1 présentée dans la figure 2.11. Si on
applique la procédure l-ConsecutiveDrop, on peut voir que cette
solution initiale est un optimum local pour l fixé à
4.
En diminuant la valeur de l (l est alors
égal à 3), on améliore la solution courante en obtenant la
solution 0 4 5 0 de coût égal à --2 présentée
dans la figure 2.12. Cette solution est de plus un optimum local relativement
à la procédure l-ConsecutiveDrop. Cependant, on peut
remarquer qu'en appliquant en premier lieu une procédure 2-
ConsecutiveDrop, on aurait obtenu la solution optimale 0 3 4 5 0 de coût
égal à --19, présentée dans la figure 2.13. On se
rend compte ainsi que la valeur de l est déterminante dans
l'efficacité de la procédure et que la limitation à la
suppression de sommets consécutifs peut être un frein à
l'efficacité de cette procédure.
10
10
10
24
10
10
13
FIGURE 2.6 - Exemple de
Profitable Tour Problem
10
10
10
24
10
13
FIGURE 2.7 - Exemple de
Profitable Tour Problem : Solution initiale
10
10
10
0
24
10
4
13
FIGURE 2.8 - Exemple de
Profitable Tour Problem : Solution après un Drop
9
1
9
2
10
3 24
0
10
4
13
FIGURE 2.9 - Exemple de Profitable
Tour Problem : Solution après un 2-ConsecutiveDrop
10
10
10
10
18
18
10
23
10
10
5
4
FIGURE 2.10 - Autre exemple de
Profitable Tour Problem
10
10
10
23
10
10
10
4
18
18
5
FIGURE 2.11 - Autre exemple
Profitable Tour Problem : Solution initiale
1
1
1
2
18
18
3 23
0
10
5
4
10
FIGURE 2.12 - Exemple de Profitable
Tour Problem : Solution après un 3-ConsecutiveDrop
1
1
1
2
10
10
10
FIGURE 2.13 - Exemple de
Profitable Tour Problem: Solution optimale
| 
