Recherche d'un cycle hamiltonien de longueur minimale

Introduction

Il s'agit d'implémenter et de comparer les résultats de trois ou quatre heuristiques (algorithme approché) qui déterminent sur un graphe non-orienté un cycle hamiltonien de valeur minimum. Un cycle hamiltonien est un cycle passant une fois et une seule par chaque sommet du graphe.

Le problème de la recherche d'un cycle hamiltonien de longueur minimale est à rapprocher de celui - classique - du voyageur de commerce. Si un voyageur de commerce, partant d'une ville de départ donnée, doit passer exactement une fois par chaque ville se trouvant sur sa liste puis revenir dans la ville initiale (chez lui), on peut comprendre qu'il ait intérêt à choisir l'ordre dans lequel il va choisir les villes, pour que la somme des distances qu'il aura à parcourir dans sa tournée soit aussi petite que possible. On considère qu'il connaît, pour chaque paire de villes, la distance les séparant. Ainsi, on peut penser qu'il a en sa possession toutes les données nécessaires pour trouver la tournée minimale, mais il n'est absolument pas évident de savoir comment utiliser ces données pour résoudre ce problème…

Celui-ci figure parmi les problèmes d'optimisation combinatoire classés difficiles. Il se rencontre dans de nombreuses situations comme par exemple des problèmes d'ordonnancement de production, de ramassage scolaire, de cablage de circuits, de synthèse des circuits logiques séquentiels… Il se modélise par la recherche d'un circuit hamiltonien (cas orienté) ou d'un cycle hamiltonien (cas non orienté) dans le graphe dont l'ensemble des sommets représente les différents sites et l'ensemble des arcs (ou des arêtes) les liaisons entre ces sites.

Il s'agit d'un problème NP-difficile, c'est-à-dire qu'il n'existe pas d'algorithme à complexité polynomiale pour le résoudre dans le cas général. Néanmoins, un certain nombre d'heuristiques (algorithmes approximatifs) ont été développées pour déterminer de "bonnes" solutions à des instances du problème. Par "bonne", on entend une solution qui, si elle n'est pas la solution optimale, n'en est pas "trop" éloignée.

Nous nous intéresserons plus particulièrement à des méthodes heuristiques simples de résolution, même si, en fait, il existe énormément d'algorithmes permettant de résoudre - plus ou moins efficacement - le problème du voyageur de commerce :

• Méthodes de descente
• Algorithmes gloutons
• Méthode Branch & Bound
• Recuit simulé
• Algorithme tabou
• Algorithmes génétiques
• Algorithme de Lin et Kerningham
• Colonies de fourmis

Nous allons donc pouvoir comparer sur différents exemples l'efficacité de des algorithmes nommés :

• Nearest Neighbour Algorithm (NNA)
• Nearest Addition Algorithm (NAA)
• Nearest Insertion Algorithm (NIA)
• Cheapest Insertion Algorithm (CIA)
• Farthest Insertion Algorithm (FIA)

Algorithmes des heuristiques retenues

• Nearest Neighbour Algorithm (NNA)
  • On part d'une tournée réduite à un seul site v_i1.
  • Tant que tous les sites ne sont pas incorporés dans la tournée répéter
  • Soit v_i1,v_i2,...,v_ik (k inférieur à n) la solution courante (chaîne) à l'itération k, on rajoute le site v_ik+1 le plus proche de v_ik à la fin de la chaîne.
  • Fin répéter
  
  
• Nearest Addition Algorithm (NAA)
  • Tv₀ /* on part d'une tournée réduite à un seul site v₀ */
  • Tant que tous les sites ne sont pas incorporés dans la tournée T répéter
  • Soit v_jT et v_kT tels que d(v_j,v_k) soit minimum
  • Soit (v_i,v_j) une des deux arêtes extrémité de v_j dans T
  • TT\(v_i,v_j){(v_i,v_k),(v_k,v_j)}
  • Fin répéter
  
  
