💻 computer science

Randomized routing strategies of fleets of CAVs may prove market efficient

Cet article soutient que, bien que les stratégies de routage aléatoires pour les flottes concurrentes de CAV puissent surpasser le routage optimal traditionnel dans divers environnements de trafic, la conception du marché doit être modifiée pour équilibrer les incitations de part de marché avec les objectifs de temps de trajet à l'échelle du système afin de prévenir les comportements antisociaux et d'assurer le bien-être social.

Auteurs originaux : Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski

Publié 2026-07-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez une ville où les feux de signalisation ne sont plus la seule chose qui décide de qui reste coincé dans un embouteillage. Imaginez plutôt un futur où chaque voiture est soit conduite par un humain, soit pilotée par un ordinateur super intelligent. Maintenant, imaginez que ces voitures pilotées par ordinateur n'appartiennent pas à une seule entreprise géante, mais à un groupe de différentes entreprises de « flottes » qui se font concurrence pour votre clientèle. C'est le monde des Véhicules Connectés et Autonomes (VCA). La grande question que les scientifiques se posent n'est pas seulement « Ces voitures peuvent-elles conduire ? », mais plutôt « Comment faire pour qu'elles ne transforment pas nos rues en un chaos total tout en luttant pour gagner des clients ? »

Pour comprendre le problème, nous avons besoin de deux idées simples. Premièrement, pensez à l'Équilibre de l'Utilisateur comme à une partie de chaises musicales où tout le monde essaie de saisir le siège le plus rapide pour soi-même. Si tout le monde fait cela, l'itinéraire « rapide » devient encombré, et soudain, plus personne n'est rapide. Deuxièmement, pensez à l'Optimum du Système comme à un chef d'orchestre, qui dit à chacun exactement quand jouer pour que toute la symphonie soit parfaite, même si cela signifie que certains musiciens doivent attendre leur tour. L'article explore ce qui se passe lorsque ces entreprises de flottes essaient de gagner votre clientèle : agissent-elles comme des joueurs égoïstes essayant de saisir les meilleurs sièges, ou agissent-elles comme des chefs d'orchestre ? Et si elles commençaient à jouer des tours pour confondre les conducteurs humains ?

Cet article, écrit par des chercheurs de l'Université Jagellonienne en Pologne, se plonge dans une expérience de pensée sauvage : et si ces entreprises de flottes étaient payées uniquement sur la base du nombre de personnes utilisant leur service (part de marché), plutôt que de vous facturer des frais ? Dans ce monde « sans frais », les entreprises ont un énorme intérêt à voler autant de conducteurs que possible. Les auteurs ont mis en place une simulation numérique — une ville virtuelle avec 200 conducteurs et deux routes parallèles — pour tester différentes stratégies. Ils ont découvert que si une entreprise de flotte veut gagner, la tactique la plus efficace est en réalité d'être un peu imprévisible.

Les chercheurs ont découvert que lorsque les opérateurs de flottes utilisent le routage aléatoire, ils peuvent piéger les conducteurs humains indépendants (CHI) pour les inciter à rester hors des routes. Voici comment cela fonctionne : si une flotte dit à ses conducteurs : « Hé, nous prendrons toujours l'itinéraire le plus rapide », les conducteurs humains comprendront rapidement quel est cet itinéraire et l'encombreront, faisant ainsi mauvaise réputation à la flotte. Mais si la flotte répartit ses conducteurs de manière aléatoire entre les deux routes chaque jour, les conducteurs humains ne peuvent pas prédire quel itineraire sera rapide. Cette incertitude fait que les conducteurs humains ont l'impression de jouer un jeu perdant, et finissent donc par abandonner pour rejoindre la flotte. Dans les simulations, ces stratégies « aléatoires » étaient étonnamment efficaces pour gagner des parts de marché, plus performantes même que les stratégies « parfaitement organisées » qui tentent de minimiser le temps de trajet total pour tout le monde.

Cependant, il y a un bémol. Si la randomisation est excellente pour l'entreprise de flotte qui cherche à gagner des clients, elle est terrible pour la ville. Les simulations ont montré que lorsque les flottes utilisent ces tours imprévisibles, le temps de trajet moyen pour tout le monde augmente et le trafic devient extrêmement instable. C'est comme un jeu où un joueur gagne en secouant tellement la table que plus personne ne peut manger sa nourriture. L'article soutient que si les villes veulent éviter ce chaos, elles ne peuvent pas simplement laisser le marché agir sans limites. Elles doivent changer les règles du jeu.

Les auteurs suggèrent une solution astucieuse : payer les entreprises de flottes sur la base d'un mélange de deux choses. Premièrement, payez-les pour le nombre de clients qu'elles ont (part de marché). Deuxièmement, payez-les pour la proximité du flux « parfait » (Optimum du Système). Dans leurs simulations, lorsque nous avons ajouté cette seconde règle, les entreprises ont cessé d'utiliser les tactiques aléatoires chaotiques. Elles ont réalisé qu'être trop imprévisibles nuisait à leur score, et elles sont donc passées à des stratégies plus coopératives et efficaces. L'article suggère qu'en ajustant la manière dont les entreprises sont récompensées, les villes peuvent encourager la compétition sans laisser le trafic devenir incontrôlable.

