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 l'une des meilleures[réf. souhaitée] 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. C'est une généralisation de 2-opt[2] et 3-opt, méthode qui échange 2 (resp. 3) arêtes afin de raccourcir la tournée. Lin-Kernighan est adaptatif, à chaque étape la méthode décide du nombre d'arêtes à échanger pour trouver une tournée plus courte.

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.