Warm-start, recherche locale et voisinages : comment notre moteur réoptimise les tournées en continue

Publié le 1 juin 2026 • Lecture : 8 min read

Dans les problèmes d’optimisation de tournées, produire une première solution est rarement le principal défi. La véritable difficulté apparaît lorsque le planning doit évoluer sous l’effet d’événements opérationnels tels que l’ajout d’une nouvelle tâche, un retard, une annulation, une modification de demande client, la réaffectation d’un véhicule ou encore la saturation locale d’une tournée.

Dans ce contexte, le moteur ne travaille sur un problème initial. Il doit adapter un système déjà construit, déjà contraint et souvent déjà partiellement optimisé, tout en préservant autant que possible sa qualité globale. C’est précisément cette capacité à faire évoluer efficacement un planning existant qui distingue les problèmes d’optimisation dynamique des approches théoriques plus classiques.

Cet article se concentre volontairement sur les mécanismes de réoptimisation utilisés dans les moteurs de tournées dynamiques : warm-start, recherche locale, voisinages et heuristiques d’exploration. 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.

Dans les opérations réelles, un moteur performant ne peut pas repartir de zéro à chaque événement. Les algorithmes d’optimisation doivent être capables de réoptimiser localement un planning vivant sans déstabiliser inutilement les tournées existantes.

Chez AntsRoute, cette problématique est au cœur de l’architecture du moteur d’optimisation.

Au programme dans cet article :

• Pourquoi repartir de zéro n’est pas viable en temps réel
• Le rôle du warm-start dans les tournées dynamiques
• Pourquoi une insertion doit être évaluée globalement
• Comment fonctionne la recherche locale
• Pourquoi tous les voisinages ne méritent pas le même niveau d’exploration
• First-improvement vs Best-improvement : deux stratégies d’optimisation
• Pourquoi les méthodes exactes atteignent rapidement leurs limites

Pourquoi repartir de zéro est rarement une bonne stratégie

En théorie, reconstruire entièrement le planning après chaque modification pourrait sembler être la meilleure approche. Dans la pratique, cette stratégie devient rapidement impraticable en raison de l’explosion du nombre de solutions à explorer, des temps de calcul qu’elle implique et de l’instabilité qu’elle génère pour les opérations terrain.

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

« Un moteur temps réel ne peut pas reconstruire intégralement les tournées à chaque nouvel événement. Le coût calculatoire et l’instabilité produite seraient beaucoup trop importants. »

C’est précisément pour cette raison que les moteurs modernes utilisent des approches de warm-start.

Le warm-start : partir d’une solution déjà optimisée

Le principe du warm-start consiste à utiliser le planning courant comme point de départ de l’optimisation. Plutôt que de rechercher une solution entièrement nouvelle, le moteur cherche à améliorer localement une solution déjà cohérente, tout en limitant les dégradations susceptibles d’affecter l’équilibre global du système.

Cette approche possède plusieurs avantages importants :

• réduction drastique de l’espace de recherche ;
• conservation d’une bonne stabilité opérationnelle ;
• temps de réponse compatibles avec le temps réel ;
• et limitation des réorganisations inutiles.

Comme le souligne Ammar Oulamara :

« Le warm-start permet au moteur de concentrer sa puissance de calcul sur les zones réellement impactées par une modification du planning. »

Cette logique change profondément la manière dont le problème est exploré.

Une insertion ne s’évalue jamais isolément

Lorsqu’une nouvelle tâche τ est insérée, le moteur ne se contente pas d’évaluer son coût marginal immédiat. Cette insertion peut en effet avoir des répercussions sur l’ensemble du planning en modifiant :

• les contraintes temporelles ;
• les marges de sécurité ;
• l’équilibre entre tournées ;
• les capacités futures de réorganisation ;
• ou la compacité géographique du planning.

