Algorithme de Lin-Kernighan
Un article de Wikipédia, l'encyclopédie libre.
En optimisation, l'algorithme de Lin-Kernighan[1] est l'une des meilleures 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 meilleure 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.
[modifier] Voir aussi
[modifier] Références
- S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
- G. A. Croes (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
