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

4.3.4 Heuristiques de recherche locale

Un appel de chacune des procédures d'amélioration classiques présentées ci-après nous permet d'obtenir un tour de coût inférieur ou égal au tour auquel on applique la procédure. Lorsqu'un nouvel individu est généré, chaque heuristique de recherche locale est appelée itérativement tant que le coût de la solution est amélioré.

2-opt

Cette procédure est classique lorsqu'on étudie le TSP (voir (Lin, 1965) pour plus de détails). Elle consiste à choisir deux villes du tour et à permuter la circulation entre ces deux villes en vue d'améliorer la solution. La complexité de cette procédure est O(m²) où m est le nombre de groupes. La procédure 2-opt est répétée tant que des améliorations sont obtenues. Ensuite, la séquence de groupe correspondant au tour des villes courant est extraite et l'algorithme ST est appliqué.

3-opt

De manière similaire au 2-opt, le 3-opt (présenté aussi dans (Lin, 1965)) choisit trois villes au lieu de deux, et modifie le chemin entre ces trois villes. La complexité de la pro-

cédure est O(m³). Une fois encore, la procédure est répétée tant que des améliorations sont obtenues et le calcul est terminé par l'appel de l'algorithme ST.

Lin-Kernighan

Nous utilisons de plus l'heuristique proposée par Lin et Kernighan (1973), disponible sur le site de Concorde¹. L'algorithme Lin-Kernighan est une des meilleures heuristiques disponibles pour le problème du Voyageur de Commerce. Il est basé entre autres sur une généralisation des procédures 2-opt et 3-opt. Cette procédure est appliquée chaque fois qu'une nouvelle meilleure solution est trouvée et lors de la génération de nouveaux individus, avec une probabilité égale à 0.50.

Meilleure insertion de groupe

L'opérateur de Meilleure Insertion de groupe (ou Move) considère la séquence de groupe d'un individu, sélectionne un groupe et détermine la meilleure position de ce groupe dans la séquence. L'opérateur de Meilleure Insertion de groupe est appliqué une fois pour chaque groupe. Afin de déterminer la meilleure position pour un groupe donnée Wi, une séquence maître est créée, pour laquelle Wi est dans un premier temps supprimé, puis inséré à nouveau entre chaque paire de groupes. L'algorithme de programmation dynamique présenté dans les sections 4.3.2 et 4.3.3 est ensuite appliqué afin de trouver le meilleur tour des villes réalisable.

L'opérateur de Meilleur Insertion de groupe peut être illustré avec l'exemple suivant. Soit W4 W3 W1 W5 W2 W4 le tour des groupes d'un individu. En appliquant l'opérateur sur le groupe W1, on obtient la séquence maître W4 W1 W3 W1 W5 W1 W2 W1 W4. Le meilleur tour des villes est ensuite calculé sur le graphe correspondant (cf. Fig. 4.4).

W4 W1 W3 W1 W5

W1 W2 W1 W4

FIGURE 4.4 - Exemple de l'opérateur Move et du graphe réduit correspondant : vue agrégée en terme de groupes

Le voisinage défini par l'opérateur de Meilleure Insertion de groupe a une taille en O(m(n/m)^m) (cette taille est calculée de manière similaire aux calculs présentés dans la section 4.3.2 pour l'opérateur de croisement). Dans l'algorithme de programmation dynamique, un label L est défini par une paire (C, 5i). Le nombre d'états est ainsi O(n) et la complexité de la procédure est O(nm).

1. http :// www.tsp.gatech.edu/concorde/DOC/index.html

Contrôle des opérateurs de recherche locale

L'appel des opérateurs présentés précédemment est contrôlé de la manière suivante. Quand un nouvel individu est introduit dans la population pendant la phase initiale, les opérateurs 2-opt, 3-opt et Lin-Kernighan sont appliqués successivement, dans cet ordre.

Quand un nouvel individu enfant est calculé avec l'opérateur de croisement, un des deux schémas de recherche local suivants est appliqué, avec une probabilité égale à 0.5 : - application de 2-opt, 3-opt et Move, dans cet ordre,

- application de Lin-Kernighan.