Un algorithme d’ordonnancement par apprentissage par renforcement multi-agent intégrant la modélisation structurelle du graphe d’état et du graphe de tâches pour la répartition en covoiturage

Pourquoi un covoiturage plus intelligent compte pour la vie urbaine

Quiconque a attendu trop longtemps une voiture de VTC ou vu des véhicules vides passer devant des coins encombrés sait combien il est difficile de coordonner le transport urbain en temps réel. Cette étude présente un nouveau système de répartition basé sur l’IA conçu pour mettre en relation passagers et véhicules de covoiturage plus rapidement et efficacement, réduisant les distances inutiles et raccourcissant les temps d’attente dans un trafic urbain dense et en rapide évolution.

Des appariements simples au trafic urbain embrouillé

Le VTC est parti d’une idée simple : un conducteur, un passager, un trajet. Les rues d’aujourd’hui ont radicalement changé. Les plateformes gèrent des milliers de véhicules et de passagers simultanément, souvent en regroupant plusieurs usagers dans le même véhicule et en routant des flottes à travers des arrondissements entiers. La demande est inégale — le centre-ville peut être submergé de demandes tandis qu’un autre secteur reste calme — et tout change minute après minute. Les règles de dispatching traditionnelles ou les stratégies simples du type « voiture la plus proche » peinent dans ce contexte, entraînant de longues attentes, une faible utilisation des véhicules et des détours inutiles. La figure

Deux cartes connectées au lieu d’un grand flou

Les auteurs proposent un nouveau cadre appelé DualG-MARL qui traite le problème de répartition comme deux cartes qui se chevauchent. Une carte décrit les véhicules : où ils se trouvent, combien de places ils ont et s’ils sont libres ou déjà occupés. L’autre carte décrit les demandes de trajet : qui veut voyager, d’où, vers où et à quel moment. Chaque carte est modélisée comme un graphe, où les points représentent des véhicules ou des demandes et les arêtes relient ceux qui sont proches en espace et en temps. En conservant les informations des véhicules et des passagers dans des graphes séparés mais liés, le système préserve la structure de chaque côté au lieu de tout mélanger en une image confuse.

Comment l’IA apprend à apparier passagers et voitures

Au-dessus de ces graphes jumeaux, le système utilise une classe de méthodes d’apprentissage automatique connues sous le nom d’apprentissage par renforcement multi-agent. Chaque véhicule est traité comme un décideur indépendant, ou « agent », qui choisit parmi les demandes à proximité. Les agents partagent un objectif commun : réduire les temps d’attente, éviter les détours excessifs et maintenir les véhicules occupés de manière productive. Le modèle parcourt les deux graphes pour extraire des motifs, puis utilise un mécanisme d’attention — un outil d’IA qui met en évidence les connexions les plus pertinentes — pour lier voitures et passagers adaptés entre les deux cartes. Pour conserver des décisions rapides et stables, il ne considère pas toutes les paires possibles. À la place, il constitue une liste restreinte des meilleurs candidats pour chaque véhicule (l’ensemble Top-K), filtrée par des règles strictes comme la capacité en sièges, le délai de prise en charge et la longueur de détour acceptable. Un apprenant centralisé évalue la performance de l’ensemble de la flotte, tandis que les véhicules individuels suivent des règles locales simples en exploitation temps réel. La figure

Tester le système sur des trajets réels de New York

Les chercheurs ont testé DualG-MARL sur des données de trajets à grande échelle de la Taxi and Limousine Commission de New York, en se concentrant sur Manhattan et Queens. Ils ont comparé leur méthode à une gamme d’approches existantes, incluant des règles manuelles, de l’optimisation mathématique et des répartiteurs avancés basés sur l’apprentissage tels que CoopRide. Dans les deux arrondissements, le nouveau système a établi de nouveaux standards sur quatre mesures clés : il a réduit le temps moyen d’attente des passagers avant prise en charge, augmenté la proportion de demandes de trajet effectivement servies, accru la part du temps pendant lequel les véhicules transportaient des clients et réduit légèrement la distance supplémentaire induite par le partage. Fait important, ces gains ont été obtenus sans explosion des coûts de calcul : en limitant l’attention à un ensemble sélectionné de correspondances prometteuses, la méthode est restée assez rapide pour une utilisation en temps réel.

Ce que cela signifie pour les passagers et les villes au quotidien

En termes simples, l’étude montre que représenter le système de VTC d’une ville comme deux réseaux structurés — l’un pour les véhicules et l’autre pour les passagers — et les faire interagir via un processus d’apprentissage soigneusement conçu peut rendre le covoiturage plus intelligent et plus réactif. Pour les passagers, cela se traduit par des attentes plus courtes et des prises en charge plus fiables ; pour les conducteurs et les plateformes, par une meilleure utilisation des véhicules et moins de trajets à vide ; et pour les villes, cela suggère un avenir où les routes existantes peuvent déplacer davantage de personnes avec moins de voitures et moins de congestion. Les auteurs suggèrent que des idées similaires basées sur les graphes et le multi-agent pourraient éventuellement s’étendre à d’autres services, des flottes de taxis autonomes à la réponse d’urgence, offrant une manière plus ordonnée de gérer les flux complexes et changeants de la vie urbaine moderne.

Citation: Sha, J., Song, M., Sui, G. et al. A multi-agent reinforcement learning scheduling algorithm integrating state graph and task graph structural modeling for ride-sharing dispatching. Sci Rep 16, 5461 (2026). https://doi.org/10.1038/s41598-026-35004-8

Mots-clés: répartition en covoiturage, apprentissage par renforcement multi-agent, réseaux de neurones graphiques, mobilité urbaine, mise en correspondance dynamique