Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

Imaginez une flotte de véhicules faisant la course contre la montre pour visiter une collection dispersée de lieux, chacun offrant une récompense différente. L'objectif est simple : collecter le plus de valeur possible avant que le temps ne s'écoule. Mais le monde n'est pas un tableur. Le temps nécessaire pour accomplir une tâche en un lieu donné est incertain ; une rafale de vent soudaine peut retarder un drone, ou une mer agitée peut ralentir un bateau. De plus, chaque lieu n'est disponible que pendant une fenêtre de temps spécifique. Si un véhicule arrive trop tôt, il doit attendre ; s'il arrive trop tard, l'opportunité disparaît à jamais. C'est l'essence même d'un défi logistique complexe connu sous le nom de problème d'orientation en équipe avec fenêtres de temps. Dans le monde réel, ce scénario se produit lorsqu'une équipe de pompiers tente de contenir un incendie de forêt, que des équipes de lutte contre les marées noires font la course pour contenir une nappe avant qu'elle n'atteigne le rivage, ou que des équipes médicales doivent visiter des patients dans des délais critiques. La difficulté réside dans la capacité à prendre la décision suivante instantanément, sans savoir exactement combien de temps la tâche actuelle prendra, et sans le luxe d'un supercalculateur pour recalculer l'ensemble du plan chaque seconde.

Pendant des années, les chercheurs ont tenté de résoudre cela en apprenant aux ordinateurs à faire évoluer des règles de décision simples. Ces règles agissent comme un contrôleur de trafic, observant la situation actuelle et décidant immédiatement quel client visiter ensuite. La méthode la plus efficace jusqu'à présent, appelée NS-GP, repose sur un ensemble fixe de onze caractéristiques de base — telles que la distance d'un client ou le temps restant — pour prendre ces décisions. Bien qu'efficace, cette approche atteint un plafond. Elle utilise un vocabulaire limité pour décrire le monde, un peu comme si l'on essayait d'écrire un roman en utilisant seulement cent mots. Les chercheurs derrière cette nouvelle étude, dirigés par Augusto Mendonça et son équipe d'universités du Brésil, ont posé une question audacieuse : et si l'ordinateur pouvait apprendre un vocabulaire plus riche en observant comment un planificateur expert résout le problème hors ligne ? Ils voulaient voir s'ils pouvaient extraire la logique cachée des solutions de haute qualité et transformer ces intuitions en règles simples et lisibles qui fonctionnent en temps réel.

L'équipe a développé une nouvelle méthode appelée SI-GP, qui signifie Solver-Informed Genetic Programming (Programmation Génétique Informée par le Solveur). Le processus ne commence pas par l'ordinateur qui devine, mais par l'ordinateur qui observe. D'abord, les chercheurs ont utilisé des solveurs puissants et rapides pour trouver les meilleurs itinéraires possibles pour un ensemble de quarante problèmes de test différents, en supposant que tout se passerait parfaitement. Ils ont ensuite repris ces itinéraires parfaits et les ont rejoués dans un monde simulé où des retards se produisent de manière aléatoire, tout comme dans la réalité. En comparant les plans parfaits à ce qui s'est réellement passé, l'équipe a identifié des opérations spécifiques que les plans parfaits effectuaient mais que les règles standards manquaient. Par exemple, ils ont remarqué que les meilleurs plans regardaient souvent plusieurs étapes plus loin pour voir quelles récompenses resteraient atteignables, ou calculaient le risque de perdre une opportunité future en s'engageant dans une action actuelle.

À partir de ces observations, les chercheurs ont construit une nouvelle bibliothèque de dix-huit caractéristiques de décision. Seize d'entre elles étaient basées sur des concepts établis en planification, tandis que deux étaient des combinaisons entièrement nouvelles conçues pour peser le coût d'une décision par rapport au gain potentiel. Ce nouveau vocabulaire a donné à l'ordinateur une façon beaucoup plus nuancée de comprendre le problème. Cependant, avoir plus d'options ne signifie pas automatiquement de meilleurs résultats ; parfois, trop de choix confondent le système. Pour résoudre cela, l'équipe a utilisé une seconde couche d'intelligence pour sélectionner le meilleur sous-ensemble de ces caractéristiques pour chaque problème spécifique. Ils ont traité le processus de sélection comme un tournoi, faisant évoluer différentes combinaisons de caractéristiques et les testant rigoureusement. Cela a été rendu possible grâce à un moteur conçu sur mesure qui fonctionne sur des cartes graphiques, permettant de tester des milliers de combinaisons dans le temps qu'il fallait auparavant pour en tester une seule.

Les résultats ont été frappants. Sur les quarante problèmes de référence, la nouvelle méthode n'a jamais été moins performante que l'ancienne norme. Dans trente-huit des cas, le système a fait évoluer une nouvelle règle qui a surpassé la meilleure précédente. En moyenne, les nouvelles règles ont amélioré la récompense totale collectée de 1,0 % sur l'ensemble des tests, et de 1,3 % sur les problèmes où il restait encore de la marge de progression. Dans dix cas spécifiques, l'amélioration était statistiquement significative et suffisamment importante pour être considérée comme une avancée majeure pour ce scénario précis. Plus important encore, les nouvelles règles sont restées simples et lisibles. Elles n'étaient pas des algorithmes de type « boîte noire » que personne ne peut comprendre ; elles étaient des expressions mathématiques compactes qu'un humain pouvait lire et vérifier. Dans de nombreux cas, les nouvelles règles étaient également plus stables, produisant des résultats cohérents même lorsque les retards aléatoires variaient, alors que les anciennes règles oscillaient parfois violemment entre de bons et de mauvais résultats.

L'étude a également révélé pourquoi ces améliorations se sont produites. Les nouvelles règles étaient particulièrement efficaces dans les situations où le système de base peinait à visiter tous les clients possibles. Dans ces scénarios « non saturés », le nouveau vocabulaire a permis au système de naviguer à travers des compromis complexes, comme visiter un client éloigné à haute valeur même si cela signifiait sauter un client proche à faible valeur. Les chercheurs ont découvert que les nouvelles caractéristiques aidaient le système à régulariser sa recherche, ce qui signifie qu'il était moins susceptible de rester coincé dans un piège local et plus susceptible de trouver un chemin robuste. La méthode a fonctionné en apprenant de la structure des solutions de haute qualité sans simplement les copier. Elle n'a pas essayé de mimer l'itinéraire exact du planificateur expert ; elle a plutôt appris les principes qui rendaient ces itinéraires fructueux et les a appliqués à un nouvel environnement incertain.

Ce travail démontre qu'il est possible de combler le fossé entre l'optimisation complexe hors ligne et la prise de décision rapide en ligne. En utilisant les enseignements de solveurs de haute qualité pour construire un meilleur vocabulaire, et en sélectionnant soigneusement les bons outils pour chaque tâche spécifique, les chercheurs ont créé un système qui est à la fois puissant et transparent. Le produit final est un ensemble de règles de décision qui peuvent être intégrées directement dans des véhicules ou des drones, permettant à ces derniers de faire des choix intelligents en quelques microsecondes sans avoir besoin de se connecter à un ordinateur central ou de lancer des simulations complexes. Cette approche suggère une nouvelle voie pour l'intelligence artificielle en logistique : une voie qui valorise l'interprétabilité et l'adaptabilité, garantissant que les machines prenant des décisions critiques puissent être comprises par les humains qui comptent sur elles. Les chercheurs ont rendu leur code, leurs données et les règles spécifiques qu'ils ont découvertes accessibles au public, invitant d'autres personnes à bâtir sur ce fondement pour de futurs défis dans des environnements incertains.