💻 computer science

Randomized routing strategies of fleets of CAVs may prove market efficient

This paper argues that while randomized routing strategies for competing CAV fleets can outperform traditional optimal routing in diverse traffic environments, the market design must be modified to balance market-share incentives with system-wide travel time goals to prevent antisocial behavior and ensure social welfare.

Original authors: Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski

Published 2026-07-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city where the traffic lights are no longer the only thing deciding who gets stuck in a jam. Instead, imagine a future where every car is either driven by a human or piloted by a super-smart computer. Now, picture that these computer-driven cars don't belong to just one giant company, but to a bunch of different "fleet" companies competing for your business. This is the world of Connected and Autonomous Vehicles (CAVs). The big question scientists are asking isn't just "Can these cars drive?" but "How do we make sure they don't turn our streets into a chaotic mess while fighting for customers?"

To understand the problem, we need two simple ideas. First, think of User Equilibrium like a game of musical chairs where everyone tries to grab the fastest seat for themselves. If everyone does this, the "fast" route gets crowded, and suddenly, no one is fast. Second, think of System Optimum as a conductor in an orchestra, telling everyone exactly when to play so the whole symphony sounds perfect, even if it means some individual musicians have to wait their turn. The paper explores what happens when these fleet companies try to win your business: do they act like selfish players grabbing the best seats, or do they act like conductors? And what if they start playing tricks to confuse the human drivers?

This paper, written by researchers from Jagiellonian University in Poland, dives into a wild thought experiment: What if these fleet companies get paid based only on how many people use their service (market share), rather than charging you a fee? In this "fee-free" world, the companies have a huge incentive to steal as many drivers as possible. The authors set up a digital simulation—a virtual city with 200 drivers and two parallel roads—to test different strategies. They found that if a fleet company wants to win, the most effective tactic is actually to be a little bit unpredictable.

The researchers discovered that when fleet operators use randomized routing, they can trick independent human drivers (HDVs) into staying off the roads. Here's how it works: If a fleet tells its drivers, "Hey, we'll always take the fastest route," the human drivers will quickly figure out which route that is and jam it up, making the fleet look bad. But if the fleet randomly shuffles its drivers between the two roads every day, the human drivers can't predict which route will be fast. This uncertainty makes the human drivers feel like they are playing a losing game, so they eventually give up and join the fleet. In the simulations, these "randomized" strategies were surprisingly good at grabbing market share, even better than the "perfectly organized" strategies that try to minimize total travel time for everyone.

However, there's a catch. While randomization is great for the fleet company trying to win customers, it's terrible for the city. The simulations showed that when fleets use these unpredictable tricks, the average travel time for everyone goes up, and the traffic becomes wildly unstable. It's like a game where one player wins by shaking the table so much that no one can eat their food. The paper argues that if cities want to avoid this chaos, they can't just let the market run wild. They need to change the rules of the game.

The authors suggest a clever fix: pay the fleet companies based on a mix of two things. First, pay them for how many customers they have (market share). Second, pay them for how close the traffic is to the "perfect" flow (System Optimum). In their simulations, when they added this second rule, the companies stopped using the chaotic random tricks. They realized that being too unpredictable hurt their score, so they switched to more cooperative, efficient strategies. The paper suggests that by tweaking how companies are rewarded, cities can encourage competition without letting the traffic spiral out of control.

The study is based entirely on computer simulations, not real-world driving tests, so while the results are promising, they are still just a model of what could happen. The researchers found that in a world with just two roads and 200 drivers, randomized routing is a powerful weapon for market share, but it comes at the cost of efficiency. They conclude that the future of autonomous driving won't just depend on better software, but on designing the right economic incentives to keep the whole system moving smoothly.

Technical Summary: Randomized Routing Strategies of Fleets of CAVs

Problem Statement

The paper addresses the challenge of designing a fair, efficient, and competitive market structure for urban Connected and Autonomous Vehicle (CAV) operations. In a future scenario where every driver owns a vehicle that can be either independently driven (HDV) or autonomously routed by competing fleet operators, the authors investigate how to align market incentives with city goals.

The specific market variant studied assumes a "fee-free" model where fleet operators are remunerated collectively from traffic taxes proportional to their market share (number of users), rather than through subscription fees or direct user payments. The core problem is determining which routing algorithms fleet operators will adopt to maximize market share and whether these strategies align with social welfare (minimizing system-wide travel time). The authors hypothesize that in a competitive environment with diverse driver attitudes, operators may adopt "antisocial" strategies—specifically randomized routing—that increase market share at the cost of system efficiency and unpredictability for independent drivers.

Methodology

System Dynamics and Simulation Framework

The authors propose a benchmark framework simulating a game with $N_D$ drivers and $N_{FLEET}$ operators over a fixed number of days. The system consists of one Origin-Destination (OD) pair with parallel routes. The daily dynamics proceed sequentially:

