KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering

Imaginez que vous soyez le répartiteur d'une flotte de camions de livraison dans une ville trépidante. Votre objectif est simple : livrer les colis aux clients et renvoyer les chauffeurs chez eux le plus rapidement possible pour économiser sur les salaires. Mais il y a un piège : la ville est vivante. Une route qui prend dix minutes à 8h00 pourrait en prendre quarante à 9h00 à cause des heures de pointe. C'est le monde de la Tournée de Véhicules Dépendante du Temps. C'est un casse-tête classique dans le domaine de la Recherche Opérationnelle, qui est essentiellement la science de la prise de décision optimale lorsque l'on dispose de ressources limitées et de règles complexes.

Pendant des décennies, les ordinateurs ont été excellents pour résoudre ces énigmes, mais généralement avec une simplification majeure : ils prétendent que le trafic est statique, comme une carte où les routes ne changent jamais. La vie réelle, cependant, est un fleuve qui coule, pas un étang immobile. Pour résoudre l'énigme parfaitement, vous devez savoir exactement quand un camion quitte le dépôt, car partir cinq minutes plus tard pourrait signifier heurter un embouteillage qui ajouterait une heure au trajet, ou cela pourrait signifier éviter un feu rouge qui économiserait dix minutes. Le défi est que les mathématiques pour déterminer le temps de départ "parfait" pour chaque camion, tout en respectant les fenêtres horaires des clients et les modèles de trafic, sont incroyablement difficiles. C'est comme essayer de résoudre un Rubik's Cube dont les couleurs changent de place à chaque fois que vous tournez les faces.

C'est ici qu'entre en scène un nouvel outil appelé KAYROS. Considérez KAYROS comme un sorcier du trafic super intelligent et infatigable qui ne se contente pas de deviner ; il calcule le meilleur emploi du temps possible. Mais voici le tour de magie : il ne vous donne pas seulement une réponse "assez bonne" après avoir attendu une heure. Il commence à donner des réponses de mieux en mieux meilleures dès la première seconde où il commence à réfléchir, et si vous l'arrêtez, il vous donne la meilleure solution qu'il ait trouvée jusqu'à présent. Plus cool encore, il peut prouver qu'une solution est mathématiquement parfaite, et non une simple chance. Le document présente également un nouvel ensemble massif de puzzles d'entraînement appelé Poryos2026, construit à partir de véritables cartes urbaines, pour tester si ces sorciers sont réellement doués dans leur travail.

La Magie de KAYROS : Un Solveur qui ne Dort Jamais

Le document présente KAYROS, un outil logiciel open-source conçu pour résoudre le "Problème de la Tournée de Véhicules Dépendante du Temps". Imaginez que vous essayez de planifier un voyage routier pour une flotte de chauffeurs de livraison. Vous avez une liste d'arrêts, et chaque arrêt a une fenêtre de temps spécifique où le client est présent (ex. : "Vous ne pouvez livrer le colis qu'entre 14h00 et 16h00"). La partie délicate est que le temps de trajet entre les arrêts change en fonction de l'heure à laquelle vous partez.

KAYROS est spécial car il fait deux choses à la fois, une combinaison rare dans le monde des solveurs informatiques :

1. Il est "Anytime" (en tout temps) : Quand vous lancez KAYROS, il ne reste pas silencieux pendant des heures. Il commence immédiatement à produire des solutions. La première peut être correcte, la suivante est meilleure, et la suivante est encore meilleure. C'est comme un chef qui goûte une soupe et y ajoute des épices continuellement ; vous pouvez arrêter la cuisson à n'importe quel moment, et vous aurez la meilleure soupe possible pour ce temps imparti.
2. Il est "Exact" : Si vous le laissez tourner assez longtemps, il ne se contente pas de deviner la meilleure réponse ; il prouve qu'elle est la meilleure possible. Il génère un "certificat", qui est comme un reçu mathématique que n'importe qui peut vérifier pour confirmer qu'aucun autre itinéraire ne pourrait être plus rapide.

Les auteurs ont construit cet outil pour qu'il soit totalement gratuit et ouvert. Vous pouvez l'installer avec une seule commande sur votre ordinateur, et il ne nécessite aucun logiciel coûteux et secret appartenant à de grandes entreprises. Il utilise un moteur ingénieux qui traite le temps de trajet non pas comme un chiffre unique, mais comme une fonction de flux — une ligne qui monte et descend selon l'heure de la journée. Cela lui permet de gérer des modèles de trafic complexes du monde réel où une route peut soudainement s'engorger à une minute précise.

L'Histoire de l'"Auto-Réfutation" : Comment ils ont attrapé leur propre erreur

