Le Problème du Voyageur de Commerce : 4 Méthodes Exactes Expliquées

Introduction

Le Problème du Voyageur de Commerce (TSP — Travelling Salesman Problem) est un classique de l'informatique et de la recherche opérationnelle :

Étant donné un ensemble de villes et les distances entre chaque paire, quel est le plus court chemin qui visite chaque ville exactement une fois et revient au point de départ ?

Malgré sa simplicité apparente, le TSP est NP-difficile — aucun algorithme en temps polynomial ne fonctionne sur toutes les instances. C'est devenu le banc d'essai de référence pour tester les techniques d'optimisation.

Dans cet article, on détaille quatre méthodes exactes (qui trouvent la solution optimale garantie) avec des animations visuelles pour chacune.

1. Force Brute — Énumération exhaustive

Principe

La méthode la plus simple : on énumère toutes les permutations possibles des villes, on calcule le coût de chaque tournée, et on garde la meilleure.

Complexité

Pour $n = 10$ villes, ça représente $362\,880$ tournées — gérable. Pour $n = 20$, c'est $\approx 1.2 \times 10^{17}$ — totalement infaisable.

Code

def brute_force_tsp(distances, n):
    villes = list(range(1, n))  # fixer la ville 0 comme départ
    meilleur_cout = float('inf')
    meilleure_tournee = None

    for perm in permutations(villes):
        tournee = [0] + list(perm) + [0]
        cout = sum(distances[tournee[i]][tournee[i+1]] for i in range(n))
        if cout < meilleur_cout:
            meilleur_cout = cout
            meilleure_tournee = tournee

    return meilleure_tournee, meilleur_cout

Quand l'utiliser ?

• Très petit nombre de villes ($n \leq 12$)
• Comme référence pour valider d'autres algorithmes

2. Programmation Dynamique — Algorithme de Held-Karp

Principe

L'algorithme de Held-Karp (1962) utilise la mémorisation pour éviter de recalculer les mêmes sous-problèmes. On représente chaque état par un couple $(S, j)$ :

• $S$ — l'ensemble des villes déjà visitées (codé en bitmask)
• $j$ — la dernière ville visitée

La relation de récurrence :

Complexité

C'est exponentiellement meilleur que $O(n!)$. Pour $n = 20$, on passe de $10^{17}$ à $\approx 4 \times 10^8$ opérations — faisable en quelques secondes.

Code

def held_karp(distances, n):
    # dp[(S, j)] = coût min pour visiter les villes de S, en finissant par j
    dp = {}
    # Cas de base : partir de la ville 0
    for j in range(1, n):
        dp[(1 << j, j)] = distances[0][j]

    for taille in range(2, n):
        for S in combinaisons(range(1, n), taille):
            bits = sum(1 << v for v in S)
            for j in S:
                bits_sans_j = bits & ~(1 << j)
                dp[(bits, j)] = min(
                    dp[(bits_sans_j, i)] + distances[i][j]
                    for i in S if i != j
                )

    # Fermer le cycle : revenir à la ville 0
    bits_tous = (1 << n) - 2  # toutes les villes sauf 0
    return min(dp[(bits_tous, j)] + distances[j][0] for j in range(1, n))

Avantages

• Bien plus rapide que la force brute
• Garantit la solution optimale
• Applicable jusqu'à $n \approx 25$ villes

3. Branch and Bound — Élagage intelligent

Principe

Le Branch and Bound explore un arbre de recherche en construisant les tournées ville par ville. À chaque nœud, on calcule une borne inférieure sur le coût de la meilleure solution atteignable. Si cette borne dépasse la meilleure solution connue, on élague (coupe) cette branche.

Les étapes clés :

1. Brancher : choisir la prochaine ville à visiter
2. Borner : calculer une borne inférieure (souvent via une relaxation, ex. MST)
3. Élaguer : ignorer les branches non prometteuses

Borne inférieure typique

On utilise souvent l'arbre couvrant minimal (MST) des villes non encore visitées :

Code

