Algorithme de Lin-Kernighan
- Algorithme de Lin-Kernighan
-
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.
Voir aussi
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.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Lin-Kernighan de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Brian Kernighan — ˈkɛrnɪhæn (le G est muet). (né en janvier 1942 à Toronto, Canada) est un informaticien connu pour avoir co écrit le premier livre sur le langage de programmation C (avec Dennis Ritchie). Il est aussi le co créateur des langages Awk … Wikipédia en Français
2-opt — En optimisation, 2 opt est un algorithme de recherche locale proposé par Croes en 1958[1] pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. Sommaire 1 L algorithme 1.1 Principe … Wikipédia en Français
Problème du voyageur de commerce — Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce consiste, étant donné un… … Wikipédia en Français
Probleme de tournees de vehicules — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit … Wikipédia en Français
Probleme du voyageur de commerce — Problème du voyageur de commerce Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce … Wikipédia en Français
Problème de livraison et de collecte — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit … Wikipédia en Français
Problème de tournées de véhicules — Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit de déterminer les tournées d une… … Wikipédia en Français
