TSP et Lin Kernighan

Bonjour,

Je suis étudiant et pour les besoins d'un cours on me demande de trouver une heuristique assez efficace pour résoudre ce qui s'est avérer être le Probleme du voyageur de commerce, c'est à dire trouver le circuit (hamiltonien) qui ne passe qu'une seule fois par chaque ville et qui est le poids minimal, qui couvre la distance minimale. Ceci en l'implémentant sur Matlab.

J'ai trouvé pas mal de publication sur un algorithme qui semblerait faire l'affaire, celui de Lin Kernighan, mais j'avoue que l'algorithmique n'étant pas du tout ma spécialité, j'ai un peu de mal à démêler toutes les notions et à les implémenter sous Matlab.

Pour l'instant j'ai une fonction qui me un premier circuit hamiltonien de poids raisonnable en prenant les plus courtes distances entre chaque point et un algorithme de Primm qui me donne l’arbre de poids minimum en excluant le point de départ/arrivé que je connecte a posteriori avec les deux point les plus proches....

je ne sais pas trop comment en partant de cet arbre de poids minimum je peux arriver à une réponse via l'algorithme de Lin Kernighan :(

Si quelqu'un pouvais m'expliquer les grandes étapes en terme profane (ou presque)

D'avance merci

PS: pour ceux qui se demande, c'est pour un cours d'"initiation" à Matlab ...