A Speculative Verification and Expert Repair Framework for Dynamic Vehicle Routing

Les systèmes de livraison du dernier kilomètre opèrent dans un monde qui ne reste que rarement immobile. Les commandes arrivent alors que les camions sont déjà en mouvement, les conditions de circulation changent et les créneaux de livraison sont souvent serrés. Dans cet environnement, un plan statique — un itinéraire calculé une seule fois au début de la journée — est rarement suffisant. Au lieu de cela, les répartiteurs doivent constamment mettre à jour leurs plans, insérant de nouveaux arrêts dans des itinéraires existants ou les réorganisant lorsqu'un client annule ou qu'un véhicule tombe en panne. Ce besoin constant de réoptimisation crée un défi computationnel difficile : le système doit trouver un nouvel arrangement valide d'arrêts en quelques secondes seulement. Si l'ordinateur met trop de temps à réfléchir, la fenêtre de livraison se referme ou le chauffeur attend inutilement. Si l'ordinateur devine un nouvel itinéraire qui viole les règles — comme un camion transportant trop de poids ou arrivant trop tard — l'ensemble du plan s'effondre et le système doit repartir de zéro. L'objectif n'est pas seulement de trouver le chemin le plus court, mais de trouver un chemin réalisable, instantanément.

Des chercheurs de l'Université de technologie automobile de Hubei ont développé une nouvelle approche à ce problème, une approche qui emprunte une stratégie au monde de l'intelligence artificielle pour rendre ces décisions de l'ordre de la fraction de seconde plus fiables. Ils appellent leur système SRI-ECR-balanced. Plutôt que d'essayer de calculer l'itinéraire parfait de zéro chaque fois qu'une nouvelle commande arrive, le système fonctionne comme un éditeur qualifié qui rédige quelques phrases, les vérifie pour détecter des erreurs, conserve les bonnes parties et corrige immédiatement les mauvaises. Cette méthode, connue sous le nom d'exécution spéculative, permet au système de proposer plusieurs arrêts futurs à la fois, de vérifier lesquels sont sûrs et de rejeter les autres avant qu'ils ne causent un problème. Ce faisant, le système peut se rétablir des conflits bien plus rapidement que les méthodes traditionnelles, garantissant qu'un plan de livraison reste réalisable même lorsque la situation sur le terrain change rapidement.

Le cœur de ce nouveau cadre est un cycle de rédaction, de vérification et de réparation. Lorsqu'une nouvelle commande arrive, un « générateur de brouillon » propose une courte séquence de clients à ajouter à l'itinéraire d'un camion. Par le passé, les systèmes pouvaient essayer d'insérer un seul client à la fois, ce qui est lent, ou essayer d'insérer une longue liste de clients d'un coup, ce qui mène souvent à des erreurs. Ce nouveau système trouve un équilibre : il propose un petit groupe d'arrêts, peut-être cinq à la fois. Un « vérificateur » distinct vérifie ensuite ce groupe par rapport aux règles de la route, telles que la limite de poids du camion et le créneau horaire du client. Le système accepte la plus longue séquence du groupe proposé qui respecte les règles et rejette immédiatement le reste. Si les trois premiers arrêts du groupe proposé sont corrects mais que le quatrième est trop lourd pour le camion, le système conserve les trois premiers et annule le quatrième. Il ne jette pas tout le plan ; il supprime seulement la partie qui a enfreint les règles.

Une fois les arrêts invalides annulés, un « expert en réparation » spécialisé intervient pour régler le problème. Il ne s'agit pas d'un réparateur générique ; le système diagnostique exactement ce qui a mal tourné. Si le problème est que le camion est trop chargé, l'expert donne la priorité à la recherche d'un autre camion ayant plus d'espace. Si le problème est qu'un client sera manqué à cause d'un créneau horaire serré, l'expert cherche un itinéraire qui peut arriver plus tôt. Cette approche ciblée est cruciale. Les chercheurs ont constaté que sans cette étape de réparation spécifique et consciente des conflits, le système ne parvenait pas à trouver de parcours valides dans les situations de stress. Lorsque le système était contraint d'utiliser une méthode de réparation aléatoire plutôt qu'une méthode experte, il ne pouvait réparer qu'environ un tiers des problèmes, laissant de nombreuses commandes non servies. Avec l'expert routier, le système a réussi à réparer chaque conflit lors de leurs tests, maintenant un dossier parfait de plans réalisables.

Pour rendre ce processus assez rapide pour une utilisation en temps réel, le système utilise également une forme de mémoire appelée cache de préfixe de route. Dans un environnement dynamique, la majeure partie de l'itinéraire d'un camion reste la même d'un moment à l'autre ; seule la fin de l'itinéraire change. Les systèmes traditionnels recalculent souvent l'intégralité du trajet chaque fois qu'ils effectuent un petit changement, gaspillant du temps sur des parties du voyage qui n'ont pas changé. Ce nouveau système mémorise les calculs pour les parties de l'itinéraire qui sont déjà confirmées. Lorsqu'il doit vérifier un nouvel arrêt, il ne calcule que la nouvelle partie, réutilisant les données stockées pour le reste. Ce simple truc a rendu le système plus de trois fois plus rapide pour évaluer les itinéraires potentiels. Lors de tests sur un ensemble standard de 100 clients, ce cache a permis au système d'évaluer les itinéraires 3,12 fois plus vite que s'il devait repartir de zéro. Sur un test plus large de 200 clients, l'accélération était de 3,08 fois.

