Méthodes de résolution

Les méthodes de résolution peuvent être classées en deux catégories :

Les algorithmes déterministes examinent toutes les possibilités ou, du moins, s'assurent de ne pas écarter la meilleure solution.

Les algorithmes d'approximation se contentent de trouver une solution raisonnable en explorant seulement une partie des possibilités. Lorsqu'ils trouvent la solution optimale, c'est dans un temps beaucoup plus court qu'avec des algorithmes déterministes mais rien ne prouve que c'est réellement la bonne solution. Pour des problèmes plus complexes (1000 villes ou plus ? ), ils deviennent incapables de trouver la solution optimale mais sont intéressants pour obtenir un premier résultat approché qui servira de base à des algorithmes déterministes.

Un classique à 280 villes : A280 (Ludwig)
2-opt optimisé

Les algorithmes déterministes

La méthode proposée dans le tableau Excel étudie toutes les possibilités et permet d'assurer que la solution trouvée est optimale. C'est une méthode déterministe.

Nous avons déjà vu qu'une telle méthode ne peut fonctionner que pour quelques villes mais pour un nombre plus important il est possible de limiter l'exploration à une partie des possibilités tout en gardant la certitude que la solution idéale n'est pas exclue.

Une technique assez simple, celle de la "séparation-évaluation", part d'une solution trouvée par un algorithme d'approximation. En examinant l'arbre des solutions, on peut éviter de parcourir une bonne partie de l'arbre en s'arrêtant sur une branche dès que la distance obtenue permet d'assurer que le record ne sera pas battu. On pourrait également partir d'une solution quelconque mais le temps de calcul serait considérablement augmenté.

Ces méthodes sont très lourdes et nécessitent de nombreux ordinateurs extrêmement puissants qui se partagent le travail. Elles permettent tout de même de résoudre des problèmes de plus en plus complexes. On peut citer, par exemple, la résolution d'un problème pour 24978 lieux de Suède qui a nécessité l'équivalent de 85 ans de temps de calcul.

Les algorithmes d'approximation

Ces algorithmes ne cherchent pas à examiner l'ensemble des solutions mais utilisent des règles permettant de choisir un segment plutôt qu'un autre ou des techniques d'optimisation permettant d'améliorer un premier parcours quelconque.

La méthode du glouton, probablement la plus ancienne, consiste à se déplacer systématiquement vers la ville la plus proche qui n'a pas encore été visitée. Elle permet rarement d'obtenir la solution optimale mais peut permettre de trouver un premier parcours pas trop long. Le trajet dépendant du point initial, on peut améliorer la technique en effectuant tous les essais à partir des différents points.

La méthode de l'élastique est délicate à mettre en oeuvre mais assez facilement compréhensible. On prend un élastique que l'on place au milieu des villes (ou comme enveloppe de l'ensemble des villes) puis on le déforme en faisant agir deux forces, une qui essaie d'approcher l'élastique des différents points et une qui empêche l'élastique de trop se détendre.

L'algorithme génétique consiste à étudier une population d'individus (des trajets permettant de relier les N villes) et de la faire évoluer de la même manière qu'une population dans la théorie de l'évolution de Darwin. On combine entre eux les parcours en sélectionnant les meilleurs parcours (stratégie élitiste) tout en en essayant d'éviter trop de "consanguinité" (ne pas toujours utiliser les parcours les plus courts) et de provoquer quelques "mutations génétiques" (des déformation aléatoire d'un parcours). De nombreux sites présentant cette méthode sur Internet, je ne vous la décrirais pas en détail mais vous invite à visiter les sites que j'ai cité en introduction.

Voici également deux autres méthodes qui seront développées plus précisément :

La méthode de la colonie de fourmis

Le 2-opt amélioré que j'utilise pour le problème des 250 villes.

Jean-Luc Juveneton : Ingénierie Educative - CRDP - Grenoble (38) / imel@ac-grenoble.fr / 12 avril 2005