L'étude repose entièrement sur des simulations informatiques, et non sur des tests de conduite en conditions réelles, de sorte que bien que les résultats soient prometteurs, il ne s'agit que d'un modèle de ce qui pourrait arriver. Les chercheurs ont constaté que dans un monde avec seulement deux routes et 200 conducteurs, le routage aléatoire est une arme puissante pour la part de marché, mais cela se fait au détriment de l'efficacité. Ils concluent que l'avenir de la conduite autonome ne dépendra pas seulement de meilleurs logiciels, mais de la conception des bons incitations économiques pour maintenir l'ensemble du système fluide.

Résumé technique : Stratégies de routage aléatoires des flottes de CAV

Énoncé du problème

L'article traite du défi de la conception d'une structure de marché équitable, efficace et compétitive pour les opérations urbaines de véhicules connectés et autonomes (CAV). Dans un scénario futur où chaque conducteur possède un véhicule pouvant être soit conduit de manière indépendante (HDV), soit routé de manière autonome par des opérateurs de flottes concurrents, les auteurs étudient comment aligner les incitations du marché avec les objectifs de la ville.

La variante spécifique du marché étudiée suppose un modèle « sans frais » où les opérateurs de flottes sont rémunérés collectivement à partir de taxes de circulation proportionnelles à leur part de marché (nombre d'utilisateurs), plutôt que par des frais d'abonnement ou des paiements directs des utilisateurs. Le problème central est de déterminer quels algorithmes de routage les opérateurs de flottes adopteront pour maximiser leur part de marché et si ces stratégies s'alignent sur le bien-être social (minimisation du temps de trajet de l'ensemble du système). Les auteurs émettent l'hypothèse que dans un environnement compétitif avec des attitudes de conducteurs diverses, les opérateurs peuvent adopter des stratégies « antisociales » — spécifiquement le routage aléatoire — qui augmentent la part de marché au détriment de l'efficacité du système et de la prévisibilité pour les conducteurs indépendants.

Méthodologie

Dynamique du système et cadre de simulation

Les auteurs proposent un cadre de référence simulant un jeu avec $N_D$ conducteurs et $N_{FLEET}$ opérateurs sur un nombre fixe de jours. Le système se compose d'une seule paire Origine-Destination (OD) avec des itinéraires parallèles. La dynamique quotidienne se déroule séquentiellement :

Offres : Chaque opérateur de flotte $f$ génère un vecteur d'offre de temps de trajet $O_{i,j}^f$ pour chaque conducteur $i$ basé sur un algorithme spécifique.
Choix du mode : Les conducteurs décident de rester indépendants (HDV) ou de rejoindre une flotte spécifique en fonction de leur expérience de trajet passée, de l'offre actuelle et d'un « facteur de remise » ( $\gamma$ ) personnel représentant leur attitude envers cette flotte.
Routage : Une fois que les conducteurs se sont engagés dans un mode, les flottes routent leurs membres. Les conducteurs indépendants choisissent des itinéraires en utilisant un modèle logit minimisant la désutilité.
Simulation : Une journée de voyage est simulée en utilisant la fonction de Bureau of Public Roads (BPR) pour calculer les temps de trajet des itinéraires en fonction de la congestion.
Mise à jour de la crédibilité : La crédibilité de la flotte est mise à jour sur la base du rapport entre le temps de trajet offert et le temps de trajet réellement expérimenté.

Modélisation du comportement humain

Les conducteurs sont modélisés avec des attitudes hétérogènes envers les CAV. Chaque conducteur $i$ possède un facteur de remise $\gamma_{i}^{F,f}$ pour la flotte $f$ , décomposé en une préférence générale pour les AV et une composante spécifique à la flotte. Ces facteurs sont tirés de distributions gaussiennes. Les conducteurs choisissent le mode (HDV ou une flotte spécifique) qui minimise leur désutilité, laquelle est une fonction du temps de trajet offert, du facteur de remise et de la crédibilité de la flotte. Les conducteurs indépendants sélectionnent des itinéraires de manière probabiliste en utilisant un modèle logit avec un paramètre $\beta=0,2$ .

Algorithmes de routage

Le document introduit et compare quatre principales stratégies algorithmiques pour les opérateurs de flottes :

