Optimisation de tournées : la vraie difficulté est dans la modélisation, pas dans l’algorithme
- 9 septembre 2026
- 9 mins
Les projets d'optimisation de tournées échouent rarement à cause de l'algorithme. Entre une règle métier et un plan de tournées optimisé se trouvent deux autres couches : la capacité du langage de modélisation à exprimer cette règle, et le fait que quelqu'un l'ait correctement formulée.
La première est la distance de modélisation, l'écart entre la façon dont une règle existe dans une opération et la façon dont un formalisme permet de la retranscrire. C'est un problème d'ingénierie, et il est quantifiable : 61 primitives abstraites produisant 149 variantes sectorielles dans notre bibliothèque fin août 2026. La seconde est humaine. Elle ne donne aucun signal quand elle échoue, elle est à l'origine de la plupart des difficultés rencontrées sur nos projets clients ces dix dernières années, et elle reste aujourd'hui ce qui sépare l'optimisation de tournées d'un produit en libre-service.
Une fenêtre horaire de livraison est une contrainte métier. Dans presque toutes les API de tournées, c'est aussi un objet natif : on fixe un début, une fin, et c'est terminé. Aucun effort de modélisation.
Un seuil de chiffre d'affaires quotidien minimum en dessous duquel un sous-traitant refuse une tournée est aussi une contrainte métier. Ce n'est un objet natif nulle part. Il faut la construire à partir de ce que le formalisme propose, à condition qu'il propose suffisamment d'outils, et à condition que quelqu'un ait identifié que cette règle existait.
Les deux contraignent le plan de la même manière. L'écart entre elles est le sujet de cet article, et il n'a rien à voir avec l'algorithme.
L'algorithme est la couche que tout le monde benchmarke, et celle qui échoue le plus rarement
Les solveurs sont comparés sur la vitesse, sur l'écart à l'optimum (la distance entre une solution et le meilleur résultat mathématique possible), et sur le nombre d'arrêts absorbés. Ces comparaisons sont légitimes, et nous les menons nous-mêmes sur notre propre moteur. Mais ce n'est pas là qu'il faut chercher pourquoi un projet a échoué.
Le problème algorithmique est difficile, et il est bien traité. Le problème de tournées de véhicules est étudié depuis soixante ans, les métaheuristiques (algorithmes de recherche généralistes) fonctionnent, et un solveur commercial compétent surpasse largement des planificateurs expérimentés en distance parcourue ou en nombre de véhicules utilisés. Nous avons nous-mêmes défendu cet argument. Ce succès a créé un angle mort : des gains aussi importants ont donné l'impression que l'algorithme était tout le produit.
En dix ans, nous n'avons jamais vu un projet échouer parce que le solveur était trop lent. Nous en avons vu beaucoup échouer parce que le plan décrivait une opération qui n'existait pas.
Entre une règle métier et un solveur se trouvent deux couches supplémentaires
Passer d'une règle qui existe dans une opération à un plan qui la respecte demande trois choses. Une seule est algorithmique.
Le secteur évalue la troisième ligne. Les projets échouent sur les deux premières.
Les deux couches supérieures sont souvent confondues en une seule, et l'exemple de la fenêtre horaire montre pourquoi : quand un formalisme dispose d'un objet natif pour une règle, l'exprimer et l'exprimer correctement se produisent dans le même geste. Elles se dissocient dès que la règle n'a pas d'objet natif.
Elles échouent aussi différemment. Une limite d'expressivité est bruyante : on cherche un moyen de formuler sa règle, on n'en trouve pas, et on le sait en une heure. Une erreur de formulation est silencieuse : on formule la règle facilement, on la formule mal, et rien ne le signale.
Un troisième cas se situe entre les deux, et c'est celui qui induit le plus en erreur. La primitive qui porte la règle existe, mais elle est suffisamment abstraite pour que le lien ne soit pas évident, et le développeur en conclut que l'API ne peut pas le faire. C'est un échec de traduction déguisé en limite d'expressivité. Il se termine généralement par un contournement construit en dehors du modèle, là où le solveur ne peut ni le voir ni l'optimiser.
La distance de modélisation : pourquoi une fenêtre horaire est gratuite et un seuil de sous-traitance ne l'est pas
La distance de modélisation est l'écart entre la façon dont une règle existe dans une opération et la façon dont le formalisme permet de la retranscrire. C'est une propriété du formalisme, pas de la règle. Une même contrainte n'a pas la même distance de modélisation selon l'outil utilisé.
À distance nulle, la règle dispose d'un objet natif. Une fenêtre horaire dans une API de tournées moderne : deux champs, rien à traduire.
À distance modérée, la règle n'a pas d'objet natif, mais le formalisme propose des constructions abstraites capables de la porter. C'est là que se trouvent la plupart des contraintes réelles, et le seuil de sous-traitance en fait partie. Aucune API de tournées sur le marché ne l'expose comme un objet, la nôtre y compris, donc il faut l'assembler à partir de primitives abstraites. Nous avons testé cette règle sur onze API. Trois pouvaient l'exprimer, chacune à sa manière et avec son propre coût de traduction. Pour les huit autres, nous n'avons trouvé aucun moyen de la formuler. Il en existe peut-être un que nous avons manqué, ce qui correspondrait exactement au troisième cas évoqué plus haut.
À distance maximale, le formalisme est un langage mathématique général, et chaque contrainte devient un projet d'ingénierie à part entière. Écrire un problème de tournées de véhicules riche directement en programmation en nombres entiers mixtes en est l'exemple de référence[5]. Chaque règle coûte des jours de travail, et la littérature documente depuis deux décennies à quel point ces formulations restent éloignées des opérations qu'elles sont censées décrire[3][4].
Réduire la distance de modélisation est une décision produit. Elle détermine la quantité de travail qui retombe sur les développeurs.
61 primitives, 149 variantes sectorielles : ce que coûte la construction de l'expressivité
Réduire la distance de modélisation revient à transformer des contraintes qui seraient autrement des projets d'ingénierie en constructions natives. C'est un problème de solveur, et c'est le défi d'ingénierie central de tout moteur d'optimisation, quel que soit son domaine ou sa technique de résolution[5]. Ajouter de l'expressivité n'est pas la partie difficile. L'ajouter sans dégrader la performance du solveur l'est, car chaque construction rendue native est une construction que le moteur doit gérer efficacement pendant la recherche. C'est probablement pour cela que huit des onze API testées ne peuvent pas exprimer le seuil de sous-traitance. Pas un oubli de leur part, mais un arbitrage assumé. Un formalisme capable de porter de nombreuses règles de ce type sans ralentir en dit long sur l'architecture qui le sous-tend.
Fin août 2026, la bibliothèque de Kardinal compte 61 primitives abstraites réparties en 11 catégories, produisant 149 contraintes concrètes à travers les 7 industries sur lesquelles nous travaillons. Ce sont celles que nous avons rencontrées. C'est un inventaire de ce que dix années de projets ont fait émerger, pas une prétention à définir les limites du problème.
Cette duplication est volontaire : un même formalisme porte des significations opérationnelles différentes selon le secteur. Maximiser l'affectation préférentielle entre arrêts et ressources signifie associer un chauffeur à sa zone d'habitation dans la livraison de colis, et associer un technicien junior à des interventions simples sur site. Même mathématique, conversation différente, façons différentes de se tromper.
C'est pourquoi une nouvelle règle métier ne signifie que rarement une nouvelle primitive. Les contraintes jamais rencontrées auparavant restent minoritaires, et quand elles apparaissent, la plupart s'avèrent exprimables avec des primitives déjà existantes. C'est aussi le cas le plus clair où les deux couches se dissocient : la règle était nouvelle, l'exprimer était facile, mais identifier quelle primitive la portait ne l'était pas.
L'expressivité est aussi la seule couche qu'un observateur extérieur peut comparer, en s'appuyant uniquement sur la documentation publique. Nous publions cette comparaison depuis 2024, et nous ne connaissons aucun équivalent ailleurs. Notre benchmark 2026 de onze API de tournées les évalue face à une liste de contraintes que nous avons reconstruite de zéro. Nous ne sommes pas une partie neutre dans cet exercice, c'est pourquoi la liste de contraintes et la méthode de notation sont publiées plutôt que simplement résumées.
Un formalisme parfait ne rend pas le modèle correct pour autant
Une conclusion est tentante ici : continuer à pousser l'expressivité jusqu'à ce que le problème de modélisation disparaisse. Donner un objet natif à chaque règle, et il n'y aurait plus rien à traduire.
L'exemple de la fenêtre horaire montre pourquoi ce n'est pas le cas. L'objet est natif, la distance de modélisation est nulle, et pourtant toutes ces questions restent ouvertes. La fenêtre est-elle stricte ou pénalisée ? S'applique-t-elle à l'heure d'arrivée ou à la fin du service ? Un dépassement de cinq minutes est-il un échec ou une simple dégradation ? La règle s'applique-t-elle encore si le client est absent ? Chaque réponse change le plan. Aucune ne devient plus simple grâce à un meilleur objet.
L'expressivité réduit le coût de la traduction. Elle réduit rarement le coût de la spécification.
La recherche opérationnelle a nommé cet écueil bien avant l'existence des logiciels de tournées : l'erreur de troisième espèce décrite par Kimball en 1957, qui consiste à donner la bonne réponse au mauvais problème[1]. La façon dont un problème est posé au départ compte parmi les déterminants les plus forts de la solution à laquelle on aboutit[2].
Notre cas du sous-traitant en est un exemple exact. Un chargeur paie sa flotte interne au kilomètre et ses sous-traitants à la tâche. Optimiser ce modèle de coût, et le solveur attribue rationnellement les tournées denses à la flotte interne, et les tournées légères aux sous-traitants. Le plan est optimal, et inapplicable, car un sous-traitant continue de payer un chauffeur pour une journée complète et refuse toute tournée en dessous d'un certain chiffre d'affaires quotidien. Ce seuil n'était écrit nulle part. Les planificateurs l'appliquaient depuis des années sans jamais l'avoir formalisé. Aucune quantité d'expressivité n'y aurait changé quoi que ce soit, car personne n'avait posé la question.
Qui peut réellement faire ce travail, et pourquoi cela ne passe pas à l'échelle
La formulation exige de tenir deux choses en tête simultanément : comment l'opération fonctionne réellement, et ce que le formalisme fera d'une formulation donnée. Un même besoin peut être modélisé de plusieurs façons, avec des effets de bord différents, et savoir laquelle produit quel comportement est tout l'enjeu du métier.
Cette personne se trouve à l'un de ces deux endroits. Chez le client, un profil opérationnel doté d'un tempérament inhabituellement analytique, suffisamment rare pour que nous ne bâtissions pas nos projets sur cette hypothèse. Ou chez le prestataire.
C'est ce second cas que nous avons construit. Nos ingénieurs solutions font ce travail, et c'est grâce à eux que nos projets aboutissent. Ils constituent aussi un goulot d'étranglement que le recrutement ne résout pas : le profil est rare, et chaque projet mobilise l'un d'eux du premier atelier jusqu'à la mise en production.
Viable pour des projets grands comptes, impossible pour une API en libre-service.
Cela laisse cette catégorie avec une question ouverte, et ce n'est pas une question algorithmique. L'expertise qui transforme une opération en une formulation correcte existe, elle n'est écrite nulle part sous une forme qu'une machine pourrait lire, et aujourd'hui elle arrive sur chaque projet sur deux jambes. Savoir si elle peut être encodée, et si un agent peut l'appliquer assez bien pour s'y substituer, fait l'objet du prochain article : les agents IA peuvent appeler votre API d'optimisation. Voici comment nous les avons amenés à modéliser le problème.
Questions fréquentes
Non, ce sont deux échecs distincts. Le GIGO concerne l'instance : les adresses, les poids et les durées de service qui alimentent une exécution donnée. Des données erronées ruinent un modèle correct, et aucun travail de modélisation ne peut y remédier. Une erreur de formulation est le cas inverse : chaque chiffre est juste, mais le modèle décrit une opération différente de la vôtre. On peut avoir l'un sans l'autre, et chacun demande un travail différent.
Le volume n'est pas le bon axe d'analyse. Une flotte de huit véhicules soumise à des règles de certification, des fenêtres d'accès sur site et des contraintes de préséance entre tâches porte plus de risque de modélisation que quatre cents véhicules effectuant une livraison résidentielle uniforme. Le signal à surveiller, c'est le nombre de règles qui contraignent qui peut faire quoi, quand, et dans quel ordre.
Cela arrive régulièrement, et c'est généralement moins problématique qu'il n'y paraît. Une règle que personne n'a encore formulée correspond rarement à un formalisme que personne n'a encore construit, si bien que la plupart des contraintes inédites s'avèrent exprimables avec des primitives déjà existantes. Les cas véritablement nouveaux sont la partie la plus intéressante de ce travail, et ils restent minoritaires.
Pour les contraintes à faible distance de modélisation, oui, et cela couvre plus de terrain qu'on ne le pense généralement. La difficulté commence là où une règle concrète doit être portée par une construction abstraite, car choisir entre deux encodages valides suppose de savoir ce que chacun produit sur le plan. Cette connaissance peut être documentée. Elle ne figure aujourd'hui dans aucune documentation d'API que nous connaissions, y compris la nôtre jusqu'à récemment. Voir les guides de modélisation que nous publions.