def branch_and_bound_tsp(distances, n):
    meilleur_cout = float('inf')
    meilleure_tournee = None

    def explorer(tournee, cout, visitees):
        nonlocal meilleur_cout, meilleure_tournee

        if len(tournee) == n:
            cout_total = cout + distances[tournee[-1]][tournee[0]]
            if cout_total < meilleur_cout:
                meilleur_cout = cout_total
                meilleure_tournee = tournee[:]
            return

        for ville in range(n):
            if ville not in visitees:
                nouveau_cout = cout + distances[tournee[-1]][ville]
                borne = nouveau_cout + mst_borne(distances, visitees | {ville}, n)
                if borne < meilleur_cout:  # élaguer si non prometteur
                    tournee.append(ville)
                    visitees.add(ville)
                    explorer(tournee, nouveau_cout, visitees)
                    tournee.pop()
                    visitees.remove(ville)

    explorer([0], 0, {0})
    return meilleure_tournee, meilleur_cout

Performances

En pratique, le Branch and Bound peut résoudre des instances de 30 à 40 villes (voire plus avec de bonnes heuristiques de borne). La clé est la qualité de la borne inférieure.

4. Programmation Linéaire en Nombres Entiers (PLNE)

Principe

On formule le TSP comme un programme linéaire en nombres entiers (PLNE). Des variables binaires $x_{ij} \in \{0, 1\}$ indiquent si l'arête $(i, j)$ fait partie de la tournée.

Formulation

Sous les contraintes :

1. Chaque ville est quittée exactement une fois : $\sum_{j \neq i} x_{ij} = 1 \quad \forall i$

2. Chaque ville est atteinte exactement une fois : $\sum_{i \neq j} x_{ij} = 1 \quad \forall j$

3. Élimination des sous-tours (contraintes de Miller-Tucker-Zemlin) : $u_i - u_j + n \cdot x_{ij} \leq n - 1 \quad \forall i, j \geq 1$

Implémentation avec un solveur

from ortools.linear_solver import pywraplp

def plne_tsp(distances, n):
    solver = pywraplp.Solver.CreateSolver('SCIP')
    
    x = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                x[i, j] = solver.BoolVar(f'x_{i}_{j}')
    
    # Fonction objectif
    solver.Minimize(
        sum(distances[i][j] * x[i, j] for i in range(n) for j in range(n) if i != j)
    )
    
    # Contraintes d'entrée/sortie
    for i in range(n):
        solver.Add(sum(x[i, j] for j in range(n) if j != i) == 1)
        solver.Add(sum(x[j, i] for j in range(n) if j != i) == 1)
    
    # Élimination des sous-tours (MTZ)
    u = [solver.IntVar(0, n - 1, f'u_{i}') for i in range(n)]
    for i in range(1, n):
        for j in range(1, n):
            if i != j:
                solver.Add(u[i] - u[j] + n * x[i, j] <= n - 1)
    
    solver.Solve()
    return extraire_tournee(x, n)

Avantages

• Exploite des solveurs industriels extrêmement optimisés (Gurobi, CPLEX, SCIP)
• Peut résoudre des instances de centaines de villes avec les bonnes techniques (coupes, relaxation LP)
• Très flexible — facile d'ajouter des contraintes supplémentaires

Comparatif

Pour finir

Le TSP est un exemple parfait de comment une question simple peut cacher une complexité de calcul énorme. Les quatre méthodes présentées ici garantissent toutes la solution optimale, mais diffèrent radicalement dans leur efficacité :

• La force brute est pédagogique mais inutilisable au-delà de 12 villes
• La programmation dynamique (Held-Karp) est le premier vrai gain algorithmique
• Le Branch and Bound ajoute de l'intelligence dans l'exploration
• La programmation linéaire exploite la puissance des solveurs modernes

Pour les instances de grande taille (milliers de villes), on se tourne vers des méthodes approchées — algorithmes gloutons, 2-opt, recuit simulé, algorithmes génétiques, colonies de fourmis. Mais ça fera l'objet d'un prochain article.

Questions ou suggestions ? Contactez-moi via la page de contact.