Pourquoi ajouter une seule livraison peut bouleverser toute une tournée

Publié le 26 mai 2026 • Lecture : 6 min read

Dans les problèmes d’optimisation de tournées dynamiques, les insertions les plus difficiles à gérer ne sont pas nécessairement les plus coûteuses.
Certaines sont immédiatement invalides :

• incompatibilité de compétences,
• dépassement de capacité,
• violation de fenêtre horaire,
• impossibilité réglementaire.

Ces cas sont relativement simples à éliminer.

Les situations réellement complexes sont souvent beaucoup plus ambiguës.

Une nouvelle tâche peut sembler parfaitement cohérente d’un point de vue géographique — faible détour, proximité avec d’autres interventions, insertion naturelle dans l’itinéraire — tout en détériorant fortement la qualité globale du planning une fois l’ensemble des contraintes propagées.

C’est précisément ce type de problème que doit résoudre un moteur d’optimisation temps réel dans la logistique du dernier kilomètre.

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

« Une insertion localement optimale peut produire une forte dégradation globale du planning lorsqu’on prend en compte l’ensemble des contraintes temporelles et opérationnelles. »

Cette distinction entre optimisation locale et stabilité globale est au cœur des problèmes modernes d’insertion dynamique.

Pour une vue plus globale des mécanismes 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.

Au programme dans cet article :

• Pourquoi les insertions dynamiques sont beaucoup plus complexes qu’il n’y paraît
• Les limites du coût marginal dans l’évaluation des tournées
• Comment les fenêtres horaires créent des dépendances fortes
• Pourquoi une tournée faisable peut devenir très fragile
• L’impact des contraintes métier sur les insertions
• Comment le moteur réorganise localement le planning
• Pourquoi toutes les insertions ne méritent pas le même niveau d’exploration

Le problème d’insertion est beaucoup plus vaste qu’il n’y paraît

Dans un planning multi-jours déjà construit, une nouvelle tâche τ ne possède pas un unique point d’insertion possible.

Le moteur doit potentiellement explorer un espace de décision de la forme :
(jour d) × (tournée rᵢ ∈ R_d) × (position p dans rᵢ)

Autrement dit :

• plusieurs jours candidats,
• plusieurs tournées par jour,
• plusieurs positions possibles dans chaque tournée.

Et chaque insertion candidate modifie le coût kilométrique, les horaires propagés, les temps d’attente, les marges temporelles, la faisabilité des contraintes métier ainsi que la capacité future de réorganisation du planning.

Le problème devient rapidement combinatoire.

Dans les systèmes réels, il ne s’agit donc pas simplement de trouver « une place disponible », mais d’évaluer la qualité globale de chaque insertion candidate.

Pourquoi le coût marginal est insuffisant

La plupart des approches d’insertion commencent naturellement par mesurer le coût marginal introduit dans la tournée :

Δc = c(vₚ₋₁, τ) + c(τ, vₚ) − c(vₚ₋₁, vₚ)

Cette mesure reste essentielle. Elle permet d’évaluer le surcoût géographique créé par l’ajout d’une nouvelle tâche τ entre deux sommets consécutifs d’une tournée.
Mais dans des tournées fortement contraintes, ce critère devient rapidement insuffisant.

Prenons un cas simple.
Deux insertions génèrent exactement le même coût marginal :

• même augmentation kilométrique,
• même temps de trajet supplémentaire.

Pourtant, la première conserve des marges temporelles importantes sur le reste de la tournée, tandis que la seconde concentre plusieurs interventions critiques sur une plage horaire déjà fortement dense entre 14h et 16h.

Géographiquement, les deux insertions semblent équivalentes. Temporellement, elles ne le sont absolument pas.
La seconde insertion rend la tournée beaucoup plus sensible :

• au trafic,
• aux retards,
• aux dépassements de temps d’intervention,
• ou aux urgences de dernière minute.

Autrement dit :
le coût local ne reflète pas nécessairement la stabilité globale de la solution.

Les fenêtres horaires créent des dépendances fortes

Dans un problème de type VRPTW (Vehicle Routing Problem with Time Windows), chaque tâche est liée aux précédentes par une chaîne de dépendances temporelles.
L’heure d’arrivée à un arrêt dépend implicitement :

• des temps de trajet précédents,
• des durées de service,
• des attentes éventuelles,
• et des retards accumulés plus tôt dans la tournée.

Lorsqu’une nouvelle tâche est insérée, toute cette structure temporelle doit être recalculée.
C’est ce phénomène de propagation qui rend les insertions dynamiques particulièrement sensibles.
Un décalage de quelques minutes au milieu d’une tournée peut suffire à :

