Heuristique gloutonne et recherche locale 2-opt

L’heuristique du plus proche voisin

L’idée la plus simple : partir d’un point, puis toujours se rendre au point non visité le plus proche.

def nearest_neighbor_route(start, D):
    n = D.shape[0]
    unvisited = set(range(n)) - {start}
    path = [start]
    while unvisited:
        last = path[-1]
        nxt = min(unvisited, key=lambda j: D[last, j])
        path.append(nxt)
        unvisited.remove(nxt)
    return path

Rapide (une seule passe), mais myope : un choix localement optimal à chaque étape peut mener à un très mauvais choix global — typiquement, un point isolé oublié en fin de parcours, qui oblige à un grand détour final.

Améliorer la solution : la recherche locale 2-opt

Le 2-opt part d’un chemin existant et cherche des paires de segments dont l’inversion raccourcit le trajet total, tant que l’inégalité triangulaire le permet.

def two_opt_refine(path, D, tol=1e-10):
    improved = True
    path = path[:]
    while improved:
        improved = False
        for i in range(1, len(path) - 2):
            for j in range(i + 1, len(path) - 1):
                a, b, c, d = path[i - 1], path[i], path[j], path[j + 1]
                gain = (D[a, b] + D[c, d]) - (D[a, c] + D[b, d])
                if gain > tol:
                    path[i:j + 1] = reversed(path[i:j + 1])
                    improved = True
    return path

Le calcul du gain ne compare que 4 sommets (a, b, c, d) plutôt que de recalculer la longueur totale du chemin à chaque tentative d’inversion — une optimisation qui rend l’algorithme praticable même sur des dizaines de points. La marge tol évite des boucles infinies dues aux arrondis flottants (une inversion qui « améliorerait » de 10⁻¹⁵ km n’est pas une vraie amélioration).

Mesurer le gain réel

naive_path = list(range(len(sous_points)))  # l'ordre brut, non optimise
naive_dist = path_distance(naive_path, D)

greedy_path = nearest_neighbor_route(0, D)
refined_path = two_opt_refine(greedy_path, D)

print("distance ordre brut:", naive_dist)
print("distance apres glouton + 2-opt:", path_distance(refined_path, D))

Sur la zone 1 (35 points) : l’ordre brut (l’ordre de génération des données, sans aucune optimisation) parcourt 2194 km, contre 646 km après glouton + 2-opt — un gain de plus de 70 %, qui illustre à quel point l’ordre de visite peut faire une différence radicale sur la distance totale parcourue.

Prochaine étape

👉 Stratégie multi-démarrage et synthèse

---

Junior TSAFACK – 12/09/2026