L'une des parties les plus fascinantes du document est une histoire d'honnêteté. Les auteurs voulaient s'assurer que leurs certificats "parfaits" étaient réellement parfaits. Ils ont établi une règle stricte : pour affirmer qu'une solution est la meilleure, quatre exécutions informatiques différentes doivent toutes s'accorder sur la même réponse exacte.

Lors d'un test, ils ont trouvé un problème. KAYROS avait émis 160 "certificats" affirmant que certains itinéraires étaient les meilleurs possibles. Mais ensuite, leur propre solveur "anytime" (celui qui continue de s'améliorer) a trouvé des itinéraires qui étaient en fait plus rapides que ces certificats "parfaits" ! Ce fut un choc. Il s'est avéré que KAYROS utilisait une astuce de "lissage" pour gérer les sauts soudains dans les données de trafic (comme une route qui devient instantanément un parking). Cette astuce était légèrement erronée, causant un mauvais calcul du temps.

Les auteurs n'ont pas caché cela. Ils ont publiquement rétracté les 160 certificats, corrigé le code pour gérer ces "sauts" de manière exacte, et relancé les tests. Cette histoire est incluse pour montrer que leur système est robuste : même quand l'IA commet une erreur, les règles de vérification la détectent, et la vérité l'emporte.

Le Nouveau Terrain de Jeu : Poryos2026

Pour tester si KAYROS fonctionne vraiment, les auteurs avaient besoin d'un terrain de jeu qui ressemble au monde réel. Ils ont créé Poryos2026, une famille de 1 080 nouveaux puzzles de test. Au lieu d'utiliser des cartes fictives et inventées, ils ont extrait de véritables réseaux routiers de cinq grandes villes : Lyon, Paris, San Francisco, Hong Kong et Tokyo, en utilisant les données d'OpenStreetMap (une carte gratuite et communautaire).

Ils ont ensuite ajouté du trafic synthétique (factice mais réaliste), des demandes de clients et des fenêtres de temps à ces cartes réelles. Cela a créé un ensemble massif de défis qui mélangent la géographie réelle avec des scénarios de trafic contrôlés. Pour chacun de ces 1 080 puzzles, ils ont généré une "meilleure solution connue" en utilisant leur propre solveur. Cela offre aux autres chercheurs un moyen équitable et réaliste de tester leurs propres outils contre un standard qui reflète la conduite urbaine réelle, et non de simples problèmes mathématiques abstraits.

L'Équipe Humaine et l'IA

La partie la plus unique de ce document est sans doute la façon dont il a été écrit. L'auteur, un étudiant en doctorat, a travaillé dans une collaboration intense avec un agent IA (un grand modèle de langage) pendant environ deux semaines. L'humain fixait les objectifs, prenait les décisions majeures et vérifiait le travail, tandis que l'IA faisait le gros du travail : écrire du code, lancer des milliers d'expériences informatiques et déboguer des erreurs.

L'auteur estime que cette collaboration de deux semaines a accompli le travail qui lui aurait pris deux ans ou plus seul. Cependant, le papier note très prudemment qu'il ne s'agissait pas simplement de "taper plus vite". L'humain devait passer beaucoup de temps à préparer l'IA avec le bon contexte, à vérifier son travail et à s'assurer que les résultats étaient scientifiquement valables. Le document soutient que ce genre de partenariat est l'avenir de la recherche, mais seulement s'il existe des règles strictes (comme le système de "certificat") pour vérifier que l'IA n'a pas inventé de faits ou halluciné des résultats.

Ce que cela signifie pour l'avenir

Le document ne prétend pas que KAYROS est le solveur le plus rapide au monde (ils ne l'ont pas encore comparé tête à tête avec tous les autres outils), ni qu'il a résolu tous les problèmes de tournée possibles. Au lieu de cela, il propose un outil solide, vérifié et gratuit qui apporte enfin la résolution "exacte" et "anytime" aux problèmes complexes de trafic dépendant du temps.

En combinant un nouveau solveur puissant, un nouvel ensemble massif de cas de test du monde réel et une histoire transparente sur la façon dont les humains et l'IA peuvent travailler ensemble de manière responsable, les auteurs ont fourni un nouveau fondement à la logistique. Qu'il s'agisse de livrer des pizzas, de gérer des camions de collecte d'ordures ou de planifier des itinéraires d'intervention d'urgence, la capacité de calculer le temps de départ parfait, tout en sachant que l'on peut s'arrêter et obtenir une bonne réponse à tout moment, est une étape significative dans la science du déplacement des choses dans notre monde trépidant.