Pourquoi l’optimisation de tournées est un problème beaucoup plus complexe qu’il n’y paraît

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

Pendant longtemps, l’optimisation de tournées a été perçue comme un problème relativement simple : calculer le meilleur trajet possible entre plusieurs points.

Dans la réalité opérationnelle, les choses sont évidemment beaucoup plus complexes.

Une tournée n’est jamais une simple suite d’adresses. Elle doit composer avec des contraintes horaires, des compétences terrain, des capacités véhicules, des temps d’intervention variables, des urgences, des demandes clients de dernière minute ou encore des réaffectations permanentes au cours de la journée.

Et surtout, une tournée n’est presque jamais figée.

Dans la logistique du dernier kilomètre, le véritable défi n’est pas uniquement de construire un planning performant le matin. Il consiste surtout à réussir à le faire évoluer intelligemment tout au long de la journée, sans dégrader l’équilibre global des opérations.

C’est précisément cette problématique qui a conduit notre équipe R&D chez AntsRoute à travailler sur des mécanismes avancés d’insertion dynamique et de scoring des tournées.

Au programme dans cet article :

• Pourquoi une tournée cache un problème mathématique beaucoup plus complexe qu’il n’y paraît
• Le véritable défi : faire évoluer un planning en temps réel
• Pourquoi les outils classiques atteignent rapidement leurs limites
• Comment notre moteur évalue chaque insertion candidate
• Pourquoi la distance seule ne suffit jamais
• L’impact des fenêtres horaires sur l’optimisation des tournées
• Les contraintes métier au cœur des décisions du moteur
• Pourquoi les heuristiques sont devenues indispensables
• Derrière les algorithmes : des enjeux très concrets pour les opérations terrain

Derrière une tournée « simple » se cache un problème mathématique extrêmement complexe

Vu de l’extérieur, ajouter une nouvelle livraison ou une intervention dans une tournée existante peut sembler relativement banal. Après tout, il suffit théoriquement de trouver un « trou » dans le planning.

Dans la pratique, les conséquences sont souvent beaucoup plus importantes.

Une seule insertion peut modifier :

• les horaires de passage suivants,
• les temps d’attente,
• les pauses réglementaires,
• la charge du véhicule,
• la faisabilité d’autres interventions,
• ou encore l’équilibre global entre les agents terrain.

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

« Ajouter une seule tâche dans une tournée existante peut modifier l’ensemble des contraintes temporelles et opérationnelles du planning. Une insertion qui paraît logique géographiquement peut devenir très mauvaise une fois toutes les contraintes métier prises en compte. »

Cette difficulté est bien connue dans le domaine de la recherche opérationnelle sous le nom de Vehicle Routing Problem (VRP).

Le principe théorique paraît relativement simple : trouver les meilleures tournées possibles pour une flotte de véhicules.

Mais dès que l’on introduit des contraintes réelles — fenêtres horaires, compétences des agents, capacités véhicules, Pick-up & Delivery ou réoptimisation temps réel — le problème devient rapidement gigantesque d’un point de vue combinatoire.

C’est notamment le cas du VRPTW (Vehicle Routing Problem with Time Windows), où chaque intervention doit être réalisée dans une fenêtre de temps précise.

À partir de quelques dizaines d’arrêts seulement, le nombre de combinaisons possibles devient déjà colossal. Et dans les opérations terrain réelles, les plannings évoluent en permanence.

Autrement dit : il devient impossible d’explorer exhaustivement toutes les possibilités.

Le vrai sujet n’est pas de construire une tournée… mais de la faire évoluer intelligemment

Dans beaucoup d’approches théoriques, les tournées sont construites « une fois pour toutes ».

Mais les opérations réelles ne fonctionnent jamais ainsi.

Les exploitants doivent gérer :

• des urgences,
• des annulations,
• des retards,
• du trafic,
• des absences,
• des modifications clients,
• ou encore des contraintes terrain imprévues.

