L'optimisation de tournées consiste à ordonner les arrêts et à affecter les véhicules pour qu'une flotte termine sa journée en moins de temps, de distance ou de coût. C'est la différence entre un livreur qui finit à 16h et un autre qui finit à 19h avec le même fourgon et les mêmes arrêts. Sous chaque bouton "tournée optimisée" d'une application logistique se trouve un solveur qui vient de mâcher des millions d'ordonnancements possibles pour en choisir un.
Ce guide explique ce qu'est réellement l'optimisation de tournées, comment les solveurs l'abordent, où elle apparaît dans le monde réel et quelles contraintes et pièges séparent une démo de la production.
Ce qu'est vraiment l'optimisation de tournées
En informatique, l'optimisation de tournées vit à l'intérieur de deux problèmes classiques. Le problème du voyageur de commerce (TSP) demande : étant donné une liste de villes et les distances entre elles, quel est le plus court itinéraire qui visite chaque ville exactement une fois et revient au point de départ ? C'est un problème mono-véhicule. Le problème de tournées de véhicules (VRP) le généralise à une flotte : étant donné un dépôt, un ensemble de clients et plusieurs véhicules, comment répartir les clients entre les véhicules, et dans quel ordre chaque véhicule doit-il les visiter ?
Les deux problèmes sont NP-difficiles. Le nombre d'ordonnancements possibles croît factoriellement avec le nombre d'arrêts. Vingt arrêts produisent déjà plus de 10 puissance 18 itinéraires possibles. Aucun algorithme exact ne peut explorer cet espace en temps réel. L'optimisation, en production, ne consiste donc pas à trouver la réponse parfaite. Il s'agit de trouver une très bonne réponse assez vite pour pouvoir agir.
Comment les solveurs abordent le problème
Comme l'espace de recherche est énorme, les vrais solveurs combinent plusieurs techniques.
Pour les petits problèmes (moins d'environ 15 arrêts), des méthodes exactes comme le branch-and-bound ou la programmation linéaire en nombres entiers peuvent renvoyer une solution prouvée optimale en quelques secondes. Au-delà de cette échelle, les méthodes exactes cessent d'être pratiques et le domaine bascule sur les heuristiques.
Un pipeline typique commence par une heuristique constructive comme le plus proche voisin ou l'algorithme des économies de Clarke-Wright pour produire un itinéraire initial. Cet itinéraire est ensuite passé à une métaheuristique, qui échange itérativement des arrêts, inverse des sous-tournées ou déplace des arrêts entre véhicules pour améliorer l'objectif. Le recuit simulé, la recherche tabou, la recherche à grand voisinage et les algorithmes génétiques sont les choix les plus courants. Ils ont tous la même forme : essayer un changement, décider de l'accepter ou non, répéter pendant un budget temps fixe.
L'autre entrée critique est la matrice de distances : une table précalculée de temps de trajet et de distance entre chaque paire d'arrêts. L'optimiseur interroge la matrice des millions de fois pendant sa recherche, donc la matrice est construite une fois en amont par un moteur de routage et conservée en mémoire pendant que le solveur tourne.
Où apparaît l'optimisation de tournées
L'optimisation de tournées alimente discrètement une longue liste d'activités opérationnelles.
- Livraison du dernier kilomètre : transporteurs de colis, livraison alimentaire et fulfillment e-commerce séquencent tous des dizaines à des centaines d'arrêts par fourgon par jour
- Service terrain : techniciens CVC, installateurs télécoms et auxiliaires de santé à domicile visitent des clients dans une région avec des fenêtres de rendez-vous et des exigences de compétences
- Main-d'œuvre mobile : équipes de service public, releveurs de compteurs et inspecteurs couvrant des territoires avec des types de tâches variés
- Livraison de repas : agrégateurs de restaurants regroupant plusieurs commandes en une seule course quand la géographie le permet
- Collecte des déchets : camions municipaux exécutant des tournées hebdomadaires fixes où de petits réordonnancements économisent du carburant réel
- Commerciaux : planification de territoire où un commercial visite 8 à 12 comptes par jour et où l'ordre compte pour le temps de trajet et la densité de rendez-vous
Dans chaque cas, l'utilisateur voit une liste d'arrêts dans le bon ordre. Le travail se fait dans l'optimiseur derrière.
Les contraintes qui comptent
Un solveur qui ne minimise que la distance est un jouet. Le routage de production se définit par ses contraintes.
- Capacité des véhicules : chaque fourgon a une limite de poids, de volume ou de palettes que les arrêts affectés ne doivent pas dépasser
- Fenêtres horaires : les clients attendent une livraison entre, disons, 9h et 11h, et arriver à 11h05 est un échec
- Services des chauffeurs : heures de travail maximales, pauses obligatoires, départ et arrivée à des dépôts spécifiques
- Correspondance compétence ou véhicule : l'installation d'un frigo nécessite une équipe de deux personnes, une livraison sous chaîne du froid nécessite un fourgon réfrigéré
- Multi-dépôts : les grandes flottes partent de plusieurs entrepôts et le solveur décide quel dépôt prend en charge quel arrêt
- Retour au dépôt : certaines tournées sont ouvertes (le chauffeur termine chez lui), d'autres sont fermées (le chauffeur revient au dépôt)
Chaque contrainte rétrécit l'ensemble réalisable des tournées et pousse le solveur vers des solutions qui paraissent légèrement moins bonnes sur le papier mais qui sont réellement livrables.
Pièges en production
L'optimisation de tournées est une catégorie où la démo marche toujours et où le déploiement coince souvent.
Optimiser le mauvais objectif. Minimiser la distance est le réflexe par défaut, mais pour beaucoup de flottes, le chiffre d'affaires ou le respect du niveau de service comptent davantage que les kilomètres économisés. Une tournée qui dépose un colis supplémentaire au prix de 2 km est généralement gagnante.
Temps fluides contre temps avec trafic. Une matrice construite à partir de vitesses routières brutes vous dira qu'une tournée prend 4 heures alors qu'aux heures de pointe elle en prend 6. Utilisez un moteur de routage qui expose des temps de trajet tenant compte du trafic pour l'heure de la journée à laquelle la tournée tournera.
Pas de replanification en temps réel. Les plans dérivent dès qu'un chauffeur tombe sur un trafic inattendu, qu'un client annule ou qu'un nouvel arrêt arrive. Les équipes opérationnelles ont besoin d'un moyen de réoptimiser les arrêts restants en milieu de journée sans jeter le travail du matin.
Plan figé qui se périme. Une tournée fixe hebdomadaire paraissait optimale en janvier et est désormais 20 % moins bonne parce que des clients ont déménagé, les volumes ont changé et un sens unique est apparu. Relancez l'optimisation périodiquement et comparez le nouveau plan au plan en cours avant d'imposer un changement aux chauffeurs.
L'optimisation de tournées dans MapAtlas
L'API Optimize Route de MapAtlas résout les problèmes de routage mono-véhicule et de flotte avec les contraintes dont les équipes opérationnelles ont vraiment besoin : capacité, fenêtres horaires, services, compétences et configurations multi-dépôts. Elle renvoie un plan séquencé par véhicule avec les heures d'arrivée et de départ prévues pour chaque arrêt.
Elle s'associe naturellement à deux autres endpoints de la stack MapAtlas. L'API Distance Matrix construit la table de temps de trajet que le solveur consomme, avec des temps tenant compte du trafic pour que les plans tiennent aux heures de pointe. L'API Directions trace les vrais chemins routiers virage par virage entre arrêts consécutifs une fois l'ordre fixé, pour qu'une appli chauffeur puisse afficher une vraie polyligne plutôt qu'une ligne droite.
L'optimisation de tournées n'aura rien de glamour dans un slide deck. Ce sont un solveur, une matrice et une liste de contraintes. Mais c'est la couche qui décide si une flotte termine sa journée à l'heure et dans le budget, et bien la calibrer, c'est ce qui sépare une fonctionnalité de routage qui sort d'une autre qui se fait discrètement éteindre.
Questions fréquemment posées
Qu'est-ce que l'optimisation de tournées ?
L'optimisation de tournées est le processus qui décide du meilleur ordre pour visiter un ensemble d'arrêts et, lorsque plusieurs véhicules sont impliqués, quel véhicule doit prendre quels arrêts. L'objectif est de minimiser un objectif comme le temps de trajet total, la distance, le carburant ou le coût, tout en respectant des contraintes du monde réel comme la capacité des véhicules, les services des chauffeurs et les fenêtres horaires des clients. En informatique, cela relève de deux problèmes classiques : le problème du voyageur de commerce (TSP) pour un seul véhicule et le problème de tournées de véhicules (VRP) pour une flotte.
Quelle est la différence entre planification et optimisation de tournées ?
La planification de tournées répond à 'comment aller de A à B'. Elle renvoie un seul chemin entre deux points, généralement avec des indications virage par virage. L'optimisation de tournées répond à 'dans quel ordre dois-je visiter ces 80 arrêts avec ces 6 fourgons, et lequel prend quel arrêt'. L'optimisation se situe une couche au-dessus de la planification : elle décide de la séquence et de l'affectation, puis appelle un moteur de routage pour tracer le vrai chemin routier entre chaque paire d'arrêts.
Quels algorithmes sont utilisés pour l'optimisation de tournées ?
Pour les petits problèmes (moins d'environ 15 arrêts), des méthodes exactes comme le branch-and-bound ou la programmation linéaire en nombres entiers peuvent trouver une solution prouvée optimale. Au-delà, l'espace de recherche explose et les systèmes de production utilisent des heuristiques et des métaheuristiques : algorithmes du plus proche voisin et des économies pour une solution initiale, puis recherche locale, recuit simulé, recherche tabou ou algorithmes génétiques pour l'améliorer. La plupart des solveurs commerciaux combinent plusieurs de ces techniques et tournent pendant un budget temps fixe plutôt que jusqu'à l'optimalité prouvée.
De quoi a besoin une API d'optimisation de tournées en entrée ?
Au minimum : la liste des arrêts avec leurs coordonnées, les véhicules avec leurs lieux de départ et d'arrivée, et une matrice de distances ou de temps entre chaque paire d'arrêts. En pratique, vous fournissez aussi les capacités des véhicules, les fenêtres horaires des clients, les durées de service à chaque arrêt, les heures de service des chauffeurs, les compétences ou types de véhicules requis par arrêt, et les emplacements des dépôts. La matrice est l'entrée la plus lourde et est généralement produite par une API de matrice de distances séparée avant que l'optimiseur ne tourne.
