Logiciel TMS

Optimisation de tournées : que fait l’algorithme et que reste-t-il au planificateur ?

Publié le · 4 min de lecture

Sur cette page
  1. De quel problème parle-t-on ?
  2. Quelles contraintes un TMS doit-il prendre en compte ?
  3. Pourquoi le calcul donne-t-il une bonne solution et pas la meilleure ?
  4. Comment l’optimisation s’intègre-t-elle dans un TMS ?
  5. Quelles questions poser à un éditeur ?
  6. Quand l’optimisation change-t-elle vraiment la donne ?
  7. Sources

L’optimisation de tournées consiste à répartir des arrêts entre des véhicules et à les ordonner pour minimiser un critère, comme la distance ou la durée, sous des contraintes. Un TMS peut le faire par algorithme, mais le résultat est une proposition, calculée selon vos données, que le planificateur doit pouvoir discuter. Cette page explique ce qui se passe derrière le bouton.

De quel problème parle-t-on ?

Les mathématiciens parlent de problème de tournées de véhicules (VRP, Vehicle Routing Problem). Google OR-Tools le décrit comme la recherche de trajets optimaux pour plusieurs véhicules qui visitent un ensemble de lieux. Avec un seul véhicule, il se réduit au problème du voyageur de commerce.

Le mot « optimal » exige une définition. Google OR-Tools explique que, dans son exemple, on minimise la longueur de la plus longue tournée, ce qui correspond à finir toutes les livraisons le plus tôt possible. Minimiser la distance totale sans autre contrainte pousserait à n’utiliser qu’un seul véhicule. Le critère choisi change donc le plan obtenu.

Quelles contraintes un TMS doit-il prendre en compte ?

La documentation de Google OR-Tools et l’article Wikipédia sur le VRP décrivent des variantes qui correspondent à des situations de terrain.

Contrainte Situation concrète Nom de la variante
Capacité des véhicules Charge maximale en poids ou en volume CVRP
Créneaux horaires Livraison chez le client entre deux heures VRPTW
Collecte et livraison Marchandise prise à un endroit, livrée à un autre VRPPD

Wikipédia liste aussi d’autres variantes : retours à vide, plusieurs dépôts, tournées multiples, tournées ouvertes, véhicules électriques. Google OR-Tools précise qu’un problème de capacité peut n’avoir aucune solution, par exemple quand la demande totale dépasse la capacité des véhicules.

Les contraintes de terrain ne s’arrêtent pas là : temps de conduite et de pause des chauffeurs (voir temps de conduite et tachygraphe), compatibilité véhicule et marchandise, accès aux sites. Chacune doit être décrite dans l’outil pour être prise en compte.

Pourquoi le calcul donne-t-il une bonne solution et pas la meilleure ?

Wikipédia indique que, le problème du voyageur de commerce étant NP-difficile, le VRP l’est aussi. En termes simples : il n’existe pas de méthode connue qui garantisse de trouver la solution optimale rapidement quand le nombre d’arrêts grandit.

Selon la même page, les méthodes exactes se heurtent à la difficulté de résoudre à l’optimum de grandes instances, et les métaheuristiques sont préférées dans ce cas. Les heuristiques sont de deux types : classiques (construction rapide d’une solution raisonnable) ou métaheuristiques (exploration de zones prometteuses de l’espace des solutions). Un passage de la page indique que les solveurs commerciaux tendent à utiliser des heuristiques, mais il y est signalé comme non référencé : retenez-le comme une explication plausible, non comme un fait établi.

Conséquence pratique : deux éditeurs peuvent produire des plans différents sur les mêmes données, sans que l’un soit « faux ». Pour comparer, il faut des critères mesurables, pas un score marketing : voir plus bas.

Comment l’optimisation s’intègre-t-elle dans un TMS ?

Aptean (2024) place la planification et l’optimisation dans le TMS : trajets et modes les plus efficaces selon distance, circulation, délais et coûts. Le même article mentionne des modules complémentaires de planification d’itinéraires pour les besoins plus poussés. Deux conséquences :

  • l’optimisation peut être un module à part, avec son propre prix : voir les modèles tarifaires ;
  • elle dépend des données du reste du TMS : adresses, créneaux, capacités, temps de service.

Appvizer (2024) rappelle que la planification se fait selon la distance, la durée, les coûts et les contraintes réglementaires, et que l’affectation des véhicules et des conducteurs en fait partie. Pour le reste des fonctions, voir les fonctions d’un TMS.

Quelles questions poser à un éditeur ?

  1. Quel critère l’outil minimise-t-il ? Distance, durée, coût, nombre de véhicules ? Peut-on le choisir ?
  2. Quelles contraintes sont gérées ? Capacité, créneaux, collecte et livraison, temps de conduite, compétences du chauffeur.
  3. Le calcul est-il manuel assisté ou automatique ? Peut-on déplacer un arrêt à la main, et que devient le reste de la tournée ?
  4. Quelle qualité des données de trajet ? Sources cartographiques, prise en compte de la circulation ou de restrictions pour poids lourds.
  5. Que se passe-t-il en cours de journée ? Nouvel ordre, retard, panne : recalcul total ou partiel ?
  6. Comment juger le résultat ? Proposez à l’éditeur une journée réelle de vos tournées et comparez au plan que vous construisez : distance, durée, respect des créneaux.

Le point 6 est le test le plus fiable : un chiffre d’économie annoncé en brochure ne dit rien de vos contraintes. Aucune des sources lues ici ne publie de gain moyen.

Quand l’optimisation change-t-elle vraiment la donne ?

Elle apporte le plus quand le nombre d’arrêts et de contraintes dépasse ce qu’un planificateur peut tenir en tête : messagerie, distribution, livraisons avec créneaux. Pour de l’affrètement de lots complets, où chaque course est un aller simple, le calcul de tournée compte peu : le sujet devient le choix du transporteur, côté commissionnaire ou chargeur.

Dans tous les cas, gardez la possibilité de corriger. Un plan théoriquement optimal et inapplicable par les chauffeurs reste un plan inutile.

Sources

Questions fréquentes

Un TMS calcule-t-il la meilleure tournée possible ?

Il calcule en général une bonne solution, pas forcément la meilleure. Wikipédia (en anglais) indique que le problème est NP-difficile et que les grandes instances sont traitées par des méthodes approchées.

Que veut-on minimiser dans une tournée ?

Cela se choisit : distance totale, durée, coût, ou durée de la plus longue tournée. Google OR-Tools note que minimiser la distance totale sans autre contrainte ramène à un seul véhicule ; le critère change donc le résultat.

Le module d’optimisation est-il toujours inclus dans le TMS ?

Pas toujours. Aptean mentionne des modules complémentaires de planification d’itinéraires pour les besoins plus poussés. Vérifiez ce qui est dans l’offre de base et ce qui est facturé en supplément.

L’optimisation remplace-t-elle le planificateur ?

Non. Elle propose un plan à partir des données et des règles saisies. Le planificateur connaît les cas que ces données ne contiennent pas, et doit pouvoir corriger la proposition.