C’est d’ailleurs ce que beaucoup d’équipes décrivent comme un véritable « équilibrage permanent des plannings » quotidien.

Le problème devient alors beaucoup plus difficile : comment insérer intelligemment une nouvelle tâche dans un planning déjà optimisé sans dégrader l’ensemble des tournées ?

Nous revenons plus en détail sur cette problématique dans notre article consacré à l’insertion dynamique des tâches et aux effets de propagation dans les tournées.

C’est précisément sur cette problématique que se concentre une grande partie des travaux de notre équipe R&D.

« Le vrai défi n’est pas seulement de construire une tournée optimale le matin », explique Ammar Oulamara. « Il faut surtout réussir à faire évoluer ce planning tout au long de la journée sans créer d’effets de bord incontrôlables. »

Pourquoi les outils classiques atteignent rapidement leurs limites

De nombreuses organisations commencent naturellement avec des outils simples : Excel, Google Maps, téléphone, SMS ou plusieurs logiciels partiellement connectés entre eux.

À petite échelle, cela peut fonctionner correctement.

Mais dès que :

• le volume d’activité augmente,
• les contraintes se multiplient,
• les équipes grandissent,
• ou que les clients imposent des créneaux plus précis,
• la gestion devient extrêmement difficile à maintenir manuellement.

Le problème ne vient pas uniquement du volume de données.

Il vient surtout du nombre d’interdépendances entre les décisions.

Modifier une seule tournée peut avoir des conséquences sur l’ensemble du planning.

C’est précisément pour cette raison que les approches purement manuelles ou partiellement manuelles atteignent rapidement leurs limites.

Comment notre moteur d’optimisation évalue chaque insertion possible

Chez AntsRoute, nous avons développé une approche basée sur un algorithme de scoring multicritère.

L’idée n’est pas simplement de trouver un créneau disponible.

Le moteur cherche plutôt à évaluer la qualité globale de chaque insertion candidate.

Concrètement, lorsqu’une nouvelle tâche doit être ajoutée, plusieurs possibilités existent :

• différents jours,
• plusieurs tournées,
• différentes positions dans chaque tournée.

Chaque combinaison potentielle est alors évaluée à travers un score d’insertion.

Nous détaillons également le fonctionnement de ce mécanisme dans notre article dédié aux algorithmes de scoring en optimisation de tournées.

Comme le précise Ammar Oulamara :

« Deux insertions qui semblent proches géographiquement peuvent avoir des impacts opérationnels très différents. Le rôle du scoring est précisément d’évaluer ces différences de manière objective. »

Le moteur ne regarde donc pas uniquement les kilomètres supplémentaires générés.

Il prend également en compte :

• les contraintes temporelles,
• les temps d’attente,
• la cohérence géographique,
• les compétences requises,
• les capacités véhicules,
• les amplitudes horaires,
• ou encore le potentiel de réorganisation locale.

Pourquoi la distance seule ne suffit jamais

L’un des premiers indicateurs utilisés consiste à mesurer le coût marginal généré par l’ajout d’une nouvelle tâche dans une tournée existante.

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

Cette formule permet d’évaluer le surcoût réellement introduit par l’insertion.

Mais dans les opérations réelles, la distance seule ne suffit jamais à prendre une bonne décision.

Une insertion géographiquement « proche » peut par exemple :

• provoquer un retard en cascade,
• créer du temps d’attente,
• déséquilibrer une tournée,
• ou rendre impossible une intervention suivante.

C’est notamment pour cette raison que les fenêtres horaires jouent un rôle central dans les algorithmes d’optimisation modernes.

Pour approfondir cette problématique, nous expliquons également pourquoi les contraintes temporelles rendent les problèmes VRPTW beaucoup plus complexes à optimiser.

Les fenêtres horaires changent profondément le problème

Dans la plupart des activités terrain, toutes les tâches ne peuvent pas être réalisées à n’importe quel moment.

Certains clients exigent :

• une livraison entre 10h et 11h,
• une intervention avant midi,
• ou un passage après une certaine heure.

