Qu'est-ce que le TSP, et pourquoi c'est le cœur d'OptiRoad

Si vous livrez 15, 30 ou 100 clients dans la journée, vous avez déjà fait, sans le savoir, du TSP, le Traveling Salesman Problem, ou problème du voyageur de commerce. C'est l'un des problèmes les plus étudiés de l'informatique, et c'est exactement celui que résout OptiRoad chaque fois que vous lancez une optimisation. Ce guide explique simplement de quoi il s'agit, pourquoi c'est plus dur qu'il n'y paraît, et comment on le résout en pratique.

Le problème, en une phrase

Vous avez un point de départ (votre dépôt, votre domicile) et une liste d'adresses à visiter dans la journée. Quel est l'ordre de passage qui minimise la distance totale parcourue ? C'est ça, le TSP.

Trivial à formuler, redoutable à résoudre dès qu'on dépasse une dizaine d'adresses. Et c'est précisément là que le bon sens humain atteint vite ses limites : l'œil repère facilement une tournée à 5 arrêts, beaucoup moins bien une tournée à 40.

Un exemple concret

Imaginez 5 livraisons à effectuer à Paris :

• A : République
• B : Bastille
• C : Montparnasse
• D : Étoile
• E : Pigalle

Si vous partez du dépôt et passez dans l'ordre alphabétique A → B → C → D → E, vous allez probablement zigzaguer dans la ville. Concrètement, ce trajet alphabétique vous fait traverser Paris d'est en ouest puis revenir : comptez environ 13 km. En réorganisant intelligemment les mêmes 5 adresses (par exemple en regroupant les arrêts proches géographiquement), l'ordre optimisé tombe à environ 9 km, soit à peu près 30 % de moins pour exactement les mêmes livraisons. Sur 200 jours travaillés par an, ces économies par tournée représentent plusieurs milliers de kilomètres, donc des heures de conduite et un budget carburant non négligeable.

Pourquoi le TSP est dur

Avec 5 adresses, il y a 5! = 120 ordres possibles. Un humain peut tester à la main. Avec 10 adresses, on grimpe à 3,6 millions d'ordres. Avec 20, c'est 2,4 milliards de milliards. Aucune machine au monde ne peut tester toutes les combinaisons d'une tournée de 30 livraisons en un temps raisonnable.

Le TSP est ce qu'on appelle un problème NP-difficile : aucun algorithme connu ne peut garantir la solution parfaite en un temps qui scale raisonnablement avec le nombre d'arrêts. Chaque adresse ajoutée multiplie l'espace des solutions, pas seulement l'additionne.

À retenir : pour 10 adresses ou moins, on peut encore tester toutes les combinaisons et garantir l'optimal absolu. Au-delà, on utilise des heuristiques, des stratégies qui donnent une très bonne solution sans garantir la perfection mathématique.

Un peu d'histoire

Le TSP n'est pas une nouveauté. Les mathématiciens l'étudient depuis les années 1930 : le mathématicien autrichien Karl Menger l'évoque à Vienne au sein de son cercle scientifique, et le problème circule rapidement dans les universités américaines. Le tournant arrive dans les années 1950 à la RAND Corporation, où George Dantzig, Delbert Ray Fulkerson et Selmer Johnson publient en 1954 la résolution exacte d'une instance célèbre : une tournée optimale reliant 49 villes des États-Unis (une par État, plus Washington). C'était un exploit pour l'époque, obtenu avec des méthodes de programmation linéaire et beaucoup de calcul à la main. Aujourd'hui encore, le TSP reste un banc d'essai de référence en recherche opérationnelle et en logistique : les nouveaux algorithmes se mesurent souvent sur ces instances historiques.

Les approches en pratique

1. Brute force (≤ 10 stops)

On teste toutes les permutations possibles, on garde la meilleure. Garantit l'optimal absolu mais devient impraticable au-delà de 10 arrêts.

2. Nearest neighbor (heuristique simple)

À chaque étape, on va au stop le plus proche du précédent. Rapide, mais souvent loin de l'optimal car on peut se retrouver coincé loin de la suite des stops.

3. 2-opt (amélioration locale)

On part d'une solution initiale (souvent obtenue par nearest neighbor), puis on essaie de "détordre" les croisements en inversant des segments de tournée. Itératif, donne typiquement des résultats à moins de 5 % de l'optimal théorique.

4. Algorithmes plus avancés

Lin-Kernighan, recuit simulé, algorithmes génétiques, programmation par contraintes : beaucoup d'approches existent en recherche opérationnelle. Pour un usage métier comme la livraison, nearest neighbor + 2-opt offre le meilleur compromis simplicité, qualité et vitesse.

Optimum parfait ou très bon tout de suite ?

C'est la vraie question quand on conçoit un outil de livraison. Un solveur peut viser la solution mathématiquement parfaite, mais elle peut demander des heures de calcul sur une grosse tournée. Or sur le terrain, personne n'attend des heures pour partir en livraison. Une solution à quelques pour cent de l'optimal, calculée en quelques secondes, bat largement une solution parfaite obtenue trop tard.

