2.4.2 L'opérateur de grand voisinage : Dropstar
La procédure Dropstar définit un
opérateur de grand voisinage. Il est basé sur le
sous-problème suivant : trouver une sous-séquence optimale
à partir d'une séquence initiale donnée. Cet
opérateur détermine ainsi l'ensemble optimal des sommets
(consécutifs ou non) à supprimer d'une séquence.
On peut penser que la calcul de la sous-séquence
optimale est coûteux. En effet, la recherche d'une sous-séquence
optimale peut être un problème NP-difficile, comme
nous le verrons par exemple dans le chapitre 3. Cette recherche
est ici effectuée par le biais d'un algorithme de programmation
dynamique récursif.
On construit un graphe selon la procédure suivante.
Comme exemple de solution initiale, nous reprenons la solution
présentée dans la figure 2.8. Un sommet est créé
pour chaque ville de la séquence, le premier sommet de la
séquence est dupliqué et placé en fin de séquence.
Des arcs sont ensuite ajoutés entre chaque sommet et les sommets qui le
suivent dans la séquence initiale (cf. Fig. 2.14). La procédure
dropstar consiste alors à trouver le plus court chemin dans le
graphe entre le premier sommet et le dernier sommet, en respectant certaines
contraintes de ressources. Le coût du chemin est alors égal
à la somme des coûts des distances, à laquelle on peut
avoir à ajouter le coût des ressources (par exemple, les
coûts d'achat des produits dans le cas du problème de l'Acheteur
Itinérant).
0 1 2 3 0
9 9 24
10
14
10
10
10
0
10
10
10
10
FIGURE 2.14 - Graphe
résultant de la procédure Dropstar, appliqué sur la
solution de la figure 2.8
La complexité de la recherche d'une
sous-séquence optimale dépend en partie de la présence ou
non de ressources. Dans le cas par exemple du Problème de Tour avec
Profits, en l'absence de ressource, la recherche d'une sous-séquence
optimale et donc d'un plus court chemin est polynomiale. Par contre, la
consommation en cours de chemin des ressources disponibles en quantités
limitées peut rendre le problème NP-difficile (voir par exemple
le chapitre 3 pour plus de détails).
L'algorithme de programmation dynamique que nous utilisons
pour trouver le plus court chemin dans le graphe est inspiré de
l'algorithme développé par Feillet et al. (2004) pour le
Problème du Plus Court Chemin Élémentaire avec Contraires
de Res-sources. Cet algorithme est une extension du célèbre
algorithme de Bellman (1957).
Un important travail est à effectuer afin
d'accélérer cette procédure pour la rendre applicable pour
les instances de taille importante. Ce travail porte essentiellement sur les
conditions de dominances et sur l'analyse des solutions initiales, afin
d'essayer de réduire la taille du graphe sur lequel appliquer la
procédure Dropstar.
| 