Le moteur doit donc explorer non seulement l’insertion elle-même, mais également les réorganisations locales qu’elle rend possibles par la suite. C’est précisément cette capacité à améliorer une solution existante qui constitue le rôle des mécanismes de recherche locale.

La recherche locale : explorer le voisinage d’une solution

Dans les problèmes de tournées, il est impossible d’explorer exhaustivement toutes les solutions possibles. Les moteurs modernes travaillent donc principalement par exploration de voisinages.
Le principe est simple :

• partir d’une solution existante ;
• appliquer localement certaines transformations ;
• puis mesurer si la nouvelle solution améliore le planning.

Chez AntsRoute, l’algorithme de recherche locale s’appuie sur plusieurs opérateurs permettant d’explorer efficacement ces voisinages.

Relocate : déplacer une tâche vers une meilleure position

L’opérateur relocate est l’un des mécanismes les plus fondamentaux en recherche locale. Il consiste à retirer une tâche d’une tournée pour la réinsérer à une autre position, soit dans la même tournée, soit dans une tournée différente.
Cette opération permet notamment de :

• de restaurer des marges temporelles ;
• d’équilibrer les charges ;
• ou de réduire certains effets de propagation.

Dans les systèmes dynamiques, relocate joue souvent un rôle central dans les réoptimisations rapides, car il permet d’améliorer localement un planning avec un coût calculatoire relativement faible.

Or-opt : déplacer des séquences de tâches

Dans certains cas, déplacer une seule tâche ne suffit pas à restaurer un bon équilibre du planning. Le moteur utilise alors des opérateurs de type Or-opt, qui consistent à déplacer une séquence de 1, 2 ou 3 tâches consécutives vers une autre position de la tournée ou du planning.

Cette approche est particulièrement utile lorsque :

• plusieurs tâches possèdent une forte cohérence géographique ;
• ou lorsqu’une réorganisation locale nécessite de conserver certaines continuités de tournée.

Comme l’explique Ammar Oulamara :

« Déplacer un groupe cohérent de tâches peut parfois restaurer beaucoup plus efficacement l’équilibre du planning qu’une série de modifications isolées. »

2-opt et 3-opt : restructurer la géographie des tournées

Les opérateurs 2-opt et 3-opt poursuivent un objectif différent. Ils consistent à inverser certaines sous-séquences d’une tournée afin d’en améliorer la structure géographique.

Ces mécanismes permettent notamment de :

• d’éliminer des croisements ;
• d’améliorer la compacité géographique ;
• ou de réduire les détours inutiles.

Ils sont particulièrement efficaces lorsque :

• les tournées deviennent fragmentées ;
• ou que certaines insertions successives détériorent progressivement leur structure spatiale.

Même dans des systèmes fortement contraints par le temps, la qualité géographique des tournées reste un élément essentiel de robustesse opérationnelle.

Cross-exchange : rééquilibrer plusieurs tournées simultanément

Dans les systèmes fortement contraints, certaines insertions ne peuvent pas être absorbées par de simples ajustements locaux. Le moteur doit alors réorganiser simultanément plusieurs tournées à l’aide d’opérateurs de cross-exchange, qui consistent à échanger des segments entiers entre tournées afin de restaurer un meilleur équilibre global.

Ces mécanismes deviennent particulièrement utiles lorsque :

• certaines ressources critiques approchent de la saturation ;
• plusieurs tournées deviennent temporellement fragiles ;
• les possibilités de réorganisation locale s’amenuisent.

Le moteur ne raisonne alors plus uniquement à l’échelle d’une tournée isolée, mais à celle de l’ensemble du planning afin d’identifier les rééquilibrages les plus pertinents.

Tous les voisinages ne méritent pas le même coût calculatoire

Explorer en profondeur chaque insertion candidate serait beaucoup trop coûteux d’un point de vue calculatoire. Le moteur doit donc prioriser ses efforts et concentrer sa puissance de calcul sur les solutions les plus prometteuses. Chez AntsRoute, cette exploration s’appuie sur une hiérarchie de voisinages permettant d’adapter progressivement la profondeur de recherche en fonction de la qualité des insertions évaluées.

