Comprendre l’optimisation de tournées

Comment fonctionne un algorithme d’optimisation de tournées ?

Mis à jour le

En bref : Un optimiseur résout un problème mathématique très complexe : répartir des arrêts entre véhicules en respectant capacités, horaires et contraintes. Il utilise des méthodes approchées et heuristiques. Sur le terrain, la qualité des données compte autant que l’algorithme.

Quand un logiciel d’optimisation de tournées produit un résultat en quelques secondes sur cent points de livraison et dix véhicules, il ne devine pas. Il applique des méthodes mathématiques précises pour explorer un espace de solutions immense et en extraire une qui soit très bonne, sinon la meilleure possible. Comprendre comment ces méthodes fonctionnent n’est pas un exercice académique : c’est ce qui permet de comprendre pourquoi deux outils produisent des résultats différents sur les mêmes données, et ce qui permet de poser les bonnes questions lors d’une évaluation.

Le problème à résoudre

Derrière tout optimiseur de tournées se cache un problème mathématique connu sous le nom de VRP, pour Vehicle Routing Problem. La formulation est simple à énoncer : étant donné un ensemble de points à visiter, une flotte de véhicules partant d’un ou plusieurs dépôts, et un ensemble de contraintes à respecter, comment organiser les tournées pour minimiser un critère donné, généralement le coût ou le kilométrage total ?

Ce problème appartient à une catégorie que les mathématiciens qualifient de NP-difficile. Ce terme technique a une implication concrète : le temps de calcul nécessaire pour trouver la solution exactement optimale croît de façon explosive avec la taille du problème. Avec dix points de livraison et un seul véhicule, il existe déjà plus de trois millions d’ordres de visite possibles. Avec cinquante points, le nombre de combinaisons dépasse ce qu’aucun ordinateur ne peut explorer exhaustivement dans un délai opérationnel.

C’est pourquoi les algorithmes d’optimisation ne cherchent pas la solution parfaite. Ils cherchent une très bonne solution dans un temps acceptable pour l’exploitation, qu’il s’agisse de quelques secondes pour un recalcul dynamique en cours de journée ou de quelques minutes pour la planification du lendemain.

Les grandes familles d’algorithmes

Les algorithmes exacts garantissent l’optimalité de la solution trouvée. Ils explorent systématiquement l’espace des solutions en éliminant intelligemment les combinaisons impossibles ou sous-optimales. Leur limite est le temps de calcul : au-delà d’une vingtaine de points, ils deviennent trop lents pour un usage opérationnel. Les éditeurs les utilisent principalement pour valider la qualité de leurs autres méthodes sur des instances de petite taille, ou pour des cas très contraints où l’optimalité est impérative.

Les heuristiques constructives bâtissent une solution de toutes pièces en appliquant des règles pratiques : partir du point le plus proche du dépôt, insérer à chaque étape le point dont l’ajout coûte le moins cher, regrouper les points géographiquement proches dans la même tournée. Ces méthodes sont rapides et produisent une solution réalisable en un temps très court. Leur faiblesse est qu’elles se contentent d’une bonne première solution sans chercher à l’améliorer. Elles servent généralement de point de départ pour des méthodes plus sophistiquées.

Les méthodes d’amélioration locale partent d’une solution existante et l’améliorent en appliquant des modifications élémentaires : échanger deux points entre deux tournées, inverser l’ordre de visite d’un sous-ensemble de points, déplacer un point d’une tournée vers une autre. À chaque étape, la modification n’est retenue que si elle améliore la solution. Ces méthodes convergent rapidement vers un optimum local, mais peuvent se retrouver coincées dans une configuration satisfaisante qui n’est pas la meilleure globalement.

Les métaheuristiques sont aujourd’hui le cœur des optimiseurs commerciaux sérieux. Elles combinent des mécanismes d’exploration et d’exploitation pour éviter les optimums locaux et continuer à chercher des solutions meilleures. La recherche tabou maintient une liste des dernières modifications effectuées pour éviter de revenir en arrière. Le recuit simulé accepte parfois des dégradations temporaires de la solution pour s’échapper d’un optimum local. Les algorithmes évolutionnaires maintiennent une population de solutions qui s’échangent des caractéristiques et évoluent vers de meilleures configurations. Ces méthodes produisent des résultats nettement supérieurs aux heuristiques simples, au prix d’un temps de calcul plus long.

En pratique, les meilleurs optimiseurs commerciaux combinent plusieurs de ces méthodes : une heuristique constructive pour générer rapidement une solution initiale, suivie d’une métaheuristique pour l’améliorer de façon itérative jusqu’à ce que le temps de calcul alloué soit écoulé. Plus on leur donne de temps, meilleure est la solution produite.

Le rôle croissant de l’intelligence artificielle

L’intelligence artificielle et l’apprentissage automatique commencent à transformer ce que les algorithmes d’optimisation peuvent faire, au-delà des méthodes classiques.

