Comment fonctionne un algorithme de scoring en optimisation de tournées

Publié le 27 mai 2026 • Lecture : 8 min read

Dans un moteur d’optimisation de tournées, le problème n’est pas uniquement de déterminer si une insertion est faisable. Le véritable enjeu consiste à déterminer si cette insertion constitue une bonne décision opérationnelle.

Cette distinction est fondamentale : dans les systèmes réels, plusieurs insertions peuvent être techniquement valides tout en produisant des comportements très différents. Certaines dégradent fortement la robustesse du planning. D’autres augmentent les temps d’attente ou verrouillent progressivement la capacité future de réorganisation des tournées. Autrement dit, la faisabilité seule ne suffit pas.

C’est précisément pour résoudre ce problème que les moteurs modernes d’optimisation utilisent des mécanismes de scoring multicritère. Chez AntsRoute, le scoring joue un rôle central dans l’évaluation et la hiérarchisation des insertions candidates au sein d’un planning déjà construit.

Au programme dans cet article :

• Pourquoi le scoring est devenu central dans les moteurs d’optimisation
• Toutes les insertions faisables ne se valent pas
• Le rôle du coût marginal dans l’évaluation des tournées
• Pourquoi la qualité temporelle change complètement le scoring
• La cohérence géographique comme critère de robustesse
• Hard constraints vs soft constraints : deux logiques différentes
• Préserver la capacité future de réorganisation
• Comment le scoring guide l’exploration du moteur
• Pourquoi un score doit rester compréhensible et explicable

Le scoring est un mécanisme d’arbitrage

Dans les approches simplifiées, une insertion est souvent évaluée selon un critère unique, comme la distance supplémentaire, le temps de trajet ou le coût immédiat. Dans les opérations réelles, cette logique devient toutefois rapidement insuffisante.

Le moteur doit simultanément arbitrer entre plusieurs objectifs parfois contradictoires :

• réduire les kilomètres ;
• préserver les marges temporelles ;
• maintenir la cohérence géographique ;
• respecter les contraintes métier ;
• limiter les attentes ;
• conserver des capacités futures de réorganisation ;
• et éviter les tournées trop fragiles.

Comme l’explique Ammar Oulamara, responsable R&D chez AntsRoute :

« Le scoring ne cherche pas uniquement l’insertion la moins coûteuse. Il cherche l’insertion qui dégrade le moins la qualité globale du planning. »

Cette nuance change profondément la manière de concevoir le moteur.

Cet article se concentre volontairement sur les mécanismes de scoring et d’évaluation des insertions. Pour une vue plus globale des problématiques d’optimisation de tournées dans la logistique du dernier kilomètre, vous pouvez également consulter notre article complet sur l’optimisation de tournées. Le problème devient alors celui de l’agrégation.

Comment comparer deux insertions lorsque :

• la première augmente légèrement les kilomètres ;
• la seconde dégrade davantage les marges temporelles ;
• mais la troisième génère plus d’attente tout en conservant une meilleure cohérence géographique ?

Pour rendre ces solutions comparables, le moteur transforme l’ensemble de ces dimensions en un score scalaire unique capable de hiérarchiser les insertions candidates.

L’objectif n’est pas de réduire artificiellement le problème à une seule métrique, mais de construire un mécanisme d’arbitrage cohérent entre plusieurs coûts opérationnels hétérogènes.

Toutes les insertions faisables ne se valent pas

Considérons une nouvelle tâche τ à insérer dans un planning multi-jours déjà construit. Le moteur doit alors explorer un espace de décision de la forme : (jour d) × (tournée rᵢ) × (position p). Chaque triplet candidat doit ensuite être évalué.
Certaines insertions sont immédiatement éliminées :

• dépassement de capacité ;
• incompatibilité de compétences ;
• violation réglementaire ;
• impossibilité temporelle.

Mais dans la majorité des cas, plusieurs insertions restent faisables.
Le rôle du scoring devient alors central : il permet de comparer ces solutions, d’en mesurer la qualité relative puis de hiérarchiser les meilleures candidates. Le moteur ne raisonne donc pas en logique binaire — faisable ou impossible — mais en qualité de solution.

