Algorithme de Lin-Kernighan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En optimisation combinatoire, l'algorithme de Lin-Kernighan[1] est une heuristiques pour le problème du voyageur de commerce. L'algorithme consiste à échanger un nombre donné d'arêtes à partir d'une solution donnée pour trouver une solution de meilleur coût.

Description[modifier | modifier le code]

L'heuristique de Lin-Kernighan est une méthode itérative, qui consiste à améliorer peu à peu une solution. C'est une généralisation de l'heuristique 2-opt[2].

Idée de base : 2-OPT[modifier | modifier le code]

Article détaillé : 2-opt.

L'heuristique 2-opt consiste à chercher deux arêtes du tour courant, (A,B) et (C,D), qui peuvent être remplacées par (A,C) et(B,D) en réduisant le cout global, et à reproduire la procédure. Ce remplacement est appelé 'flip. Une généralisation naturelle est de prendre plus deux arêtes ("k-opt"), mais le temps de calcul devient rapidement grand pour un grand nombre d'arêtes considérés[3].

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 cout de (v,s(v))+(p,s(p)) est plus grand que le cout de (v,p)+(s(v),s(p)) alors effectuer le flip.

Le principe[modifier | modifier le code]

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 certains nombres de flips successifs. La différence avec 2-opt, est que l'on ne demande pas que les étapes intermédiaires réduisent le cout de la solution, seul le cout final est pris en compte. La différence avec k-opt est que l'on ne considère pas toutes les suites de flips possible, on se restreint à ceux qui sont jugé "prometteurs", dans le sens suivant[4].

Un flip est prometteur si (en suivant les notations de la partie précédente), le cout de (v,s(v)) est supérieur au cout 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 flip prometteur à partir d'un somme v, en enregistrant après chaque flip la valeur du tour créé. Puis à faire la suite de flips jusqu'à atteindre le minimum correspondant à cette série.

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

Histoire[modifier | modifier le code]

Dans les années 1950 et 1960, le problème du voyageur de commerce est devenu relativement populaires, et de nombreux chercheurs ont définis des heuristiques pour obtenir des solutions de faible cout[3]. L'heuristique de Lin et Kernighan est l'une des plus populaires, et est utilisée comme sous-routine de la plupart des heuristiques rapides actuelles[3].

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
  2. G. A. Croes (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
  3. a, b et c David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, « History of TSP computation », dans The traveling Salesman Problem: A Computational Study, Princeton University Press,‎ , chap. 3
  4. a et b David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, « Tour finding : Lin-Kernighan », dans The traveling Salesman Problem: A Computational Study, Princeton University Press,‎ , chap. 15