Voisinage de degré 1

Le premier niveau de voisinage repose uniquement sur des modifications locales simples réalisées au sein d’une même tournée. L’objectif est de filtrer rapidement les insertions manifestement défavorables tout en limitant le coût calculatoire.

Voisinage de degré 2

À ce stade, le moteur autorise des échanges entre tournées ainsi que des rééquilibrages plus larges. Cette exploration permet d’évaluer les conséquences globales de certaines insertions et d’identifier des améliorations qui ne seraient pas visibles à l’échelle d’une seule tournée.

Voisinage de degré 3

Le troisième niveau de voisinage autorise des réorganisations beaucoup plus profondes, pouvant inclure des restructurations multi-jours ou des modifications significatives du planning. Ces explorations plus coûteuses sont réservées aux insertions les plus prometteuses ou aux situations particulièrement contraintes.

Cette hiérarchie de voisinages permet d’allouer intelligemment la puissance de calcul en adaptant la profondeur de recherche à la qualité des solutions rencontrées.

First-improvement vs Best-improvement

L’un des arbitrages les plus importants en recherche locale concerne la stratégie utilisée pour explorer le voisinage d’une solution. Deux approches principales sont généralement employées : first-improvement et best-improvement.

First-improvement

Avec la stratégie first-improvement, le moteur accepte la première amélioration rencontrée lors de l’exploration. Cette approche présente plusieurs avantages :

• convergence rapide ;
• faible coût calculatoire ;
• bonne efficacité dans les premières phases d’exploration.

Best-improvement

À l’inverse, la stratégie best-improvement consiste à explorer l’ensemble du voisinage avant de sélectionner la meilleure amélioration disponible. Elle permet généralement :

• d’obtenir une meilleure qualité de solution ;
• d’explorer plus en profondeur les possibilités d’optimisation.

En contrepartie, son coût calculatoire est nettement plus élevé.

Comme l’explique Ammar Oulamara :

« Le choix entre first-improvement et best-improvement dépend fortement de la densité du planning et du budget de calcul disponible. »

Chez AntsRoute, le moteur alterne dynamiquement entre ces deux stratégies en fonction de la qualité des solutions observées, du niveau de convergence atteint et du degré de saturation du planning.

Pourquoi les méthodes exactes deviennent rapidement limitées

Les problèmes de tournées dynamiques appartiennent à une classe de problèmes combinatoires particulièrement complexes. À mesure que les contraintes se multiplient, que les tournées se densifient et que les événements temps réel deviennent plus fréquents, la taille de l’espace de recherche augmente considérablement. Les méthodes exactes deviennent alors rapidement incompatibles avec les exigences opérationnelles, tant en matière de temps de calcul que de réactivité.

Comme le rappelle Ammar Oulamara :

« Le moteur ne cherche pas la solution théoriquement parfaite. Il cherche la meilleure solution exploitable dans un temps de calcul compatible avec les opérations. »

C’est précisément pour cette raison que les moteurs modernes s’appuient sur une combinaison d’heuristiques, de mécanismes de warm-start, d’opérateurs de recherche locale et de stratégies d’exploration adaptatives afin de produire rapidement des solutions robustes et opérationnellement pertinentes.

Conclusion

Dans les systèmes modernes d’optimisation de tournées, la difficulté ne consiste pas uniquement à construire un planning initial. Le véritable défi est de réussir à le faire évoluer en continu sans compromettre sa robustesse, sa stabilité ou sa qualité opérationnelle.

Le warm-start, les opérateurs de recherche locale et les explorations multi-voisinages permettent précisément de répondre à cette problématique. En logistique du dernier kilomètre, une tournée n’est jamais totalement figée : elle doit pouvoir s’adapter en permanence aux changements du terrain tout en conservant un bon niveau de performance opérationnelle.