Le premier apport concret est l’amélioration de la qualité des données d’entrée. Un algorithme ne peut pas produire de bonnes tournées avec de mauvaises données. Les modèles d’apprentissage permettent d’affiner les estimations de temps de trajet en fonction de l’heure, du jour, de la météo et de l’historique réel des conducteurs. Ils permettent aussi d’estimer les durées de service réelles à chaque point, qui varient selon le client, le conducteur et le type de livraison, là où les optimiseurs traditionnels utilisent des valeurs fixes.

Le deuxième apport est l’adaptation au contexte. Des modèles entraînés sur l’historique des tournées peuvent anticiper les aléas récurrents : tel client est systématiquement indisponible le vendredi matin, tel accès est congestionné entre 8h et 9h sans exception. L’algorithme intègre ces patterns pour produire des tournées plus robustes que celles calculées sur des données purement théoriques.

Le troisième apport concerne l’optimisation à grande échelle. Les approches par apprentissage par renforcement permettent d’apprendre directement des politiques de décision efficaces pour des problèmes très complexes, là où les métaheuristiques classiques peinent à passer à l’échelle. C’est un domaine de recherche active dont les applications commerciales se développent progressivement.

Ces évolutions ne remplacent pas les algorithmes classiques : elles les augmentent. L’IA est un levier d’amélioration incrémentale sur des flottes qui accumulent des données d’exploitation, pas une révolution qui rend obsolètes les méthodes éprouvées.

Ce que l’algorithme ne peut pas compenser

Un algorithme d’optimisation est aussi bon que les données qu’on lui fournit. C’est une évidence que les projets d’optimisation de tournées rappellent systématiquement lors du déploiement.

La qualité du géocodage est le premier point de défaillance. Si les adresses sont mal converties en coordonnées GPS, l’algorithme optimise des trajets vers de mauvais points. Le résultat est des tournées théoriquement optimales mais inexploitables sur le terrain.

La fiabilité des temps de trajet conditionne le respect des fenêtres horaires. Un algorithme qui sous-estime systématiquement les temps de trajet en zone urbaine dense produira des tournées irréalisables, quelle que soit la sophistication de ses méthodes d’optimisation.

La complétude des contraintes est souvent sous-estimée lors du paramétrage. Un algorithme optimise selon les contraintes qu’on lui communique. Une contrainte non renseignée, qu’il s’agisse d’une fenêtre horaire, d’une restriction d’accès ou d’une habilitation conducteur, sera ignorée. Les conducteurs devront retravailler manuellement les tournées produites, ce qui annule une grande partie du gain attendu.

La qualité du paramétrage initial, enfin, détermine dans quelle mesure les résultats de l’algorithme reflètent la réalité opérationnelle. Un outil mal paramétré produira des résultats régulièrement rejetés par les conducteurs, signe le plus visible d’un projet d’optimisation qui ne tient pas ses promesses.

Ce qui différencie vraiment les optimiseurs sur le terrain

Quand deux optimiseurs sont mis en compétition sur les mêmes données, les écarts de performance algorithmique sont réels mais rarement décisifs à eux seuls. Ce qui fait la différence dans un projet réel, c’est la combinaison de plusieurs facteurs.

La capacité à gérer nativement les contraintes spécifiques à votre activité sans développement coûteux est souvent plus importante que la sophistication de l’algorithme. Un outil dont l’algorithme est légèrement moins performant mais qui gère parfaitement vos contraintes métier produira de meilleurs résultats sur le terrain qu’un outil algorithmiquement supérieur mais qui approxime vos contraintes.

La vitesse de calcul est un critère opérationnel concret. Pour la planification à J-1, quelques minutes de calcul sont acceptables et permettent à l’algorithme d’explorer davantage de solutions. Pour le recalcul dynamique en cours de journée, le résultat doit être disponible en quelques secondes. Ces deux modes d’usage ne font pas appel aux mêmes méthodes et tous les outils ne les couvrent pas avec le même niveau de qualité.

La robustesse des résultats, c’est-à-dire leur capacité à rester exploitables malgré les aléas du terrain, est une qualité que peu d’éditeurs mettent en avant mais que les opérationnels ressentent au quotidien. Une tournée calculée au plus juste qui s’effondre à la moindre déviation vaut moins qu’une tournée légèrement sous-optimale mais conçue pour absorber les imprévus.

La meilleure façon de comparer deux optimiseurs n’est pas de lire leurs fiches techniques, c’est de les faire tourner sur un mois de vos données réelles avec vos contraintes réelles, et de mesurer les résultats avec vos propres indicateurs. Tout le reste est de la communication commerciale.

Vous voulez identifier l’optimiseur de tournées dont l’algorithme et les fonctionnalités correspondent à votre profil opérationnel réel ? Le questionnaire QuelleTournee.fr analyse votre contexte et vous propose une sélection personnalisée.

Trouver mon optimiseur de tournées →