Premier niveau du score : le coût marginal d’insertion

La première composante du scoring reste naturellement le coût géographique. Chez AntsRoute, le moteur évalue notamment le coût marginal introduit par l’ajout d’une tâche selon la formule suivante :
Δc = c(vₚ₋₁, τ) + c(τ, vₚ) − c(vₚ₋₁, vₚ)

Cette mesure permet de quantifier le surcoût direct créé par l’insertion entre deux sommets consécutifs d’une tournée. Plus ce coût est faible :

• plus l’insertion est géographiquement cohérente ;
• plus la tournée conserve sa compacité spatiale.

Mais ce composant ne constitue qu’une partie du score global.
Comme le rappelle Ammar Oulamara :

« Le coût kilométrique seul est un très mauvais indicateur de qualité dans des tournées fortement contraintes. »

Le score doit intégrer la qualité temporelle de la tournée

Dans les problèmes de type VRPTW (Vehicle Routing Problem with Time Windows), les contraintes temporelles deviennent dominantes.Une insertion peut :

• augmenter les attentes ;
• réduire les marges ;
• densifier certaines plages horaires ;
• ou dégrader fortement la stabilité temporelle du planning.

Le moteur pénalise donc également les temps d’attente inutiles selon l’objectif suivant :
min Σᵢ max(0, eᵢ − tᵢ)

Dans cette formulation, ei représente l’ouverture de la fenêtre de temps, tandis que ti correspond à l’heure d’arrivée estimée.

Ces attentes jouent un rôle important dans le scoring, car elles dégradent progressivement la productivité opérationnelle, la densité des tournées et la capacité future d’absorption des aléas.

L’une des difficultés majeures d’un scoring multicritère réside dans l’hétérogénéité des métriques manipulées. Les kilomètres supplémentaires, les temps d’attente, les pénalités de contraintes ou encore les déséquilibres de charge ne possèdent ni les mêmes unités ni les mêmes ordres de grandeur. Le moteur doit donc normaliser ces différentes dimensions afin d’éviter qu’un critère domine artificiellement les autres uniquement à cause de son échelle numérique.

Cette normalisation permet ensuite de comparer objectivement des insertions ayant des profils opérationnels très différents. Le moteur peut alors agréger ces composantes normalisées dans un score scalaire global utilisé pour classer les insertions candidates.

Le score mesure aussi la cohérence géographique

Une tournée peut être mathématiquement optimisée tout en restant difficilement exploitable sur le terrain. C’est notamment le cas des tournées fragmentées :

• croisements fréquents ;
• zones géographiques éclatées ;
• allers-retours inutiles ;
• répartition peu lisible des interventions.

Chez AntsRoute, le scoring intègre donc également des critères de compacité spatiale.
L’objectif est de favoriser :

• le regroupement géographique des clients ;
• la continuité des tournées ;
• et la lisibilité opérationnelle du planning.

Comme l’explique Ammar Oulamara :

« Une tournée cohérente géographiquement est souvent plus robuste et plus facile à exploiter opérationnellement. »

Hard constraints et soft constraints : deux logiques très différentes

L’un des éléments centraux du scoring repose sur la distinction entre les contraintes strictes et les contraintes pénalisables.

Certaines violations sont interdites et entraînent l’exclusion immédiate de la solution par le moteur, notamment :

• incompatibilité de compétences ;
• dépassement réglementaire ;
• impossibilité de pickup & delivery ;
• dépassement de capacité véhicule.

À l’inverse, d’autres dégradations restent techniquement acceptables, même si elles diminuent la qualité globale du planning. Le moteur les intègre alors sous forme de pénalités dans le score. Cela concerne par exemple :

• les attentes excessives ;
• les surcharges temporelles ;
• une faible robustesse ;
• les déséquilibres entre tournées.

Toutes les dégradations n’ont cependant pas le même impact opérationnel. Une légère densification d’une tournée peut rester acceptable. En revanche, une réduction excessive des marges temporelles ou une forte concentration des interventions critiques sur une même plage horaire peut fortement détériorer la robustesse globale du planning.