• supprimer des marges de sécurité,
• déplacer une pause réglementaire,
• générer des attentes supplémentaires,
• ou provoquer plusieurs violations plus loin dans la journée.

Chez AntsRoute, le moteur pénalise notamment les temps d’attente inutiles :
min Σᵢ max(0, eᵢ − tᵢ)

où :

• ei représente l’ouverture de la fenêtre de temps du client,
• et ti l’heure d’arrivée estimée.

Ces attentes sont souvent sous-estimées dans les approches simplifiées alors qu’elles dégradent fortement la productivité, la densité des tournées et la capacité future d’absorption des imprévus.

Une tournée peut être faisable… mais extrêmement fragile

Dans beaucoup de systèmes, la faisabilité est traitée comme une condition binaire :

• une insertion est valide,
• ou elle ne l’est pas.

Dans les opérations réelles, la situation est beaucoup plus nuancée. Certaines insertions restent techniquement faisables tout en produisant une tournée extrêmement fragile.

Par exemple, une tournée peut respecter toutes les fenêtres horaires tout en ne laissant quasiment plus aucune marge temporelle, restant techniquement valide mais devenant incapable d’absorber le moindre retard.

Comme le souligne Ammar Oulamara :

« Le problème ne consiste pas uniquement à garantir la faisabilité immédiate d’une insertion. Il faut aussi préserver la robustesse opérationnelle du planning. »

Cette notion de robustesse devient centrale dans les systèmes dynamiques.
Une solution légèrement moins optimisée kilométriquement peut être préférable si elle conserve davantage de flexibilité opérationnelle.

Les contraintes métier amplifient encore les effets de bord

Les difficultés augmentent fortement lorsque le moteur doit intégrer des contraintes métier complexes :

• compétences spécifiques,
• habilitations,
• équipements particuliers,
• amplitudes horaires,
• capacités véhicules,
• contraintes de pickup & delivery,
• règles d’affectation.

Certaines ressources deviennent alors critiques.

Certaines ressources deviennent alors critiques. Une insertion mal positionnée peut par exemple saturer prématurément un agent possédant une compétence rare, empêcher une future réaffectation ou encore verrouiller certaines possibilités de réorganisation.

Dans les problèmes de pickup & delivery, le moteur doit également garantir des contraintes de précédence :
t(dτ) − t(pτ) ≤ Δtₘₐₓ

Autrement dit :
le délai maximal entre un enlèvement et une livraison doit rester compatible avec les contraintes opérationnelles du système.
Ces dépendances supplémentaires augmentent fortement la complexité des insertions dynamiques.

Pourquoi le moteur doit réorganiser localement le planning

Face à ces interactions multiples, une simple logique d’insertion directe devient insuffisante.

Une insertion candidate doit souvent être suivie d’une phase de réorganisation locale destinée à restaurer un équilibre acceptable dans le planning.

Chez AntsRoute, le moteur exploite plusieurs opérateurs de recherche locale :

• relocate,
• Or-opt,
• 2-opt,
• cross-exchange.

L’objectif n’est pas uniquement de rendre l’insertion faisable.
Il s’agit aussi :

• de réduire les effets de propagation,
• de restaurer des marges temporelles,
• d’améliorer la compacité des tournées,
• et de préserver la stabilité globale du système.

Comme l’explique Ammar Oulamara :

« Une insertion ne doit jamais être évaluée isolément. Il faut également mesurer le potentiel d’amélioration locale qu’elle autorise ensuite. »

Cette logique est fondamentale dans les moteurs d’optimisation modernes.

Toutes les insertions ne méritent pas le même niveau d’exploration

L’un des principaux défis d’un moteur temps réel est le coût calculatoire.
Explorer exhaustivement toutes les réorganisations possibles serait incompatible avec les contraintes opérationnelles du dernier kilomètre.

C’est pourquoi notre moteur utilise une hiérarchie de voisinages.
Les insertions manifestement défavorables sont éliminées rapidement via des modifications locales limitées.
Les insertions plus prometteuses bénéficient ensuite d’une exploration plus profonde :

• échanges inter-tournées,
• réorganisation multi-jours,
• optimisation locale avancée.

Cette structure permet de concentrer intelligemment la puissance de calcul sur les solutions réellement intéressantes.

Conclusion

Dans les systèmes de tournées dynamiques, une insertion géographiquement optimale peut produire des effets très négatifs sur la qualité globale du planning.

Une tournée ne se résume pas à une simple succession de trajets. C’est une organisation sous contraintes, où les marges temporelles, les dépendances métier, les capacités de réorganisation et la robustesse opérationnelle évoluent en permanence.

L’optimisation des insertions dynamiques ne consiste donc pas uniquement à minimiser un détour kilométrique.
Elle consiste surtout à préserver l’équilibre global du système après chaque modification du planning.