Offers: Each fleet operator $f$ generates a travel time offer vector $O_{i,j}^f$ for every driver $i$ based on a specific algorithm.
Mode Choice: Drivers decide whether to remain independent (HDV) or join a specific fleet based on past travel experience, the current offer, and a personal "discount factor" ( $\gamma$ ) representing their attitude toward that fleet.
Routing: Once drivers commit to a mode, fleets route their members. Independent drivers choose routes based on a logit model minimizing disutility.
Simulation: A day of travel is simulated using the Bureau of Public Roads (BPR) function to calculate route travel times based on congestion.
Credibility Update: Fleet credibility is updated based on the ratio of offered travel time to actual experienced travel time.

Human Behavior Modeling

Drivers are modeled with heterogeneous attitudes toward CAVs. Each driver $i$ has a discount factor $\gamma_{i}^{F,f}$ for fleet $f$ , decomposed into a general preference for AVs and a fleet-specific component. These factors are drawn from Gaussian distributions. Drivers choose the mode (HDV or a specific fleet) that minimizes their disutility, which is a function of the offered travel time, the discount factor, and the fleet's credibility. Independent drivers select routes probabilistically using a logit model with parameter $\beta=0.2$ .

Routing Algorithms

The paper introduces and compares four main algorithmic strategies for fleet operators:

Proportional SO (System Optimum): Routes drivers to achieve the system optimum flow, offering the average SO travel time. It uses random turn-taking to split drivers proportionally to the optimal flow.
Proportional UE (User Equilibrium): Routes drivers to achieve user equilibrium flows.
RFlexV (Randomized Flexibility - Version): A heuristic designed to maximize market share by introducing uncertainty. It deliberately randomizes route assignments to make it difficult for independent drivers to predict the fastest route, thereby coaxing them to switch to the fleet. It prioritizes keeping current members happy while maximizing the "unhappiness" of potential defectors.
RFlex (Randomized Flexibility): An extension of RFlexV that adaptively calculates the minimum share of time a driver needs to be on the faster route to remain satisfied, optimizing the assignment to retain customers with minimal efficiency loss.

The study also tests variants where fleets offer unrealistically short travel times (e.g., $0.5 \times$ SO time) to attract users initially.

Key Contributions

Benchmark Framework: The authors introduce a dynamic simulation framework for comparing routing algorithms in a competitive CAV market where revenue is tied to market share.
Demonstration of Randomized Superiority: The paper experimentally demonstrates that randomized routing algorithms (RFlexV and RFlex) are strictly superior to non-randomized baseline algorithms (SO and UE) in terms of market share acquisition, particularly when driver attitudes are diverse.
Identification of Antisocial Equilibria: The study reveals that randomized strategies create a "prisoner's dilemma" scenario where, if one fleet adopts randomization, others must follow to remain competitive, leading to highly variable and increased system-wide travel times.
Market Design Proposal: The authors propose a modified objective function for fleet operators that combines market share maximization with the minimization of mean system-wide travel time. They show that augmenting the objective with a travel time penalty (parameter $\mu$ ) can effectively discourage randomized strategies and drive the market toward social welfare-oriented cooperation without eliminating competition.

Results

Market Share vs. Efficiency: In scenarios where the sole objective is market share maximization ( $\mu=0$ ), randomized algorithms (RFlexV-, RFlex-) outperform System Optimum (SO-) algorithms. They successfully attract drivers who would otherwise remain independent or choose other fleets, even those with high discount factors (skepticism toward AVs).
System Instability: The adoption of randomized strategies leads to significant fluctuations in travel times and an increase in the mean system-wide travel time. When two fleets compete using randomized strategies, the system exhibits high variance compared to the stability of SO routing.
Competitive Dynamics: If one fleet uses a randomized algorithm, a competitor using a standard SO algorithm loses competitiveness and is forced to switch to a randomized strategy to survive.
Impact of Objective Function: When the objective function is modified to include a penalty for increased travel time (increasing $\mu$ ), the performance of randomized algorithms degrades. At $\mu \approx 0.5$ , the SO-based algorithm becomes competitive again, and the incentive to use randomized, antisocial strategies is removed. The system converges to a state with lower travel time variance and better social welfare.

Significance and Claims

The paper claims to provide a foundational analysis of the emerging market for collectively routed CAV fleets. Its primary significance lies in identifying that market-share-based remuneration alone creates incentives for operators to adopt randomized routing strategies that are efficient for the operator but detrimental to the city's overall traffic flow.

The authors argue that while randomized routing is a rational response to market competition under current assumptions, it is not aligned with city goals. They propose that city authorities can shape this market by adjusting the remuneration scheme to include a component based on system-wide travel time. This adjustment is claimed to be sufficient to "drive the competition towards social welfare oriented cooperation" and limit antisocial strategies without destroying the competitive nature of the market.

The paper concludes modestly, noting that these findings are based on a simplified benchmark (two routes, known discount factors) and that future work will involve more complex scenarios, machine learning-based algorithms, and realistic city-scale simulations (e.g., SUMO).