Le moteur applique donc des pénalités progressives dont l’intensité dépend de la gravité estimée de la dégradation produite par l’insertion. Cette approche permet d’éviter des raisonnements trop rigides tout en comparant intelligemment plusieurs solutions imparfaites.

Enfin, tous les critères n’ont pas le même poids dans l’évaluation finale. Selon le contexte opérationnel, certaines priorités peuvent devenir dominantes :

• stabilité temporelle ;
• réduction des kilomètres ;
• densité géographique ;
• capacité d’absorption des urgences.

Le rôle des pondérations consiste précisément à refléter ces priorités métier dans le calcul du score. Le moteur ne cherche donc pas un optimum universel, mais un compromis cohérent avec les objectifs réels de l’exploitation.

Le score doit aussi mesurer le potentiel futur de réorganisation

L’un des aspects les plus difficiles des systèmes dynamiques concerne la capacité future d’évolution du planning. Certaines insertions paraissent très efficaces à court terme, mais rendent ensuite les tournées beaucoup plus difficiles à réoptimiser. Cela peut notamment se traduire par :

• disparition des marges temporelles ;
• saturation de certaines ressources ;
• verrouillage des voisinages ;
• forte densification locale.

Chez AntsRoute, le scoring intègre donc également le potentiel d’amélioration locale des insertions candidates. Comme le souligne Ammar Oulamara :

« Une bonne insertion doit aussi préserver la capacité future du moteur à réorganiser efficacement le planning. »

Dans un environnement dynamique, le score d’une insertion n’est jamais figé. Il évolue continuellement à mesure que :

• le planning se densifie ;
• de nouvelles contraintes apparaissent ;
• ou que certaines marges temporelles disparaissent.

Cette logique est essentielle dans les environnements temps réel.

Le scoring sert aussi à guider l’exploration algorithmique

Le score ne sert pas uniquement à classer des solutions : il permet également d’orienter la puissance de calcul du moteur. Toutes les insertions ne méritent pas le même budget calculatoire.

Les solutions les moins prometteuses sont éliminées rapidement à travers des évaluations locales limitées. À l’inverse, les insertions obtenant les meilleurs scores bénéficient ensuite :

• d’explorations de voisinage plus profondes ;
• de mécanismes de recherche locale ;
• ou de stratégies d’amélioration plus coûteuses.

Le scoring devient ainsi un véritable mécanisme de priorisation de l’espace de recherche. À l’issue de l’évaluation, les créneaux candidats peuvent être classés selon leur qualité opérationnelle afin de guider automatiquement la sélection des insertions les plus pertinentes.

Cette hiérarchisation est essentielle pour maintenir :

• des temps de réponse compatibles avec le temps réel ;
• tout en conservant une excellente qualité d’optimisation.

Pourquoi un score doit rester explicable

Dans beaucoup de systèmes d’optimisation, l’un des problèmes majeurs concerne l’opacité des décisions. Un moteur qui produit une solution sans être capable d’expliquer pourquoi une insertion a été retenue, pourquoi une autre a été rejetée ou quelles contraintes ont pesé dans l’arbitrage devient difficile à exploiter opérationnellement.

Chez AntsRoute, le scoring est donc conçu pour rester interprétable. Les principales composantes du score restent lisibles et analysables, notamment :

• le coût marginal ;
• les pénalités appliquées ;
• la faisabilité ;
• la qualité temporelle ;
• le potentiel de réorganisation.

Cette explicabilité permet non seulement de mieux comprendre les arbitrages réalisés par le moteur, mais aussi de renforcer la confiance des exploitants dans les décisions proposées.

Conclusion

Dans un moteur moderne d’optimisation de tournées, le scoring ne consiste pas simplement à calculer une distance supplémentaire. Il agit comme un système d’évaluation multicritère capable de mesurer :

• la qualité géographique d’une insertion ;
• sa robustesse temporelle ;
• sa faisabilité métier ;
• sa cohérence opérationnelle ;
• et son impact futur sur le planning.

Cette logique permet au moteur de dépasser les raisonnements purement locaux afin de hiérarchiser les solutions à l’échelle globale du système. Car dans les opérations du dernier kilomètre, une bonne décision n’est pas seulement une décision faisable : c’est une décision capable de préserver durablement l’équilibre opérationnel du planning.