Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

2.2 Recherche à grand voisinage

Dans ce chapitre, on s'intéresse plus particulièrement aux algorithmes de recherche à voisinage pour lesquels la taille du voisinage est très importante par rapport à la taille de l'instance du problème considéré. Pour des instances de très grandes tailles, il est impossible, dans des temps de calcul raisonnables, de parcourir énumérativement l'ensemble des solutions définies par de tels voisinages, et il faut soit explorer un sous-ensemble du voisinage, soit développer un algorithme efficace pour l'exploration du voisinage.

Une des principales difficultés dans la création d'une approche par recherche locale est le choix de la structure de voisinage, c'est-à-dire la façon dont le voisinage est

défini. Ce choix détermine de façon très importante si la recherche locale donnera des solutions de très bonne qualité ou des solutions qui représentent des optima locaux de mauvaise qualité. Il est évident que plus le voisinage est de taille importante, plus les solutions renvoyées par la recherche locale seront de bonne qualité et la solution finale proche de l'optimum. Malheureusement, en augmentant la taille du voisinage, on augmente aussi le temps de calcul nécessaire pour explorer ce voisinage. Comme la recherche locale est généralement appliquée à partir de plusieurs solutions initiales, de longs temps d'exécutions par itération restreignent le nombre d'appels à la recherche locale par unité de temps. Pour cette raison, un voisinage de taille importante n'amène pas nécessairement à une heuristique efficace, sauf s'il est possible d'explorer ce voisinage de manière particulièrement efficace.

Certaines méthodes largement utilisées en recherche opérationnelle peuvent être vues comme des techniques de recherche à grand voisinage. Par exemple, si l'algorithme du simplexe utilisé pour résoudre les programmes linéaires peut être vu comme un algorithme de recherche locale, alors la génération de colonnes peut être vue comme une méthode de recherche à grand voisinage. De manière équivalente, les techniques d'augmentation utilisées pour la résolution de nombreux problèmes de flots dans les réseaux peuvent être classées parmi les méthodes de recherche à grand voisinage.

Ahuja et al. (2002) ont classé les méthodes de recherche à grand voisinage dans trois classes non-exclusives. La première catégorie des algorithmes de recherche locale représente les méthodes à profondeur variable. Ces algorithmes se concentrent sur des voisinages de taille exponentielle et effectuent une exploration partielle de ces voisinages, en utilisant des heuristiques. La deuxième catégorie est composée des algorithmes d'améliorations de flots dans les réseaux. Ces méthodes de recherche à voisinage utilisent les techniques de flots dans les réseaux pour trouver des solutions voisines améliorantes. Enfin, la troisième catégorie se compose de structures de voisinages pour problèmes NP-difficiles dont certaines sous-classes peuvent être résolues en temps polynomial. Selon cette classification, l'opérateur de voisinage que nous proposons appartient à la catégorie des algorithmes d'améliorations de flots dans les réseaux, basés sur des calculs de plus courts chemins.

2.2.1 Notations et définitions de la recherche à grand voisinage

Nous allons maintenant introduire de manière plus formelle les concepts de problème d'optimisation combinatoire et de voisinage. Soit E = 1,2, . . . , m un ensemble fini. On note |S| la cardinalité d'un ensemble S. Soit F ç 2^E, où 2^E représente l'ensemble des sous-ensembles de E. Les éléments de F sont appelés des solutions réalisables. Soit f la fonction appelée fonction objectif. Une instance d'un problème d'optimisation combinatoire est représentée ainsi :

Minimiserf(S) : S E F

Une structure de voisinage est définie par la fonction N : F 2^E. Pour chaque S F

est associé un sous-ensemble N(S) de E. Cet ensemble N(S) est appelé le voisinage de

la solution S, et on pose que S ? N(S). Une solution S^* ? F est appelée optimum local relativement à la fonction de voisinage N si f(S^*) < f(S) quel que soit S ? N(S). Le voisinage défini par N(S) est dit de taille exponentielle si |N(s)| augmente exponentiellement lorsque m augmente.

Les techniques faisant appel à de tels voisinages sont appelées des algorithmes de recherche à grand voisinage. Pour deux solutions S et T, on appelle S - T l'ensemble des éléments qui apparaissent dans S, mais qui n'apparaissent pas dans T. On peut alors définir la distance d(S, T) égale à |S - T| + |T - S|, qui représente le nombre d'éléments de E qui apparaissent dans S ou dans T mais qui n'apparaissent pas dans les deux solutions (de nombreuses autres distances, permettant de mesurer la différence entre une paire de solutions pour des algorithmes génétiques, ont été présentées par Sevaux et Sörensen (2005)).

On peut donc définir un voisinage de distance k de la manière suivante : Nk(S) = T ? F : d(S; T) = k. On peut facilement remarquer que N_m(S) = F et donc, se rendre compte qu'explorer un voisinage de distance k peut être difficile lorsque k augmente. Cela est typiquement la situation lorsque k n'est pas fixé. Dans ce cas, trouver la meilleure solution (ou une solution meilleure que la solution actuelle) dans un tel voisinage est NP-difficile, si le problème original est NP-difficile.