Qu'est-ce que le TSP (problème du voyageur de commerce) ?

Comment déterminer le meilleur itinéraire pour visiter plusieurs clients en parcourant le moins de kilomètres possible ? Derrière cette question, qui concerne quotidiennement les commerciaux itinérants, se cache un problème mathématique étudié depuis des décennies : le problème du voyageur de commerce, ou Traveling Salesperson Problem (TSP).

Son principe est simple : trouver le chemin le plus court reliant plusieurs destinations. Mais sa résolution devient rapidement complexe lorsque le nombre de points à visiter augmente.

Et dans la réalité, organiser une tournée commerciale ne se limite pas à calculer des distances. Il faut aussi respecter les horaires d'ouverture des clients, les rendez-vous déjà planifiés, les durées de visite et les journées de travail.

Alors, comment fonctionne le TSP ? Pourquoi est-il si difficile à résoudre ? Et comment ses principes permettent-ils de construire des tournées commerciales plus efficaces ?

Qu'est-ce que le problème du voyageur de commerce (TSP) ?

Le problème du voyageur de commerce, appelé Traveling Salesperson Problem (TSP) en anglais, est un problème classique d'optimisation combinatoire.

Il consiste à déterminer le circuit le plus court permettant de visiter un ensemble de destinations, en passant une seule fois par chacune d'elles, avant de revenir au point de départ.

Prenons un exemple.

Un commercial doit visiter cinq magasins répartis sur son secteur. Il connaît leurs adresses, mais doit déterminer dans quel ordre les visiter pour minimiser la distance parcourue.

Il pourrait commencer par le magasin A, poursuivre vers le B, puis le C, le D et le E. Mais il pourrait également visiter ces magasins dans un ordre totalement différent.

Chaque combinaison produit un itinéraire dont la distance totale peut varier.

L'objectif du TSP est de trouver l'ordre de passage qui permet de parcourir la distance totale la plus courte.

Cette problématique dépasse largement le cadre des forces de vente. Elle se retrouve dans la logistique, la livraison, les transports ou encore certains processus industriels.

Pourquoi le TSP est-il si complexe à résoudre ?

Lorsque le nombre de destinations est limité, il est relativement simple de comparer plusieurs itinéraires.

Mais chaque nouvelle destination augmente considérablement le nombre de combinaisons possibles.

En fixant un point de départ et en considérant tous les ordres de visite possibles :

• Avec 5 destinations, il existe 24 séquences possibles.

• Avec 10 destinations, il en existe 362 880.

• Avec 15 destinations, ce nombre dépasse 87 milliards.

Ces chiffres illustrent ce que l'on appelle une explosion combinatoire : le nombre de solutions possibles augmente extrêmement rapidement avec la taille du problème.

En informatique, le TSP appartient à la famille des problèmes NP-difficiles. Autrement dit, aucune méthode générale connue ne permet de garantir la résolution exacte de toutes les instances en un temps de calcul qui augmente de façon polynomiale avec leur taille.

Cela ne signifie pas qu'il est impossible de trouver la solution optimale. Des méthodes exactes existent et permettent de résoudre de nombreuses instances.

En revanche, lorsque le nombre de destinations et les contraintes augmentent, rechercher systématiquement la solution parfaite peut nécessiter des ressources de calcul importantes.

C'est pourquoi les outils d'optimisation utilisent différentes méthodes pour trouver des itinéraires efficaces dans un délai raisonnable.

Comment fonctionne un algorithme TSP ?

Dans sa formulation classique, le problème du voyageur de commerce repose principalement sur deux éléments :

1. Les destinations à visiter, représentées par des points géographiques.

2. La distance ou le coût de déplacement entre ces destinations, permettant de comparer les itinéraires.

Le problème définit également un circuit, avec un point de départ et un retour à ce même point.

À partir de ces informations, l'algorithme cherche l'ordre de visite qui minimise la distance totale.

Les différentes méthodes de résolution

Plusieurs approches permettent de résoudre un problème TSP.

Les méthodes exactes explorent les solutions de manière structurée pour identifier et prouver le meilleur itinéraire possible. Elles peuvent devenir coûteuses lorsque le problème se complexifie.

Les heuristiques cherchent à obtenir rapidement une solution satisfaisante, sans garantir qu'elle soit optimale. Une approche simple consiste, par exemple, à rejoindre à chaque étape la destination non visitée la plus proche.

Les métaheuristiques utilisent des stratégies de recherche plus élaborées pour explorer et améliorer différentes solutions. Elles sont particulièrement intéressantes pour les problèmes de grande taille.

Le choix de la méthode dépend du nombre de destinations, du temps de calcul disponible et du niveau de précision recherché.

Mais dans le cadre des tournées commerciales, un autre élément entre en jeu : la distance n'est pas la seule contrainte à respecter.

Du TSP à l'optimisation des tournées commerciales : pourquoi le trajet le plus court ne suffit pas

Le TSP classique répond à une question : quel est le circuit le plus court pour visiter toutes les destinations ?

Un commercial itinérant doit répondre à une question beaucoup plus complexe : comment organiser mes visites pour rencontrer les bons clients, aux bons moments, en limitant mes déplacements et en respectant mes contraintes quotidiennes ?

La différence est importante.

Imaginons un chef de secteur qui doit visiter quinze magasins sur trois jours.

Un algorithme qui cherche uniquement à réduire la distance pourrait lui proposer un itinéraire très court sur le papier. Mais ce planning pourrait être impossible à réaliser :

• Un magasin serait fermé au moment de son passage.

• Une visite durerait plus longtemps que le créneau disponible.

• Deux rendez-vous se chevaucheraient.

• Le commercial terminerait sa journée après ses horaires de travail.

• Un rendez-vous déjà confirmé devrait être déplacé.