Pourquoi ? Parce que les derniers pour cent de distance grattés ne valent presque jamais l'attente : entre une tournée à 9,0 km et une tournée à 8,8 km, la différence sur votre journée est négligeable, alors que le temps de calcul, lui, peut exploser. C'est exactement pourquoi les heuristiques comme nearest neighbor + 2-opt sont le bon choix d'ingénierie : elles offrent l'essentiel du gain, immédiatement et de façon fiable. La perfection théorique reste l'affaire des chercheurs ; la rentabilité quotidienne, celle des livreurs.

Les variantes qui comptent pour la livraison

Le TSP "pur" suppose qu'on rentre au point de départ à la fin. En pratique, vos contraintes sont plus riches :

• TSP open-loop : pas de retour au dépôt (vous finissez chez le dernier client).
• VRPTW (Vehicle Routing Problem with Time Windows) : chaque adresse a une plage horaire d'ouverture (ex. 9h à 12h). C'est ce que vous utilisez pour les fenêtres de livraison.
• VRP multi-véhicules : plusieurs livreurs, comment répartir les arrêts entre véhicules pour minimiser le temps total ?
• VRP avec capacités : chaque véhicule a une charge utile maximale.

OptiRoad gère ces variantes : VRPTW pour les fenêtres horaires (en plan Pro et Business) et VRP multi-véhicules avec algorithme Clarke-Wright Savings (plan Business, jusqu'à 10 véhicules).

Comment OptiRoad résout votre TSP

À chaque clic sur Optimiser dans le dashboard, OptiRoad applique la stratégie suivante :

1. Géocode vos adresses (les transforme en coordonnées GPS) si elles ne le sont pas déjà.
2. Construit la matrice de distances entre tous les points via OpenRouteService (ou Google Routes en fallback).
3. Si ≤ 10 stops : brute force, toutes les permutations testées, optimal absolu garanti.
4. Sinon : nearest neighbor pour construire la route initiale, puis 2-opt pour l'affiner par itérations successives.
5. Si VRPTW activé : le solveur tient compte des fenêtres horaires via une approche Earliest Deadline First, en signalant tout retard prévisible.
6. Si multi-véhicules : Clarke-Wright Savings pour répartir les stops, puis TSP local sur chaque tournée.

Le tout en quelques secondes (3 secondes pour 15 stops, jusqu'à 20 secondes pour 150 stops avec timeout adaptatif).

En pratique : ce que ça change pour vous

Sur une tournée typique de 30 livraisons en zone urbaine :

• Sans optimisation : environ 120 km, environ 5h de route
• Avec OptiRoad : environ 85 à 90 km, environ 3h30 à 4h de route
• Gain typique : 25 à 30 % de distance, 20 à 30 % de temps

Sur 200 jours travaillés par an, c'est plusieurs milliers de kilomètres et plusieurs centaines d'heures économisées. Et tout ça vient du fait qu'on résout un problème qu'on appelle "le TSP" depuis 1930.

Questions fréquentes

Combien d'adresses OptiRoad peut-il optimiser ?

Jusqu'à 150 arrêts par tournée. Jusqu'à 10 arrêts, le brute force teste toutes les combinaisons et garantit l'optimum absolu. Au-delà, OptiRoad bascule sur les heuristiques (nearest neighbor puis 2-opt) qui restent excellentes même sur les grosses tournées.

La tournée est-elle toujours la plus courte possible ?

Oui, et c'est mathématiquement garanti jusqu'à 10 arrêts. Au-delà, le résultat se situe typiquement à moins de 5 % de l'optimum théorique grâce au 2-opt : un écart imperceptible sur le terrain, pour un calcul quasi instantané.

Ai-je besoin d'un point de départ ?

Oui. Il faut un point de départ : un dépôt ou une adresse de domicile. Le point d'arrivée, lui, est optionnel : si vous n'en indiquez pas, OptiRoad considère que vous rentrez à votre point de départ (tournée en boucle).

Combien de temps prend le calcul ?

Quelques secondes. OptiRoad utilise un timeout adaptatif : environ 3 secondes pour les petites tournées, jusqu'à 20 secondes pour 150 arrêts. Si la limite est atteinte, l'outil renvoie quand même la meilleure tournée trouvée.

Pour aller plus loin

Si vous voulez voir l'algorithme à l'œuvre sur vos propres adresses, le plan gratuit d'OptiRoad inclut 5 tournées par mois jusqu'à 10 stops, donc dans la zone où l'optimal absolu est garanti par brute force. C'est le meilleur moyen de mesurer concrètement ce que vous gagnez.

Vous voulez creuser les variantes (fenêtres horaires, multi-véhicules) ? Continuez sur les autres articles du blog ou lisez la documentation API.