Le problème du voyageur de commerce expliqué aux dispatchers

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

Un chauffeur doit livrer 20 adresses puis rentrer au dépôt. Dans quel ordre les visiter pour parcourir le moins de kilomètres ? Cette question porte un nom : le problème du voyageur de commerce (TSP, Travelling Salesman Problem). Dès qu'on ajoute plusieurs véhicules, des capacités de charge et des horaires, il devient le problème de tournées de véhicules (VRP, Vehicle Routing Problem) — le cœur mathématique de tout logiciel de dispatch.

Pourquoi c'est plus difficile qu'il n'y paraît

Le VRP est un problème NP-difficile : il se ramène au voyageur de commerce, pour lequel aucun algorithme exact rapide n'est connu à grande échelle. La raison est combinatoire. Pour une dizaine d'arrêts, il existe déjà des centaines de milliers d'ordres possibles ; pour vingt arrêts, le nombre de combinaisons dépasse l'entendement. Tester toutes les possibilités — la « force brute » — devient impossible au-delà d'une poignée de points, même pour un ordinateur.

C'est pourquoi un planificateur humain, aussi expérimenté soit-il, ne peut pas optimiser mentalement 40 livraisons sous contraintes horaires. Le cerveau trouve une solution « correcte », rarement la meilleure.

La solution : les heuristiques

Puisqu'on ne peut pas garantir l'optimum, on cherche une très bonne solution, très vite. C'est le rôle des heuristiques. La plus célèbre, 2-opt, a été proposée par Croes en 1958 : elle prend un itinéraire, retire deux segments et les reconnecte autrement ; si la distance totale diminue, on conserve le changement, puis on recommence jusqu'à ne plus pouvoir améliorer. Combinée à d'autres techniques (recherche locale, recuit simulé, algorithmes génétiques), elle produit des tournées proches de l'optimal en quelques secondes.

Les contraintes du monde réel

Un bon moteur ne minimise pas que la distance. Il intègre la capacité des véhicules, les fenêtres de livraison, les temps de service à chaque arrêt, les compétences requises et, de plus en plus, le trafic en temps réel. Chaque contrainte ajoutée alourdit le calcul — d'où l'intérêt d'un outil dédié plutôt que d'une carte et d'un tableur.

Ce que ça change concrètement

L'enjeu est financier. Selon les analyses sectorielles du marché de la gestion de flotte, l'optimisation d'itinéraires, la réduction des temps morts et le suivi de conduite permettent des réductions de carburant de l'ordre de 10 à 30 %. Pour une PME de quelques véhicules, c'est un poste de coût entier que l'on rationalise.

Laissez l'algorithme calculer vos tournées. Essayez dropfleet gratuitement 14 jours — sans carte bancaire, prêt en 5 minutes.