Le chemin le plus court n'est donc pas nécessairement la tournée la plus efficace, ni même une tournée réalisable.

Pour répondre à ces problématiques, les logiciels d'optimisation de tournées utilisent des modèles mathématiques plus avancés que le TSP classique.

Ils se rapprochent notamment des problèmes de tournées de véhicules, appelés Vehicle Routing Problems (VRP), et de leurs variantes intégrant des fenêtres horaires ou des contraintes de planification.

Ces modèles permettent de rechercher non seulement un ordre de passage, mais aussi une répartition cohérente des visites dans le temps.

Quelles contraintes un optimiseur de tournées commerciales doit-il prendre en compte ?

Pour construire une tournée adaptée aux réalités du terrain, plusieurs paramètres peuvent être intégrés.

L'adresse de départ

Elle permet de définir le point à partir duquel le commercial commence ses déplacements : domicile, bureau ou autre adresse de référence.

Les horaires de travail

Ils délimitent la plage pendant laquelle les déplacements et les visites doivent être organisés. Un commercial travaillant de 8 h à 17 h ne dispose pas du même temps qu'un commercial terminant sa journée à 19 h.

Le nombre maximal de visites par jour

Il permet de limiter le nombre de rendez-vous planifiés quotidiennement, notamment pour éviter de surcharger les journées.

La durée des visites

Toutes les visites commerciales ne mobilisent pas le même temps. Un rendez-vous de prospection de quinze minutes ne s'organise pas comme une visite de quarante-cinq minutes en grande distribution.

Les horaires d'ouverture des établissements

Une pharmacie, un restaurant ou un magasin ne peuvent pas nécessairement être visités à n'importe quel moment. L'optimisation doit tenir compte de leurs plages d'ouverture lorsqu'elles sont renseignées.

La pause déjeuner

Elle peut être intégrée à la planification pour réserver un temps de pause pendant la journée.

Les jours d'activité et les jours exclus

Un commercial peut travailler sur plusieurs jours tout en excluant certaines journées consacrées à d'autres activités, à des réunions ou à des congés.

La période de planification

L'optimisation peut concerner une journée, une semaine ou une période plus longue, selon les besoins de couverture du portefeuille.

Les rendez-vous déjà planifiés

C'est une contrainte particulièrement importante. Lorsqu'un commercial dispose de rendez-vous confirmés, l'optimisation doit pouvoir organiser les autres visites autour de ces engagements.

L'ensemble de ces paramètres transforme un simple problème de distance en un véritable problème de planification commerciale.

Découvrez comment aider vos commerciaux à planifier leurs tournées commerciales.

Pourquoi une tournée optimisée peut-elle parfois sembler illogique ?

Prenons un exemple concret.

Un commercial visite un magasin à Toulouse. À seulement 200 mètres se trouve un autre point de vente appartenant à son portefeuille.

Pourtant, l'optimiseur ne programme pas ce deuxième magasin le même jour. Il le positionne le lendemain.

À première vue, ce choix semble contre-intuitif. Pourquoi repasser dans le même quartier alors que les deux établissements sont si proches ?

Plusieurs contraintes peuvent expliquer cette situation.

Le magasin peut être fermé au moment du passage. La durée de visite prévue peut empêcher le commercial d'arriver à l'heure à son prochain rendez-vous. Le nombre maximal de visites peut également avoir été atteint.

L'optimiseur recherche une solution qui respecte les contraintes définies. La proximité géographique ne suffit donc pas toujours à justifier l'ajout d'un établissement à une tournée.

Cet exemple illustre une différence fondamentale entre le TSP et son application commerciale.

Une tournée optimisée ne correspond pas nécessairement au trajet le plus court entre les clients, mais à une organisation qui cherche le meilleur compromis entre déplacements, temps disponible et contraintes de visite.

Comment passer du TSP à une tournée commerciale optimisée ?

Le problème du voyageur de commerce permet de comprendre la difficulté mathématique liée à la recherche du meilleur itinéraire. Mais pour organiser les déplacements d'un commercial itinérant, un logiciel doit aller plus loin.

Il doit intégrer les données clients, les horaires de travail, les durées de visite et les rendez-vous existants, puis rechercher une organisation cohérente à partir de ces contraintes.

C'est le rôle d'un moteur d'optimisation de tournées : transformer une sélection de clients et des paramètres de planification en une proposition de tournée exploitable.

Avec Sidely, ce moteur est directement intégré au CRM terrain. Les commerciaux peuvent lancer une optimisation depuis leur carte ou leur calendrier, en tenant compte des rendez-vous déjà planifiés.

Pour comprendre les différentes étapes du calcul, les méthodes utilisées et la manière dont Sidely organise les visites, découvrez notre article : Comment fonctionne un moteur d'optimisation de tournées ?

TSP et optimisation de tournées : ce qu'il faut retenir

Le problème du voyageur de commerce est l'un des problèmes les plus connus de l'optimisation mathématique. Il cherche à identifier le circuit le plus court permettant de visiter un ensemble de destinations avant de revenir au point de départ.

Mais dans le quotidien des commerciaux itinérants, la distance ne représente qu'une partie du problème.

Les horaires d'ouverture, les durées de visite, les rendez-vous confirmés, les journées de travail et les priorités commerciales doivent également être pris en compte.

C'est pourquoi les optimiseurs de tournées professionnels s'appuient sur des modèles de planification plus complexes que le TSP classique.

Leur objectif n'est pas seulement de faire parcourir moins de kilomètres aux commerciaux, mais de les aider à organiser des journées réalistes, cohérentes et commercialement utiles.

En intégrant cette logique directement au CRM, Sidely permet aux équipes terrain de passer plus facilement de la sélection des clients à visiter à l'organisation concrète de leurs déplacements.