• Nearest Insertion Algorithm (NIA)
  • Tv₀ /* on part d'une tournée réduite à un seul site v₀ */
  • Tant que tous les sites ne sont pas incorporés dans la tournée T répéter
  • Soit v_jT et v_kT tels que d(v_j,v_k) soit minimum
  • Soit v_i le point voisin de v_j dans T tel que d(v_i,v_k)+d(v_k,v_j)-d(v_i,v_j) est minimum
  • TT\(v_i,v_j){(v_i,v_k),(v_k,v_j)}
  • Fin répéter
  
  
• Cheapest Insertion Algorithm (CIA)
  • Tv₀ /* on part d'une tournée réduite à un seul site v₀ */
  • Tant que tous les sites ne sont pas incorporés dans la tournée T répéter
  • Soit v_kT et (v_i,v_j) une arête de T telle que d(v_i,v_k)+d(v_k,v_j)-d(v_i,v_j) est minimum
  • TT\(v_i,v_j){(v_i,v_k),(v_k,v_j)}
  • Fin répéter
  
  
• Farthest Insertion Algorithm (FIA)
  • Tv₀ /* on part d'une tournée réduite à un seul site v₀ */
  • Tant que tous les sites ne sont pas incorporés dans la tournée T répéter
  • Soit v_kT tel que min{d(v_j,v_k) | v_jT} soit maximum
  • Soit (v_i,v_j) une arête de T telle que d(v_i,v_k)+d(v_k,v_j)-d(v_i,v_j) est minimum
  • TT\(v_i,v_j){(v_i,v_k),(v_k,v_j)}
  • Fin répéter

Applet Java illustrant toutes ces heuristiques

Conclusion : étude comparative des heuristiques

Nous pouvons maintenant comparer les résultats fournis par les cinq heuristiques. Pour cette comparaison, et dans un souci de clarté, portons sur un même graphique la longueur moyenne de la tournée, calculée sur 100 itérations pour chaque heuristique, en fonction du nombre de points.

Pour un petit nombre de points, on peut constater que l'algorithme NNA, le plus simple qui soit (à chaque étape, on se dirige vers la ville la plus proche), donne de biens meilleurs résultats que les quatre autres. Puis, pour des cartes ayant entre 10 et 15 villes, la tendance s'inverse avec l'algorithme le plus élaboré, l'algorithme FIA, qui devient alors plus avantageux.

L'algorithme NAA, insérant dans la tournée aléatoirement le point qui en est le plus proche, est en revanche immédiatement beaucoup plus mauvais que les quatre autres.

On peut alors ce demander ce qu'il adviendra lorsque le nombre de points va augmenter.

Pour un nombre de points allant jusqu'à 200, on se rend compte que la tendance qui se révélait au bout de 50 points se confirme très nettement.

En effet, l'algorithme NAA donne des résultats de plus en plus mauvais, et finit en dernier de ces heuristiques, tandis que l'algorithme FIA confirme ses très bons résultats quand le nombre de points augmente.

De plus, l'algorithme "Nearest Neighbour" (NNA), qui se classait en second pour de petits nombres de points, passe en troisième quand le nombre de points augmente. Il paraît quand même étonnant que cet algorithme, très simple, parvienne à d'aussi bons résultats, par rapport à l'heuristique FIA.

Il semble en revanche normal que l'algorithme CIA se classe systématiquement devant l'algorithme NIA, car au lieu d'insérer au mieux l'élément le plus proche de la tournée, il cherche d'emblée le point qui s'insèrera le mieux dans la tournée. On peut aussi remarquer que NNA et CIA donnent des solutions assez proches en ce qui concerne la longueur de la tournée.

Ces méthodes ont le mérite de procurer rapidement une solution à un problème. Elles peuvent de plus être utilisées comme solution courante de départ dans un algorithme "Branch and Bound" ou dans des méthodes de voisinage.