Comprendre l'Algorithme du Voyageur de Commerce avec l'Approche Gloutonne et 2-opt

Une analyse complète de l'implémentation MATLAB pour résoudre le problème TSP avec optimisation locale

Points essentiels

L'algorithme combine une approche gloutonne initiale avec une optimisation 2-opt pour résoudre le problème du voyageur de commerce (TSP)
La méthode gloutonne construit rapidement un premier parcours en sélectionnant toujours la ville la plus proche
L'amélioration 2-opt (exchange2) optimise le parcours en échangeant des segments pour réduire la distance totale

Vue d'ensemble de l'algorithme TSP

L'algorithme présenté est une solution au célèbre problème du voyageur de commerce (Traveling Salesman Problem). Ce problème d'optimisation combinatoire consiste à trouver le chemin le plus court permettant de visiter toutes les villes une seule fois avant de revenir au point de départ.

Cette implémentation utilise une approche en deux phases :

Une construction initiale rapide avec un algorithme glouton
Une amélioration itérative avec l'algorithme d'échange 2-opt

Génération des données du problème

Les premières lignes génèrent aléatoirement 50 points dans un espace bidimensionnel, représentant les villes à visiter :

X = rand(50,2);
[n,dim] = size(X);

Ici, X est une matrice de 50 lignes (villes) et 2 colonnes (coordonnées x et y), n représente le nombre de villes (50) et dim la dimension (2).

Calcul des distances entre villes

La matrice de distances D est calculée en utilisant la distance euclidienne entre chaque paire de villes :

D = squareform(pdist(X,'euclidean'));

La fonction pdist calcule les distances entre toutes les paires de points, puis squareform convertit le résultat en matrice carrée où D(i,j) représente la distance entre la ville i et la ville j.

Sélection aléatoire du point de départ

start = fix(rand*n)+1;

Cette ligne choisit aléatoirement une ville de départ parmi les n villes disponibles. fix(rand*n)+1 génère un entier aléatoire entre 1 et n.

Algorithme glouton (Greedy)

La fonction greedy implémente une stratégie gloutonne pour construire un premier parcours :

function p = greedy(s,D)
    % D distance matrix
    n = size(D,1);
    p = zeros(1,n);
    p(1) = s;
    for k = 2:n
        D(s,:) = inf;
        [~,s] = min(D(:,s));
        p(k) = s;
    end
end

Fonctionnement de l'algorithme glouton

L'algorithme glouton du plus proche voisin fonctionne comme suit :

Commencer à la ville de départ s
Placer cette ville comme premier élément du parcours p(1) = s
Pour chaque étape suivante (de 2 à n) :
- Marquer la ville actuelle comme visitée en remplaçant sa ligne dans la matrice de distances par l'infini D(s,:) = inf
- Trouver la ville non visitée la plus proche de la ville actuelle [~,s] = min(D(:,s))
- Ajouter cette ville au parcours p(k) = s

Cette approche garantit que chaque ville est visitée exactement une fois, mais ne garantit pas que le parcours final soit optimal.

Ce graphique radar compare les caractéristiques des différentes approches utilisées dans l'algorithme. L'algorithme glouton excelle en rapidité et simplicité mais produit des solutions de qualité moyenne, tandis que l'algorithme 2-opt améliore la qualité des solutions mais nécessite plus de temps de calcul.

Visualisation du parcours

La fonction tspplot1 visualise graphiquement le parcours trouvé :

function tspplot1(p,X)
    x = X(p,1); x = [x;x(1)];
    y = X(p,2); y = [y;y(1)];
    % Plot
    plot(x,y,'kx',x(1),y(1),'ob','MarkerSize',12, 'LineWidth',2)
    hold on
    pause(0.2)
    for i=2:length(p)+1
        plot([x(i-1) x(i)],[y(i-1) y(i)],'r','LineWidth',2)
        pause(0.2)
    end
    % Add title
    L = sqrt(diff(x).^2 + diff(y).^2);
    str = sprintf('Tour Length: %g',sum(L));
    title(str)
end

Étapes de la visualisation