Ces contraintes transforment profondément l’optimisation des tournées.

Un véhicule peut parfois arriver trop tôt et devoir attendre avant de pouvoir intervenir.

Notre moteur intègre donc également les temps d’attente dans son évaluation des tournées.

min Σᵢ max(0, eᵢ − tᵢ)

L’objectif est de limiter autant que possible les périodes improductives qui dégradent la qualité opérationnelle des tournées.

Les contraintes métier sont souvent le vrai cœur du problème

Dans beaucoup de projets logistiques, la difficulté n’est pas uniquement géographique.

Elle est métier.

Comme le rappelle Ammar Oulamara :

« Le moteur d’optimisation doit raisonner avec les contraintes réelles du terrain, pas uniquement avec des distances sur une carte. »

Certaines interventions nécessitent :

• des compétences spécifiques,
• des habilitations,
• des équipements particuliers,
• ou des affectations précises.

D’autres imposent :

• des contraintes de pickup & delivery,
• des amplitudes maximales,
• des pauses réglementaires,
• ou des règles propres à l’organisation.

Cette réalité opérationnelle est souvent ce qui distingue les modèles théoriques des systèmes réellement exploitables sur le terrain.

Pourquoi les heuristiques sont devenues indispensables

Face à cette complexité, les approches exhaustives deviennent irréalistes.

Explorer toutes les combinaisons possibles demanderait des temps de calcul incompatibles avec les contraintes opérationnelles du dernier kilomètre.

C’est pourquoi les moteurs modernes s’appuient largement sur des heuristiques et des mécanismes de recherche locale.

L’objectif n’est pas nécessairement de trouver la solution mathématiquement parfaite.

L’objectif est surtout de produire rapidement une solution :

• robuste,
• cohérente,
• et exploitable opérationnellement.

Chez AntsRoute, notre approche repose notamment sur :

• des mécanismes de warm-start,
• des opérateurs de recherche locale,
• et des stratégies d’exploration adaptatives.

Nous revenons plus en détail sur ces mécanismes de réoptimisation dans notre article consacré au warm-start, à la recherche locale et aux stratégies de voisinage utilisées dans les moteurs de tournées dynamiques.

« Explorer toutes les possibilités serait beaucoup trop coûteux en temps de calcul », explique Ammar Oulamara. « L’enjeu consiste surtout à concentrer intelligemment la puissance de calcul sur les insertions les plus prometteuses. »

Derrière les algorithmes, un objectif très concret

Dans beaucoup d’entreprises, les équipes exploitation passent encore une partie importante de leur journée à réorganiser manuellement les tournées.

Cette charge mentale opérationnelle est souvent sous-estimée.

Pourtant, c’est précisément là que se joue une grande partie de la performance terrain :

• capacité à absorber les imprévus,
• réactivité,
• qualité de service,
• robustesse des plannings,
• satisfaction client,
• maîtrise des coûts.

L’objectif des moteurs d’optimisation modernes n’est donc pas uniquement de réduire des kilomètres.

Il s’agit surtout d’aider les équipes à prendre de meilleures décisions dans un environnement mouvant et fortement contraint.

Conclusion

L’optimisation de tournées est souvent présentée comme un simple problème de calcul d’itinéraire.

Dans la réalité, il s’agit surtout d’un problème d’arbitrage permanent entre :

• contraintes métier,
• qualité de service,
• faisabilité opérationnelle,
• stabilité des tournées,
• et performance économique.

Et plus les opérations évoluent en temps réel, plus cette difficulté augmente.

Chez AntsRoute, notre approche consiste précisément à concevoir des moteurs capables de s’adapter à cette réalité terrain : des systèmes capables d’évaluer intelligemment chaque insertion possible tout en tenant compte des contraintes réelles des opérations.

Parce qu’en logistique du dernier kilomètre, le véritable enjeu n’est pas simplement d’optimiser un planning.

C’est de continuer à prendre les bonnes décisions quand le terrain change en permanence.