Paper deep dive
Randomized routing strategies of fleets of CAVs may prove market efficient
Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/17/2026, 2:18:07 AM
Summary
This paper investigates the market structure for collectively routed fleets of Connected and Autonomous Vehicles (CAVs) competing with Human-Driven Vehicles (HDVs). It demonstrates that randomized CAV routing strategies outperform traditional System Optimum (SO) and User Equilibrium (UE) routing when human driver attitudes exhibit significant diversity. The authors propose augmenting the market-share objective with mean systemwide travel time to mitigate antisocial strategies and align fleet competition with social welfare goals.
Entities (10)
Relation Signals (9)
CAV → competeswith → HDV
confidence 95% · In future cities every driver may own a vehicle which could be either independently driven (HDV), or autonomously routed and piloted (CAV).
Travel Time → calculatedusing → BPR Function
confidence 90% · travel times are given by the BPR function: t_BPR(q) = (5min)*(1+(q/(0.5*N_D))^2)
RFlex Algorithm → implements → Randomized Routing Strategy
confidence 90% · Algorithm 4: RFlex is an extension of RFlexV, optimizing the choice of drivers to be routed via the faster route so that drivers who do not need to be routed via the faster route are not routed via it.
Randomized Routing → outperforms → SO/UE Routing
confidence 90% · randomised CAV routing, resulting in unpredictable travel times for HDVs, is more efficient than routing proportional to system optimum/user equilibrium.
Market Structure → aimsfor → Social Welfare
confidence 85% · drive the competition towards social welfare oriented cooperation.
Market Share Objective → augmentedby → Mean Systemwide Travel Time
confidence 85% · augmenting the market-share objective with mean systemwide travel time in order to limit antisocial randomised strategies of fleet operators and drive the competition towards social welfare oriented cooperation.
Randomized Routing → causes → Unpredictable Travel Times
confidence 85% · randomised CAV routing, resulting in unpredictable travel times for HDVs, is more efficient than routing proportional to system optimum/user equilibrium.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In future cities every driver may own a vehicle which could be either independently driven (HDV), or autonomously routed and piloted (CAV). The autonomous operations could be handled by a few competing companies. What is the market structure which would make this market aligned with city goals? In this paper we discuss a variant of the emerging market of collectively routed fleets of CAVs, where revenue for fleet operators is proportional to market share. We provide benchmark scenarios to compare the routing algorithms. We present several routing algorithms and demonstrate that, when the attitudes of human drivers towards CAVs exhibit significant diversity, randomised CAV routing, resulting in unpredictable travel times for HDVs, is more efficient than routing proportional to system optimum/user equilibrium. Based on this, we propose to improve the design of the market by augmenting the market-share objective with mean systemwide travel time in order to limit antisocial randomised strategies of fleet operators and drive the competition towards social welfare oriented cooperation.
Tags
Links
- Source: https://arxiv.org/abs/2607.14859v1
- Canonical: https://arxiv.org/abs/2607.14859v1
Trouble viewing inline? Open PDF directly →
Full Text
36,039 characters extracted from source content.
Expand or collapse full text
Randomized routing strategies of fleets of CAVs may prove market efficient Grzegorz Jamróz Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland Łukasz Gorczyca Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland Rafał Kucharski Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland Short summary In future cities every driver may own a vehicle which could be either independently driven (HDV), or autonomously routed and piloted (CAV). The autonomous operations could be handled by a few competing companies. What is the market structure which would make this market aligned with city goals? In this paper we discuss a variant of the emerging market of collectively routed fleets of CAVs, where revenue for fleet operators is proportional to market share. We provide benchmark scenarios to compare the routing algorithms. We present several routing algorithms and demonstrate that, when the attitudes of human drivers towards CAVs exhibit significant diversity, randomised CAV routing, resulting in unpredictable travel times for HDVs, is more efficient than routing proportional to system optimum/user equilibrium. Based on this, we propose to improve the design of the market by augmenting the market-share objective with mean systemwide travel time in order to limit antisocial randomised strategies of fleet operators and drive the competition towards social welfare oriented cooperation. Keywords: Autonomous driving and routing, choice modelling, market competition, randomized routing 1 Introduction Design of a fair, efficient and competitive market of urban CAV operations is likely to be a challenge, like for other markets, compare \@BBOPcite\@BAP\@BBNKominers et al. (2017)\@BBCP. The unfair predatory pricing policies of companies backed by huge venture capital like Amazon or Uber, e.g. \@BBOPcite\@BAP\@BBNKhan (2016)\@BBCP, resulting in long-term consumer harming mono/duopolies, even though common, are undesirable and preventable. As the market share of CAVs in major cities such as Los Angeles and Beijing is still too small, e.g. \@BBOPcite\@BAP\@BBNGoldmanSachs (2024)\@BBCP, to significantly influence the urban routing market, we are in a position to design the market structure which would be most beneficial for cities and avoid learning from failures, see e.g. \@BBOPcite\@BAP\@BBNRoth (2018)\@BBCP. Accordingly, in this paper we consider one variant of CAV autonomous-routing market where the revenue is derived only from market-share and not subscription/purchase cost. This potential future market is based on the following assumptions: • Every driver owns a vehicle which can be either driven independently (HDV) or routed and navigated by one of several providers (CAV fleet operators). • Autonomous driving is indistinguishable from human driving in traffic. • Each driver can freely choose/switch between HDV and one of CAV fleets. • Fleet operators are remunerated collectively from traffic taxes proportionally to the number of users (market-share maximization). Figure 1: Incentives to switch to CAV. Compared to independent driving, AV technology offers better value of time for most drivers so that UE routing is enough to convince to switch to CAV. If this is not enough, leveraging collective market power via SO routing may convince some drivers. Finally, randomized routing which strips HDV drivers of the information which route will be fastest on a given day, may convince the most reluctant. The above ’fee-free’ design favours algorithmic routing and quality advancements over pure discount-based monopole building strategies which benefit from economy-of-scale effects, e.g. \@BBOPcite\@BAP\@BBNCramer and Krueger (2016)\@BBCP, and weak regulation, \@BBOPcite\@BAP\@BBNCollier et al. (2018)\@BBCP. We study the dynamics of this market in a simplified case of one OD pair with two parallel routes. Fleet operators aim at maximum market share. Why would, however, a driver switch from independent driving (HDV) to autonomous driving and routing (CAV)? Three levels of incentives are presented in Fig. 1: i) People’s travel time cost spent in an AV is less than in an HDV. This is likely to be the case for most drivers, see \@BBOPcite\@BAP\@BBNde Almeida Correia et al. (2019)\@BBCP. These customers are ’taken for free’ by fleet operators by using user equilibrium (UE) routing. i) Collective routing can improve average travel times compared to user equilibrium by routing according to System Optimum (SO) with turn-taking for equity, see \@BBOPcite\@BAP\@BBNHoffmann et al. (2025)\@BBCP and references therein. i) SO routing is unstable as every driver may be inclined to defect and use the faster route. Moreover, drivers originally reluctant to use AVs will still not be convinced. Randomized routing addresses these two issues by deliberately introducing uncertainty and depriving independent drivers of the information which route is likely to be fastest on a given day. To study the above mentioned mechanisms and design a reasonable market structure, we: • Introduce a framework(benchmark) for comparing algorithms for routing fleets of CAVs aimed at maximizing market share, including both baseline algorithms and more sophisticated heuristics. • Introduce dynamic randomized algorithms for routing and demonstrate experimentally that they are strictly superior to non-randomized algorithms; note that randomization in the static full market-share context was discussed in \@BBOPcite\@BAP\@BBNJamróz et al. (2025)\@BBCP. • Show that including average system travel time minimization in the objective renders randomized algorithms less efficient and favors algorithms more aligned with city goals, while preserving competition. 2 Methodology System dynamics We present benchmark scenarios modelling the competition of fleet operators in systems consisting, for simplicity, of one OD pair and parallel routes r=1,…,Rr=1,…,R. We consider a fixed number NDN_D drivers, who every day decide whether to drive independently or join one of NFLEETN_FLEET fleets of autonomously routed vehicles, based on travel times offered by each of the fleets and credibility of fleet offers. Consequently, the system can be considered a game with ND+NFLEETN_D+N_FLEET players, who make decisions as follows. On a given day j, sequentially, see Fig. 2: i) Each fleet operator f∈0,1…,NFLEET−1f∈\0,1…,N_FLEET-1\ creates an offer vector Oif,jO^f,j_i for i=0,1,…,ND−1i=0,1,…,N_D-1 based on some algorithm Algo^f_offer such that Oif,jO_i^f,j is the mean long-term travel time fleet f offers to driver i. i) Each driver i=0,1,…,ND−1i=0,1,…,N_D-1 decides, based on previous travel experience and offers from fleet operators whether to remain independent (HDV) or be part of one of the fleets, resulting in mode vector Mj∈HDV,0,1,…,NFLEET−1NDM^j∈\HDV,0,1,…,N_FLEET-1\^N_D, where MijM^j_i is the the mode chosen by driver i on day j. i) Once the drivers have committed to fleets or to staying independent HDVs, each fleet f creates, based on some algorithm Algo^f_routing, a routing vector [rf,j]i[r^f,j]_i for drivers i∈If,j:=i:Mij=fi∈ I^f,j:=\i:M_i^j=f\, i.e drivers who have chosen fleet f on day j. The value rif,j∈1,…,Rr^f,j_i∈\1,…,R\ corresponds then to the route via which driver i will be routed on day j. The drivers i who have decided to remain independent, choose routes based on minimizing disutility, see below, resulting in vector riHDV,jr^HDV,j_i. The resulting routing vector on day j is given by rij=riMij,jr_i^j=r_i^M_i^j,j such that rijr_i^j is the route via which driver i will go on day j. Figure 2: Dynamics of the system at a glance. Every day each driver i selects the mode (HDV or CAV f) and route based on utilities derived from experienced and mean travel times and fleet operators’ travel time offers. After all the routing decisions have been made, a day of travelling is simulated, resulting in route travel time trjt^j_r, for r=1,…,Rr=1,…,R. The travel times are assumed to be independent of driver identity, however they depend on congestion and in our considerations are given by the BPR function: tBPR(q)=(5min)∗(1+(q/(0.5∗ND))2)t^BPR(q)=(5min)* (1+(q/(0.5*N_D))^2 ) (1) where q is the number of vehicles driving via the route on a given day. Human behaviour We assume that each driver i has, for each fleet f, a discount factor γiF,f>0 _i^F,f>0, which models the attitude towards using fleet f. This attitude can be decomposed into a part corresponding to the general liking of using fleets, γiF _i^F (drawn from a given known distribution, in our simulations assumed to be gaussian, clipped at 0, centred at 0.70.7 with standard deviation 0.20.2, compare \@BBOPcite\@BAP\@BBNde Almeida Correia et al. (2019)\@BBCP) and a factor specific to a given fleet γiF,specf _i^F,specf, drawn from N(0,(0.15)2)N(0,(0.15)^2) (gaussian centred at 0 and standard deviation 0.150.15), resulting in γiF,f=γiF+γiF,specf _i^F,f= _i^F+ _i^F,specf. The utility of driving independently uiHDVu_i^HDV is given by the mean travel times over the past javgj_avg days, sampled uniformly from 1,2,…,9\1,2,…,9\, weighted with logit probabilities. Contrariwise, the utility uiCAV,fu_i^CAV,f of using fleet f is proportional to the travel time offered multiplied by the discount factor γif _i^f and divided by credibility . Consequently, on day j, for tr¯=∑ι=j−javgj−1trι t_r= _ =j-j_avg^j-1t _r, disutilities of using different modes are: uiHDV u_i^HDV = = ∑r∈Re−βtr¯tr¯/∑r∈Re−βtr¯ _r∈ Re^-β t_r t_r/ _r∈ Re^-β t_r (2) uiCAV,f u_i^CAV,f = = γiF,f∗Oif,j/Credif, γ^F,f_i*O_i^f,j/Cred_i^f, (3) where Oif,jO_i^f,j is the travel time offered by fleet f to driver i and Credif>0Cred^f_i>0 is the credibility of fleet f to driver i. The initial credibility of fleets is assumed to be 11 and it is updated by Credif←(1−α)∗Credif+α∗Oif,j/trijjCred_i^f←(1-α)*Cred_i^f+α*O_i^f,j/t_r_i^j^j (4) for some update rate α (which in this paper is assumed to equal 0.20.2), if driver i chose fleet f on the previous day j and was routed via rijr_i^j. This means that human drivers are inclined to try out different fleets initially, provided the (honest or dishonest) travel time offer Oif,jO_i^f,j is attractive enough. However, if the offers are later not confirmed in the real driving, the credibility of a given fleet decreases. The gradual update of credibility is important as the fleets are supposed to offer long-term average travel times and not exact travel times on the following day. Finally, driver i is assumed to choose the mode (HDV or one of the fleets f) with lowest disutility. If HDV is chosen, the route choice is based on logit choice of routes, i.e. probability of choosing route r is given by e−βtr¯/∑r∈Re−βtr¯e^-β t_r/ _r∈ Re^-β t_r, where we assume β=0.2β=0.2. The rationale for choosing this model is that in the future even HDVs are likely to use some apps to propose routes, and a simple way to choose roughly optimal routes on a population level with small error is to use logit probabilities with small β, while mode choice, which would perhaps follow some bounded rationality model with near-deterministic logit probabilities can be approximated by deterministic mode choice. Algorithms for CAV fleet behaviour Algorithm 1: Proportional SO router This baseline algorithm offers routing aimed at achieving System Optimum. To reach this goal it first determines the system optimal flows =(q1SO,…,qrSO)q^SO=(q^SO_1,…,q^SO_r), which is straightforward in the case of two parallel routes as well as the average travel time at System Optimum, tavgSOt^SO_avg. Algo^f_offer is based on offering every driver average system optimal travel time, i.e. Oif,j=tavgSO_i^f,j=t^SO_avg for every day j and driver i. Algo^f_routing is the following. Given the set of drivers If,jI^f,j that have chosen fleet f on day j the drivers are split randomly with probabilities proportional to q^SO. In the case of two available routes, it consists of selecting a uniformly random sample IrandI^rand of ⌊|If,j|∗q1SO/||⌋ |I^f,j|*q^SO_1/|q^SO| agent indices from If,jI^f,j and setting rif,j=0 for i∈Irand,1 for i∈If,j and.r^f,j_i= cases0& for i∈ I^rand,\\ 1& for i∈ I^f,j I^rand. cases The rationale behind this algorithm is that if all the drivers choose this fleet, routing according to system optimal assignment is the most efficient way to minimize average travel time, which is desirable. The downside is that this routing treats all the drivers in the same way and disregards different attitudes towards the fleet, making the routing potentially inefficient. Furthermore, in the case of non-full market penetration, the offered travel times cannot in fact be realized, which decreseas the credibility of the fleet. A variant of the algorithm consists in offering travel times lower than system optimum, i.e. Oif,j=κtavgSO_i^f,j=κ t^SO_avg (5) for some κ∈(0,1]κ∈(0,1] in order to win over customers at the beginning. Algorithm 2: Proportional UE router This algorithm is analogous to Proportional SO routes, with q^SO replaced by q^UE, i.e. user-equilibrium flows and setting Oif,j=tUEO_i^f,j=t^UE, where tUEt^UE is the travel time via both routes at User Equilibrium. We note that in the case of two equivalent routes, SO and UE coincide and there is no distinction between the two algorithms. Algorithm 3: Randomized algorithm RFlexV The standard offer algorithm Algo^f_offer is to offer the scaled average system optimal travel time (5) with κ=0.5κ=0.5 (by default). The routing is given by the following randomized Algo^f_routing algorithm. Let |If,j||I^f,j| be the number of drivers who have chosen fleet f on day j. For two equivalent routes 0,10,1 the fleet operator proposes a symmetric randomized strategy such that • all the current members of the fleet are happy (i.e. will not want to leave the fleet to become an HDV on the next day), • the strategy is as randomized as possible in order to make independent routing difficult for other drivers and coax them to switch to the fleet. To achieve this, we assume that the remaining drivers will split 50-50 (as the routing is symmetric) and choose nfaster∗∈argminNunhappy(nfaster):nfaster=1,2,…,⌊|If,j|/2⌋,n^faster*∈ \N_unhappy(n_faster):n_faster=1,2,…, |I^f,j|/2 \, (6) where Nunhappy(nfaster)N_unhappy(n_faster) stands for the number of drivers who would rather switch to HDV than stay with the fleet when the fleet puts nfastern_faster agents with highest discount factors on the faster route and is given by Nunhappy(nfaster)=|i∈If,j:γiF,ftrif,jsim>trsim¯|,N_unhappy(n_faster)= | \i∈ I^f,j: _i^F,ft^sim_r^f,j_i> t_r^sim \ |, where trsim¯:=1NR∑r=1NRtrsim t_r^sim:= 1N_R _r=1^N_Rt^sim_r and trsimt^sim_r is the simulated travel time of route r provided nfaster<|If,j|/2n_faster<|I^f,j|/2 fleet members are routed, without loss of generality, via route 0 (which will be the faster route) and |If,j|−nfaster|I^f,j|-n_faster drivers are put on the other (slower) route 11. We obtain: t0sim t^sim_0 = = t0(nfaster+⌊(ND−|If,j|)/2⌋) t_0 (n_faster+ (N_D-|I^f,j|)/2 ) t1sim t^sim_1 = = t1(|If,j|−nfaster+⌈(ND−|If,j|)/2⌉) t_1 (|I^f,j|-n_faster+ (N_D-|I^f,j|)/2 ) and t0=t1t_0=t_1 are the known functional dependences of travel time on flow, see (1). Now, let nfaster∗n^faster* be the smallest such that equation (6) is satisfied. The algorithm assigns nfaster∗n^faster* drivers with highest discount factors to a random route and |If,j|−nfaster∗|I^f,j|-n^faster* drivers to the alternative route, i.e. for r∗r^* - a random number from 0,1\0,1\ we have rif,j=r∗ if s(i)<nfaster∗,1−r∗ otherwise, r_i^f,j= casesr^*& if s(i)<n^faster*,\\ 1-r^*& otherwise, cases where s:0,1,…,|If,j|−1→If,js:\0,1,…,|I^f,j|-1\→ I^f,j (7) is a sorting function such that γs(0)F,f,…,γs(|If,j|)F,fγ^F,f_s(0),…,γ^F,f_s(|I^f,j|) is a non-decreasing sequence (note s depends on If,jI^f,j). The algorithm tries to maintain its current customer base while randomizing the assignment so that it is less convenient to remain an independent driver for discount factors γiF,f>1γ^F,f_i>1. This, however, (even in the case of one fleet) may be suboptimal, as a driver i with γiF,f>1 _i^F,f>1 does not have to be routed via the faster route every day, but for instance only on 80%80\% of days, see \@BBOPcite\@BAP\@BBNJamróz et al. (2025)\@BBCP. Algorithm 4: RFlex RFlex is an extension of RFlexV, optimizing the choice of drivers to be routed via the faster route so that drivers who do not need to be routed via the faster route are not routed via it. To this end, it computes the least necessary share shish_i of routing driver i via the faster route to keep i happy as: shi∗=mins:γiF,f(st0sim+(1−s)t1sim)<trsim¯.sh^*_i= \s:γ^F,f_i(st_0^sim+(1-s)t_1^sim)< t_r^sim \. Solving the above equation we obtain: shi∗=t1sim−trsim¯/γiF,f(t1sim−t0sim) sh_i^*= t_1^sim- t_r^sim/ _i^F,f(t_1^sim-t_0^sim) with the caveat that if shi∗<0sh_i^*<0 then driver i will always be happy (we put shi∗=0sh_i^*=0) and when shi∗>1sh_i^*>1 then driver i cannot be made happy (we put shi∗=∞sh_i^*=∞, because this driver cannot be convinced anyway for the given nfastern_faster). Let s(i)s(i) be the sorting function from (7). The theoretical maximum number of drivers that can be made happy is given by nmaxhappy=maxn:1n∑i=0n−1shs(i)∗<nfastern.n_maxhappy=max \n: 1n _i=0^n-1sh^*_s(i)< n_fastern \. The routing should theoretically now be given by randomly assigning the drivers to routes by rif,jr^f,j_i such that rs(i)f,j<shs(i)∗Er^f,j_s(i)<sh^*_s(i) (8) for every i=0,…,n−1i=0,…,n-1, where, without loss of generality 0 is the faster route and 11 is the slower route. The overall routing could consist in finding nfastern^faster such that nmaxhappyn_maxhappy is the highest and routing such that (8) is satisfied. This would work if human drivers fully trusted the fleet operator to deliver the offered travel times. However, in practice, the drivers might be discouraged if they are not offered good travel times initially after joining the fleet and, moreover, the number of participants of the fleet changes making the theoretical delivery of offered travel times tricky. In view of the above, we opt for a heuristic Algo^f_routing given by setting the target ratio of routing every driver via the faster route as shitarget=shi∗/σsh_i^target=sh_i^*/σ, where σ∈(0,1]σ∈(0,1] is a parameter to optimize (we use σ=0.4σ=0.4). We obtain: rif,j=r∗ if difasterdifaster+dislower+1>shitarget,1−r∗ otherwise,r_i^f,j= casesr^*& if d_i^fasterd_i^faster+d_i^slower+1>sh_i^target,\\ 1-r^*& otherwise, cases where difasterd_i^faster and dislowerd_i^slower is the number of days driver i was routed via the faster (slower) alternative since joining the fleet and r∗r^* is a random number from 0,1\0,1\. Estimation of human drivers’ discount factors Across most scenarios, we assume that the discount factors are known to the fleets. 3 Results and discussion In this paper we consider the simplest benchmark scenario of two equivalent routes and discount factors known to fleet operators, leaving extensions with more realistic details to further work. The parameters used are listed in Table 1. Table 1: Simulation parameters Parameter Symbol Value Number of drivers NDN_D 200200 Number of days J 300300 Route 0 delay function t0(q0)t_0(q_0) tBPRt^BPR Route 1 delay function t1(q1)t_1(q_1) tBPRt^BPR Initial fleets’ credibility CredinitCred_init 11 Fleet discount factor distribution γFDγ^FD N(0.7,(0.2)2)N(0.7,(0.2)^2) Fleet specific discount factor term γF,specfDγ^F,specfD N(0,(0.15)2)N(0,(0.15)^2) Discount factors known to Fleets? DiscFknownDiscF_known True Discount factor distribution known? DiscDknownDiscD_known True HDV logit parameter β 0.20.2 Table 2: Algorithms used Algorithm Offer creation Algo^f_offer Assignment method Algo^f_routing SO Avg SO travel time Proportional to SO + random turn-taking SO- 0.8∗0.8* Avg SO travel time Proportional to SO + random turn-taking UE Avg UE travel time Proportional to UE UE- 0.5∗0.5* Avg UE travel time Proportional to UE RFlexV Avg SO travel time highest γFγ^F to (randomized) faster route RFlexV- 0.5∗0.5* Avg SO travel time highest γFγ^F to (randomized) faster route RFlex Avg SO travel time Adaptive randomized routing to make happy RFlex- 0.5∗0.5* Avg SO travel time Adaptive randomized routing to make happy Infty Infinite No assignment, used for one-fleet scenarios Your Algorithm ? ? The execution of the benchmark scenarios proceeds as follows. 1. A list of NDN_D human drivers is created. At the beginning, each driver i∈0,…,ND−1i∈\0,…,N_D-1\ has the initial credibility towards the fleets equal CredinitCred_init and a couple of discount factors γiF,0,γiF,1γ^F,0_i,γ^F,1_i, where γiF,f=ξi+ξi,fγ^F,f_i= _i+ _i,f for f=0,1f=0,1 where ξi _i a number drawn from γFDγ^FD and ξi,f _i,f drawn independently from γF,specfDγ^F,specfD for f=1,2f=1,2. If any of the resulting factors is ≤0≤ 0 then it is set to ε , where ε=0.0001 =0.0001 is a very small positive number. In this way, the attitude of a human towards fleet f is broken down into the general attitude towards using fleets of AVs and fleet specific components. 2. Fleets f for f∈0,1f∈\0,1\ are created. Every fleet uses one of the algorithms specified in Table 2 and described in detail in Section Methodology - Algorithms for CAV fleet behaviour. 3. The dynamics of the system are simulated in line with Section Methodology - System Dynamics. Various parameters are recorded. 4. The parameters like market share of a fleet are plotted and compared to other algorithms. Experiment 1: Offering realistic travel times vs. unrealistically short travel times Fig. 3 shows the performance of different algorithms in the variants with best realistically possible mean travel times offered (without ’-’) and with offered travel times much faster than achievable (with ’-’). For SO the advantage for ’-’ only persistis temporarily whereas for RFlex and RFlexV it is long-term. Moreover the logit parameter of human assignment equal 0.20.2 offers better, stable travel times, which is preferred over every driver striving to choose the faster route every time which results in high variance (P = 1.0). Therefore, for further experiments we choose to set the logit parameter to 0.20.2 and study only algorithms offering unrealistically short travel times. Figure 3: Comparison of properties of the system for different logit parameters of human driver assignment (P) and routing algorithms (F0) with travel time offers either unrelistically low (with ’-’) or more realistic (without ’-’). Upper panel: Logit parameter 0.20.2 is a preferred choice for the human population as it results in relatively stable assignment when Fleet is absent (F0 = infty). Lower panel: The performance of ’-’ algorithms is superior to those offering more realistic travel times. Experiment 2: Randomized algorithms vs. baseline algorithms In Fig. 4 we pitch the algorithms against each other. The outcomes reveal that RFlexV is superior to SO and RFlex is superior to RFlexV when there is one fleet (last row/last column in bottom panel). However, when there are two fleet operators, the results are mixed, with RFlex/RFlexV performing slightly better than SO against SO (first row/first column, bottom panel), however not necessarily so against either RFlexV or RFlex (four central subplots). The upper panel demonstrates that randomized strategies entail large variations of travel times and the increase of mean travel time in the system. Fig. 5 shows which vehicles belong to which fleet on a sample day 150 plotted against discount factors towards both fleets. The baseline natural split is for both fleets using SO algorithms - drivers join the fleet with better discount factor provided it is <1<1. This changes when more advanced algorithms are used. E.g. in the last row it can be seen how RFlexV/RFlex can convince even drivers who, without randomization would not join the fleet. Moreover, if a fleet uses a randomized algorithm then the other fleet sticking to the baseline SO algorithm fails to be competitive (first row and left column) and has to switch to a different algorithm. The four central panels illustrate continual competition for customers. The sample of discount factors is the same for every subplot. Figure 4: Competition of fleet operators in a benchmark scenario. Randomized algorithms RFlexV- and RFlex- perform better in one-fleet scenario (against F1 = Infty), while in two-fleet scenarios the results are mixed. The travel times when one or two fleets use randomized algorithms are highly variable. Figure 5: Usage of HDV or Fleet 0 or Fleet 1 on day 150150 in simulations. Every dot in a panel corresponds to one vehicle and is plotted at coordinates corresponding to respective discount factors of fleets. Dashed lines separate the natural basins of belonging - as in the upper left panel. More efficient algorithms are able to attract and retain customers from outside of their basins. The HDV sample of discount factors is the same in every panel. Experiment 3: SO component in objective Experiment 2 shows that randomized algorithms are efficient in reaching higher market share, however for the price of increased and highly varying average travel times. Here, we demonstrate that a combination of share maximization with minimization of average travel time could be an objective which would be more socially acceptable (less oscillations), while preserving competition and discouriging randomization. Figure 6: Smoothed-out objective (50-day moving average) for different values of μ and algorithm used by the fleet F0F0 against the fleet F1F1 is competing. Red/green/orange line correspond to F1F1 using SO-/RFlexV-/RFlex-, respectively. With growing μ the algorithm aiming at SO, ie. SO- becomes more and more competitive and eventually superior to randomized algorithms aiming solely at share maximization. To this end let tavgj=1ND∑r∈Rqrjtrj t^j_avg= 1N_D _r∈ Rq_r^jt_r^j where qrjq_r^j is the flow (number) of vehicles on route r and day j. Let τavgj:=tavgSO/tavgjτ^j_avg:=t^SO_avg/t^j_avg be the normalized average travel time and let nf,j=|If,j|/NDn^f,j=|I^f,j|/N_D be the share of fleet f on day j. Fig. 6 shows the objectives we propose (to be maximized): Objμ=(1−μ)nf,j+μτavgjObj^μ=(1-μ)n^f,j+μτ^j_avg for different values of parameter μ. We note that μ=0μ=0 corresponds to market share maximization while μ=1μ=1 corresponds to minimizing average travel time. As already noticed before, for μ=0μ=0 the randomized algorithms RFlex−RFlex- and RFlexV−RFlexV- are superior to SO oriented SO−SO-. This changes with increasing μ and for μ≈0.5μ≈ 0.5 the plain algorithm SO−SO- becomes competitive enough and randomization is discouraged; indeed using randomization resulting in increased average travel times reduces the objective, i.e. payoff for the fleet operator. 4 Conclusions In the paper we introduced a benchmark for comparing routing algorithms competing for customers in the scenario with diverse drivers. We provided baseline algorithms (SO) as well as more advanced heuristic randomized algorithms (RFlexV, RFlex). Running the benchmark scenario we found that: • Dynamic routing algorithms using randomized strategies, which result in highly variable travel times seem to be more efficient than baselines when the sole objective is maximization of market share (and attitudes of drivers towards fleets are known). • If one fleet uses a randomized algorithm, the other cannot stick to the baseline SO routing to stay competitive. • The city could shape the market by setting the remuneration scheme based on combining the market share objective and deviation from System Optimum objective. • There are indications that cities might be able to preserve competition while discouraging unwanted market-share optimizing behaviours such as randomized routing. Future work will encompass: • Including benchmark scenarios with more routes than 22 and more fleets than 22. • Developing even more efficient routing algorithms which directly address competition against other fleet providers as well as take into account the objective set by city authorities. • Developing ML-based routing algorithms in the competition case. • Considering scenarios where fleet discount factors are not known to fleet operators and have to be inferred. • Simulations in realistic city-scale simulators such as open-source SUMO, \@BBOPcite\@BAP\@BBNLopez et al. (2018)\@BBCP. Acknowledgements This work was financed by the European Union within the Horizon Europe Framework Programme (ERC Starting Grant COeXISTENCE no. 101075838). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. References R. B. Collier, V. B. Dubal, and C. L. Carter (2018) Disrupting regulation, regulating disruption: the politics of uber in the united states. Perspectives on Politics 16 (4), p. 919–937. Cited by: §1. J. Cramer and A. B. Krueger (2016) Disruptive change in the taxi business: the case of uber. American Economic Review 106 (5), p. 177–182. Cited by: §1. G. H. de Almeida Correia, E. Looff, S. Van Cranenburgh, M. Snelder, and B. Van Arem (2019) On the impact of vehicle automation on the value of travel time while performing work and leisure activities in a car: theoretical insights and results from a stated preference survey. Transportation Research Part A: Policy and Practice 119, p. 359–382. Cited by: item i), §2. GoldmanSachs (2024) Note: Accessed: 2026-02-21 External Links: Link Cited by: §1. M. Hoffmann, M. Bujak, G. Jamróz, and R. Kucharski (2025) Wardropian cycles make traffic assignment both optimal and fair by eliminating price-of-anarchy with cyclical user equilibrium for compliant connected autonomous vehicles. arXiv preprint arXiv:2507.19675. Cited by: item i). G. Jamróz, R. Kucharski, and D. Watling (2025) Market share maximizing strategies of cav fleet operators may cause chaos in our cities. arXiv preprint arXiv:2512.03524. Cited by: 2nd item, §2. L. M. Khan (2016) Amazon’s antitrust paradox. Yale lJ 126, p. 710. Cited by: §1. S. D. Kominers, A. Teytelboym, and V. P. Crawford (2017) An invitation to market design. Oxford Review of Economic Policy 33 (4), p. 541–571. Cited by: §1. P. A. Lopez, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, and E. Wiessner (2018) Microscopic traffic simulation using sumo. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), Vol. , p. 2575–2582. External Links: Document Cited by: Appendix A, 5th item. A. E. Roth (2018) Marketplaces, markets, and market design. American Economic Review 108 (7), p. 1609–1658. Cited by: §1. Appendix A Appendix: SUMO-based simulations Figure 7: Screenshot of SUMO-based simulation experiment. The two equivalent routes with stop signs exhibit BPR-like dependence of mean travel time on flow. While the experiments in the main text clearly demonstrated the advanteges of randomized algorithms, they still used simplified flow-delay relations based on BPR functions. This experiment demonstrates the first step towards more realistic scenarios which is conducted as a microsimulation in SUMO, \@BBOPcite\@BAP\@BBNLopez et al. (2018)\@BBCP. To do this, we designed a system of two routes with properties similar to the one used in the main experiments. We assumed that: • There are two equivalent routes with stop signs, see Fig. 7. • There are 150 vehicles, departing within 600 seconds. • Each vehicle (be it HDV or CAV) chooses/is assigned route, however it cannot choose the exact departure time. • Vehicles arrive at start of routes with uniform probability within 10 min. • The travel time depends on congestion on each route, and is stochastic: a driver may get stuck at STOP for long if unlucky or may pass quickly. • A day of travel is an independent SUMO run yielding actual private travel times for every driver and public means on routes. • HDV utilities are given by (2) with tr¯=∑ι=j−javgj−1trSUMO(qr(ι)) t_r= _ =j-j_avg^j-1t^SUMO_r(q_r( )), where qr(ι)q_r( ) is the number of vehicles that chose route r on day ι and trSUMOt_r^SUMO is the mean dependence of travel time on flow from Fig. 8. • CAV utilities are based on (3) with CAV fleet credibilities based on (4) with trijjt_r_i^j^j replaced by tij,SUMOt_i^j,SUMO, where tij,SUMOt_i^j,SUMO is the private travel time of driver i in the SUMO simulation of day j. • CAVs use the (known) dependece in Fig. 8 for their algorithms. Figure 8: Dependence of average travel time on routes (blue - upper route, orange - lower route) on vehicle number in the SUMO-based system. The number of vehicles on orange route equals 150150 minus the number of vehicles on blue route. Error bars correspond to standard deviation. Data from 1010 indepent simulations. The experimental results shown in Fig. 9 demonstrate that: • The randomized algorithms RFlexV- manages to achieve higher market share than baseline SO-. • The results presented in this paper paper are likely to generalize to real-world scenarios. Figure 9: Modal split on days 1−2001-200 in the SUMO-based experiment. Each circle sector depicts the chosen modes of a driver (angle 0 - day 11, angle 3π/23π/2 - day 200200). The advantage of randomised algorithms over SO- is clearly present in this setting as well.