Extraire les coordonnées x et y des villes dans l'ordre du parcours défini par p
Ajouter les coordonnées de la première ville à la fin pour fermer le circuit
Tracer toutes les villes avec des croix noires ('kx') et marquer la ville de départ par un cercle bleu ('ob')
Tracer chaque segment du parcours avec une ligne rouge épaisse
Calculer la longueur totale du parcours et l'afficher dans le titre

Les pauses (pause(0.2)) permettent de visualiser la construction progressive du parcours.

Optimisation par échange 2-opt

La dernière étape fait appel à la fonction exchange2 pour améliorer le parcours :

[p,L] = exchange2(p,D,X);

Bien que cette fonction ne soit pas définie dans le code fourni, l'algorithme 2-opt est une technique d'optimisation locale qui améliore itérativement un parcours en échangeant deux segments.

Fonctionnement de l'algorithme 2-opt

L'algorithme 2-opt fonctionne selon le principe suivant :

Commencer avec un parcours initial (celui obtenu par l'algorithme glouton)
Pour chaque paire de segments non adjacents du parcours :
- Calculer la longueur actuelle du parcours
- Inverser l'ordre des villes entre ces deux segments
- Calculer la nouvelle longueur du parcours
- Si la nouvelle longueur est plus courte, adopter ce nouveau parcours
Répéter jusqu'à ce qu'aucune amélioration ne soit possible

Méthode	Description	Avantages	Inconvénients	Complexité
Algorithme glouton (Greedy)	Choisit toujours la ville la plus proche non visitée	Rapide, simple à implémenter, donne une solution initiale raisonnable	Solution souvent loin de l'optimum, sensible au point de départ	O(n²)
Algorithme 2-opt	Améliore un parcours en échangeant des paires de segments	Améliore considérablement les solutions, converge vers un optimum local	Peut être lent pour de grandes instances, s'arrête au premier optimum local	O(n²) par itération
Approche combinée (Greedy + 2-opt)	Construit rapidement une solution puis l'améliore	Bon compromis entre qualité et temps d'exécution	Reste sous-optimal par rapport aux méthodes exactes	O(n²) + O(k·n²) où k est le nombre d'itérations 2-opt

mindmap root["Algorithme du voyageur de commerce"] ::icon(fa fa-route) ["Initialisation"] ["Génération de points aléatoires"] ["Calcul de la matrice de distances"] ["Sélection aléatoire du point de départ"] ["Construction gloutonne"] ["Principe du plus proche voisin"] ["Exécution rapide (O(n²))"] ["Solution initiale sous-optimale"] ["Visualisation"] ["Affichage des villes"] ["Tracé progressif du parcours"] ["Calcul de la longueur totale"] ["Optimisation 2-opt"] ["Échanges de segments"] ["Amélioration itérative"] ["Convergence vers un optimum local"]

Pourquoi cette approche est efficace

La combinaison d'un algorithme glouton suivi d'une amélioration 2-opt est particulièrement efficace pour plusieurs raisons :

Équilibre entre rapidité et qualité

L'algorithme glouton fournit rapidement une solution initiale raisonnable, tandis que l'algorithme 2-opt améliore cette solution de manière significative sans le coût prohibitif des méthodes exactes.

Simplicité d'implémentation

Les deux algorithmes sont relativement simples à comprendre et à implémenter, ce qui les rend accessibles et faciles à adapter à différents contextes.

Bonnes performances pratiques

Bien que cette approche ne garantisse pas de trouver la solution optimale, elle produit généralement des solutions de bonne qualité pour des instances de taille moyenne (jusqu'à plusieurs centaines de villes).

Cette vidéo explique en détail le fonctionnement de l'algorithme 2-opt et montre visuellement comment il améliore progressivement une solution au problème du voyageur de commerce, exactement comme le fait la fonction exchange2 dans notre algorithme.

Exemples visuels d'optimisation TSP

Cette image montre une visualisation du processus d'optimisation 2-opt sur un problème TSP. On peut voir comment l'algorithme identifie et corrige les croisements dans le parcours pour réduire la longueur totale.

Cette image compare différentes approches métaheuristiques pour résoudre le problème TSP, illustrant les avantages et les limites de chaque méthode, dont l'approche gloutonne et l'optimisation 2-opt utilisées dans notre algorithme.