SO Proportionnel (Optimum du Système) : Route les conducteurs pour atteindre l'écoulement de l'optimum du système, offrant le temps de trajet moyen du SO. Il utilise une alternance aléatoire pour répartir les conducteurs proportionnellement au flux optimal.
UE Proportionnel (Équilibre de l'Utilisateur) : Route les conducteurs pour atteindre les flux d'équilibre de l'utilisateur.
RFlexV (Version de la Flexibilité Aléatoire) : Une heuristique conçue pour maximiser la part de marché en introduisant de l'incertitude. Elle randomise délibérément les affectations de routes pour rendre difficile la prédiction de l'itinéraire le plus rapide par les conducteurs indépendants, les incitant ainsi à passer à la flotte. Elle donne la priorité au maintien de la satisfaction des membres actuels tout en maximisant le « malheur » des potentiels défecteurs.
RFlex (Flexibilité Aléatoire) : Une extension de RFlexV qui calcule de manière adaptative la part minimale de temps qu'un conducteur doit passer sur l'itinéraire le plus rapide pour rester satisfait, optimisant l'affectation pour conserver les clients avec une perte d'efficacité minimale.

L'étude teste également des variantes où les flottes offrent des temps de trajet irréalistement courts (par exemple, $0,5 \times$ le temps SO) pour attirer les utilisateurs initialement.

Contributions clés

Cadre de référence : Les auteurs introduisent un cadre de simulation dynamique pour comparer les algorithmes de routage dans un marché de CAV compétitif où les revenus sont liés à la part de marché.
Démonstration de la supériorité du hasard : L'article démontre expérimentalement que les algorithmes de routage aléatoires (RFlexV et RFlex) sont strictement supérieurs aux algorithmes de référence non aléatoires (SO et UE) en termes d'acquisition de parts de marché, particulièrement lorsque les attitudes des conducteurs sont diverses.
Identification des équilibres antisocials : L'étude révèle que les stratégies de randomisation créent un scénario de « dilemme du prisonnier » où, si une flotte adopte la randomisation, les autres doivent suivre pour rester compétitives, entraînant une grande variabilité et une augmentation des temps de trajet de l'ensemble du système.
Proposition de conception de marché : Les auteurs proposent une fonction objectif modifiée pour les opérateurs de flottes qui combine la maximisation de la part de marché avec la minimisation du temps de trajet moyen du système. Ils montrent qu'augmenter la fonction par une pénalité de temps de trajet (paramètre $\mu$ ) peut efficacement décourager les stratégies de randomisation et conduire le marché vers une coopération orientée vers le bien-être social sans éliminer la compétition.

Résultats

Part de marché vs Efficacité : Dans les scénarios où le seul objectif est la maximisation de la part de marché ( $\mu=0$ ), les algorithmes aléatoires (RFlexV-, RFlex-) surpassent les algorithmes d'Optimum du Système (SO-). Ils attirent avec succès des conducteurs qui resteraient autrement indépendants ou choisiraient d'autres flottes, même ceux ayant des facteurs de remise élevés (scepticisme envers les AV).
Instabilité du système : L'adoption de stratégies de randomisation entraîne des fluctuations significatives des temps de trajet et une augmentation du temps de trajet moyen du système. Lorsque deux flottes utilisent des stratégies de randomisation, le système présente une variance élevée par rapport à la stabilité du routage SO.
Dynamique compétitive : Si une flotte utilise un algorithme de randomisation, un concurrent utilisant un algorithme SO standard perd en compétitivité et est contraint de passer à une stratégie de randomisation pour survivre.
Impact de la fonction objectif : Lorsque la fonction objectif est modifiée pour inclure une pénalité pour l'augmentation du temps de trajet (augmentation de $\mu$ ), la performance des algorithmes de randomisation se dégrade. À $\mu \approx 0,5$ , l'algorithme basé sur le SO redevient compétitif, et l'incitation à utiliser des stratégies de randomisation antisociales est supprimée. Le système converge vers un état avec une variance de temps de trajet plus faible et un meilleur bien-être social.

Signification et affirmations

L'article prétend fournir une analyse fondamentale du marché émergent des flottes de CAV routées collectivement. Sa principale importance réside dans l'identification du fait que la rémunération basée uniquement sur la part de marché crée des incitations pour que les opérateurs adoptent des stratégies de routage aléatoires qui sont efficaces pour l'opérateur mais préjudiciables au flux de trafic global de la ville.

Les auteurs soutiennent que le routage aléatoire est une réponse rationnelle à la compétition du marché sous les hypothèses actuelles, mais qu'il n'est pas aligné avec les objectifs de la ville. Ils proposent que les autorités municipales puissent façonner ce marché en ajustant le schéma de rémunération pour inclure une composante basée sur le temps de trajet du système global. Cet ajustement est affirmé comme étant suffisant pour « conduire la compétition vers une coopération orientée vers le bien-être social » et limiter les stratégies antisociales sans détruire la nature compétitive du marché.

L'article conclut modestement, notant que ces conclusions sont basées sur un benchmark simplifié (deux itinéraires, facteurs de remise connus) et que les travaux futurs impliqueront des scénarios plus complexes, des algorithmes basés sur l'apprentissage automatique et des simulations à l'échelle d'une ville réaliste (par exemple, SUMO).