Heuristique de Lin-Kernighan

Le problème du voyageur de commerce est de trouver le plus court cycle hamiltonien dans un graphe complet ${\displaystyle G=(V,A,\omega )}$ avec ${\displaystyle V}$ un ensemble de sommets, ${\displaystyle A}$ un ensemble d'arêtes et ${\displaystyle \omega }$ une fonction de coût sur les arcs. L'heuristique 2-opt consiste à partir d'un cycle hamiltonien ${\displaystyle H}$ dans ${\displaystyle G}$ généré aléatoirement ou de façon gloutonne, puis à chercher deux arêtes de ${\displaystyle H}$, (A, B) et (C, D), qui peuvent être remplacées par (A, C) et (B, D) en réduisant le coût global. Ce remplacement est appelé 2-permutation. La procédure est ensuite répétée tant qu'une telle 2-permutation est possible dans ${\displaystyle H}$. Une généralisation naturelle est de prendre plus de deux arêtes, on parle alors de k-opt, mais le temps de calcul devient rapidement grand pour un grand nombre d'arêtes considérées[2].

La méthode 2-opt peut être vue de la manière suivante (en notant s(v) le sommet qui suit v dans le tour) :

• Choisir un sommet v (appelé la base),
• Choisir un sommet p,
• Si le coût de (v,s(v))+(p,s(p)) est plus grand que le coût de (v,p)+(s(v),s(p)), alors effectuer la permutation.

Le principe de l'heuristique de Lin-Kernighan est de faire un k-opt adaptatif (variable k-opt) qui consiste à améliorer une solution en faisant un certain nombre de permutations successives. La différence avec 2-opt est que l'on ne demande pas que les étapes intermédiaires réduisent le coût de la solution, seul le coût final est pris en compte. La différence avec k-opt est que l'on ne considère pas toutes les suites de permutations possibles, on se restreint à celles qui sont jugées « prometteuses », dans le sens suivant[3] : une permutation est « prometteuse » si (en suivant les notations de la partie précédente) le coût de (v, s(v)) est supérieur au coût de (s(v), s(p)). D'une certaine manière, cela revient à dire que l'on s’intéresse seulement à l'amélioration d'une arête sur les deux.

Une étape consiste à épuiser la réserve de permutations prometteuses à partir d'un sommet v, en enregistrant après chaque permutation la valeur du tour créé. Puis à faire la suite de permutations jusqu'à atteindre le minimum correspondant à cette série.

Il existe ensuite plusieurs variantes, pour restreindre les sommets prometteurs afin de gager en efficacité, ou pour décider de l'ordre dans lequel ils doivent être considérés[3].

L’algorithme de Lin-Kernighan-Helsgaun (LKH) est proposé en 2000 par Keld Helsgaun[5], avec des résultats expérimentaux qui montrent des performances supérieures aux autres variantes. Là où l'algorithme Lin-Kernighan original recherche les arêtes candidates à échanger parmi les proches voisins de chaque nœud, LKH étend la recherche à d'autres arêtes sans compromettre l'efficacité de l'algorithme, en utilisant l'arbre couvrant de poids minimal pour sélectionner de arêtes candidates et calculer pour chacune une probabilité (valeurs alpha) d'appartenir à la solution optimale.

Une des améliorations possibles de LKH utilise la métaheuristique POPMUSIC (Partial OPtimization Metaheuristic Under Special Intensification Conditions) pour explorer simultanément différents ensembles d’arêtes candidates, puis ne garder que les meilleures arêtes apparaissant dans plusieurs de ces explorations. Les résultats expérimentaux montrent que cette approche est plus efficace que LKH[6].

Plusieurs travaux ont proposé à partir des années 2020 d'utiliser les réseaux de neurones pour améliorer et accélérer la phase de sélection des arêtes candidates, qui est l'étape critique dans l'heuristique. Parmi ces approches, qui sont basées sur LKH, VSR-LKH (Variable Strategy Reinforced LKH) utilise l'apprentissage par renforcement[7], et NeuroLKH encode un réseau creux pour optimiser le calcul des paramètres de LKH[8]. Dans les deux cas, le réseau de neurones est entraîné pour trouver les arêtes candidates de façon plus adaptée à la tournée courante que LKH. Les résultats expérimentaux de ces approches sont positifs tant en termes de performance que d'efficacité.