Les chercheurs ont testé leur système contre des outils existants utilisés par les entreprises de logistique, notamment OR-Tools et PyVRP, qui sont des solveurs puissants conçus pour trouver les itinéraires les plus courts possibles. Ils ont lancé des simulations où de nouvelles commandes arrivaient constamment et où les fenêtres horaires étaient artificiellement serrées pour créer du stress. Dans ces conditions difficiles, les solveurs traditionnels prenaient presque la totalité des trois secondes autorisées pour chaque décision pour trouver une solution, et même ainsi, ils produisaient parfois des itinéraires légèrement plus courts mais qui prenaient plus de temps à calculer. Le nouveau système, en revanche, trouvait une solution valide en moins d'une demi-seconde en moyenne. Bien que les itinéraires produits soient environ 7,8 % plus longs en distance totale que ceux trouvés par les solveurs puissants, l'échange était délibéré. Dans un scénario de livraison réel, un itinéraire légèrement plus long qui est prêt instantanément est souvent plus précieux qu'un itinéraire parfait qui arrive trop tard. Le système a privilégié l'obtention d'un plan exploitable plutôt que de chercher à extraire chaque dernier kilomètre d'efficacité.

L'étude a également exploré le comportement du système sous différents niveaux de risque. Ils ont comparé une approche « équilibrée », qui pèse soigneusement le risque d'ajouter un nouvel arrêt, à une approche « agressive » qui tente d'ajouter autant d'arrêts que possible avant de vérifier. La méthode agressive a provoqué de nombreuses erreurs qui ont dû être annulées, ralentissant considérablement le système. L'approche équilibrée, qui pénalise les mouvements risqués avant même qu'ils ne soient proposés, a réduit le nombre d'erreurs et a permis au système de progresser sans encombre. Cela a confirmé que le système fonctionne mieux lorsqu'il spécule avec prudence, proposant quelques étapes à l'avance mais les vérifiant rigoureusement avant de s'engager.

Les chercheurs n'ont pas prétendu que leur système soit le meilleur pour trouver l'itinéraire le plus court possible dans un monde statique où le temps n'est pas un facteur. Ils ont explicitement déclaré que pour les problèmes où le seul objectif est de minimiser la distance et que l'ordinateur dispose de plusieurs secondes pour réfléchir, les solveurs traditionnels l'emportent encore. La valeur de ce nouveau cadre réside spécifiquement dans le monde chaotique et sous pression temporelle de la répartition dynamique. Dans ces scénarios, la capacité de se rétracter instantanément d'un conflit et de maintenir un plan valide est plus importante qu'une amélioration marginale de la distance. Le système a prouvé sa valeur en servant 100 % des clients dans les scénarios de test les plus stressants, avec zéro commande rejetée, tout en maintenant un temps de réponse suffisamment bas pour être utile à un centre de répartition en direct.

Même lorsque les chercheurs ont introduit un bruit aléatoire pour simuler des retards de trafic imprévisibles, le système a tenu bon. Il a continué à servir tous les clients et à réparer les conflits avec succès, montrant que la méthode est assez robuste pour gérer l'incertitude du monde réel. Ils ont également testé le système sur une tranche de données de livraison réelles provenant d'une grande entreprise de logistique, utilisant des coordonnées de livraison réelles. Le système a fonctionné avec succès sur ces données réelles, servant les 80 arrêts de l'ensemble de test. Cependant, les chercheurs ont pris soin de noter les limites de leur conception actuelle. Lorsqu'ils ont testé un scénario beaucoup plus vaste avec 400 clients, le système n'a pas pu trouver de solution parfaite dans le délai imparti, ne servant qu'environ les trois quarts des commandes. Cela indique que si la méthode fonctionne bien pour des flottes de taille moyenne, les opérations plus vastes nécessiteraient des stratégies supplémentaires pour diviser le problème en morceaux plus petits.

En fin de compte, ce travail démontre un changement dans notre façon de concevoir la résolution des problèmes de routage. Au lieu de voir l'ordinateur comme une calculatrice qui doit trouver la réponse unique et optimale, les chercheurs ont traité l'ordinateur comme un décideur qui doit trouver une bonne réponse rapidement. En adoptant les modèles spéculatifs utilisés dans l'intelligence artificielle moderne — rédaction, vérification et mise en cache — le système peut naviguer dans l'incertitude de la livraison dynamique avec rapidité et fiabilité. Les résultats suggèrent que pour de nombreux défis logistiques du monde réel, la capacité de s'adapter instantanément est la véritable mesure d'un système réussi. Le système ne promet pas d'éliminer tous les retards ou de trouver le chemin le plus court à chaque fois, mais il promet que lorsqu'une nouvelle commande arrive, un plan sera prêt presque immédiatement, faisant ainsi tourner les roues du réseau de livraison.