Tommaso Toso

Alain Y Kibangou

Paolo Frasca

Modeling the Impact of Route Recommendations in Road Traffic

Keywords: Control of networks, Modelling and control of road traffic networks, Urban mobility, Route recommendations, Traffic congestion, Switching systems

In this work, effects of real-time route recommendations between two alternative routes are analyzed. The aim is to assess the consequences of route planner applications (apps) on road congestion. For this purpose, the considered model takes the form of a state-dependent switching system that describes a supply-demand mechanism, based on established macroscopic traffic flow models. Through a comprehensive stability analysis of the system, with an emphasis on the dependence on the system parameters (such as road capacities, critical densities, traffic demand), it is shown that real-time recommendations can cause congestion in the network and failure to satisfy user demand.

INTRODUCTION

Users of transportation networks moving from one location to another try to do so by choosing what they think is the best path, typically the path associated with the shortest travel time. For this reason, the usage of route planner applications (apps) such as Google Maps, Apple Maps, Waze, Inrix, etc., which provide information about traffic status and an indication of the shortest travel time route, has spread rapidly and massively in recent years. Such a large deployment of route planner apps leads to ask: what is their impact on traffic dynamics, what are the possible benefits, and what are potential drawbacks. Some works in the literature already addressed these questions and have highlighted that the use of route planner apps can deteriorate the efficiency of the transportation network, see [START_REF] Keimer | Routing on traffic networks incorporating past memory up to real-time information on the network state[END_REF]; [START_REF] Festa | Modeling the impact of on-line navigation devices in traffic flows[END_REF]; [START_REF] Thai | Negative externalities of GPS-enabled routing applications: A game theoretical approach[END_REF]. Roughly, this is due to the fact that apps combined with users' selfish behavior can lead to traffic configurations where no user has an incentive to change route, known as Wardrop equilibria, which are in general non optimal; [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. The paper by [START_REF] Festa | Modeling the impact of on-line navigation devices in traffic flows[END_REF] emphasises that when the percentage of users resorting to route planner apps is low enough, congestion in terms of total travel time decreases, but a generalised use has negative effects. Moreover, the work by [START_REF] Thai | Negative externalities of GPS-enabled routing applications: A game theoretical approach[END_REF] points out that the use of these apps causes a severe increase of the pressure on secondary roads, while only alleviating it slightly on larger ones, thus creating undesired effects. Another aspect is the possibility that the use of route planner apps may result in traffic oscillations in the road network, synonymous with an alteration of its ⋆ This work is partly supported by the French National Research Agency, grants ANR-15-IDEX-02 and ANR-11-LABX-0025-01.

stability properties. The work by [START_REF] Bianchin | Routing apps may cause oscillatory congestions in traffic networks[END_REF] proves this by resorting to a network traffic model whose road traffic dynamic is associated with a dynamic output feedback control law, whereas [START_REF] Wahle | Decision dynamics in traffic scenario[END_REF] and [START_REF] Hino | Effect of bottleneck on route choice in two-route traffic system with real-time information[END_REF] propose discrete models for road fork networks, highlighting the oscillating behavior of the system, depending on the system parameters.

In order to assess the effect of using route planner apps on traffic congestion, in this paper we introduce a model allowing to study the traffic on a origin-destination pair connected by two alternative non-intersecting routes, assuming that drivers can resort to a route recommendation system. The model describes the traffic dynamic on each route by a supply and demand mechanism, inspired by [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF]; [START_REF] Morȃrescu | Highway traffic model-based density estimation[END_REF]. Route recommendations are then captured by routing ratios determining how user demand splits on the two routes. Through a complete stability analysis of the model, we investigate the effects on congestion caused by recommendations. Our results suggest that route recommendation systems can give rise to traffic congestion, due to the fact that recommendations are based solely on a comparison of travel times, while other relevant features such as route supplies and capacities are disregarded.

From a model design point of view, our model falls within the framework of transportation network models relying on a supply and demand mechanism for the traffic dynamic description, see [START_REF] Coogan | A compartmental model for traffic networks and its dynamical behavior[END_REF]; [START_REF] Lovisari | Stability of monotone dynamical flow networks[END_REF]. This choice is crucial for the interpretation of our results, since the supply and demand mechanism allows us to easily define the concept of congestion. However, differently from these works, we define state-dependent routing ratios capturing the effects due to route recommendations. In most works, routing ratios are modeled by means of nonlinear functions of the state variable, as in Como et al. (2013a); [START_REF] Bayen | Time-continuous instantaneous and past memory routing on traffic networks: A mathematical analysis on the basis of the link-delay model[END_REF]; [START_REF] Keimer | Routing on traffic networks incorporating past memory up to real-time information on the network state[END_REF]; [START_REF] Como | Throughput optimality and overload behavior of dynamical flow networks under monotone distributed routing[END_REF]. On the contrary, we resort to affine functions in order to simplify the model and to carry out more in-depth analysis, while maintaining the most important features that routing ratios must possess.

The paper is organized as follows. In Section 2 we define the model and we discuss its main features. Then in Section 3 we establish its stability properties, underlining their consequences from a traffic congestion perspective. The main concepts are illustrated with a realistic example before concluding the paper in Section 4.

Notation and definitions.

Let R d (R d + ) be the space of real-valued (non-negative-valued) vectors of dimension d. Let int(X ) and X be the interior and the closure of X ⊆ R d , respectively. Given a domain D ⊆ R d and a system of differential equation ẏ = g(y), with g : D → R d , admitting a unique solution φ(t, y 0 ), t ≥ 0, for all initial conditions y 0 ∈ D, we say that Y ⊆ D is a positively invariant region of the system if y 0 ∈ Y implies that φ(t, y 0 ) ∈ Y, ∀t ≥ 0. We say that Y is globally attractive if, for any open neighbourhood U of Y, ∀y 0 ∈ D, there exists a time τ (y 0 ) > 0 such that φ(t, y 0 ) ∈ U, ∀t > τ (y 0 ).

MODEL DESCRIPTION

The purpose of this section is to define the adopted model, highlight its features and provide a clear explanation of the motivations behind the choice of the routing ratios.

Model definition

Consider an origin-destination pair connected by two alternative non intersecting routes (see Figure 1). The user demand, considered as a constant flow ϕ > 0, enters the network from the origin node and reaches the destination node through the two routes. In what follows, for route i, x i , B i , C i , F i , L i are non-negative values representing the density, jam density (veh/km), critical density (veh/km) maximum capacity (veh/h) and length (km) respectively, with C i < B i . The density x i ∈ [0, B i ] of the route i, i = 1, 2, evolves as follows:

ẋi := 1 L i (min{ϕr i (x), S i (x i )} -D i (x i )) , i = 1, 2, (1)
where S i (x i ) ≥ 0 (veh/h), D i (x i ) (veh/h) and r i (x i ) ≥ 0 stand respectively for the supply, the demand and the routing ratio of the i-th route while x = (x 1 , x 2 ) T represents the state of the network. Supply functions are Lipschitz continuous functions of the traffic density:

S i (x i ) :=    F i , if x i ≤ C i F i B i -C i (B i -x i ), otherwise , i = 1, 2.
(2) Demand functions are also Lipschitz continuous functions of the traffic density:

D i (x i ) := v i x i , if x i ≤ C i F i , otherwise , i = 1, 2, (3)
where v i = Fi Ci (in km/h), i = 1, 2. The following assumptions ensure that the network is well-dimensioned with respect to the user demand. Assumption 1. The following inequality holds:

ϕ < F 1 + F 2 . ( 4
)
Assumption 2. The network destination is always able to satisfy the sum of the two route demands.

Modeling the routing ratios

The most natural choice when modeling phenomena involving route recommendation apps is to take routing ratios as functions of travel times. Typically, travel times are strictly increasing functions of traffic densities, see [START_REF] Kachroo | Traffic assignment using a density-based travel-time function for intelligent transportation systems[END_REF]; [START_REF] Bianchin | Routing apps may cause oscillatory congestions in traffic networks[END_REF]; [START_REF] Bayen | Time-continuous instantaneous and past memory routing on traffic networks: A mathematical analysis on the basis of the link-delay model[END_REF]. For sake of simplicity, we exploit this one-to-one relationship and we write the routing ratios as functions of the route occupancy indices x i /B i , i = 1, 2. The routing ratios are modeled by the following affine functions of the state variables:

r 1 (x) = 1 2 + 1 2 x 2 B 2 - x 1 B 1 , r 2 (x) = 1 2 + 1 2 x 1 B 1 - x 2 B 2 .
(5) If we look at routing ratios as control variable of the system, (5) can be seen as a static state feedback control law. Observe that (5) meets the following requirements that support its choice as routing ratios:

(1) 0 ≤ r i (x) ≤ 1, ∀x ∈ [0, B 1 ] × [0, B 2 ], i = 1, 2,
i.e., the user demand directed towards each route is nonnegative;

(2) r 1 (x) + r 2 (x) = 1, ∀x ∈ [0, B 1 ] × [0, B 2 ],
i.e., the route recommendation app distributes the entire user demand;

(3) the system directs an higher quantity of user demand ϕ on the route with the lowest occupancy index, i.e., it advises to take the route with the shortest travel time. Remark 3. (Routing ratios and logit choice). The choice to take linear routing ratios has the objective to allow for a complete stability analysis of the dynamical system. Although such a choice has never been made before, we are nevertheless able to relate it with other works in the literature. Our law refers to a scenario in which not all users choose the route associated to the minimum occupancy index, i.e., the minimum travel time. The number of users following routing recommendations is proportional to the difference between travel times. It is reasonable to assume that this occurs because some criteria, different from travel time, are taken into account by users when they choose their route, but these become gradually less relevant as the difference between travel times increases. This scenario is the same as that described by other widely used laws in the literature, such as the logit law, see [START_REF] Cianfanelli | On stability of users equilibria in heterogeneous routing games[END_REF]; Como et al. (2013a,b). The logit law would correspond to the following routing ratios: Notice how the logit law recommendations become more sensitive to variations in x2 B2 -x1 B1 as η decreases.

r i (x) = 1 1 + exp -1 η xj Bj -xi Bi , (6)
where i ̸ = j, i = 1, 2. η ∈ [0, +∞) is called noise parameter. Indeed, when η → +∞, i.e., noise is very high, users tend to randomize their choice. When instead η → 0, all users tend to take the route with smallest occupancy index.

The logit law corresponds to a perturbed version of the best response law (exclusively based on travel times) and η quantifies the magnitude of the perturbation, see [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF]. From our point of view, the perturbation can be seen as the influence exerted by other (unknown and not modeled) features on users' choice: as η → 0, the occupancy indices become the key criterion on which to base the choice, whereas when η → +∞, they become irrelevant to the users. Figure 2 shows a graphical comparison between ( 5) and ( 6), for some values of η, with respect to x2 B2 -x1 B1 . For appropriate value ranges of η, the two laws show similar behaviours.

Congestion concept

Route congestion can be either external or internal, defined by looking at its entry or exit. When the fraction of user demand ϕr i is less than its supply S i (x i ), we say that its entry is in free-flow (F), otherwise it is congested (C). Equivalently, we say that the route is externally congested. Analogously, if the internal demand D i (x i ) of the route is lower than its capacity F i , then we say that the route exit is in free-flow, otherwise it is congested (internal congestion). Therefore, each route is characterized by four possible modes, which are reported in Table 1 and that can be made explicit by rewriting (1) as follows: where w i = Fi Bi-Ci . The equations in (7) follow the order of the modes in Table 1. Remark 4. (Unsatisfied demand). When one of the two entries is congested, the excess demand directed towards it does not enter the network. Therefore, the user demand is only partly satisfied. We can imagine that the excess demand would correspond in a real-world scenario to a traffic jam of vehicles stuck at the entry of the route, clearly a situation to be avoided. Notice that the two entries cannot be simultaneously congested, since this would contradict (4). Therefore, system mode CF-CF cannot be attained.

ẋi =                      (ϕr i (x) -v i x i )/L i , if x i ≤ C i , r i (x) ≤ S i (x i ) ϕ (F i -v i x i )/L i , if x i ≤ C i , r i (x) > S i (x i ) ϕ (ϕr i (x) -F i )/L i , if x i > C i , r i (x) ≤ S i (x i ) ϕ w i (C i -x i )/L i , if x i > C i , r i (x) > S i (x i ) ϕ , (7)

STABILITY ANALYSIS

Let us denote the set of parameters by

α = (F 1 , F 2 , C 1 , C 2 , B 1 , B 2 , L 1 , L 2 , ϕ).
From (1), we see that the system is two-dimensional and its state-space is given by Ω α = [0, B 1 ]×[0, B 2 ]. First of all, as far as concerns the existence and uniqueness properties of the solutions of (1)-( 5), these are ensured by the system being Lipschitz continuous (the latter fact is clear from the definitions of S i , D i and r i , i = 1, 2). Therefore, if we indicate γ(t, x 0 ), t ≥ 0 as the solution to (1) associated with the initial condition x 0 = (x 1 (0), x 2 (0)) ∈ Ω α , then it is guaranteed that γ(t, x 0 ) exists, is unique and globally defined with respect to time t. Moreover, we would like to remark that (1) is well-posed with respect to Ω α , i.e., Ω α is positively invariant. Indeed,

x i = 0 ⇒ ẋi > 0, x i = B i ⇒ ẋi < 0. (8) Hence, if x 0 ∈ Ω α , then γ(t, x 0 ) ∈ Ω α , ∀t ≥ 0.
We now observe that (1) is a state-dependent switched system with the system modes in (7) and each of them is active in a specific sub-region of Ω α . From now on, every route mode combination M 1 -M 2 , where M 1 , M 2 ∈ {FF, CF, FC, CC} indicate the modes of route 1 and route 2, respectively, will be called system mode. Furthermore, we will refer to the sub-system associated to system mode M 1 -M 2 with the notation Σ M1-M2 α and we will indicate as R M1-M2 α the region of the state space where sub-system Σ M1-M2 α is active. By considering (7), one can see that each sub-system Σ M1-M2 α actually consists in an affine system of the form

ẋ = A M1-M2 α x + b M1-M2 α , (9)
where

A M1-M2 α ∈ R 2×2 , b M1-M2 α ∈ R 2 .
The different mode regions of (1) are delimited by the lines reported below:

l (1) α : x 1 = C 1 , l (2) α : x 2 = C 2 , l (3) α : x 2 = B 2 x 1 B 1 -1 - 2F 1 ϕ , l (4) α : x 2 = B 2 x 1 B 1 + 1 - 2F 2 ϕ , l (5) α : x 2 = B 2 ϕ(B 1 -C 1 ) -2F 1 B 1 ϕ(B 1 -C 1 ) x 1 B 1 -1 , l (6) α : x 2 = B 2 ϕ(B 2 -C 2 ) ϕ(B 2 -C 2 ) -2F 2 B 2 x 1 B 1 + 1 . Lines l (1) α , l (2)
α correspond to the critical density thresholds of routes 1 and 2, respectively. Lines l

(3) α , l (5)
α correspond to the supply thresholds with respect to the fraction of demand directed to route 1, when distinguishing the cases x 1 ≤ C 1 and x 1 > C 1 , respectively. The same applies to lines l

(4) α , l (6)
α for route 2. Clearly, the subdivision of Ω α is highly dependent on α and, as one can see in Figure 3, the number of nonempty sub-regions may vary from a set of parameter to another.

We now present some preliminary results allowing us to simplify the stability analysis of (1). Let us define the two following regions:

P α := {x ∈ Ω α | 0 ≤ x i ≤ C i , i = 1, 2}, T α := Ω α \ P α . Notice that P α = R FF-FF α ∪ R CF-FF α ∪ R FC-FF α , (10)
and that all regions R M1-M2 α such that M 1 ∈ {FC, CC} ∨ M 2 ∈ {FC, CC} are contained in T α . Lemma 5. P α is positively invariant.

Proof. This claim follows immediately after observing that

x 1 = C 1 ⇒ ẋ1 < 0, x 2 = C 2 ⇒ ẋ2 < 0.
(11) This ensures that trajectories cannot escape P α .

2 Lemma 6. P α is globally attractive.

Proof. Consider x 0 / ∈ Ω α \ P α = T α . By definition of T α , at least one of the two routes is in mode FC or CC. Specifically, if x = (x 1 , x 2 ) ⊤ ∈ T α , then, if route i is the route/one of the routes in mode FC or CC, we can write ẋi ≤ -

1 L i F i B i -C i x i + F i C i B i -C i , i = 1, 2.
This inequality shows that all routes that are in mode FC or CC at the initial condition will always eventually reach P α , since

x i (t) ≤ 1 L i C i + (x i (0) -C i )e - F i C i B i -C i t , i = 1, 2.
This concludes the proof. 2

Remark 7. Since P α is positively invariant and globally attractive implies that, in conducting the stability analysis, it suffices to focus on region P α and the system modes contained in it. Remark 8. From the point of view of traffic congestion, the positive invariance of P α implies that internal congestion cannot arise from a free-flow condition. Moreover, global attractiveness implies that if there is internal congestion at the initial condition, this is going to disappear over time. This is clearly due to Assumption 2.

We now provide a result ensuring that (1) admits a unique equilibrium point. It also provides its expression in terms of the system parameters and indicates in which system mode region it is located. To this end, let us first define the effective capacity of route i as

( Fi ) α = q i + q 2 i + k i 2 , i = 1, 2,
where

q i := F i + C i B i -1 v j B j , k i := 8F i v j B j , i ̸ = j, i = 1, 2.
Proposition 9. System (1)-( 5) admits a unique equilibrium point x α and the following conditions hold:

• if ϕ ≤ min{( F1 ) α , ( F2 ) α }, (12)
then

x α =      ϕB 1 (ϕ + v 2 B 2 ) 2v 1 B 1 v 2 B 2 + ϕ(v 1 B 1 + v 2 B 2 ) ϕB 2 (ϕ + v 1 B 1 ) 2v 1 B 1 v 2 B 2 + ϕ(v 1 B 1 + v 2 B 2 )      ∈ R FF-FF α ; (13) • if ϕ > min{( F1 ) α , ( F2 ) α } = ( F1 ) α , (14)
then

x α =    C 1 ϕB 2 (B 1 + C 1 ) B 1 (ϕ + 2v 2 B 2 )    ∈ R CF-FF α ;
(15)

• if ϕ > min{( F1 ) α , ( F2 ) α } = ( F2 ) α , (16)
then

x α =    ϕB 1 (B 2 + C 2 ) B 2 (ϕ + 2v 1 B 1 ) C 2    ∈ R FF-CF α . ( 17
)
Proof. From Remark 7, all equilibrium points of (1) are contained in P α . Since

P α = R FF-FF α ∪ R CF-FF α ∪ R FC-FF
α , the set of the equilibrium points of (1) coincides with the set of the active equilibrium points of sub-systems Σ

FF-FF α , Σ CF-FF α , Σ FF-CF α . Specifically, the equilibrium point x M1-M2 α of sub-system Σ M1-M2 α is active if x M1-M2 α ∈ R M1-M2 α . Clearly, x M1-M2
α needs to be active to be an equilibrium point of (1). Now, each of sub-systems Σ FF-FF α , Σ CF-FF α , Σ FF-CF α admits a unique equilibrium point. Let us indicate these unique equilibrium points as x FF-FF α , x CF-FF α , x FF-CF α , respectively. One can verify that they coincide with the equilibria in ( 13), ( 15), (17), respectively. Moreover:

• x FF-FF α is active if ϕ ≤ min{( F1 ) α , ( F2 ) α }; • x CF-FF α is active if ϕ > min{( F1 ) α , ( F2 ) α } = ( F1 ) α ; • x FF-CF α is active if ϕ > min{( F1 ) α , ( F2 ) α } = ( F2 ) α .
Since these conditions on ϕ are exhaustive and mutually exclusive, we conclude that (1) has a unique equilibrium point x α . 2 Remark 10. (Effective capacity). Notice how the effective capacities ( F1 ) α , ( F2 ) α allow to identify the route on which Fig. 3. Two examples of the partition of Ω α into mode regions. The system parameters are the same as in Section 3.2.

Notice the difference in terms of the number of mode regions between the two plots. The gray arrows represent the vector field at each point.

congestion will arise: the lowest effective capacity route is the one getting congested as ϕ increases. Notice that ϕ cannot exceed both effective capacities ( F1 ) α , ( F2 ) α . Indeed, one can verify that ϕ ≤ ( F1 ) α and ϕ ≤ ( F2 ) α are mutually exclusive and exhaustive conditions.

Global asymptotic stability

We now prove the global asymptotic stability of x α . Theorem 11. Equilibrium x α is globally asymptotically stable for any α.

Proof. Following Remark 7, we limit our analysis to region P α . Consider then the two lines such that ẋ1 = 0 and ẋ2 = 0, respectively:

l (7) α : x 2 = B 2 1 B 1 + 2v 1 ϕ x 1 -1 , l (8) α : x 2 = B 2 ϕ ϕ + 2v 2 B 2 x 1 B 1 + 1 . Lines l (7) α , l (8)
α create the following partition of P α :

R ++ α = {x ∈ P α : ẋ1 , ẋ2 > 0}, R +- α = {x ∈ P α : ẋ1 > 0, ẋ2 < 0}, R -- α = {x ∈ P α : ẋ1 , ẋ2 < 0}, R -+ α = {x ∈ P α : ẋ1 < 0, ẋ2 > 0}. (18)
The regions in (18) can be divided into two couples, R ++ α , R -- α and R +- α , R -+ α , where each couple correspond to one of the two double cones originating from the intersection of l

α might change significantly. To see this, observe that the intersection point between lines l

(7) α , l (8) α corresponds to x FF-FF α , i.e.,
x FF-FF α = l (7) α ∩ l (8) α . It can be verified that if (12) does not hold, then one among ( 14) and ( 16) does, and therefore x FF-FF α / ∈ P α . As a consequence, depending on whether x FF-FF α belongs to P α or not, all four regions in (18) will be non-empty or not, respectively. To see this, one can inspect Figure 4. On the other hand, we can see that R ++ α will always be nonempty, in that both ẋ1 and ẋ2 are positive at (0, 0) and x FF-FF α will always differ from (0, 0). Another interesting fact to notice is that

x CF-FF α = l (1) α ∩ l (8) α , x FF-CF α = l (2) α ∩ l (7) α . (19)
Indeed, this implies that

x α ∈ R ++ α ∪ R -- α , where R ++ α ∪ R -- α
is a non-empty, compact and connected set. On the contrary, notice that R +-

α ∪ R -+
α , is a disconnected set, although still compact. Finally, by definition of l (7) α and l (8) α , the mutual positions of the four regions in (18) will be always the same. Indeed, l

α and l (8) α have a negative and a positive intercept on the x 2 -axis and the slope of l (7) α is always higher then the slop of l (8) α . After these premises, we now prove the thesis by proving the following claims.

• R ++ α ∪R -- α is positively invariant. The normal vectors of l

α = - 1 B 1 + 2v 1 ϕ , 1 , - → n (8) + α = ϕB 2 B 1 (ϕ + 2v 2 B 2 )
, -1 , respectively. In both cases, the scalar product with the vector field evaluated at a point lying on the line in question (different from x α ) is positive. One can repeat the same process for R -α by considering the normal vectors

- → n (7) - α = -- → n (7) + α , - → n (8) - α = -- → n (8) + α .
• Every trajectory of the system with initial condition contained in R ++ α ∪ R -- α must converge to the unique equilibrium point of the system x α . This comes from R ++ α ∪R -- α being positively invariant and the components of every trajectory inside this region are monotone. Combining these two facts with the compactness of R ++ α ∪R -- α , we g that the trajectories converge to an equilibrium point contained in R ++ α ∪ R -- α . The claim follows from x α being the only equilibrium point in R ++ α ∪ R -- α .

Fig. 4. Examples of different partitions of P α . The system parameters are equal to the ones used in Figure 3.

• Every trajectory of the system with initial condition contained in R +- α ∪ R -+ α either enters R ++ α ∪ R -- α or converges to x α . By the definitions of regions R +- α , R -+ α , also in this case each trajectory with initial condition in R +- α ∪R -+ α will be monotone. Then, since the trajectory is contained in the positive invariant region P α , it will admit a limit point in P α , but the latter cannot be contained in R +- α ∪ R -+ α by definition. If the limit point lies on the border of R +- α ∪ R -+ α , then the trajectory will converge to it asymptotically. Note that the limit point can only be the unique equilibrium of the system x α . If instead the limit point is outside the closure of R +- α ∪ R -+ α , the trajectory will hit the border of R +-

α ∪ R -+ α in finite time and enter R ++ α ∪ R -- α .
Then, from the previous claim, we get asymptotic convergence to x α . This concludes the proof.

2

Theorem 11 guarantees the convergence to the unique equilibrium point of the system x α . Combining this with Proposition 9, we see that there are cases in which the system converges to an equilibrium point whose associated recommendation fails to satisfy the user traffic demand ϕ. This drawback stems from the fact that recommendations are based exclusively on traffic densities and ignore other important features, e.g., route capacities. This means that route recommendations are responsible for traffic congestion originated at one of the network entries and highlights a critical issue arising from its use.

Case study from Grenoble, France

Consider a pair of routes with parameters (2022): route 1 corresponds to traveling east-west along the Grenoble South Ring and route 2 corresponds to traveling east-west by crossing the city center. Fig. 5 shows how the demand fractions, the traffic densities and the fraction of unsatisfied demand at equilibrium evolve as the user demand increases. As outlined by Proposition 9, considering that min{( F1 ) α , ( F2 ) α } = ( F2 ) α ≈ 2494 veh/h, when ϕ exceeds this threshold, route 2 becomes externally congested at equilibrium. Indeed, for ϕ ≥ ( F2 ) α , even if the fraction of user demand directed towards route 2 keeps increasing, its density and its inflow stay constant, because the route supply has reached its maximum. This failure to satisfy user demand arises because (5) only takes into consideration the occupancy indices. If ϕ keeps growing higher than the effective capacity of route 2, then a growing fraction of user demand will be sent to route 2, since its occupancy index will not grow.

This congestion phenomenon is a drawback stemming from (5), which could be avoided by making a wiser choice of routing ratios. Restricting our attention to constant routing ratios and recalling that the network is welldesigned with respect to user demand, there exists a unique routing ratio pair r * α = (r * 1 , r * 2 ) ⊤ such that ϕ(r * α ) i ≤ F i , i = 1, 2, ∀ϕ < F 1 + F 2 . Indeed, Figure 5 demonstrates that the routing ratios

r * α = F 1 F 1 + F 2 , F 2 F 1 + F 2 ⊤ = 3500 4600 , 1100 4600
⊤ are capable of satisfying all possible values of user demand not exceeding F 1 + F 2 , thus causing no demand loss.

CONCLUSIONS

In this paper we assessed the effects of route planner apps on traffic congestion. We proposed a model consisting in a state-dependent switching system which considers the case of an origin-destination pair connected by two alternative non intersecting routes. By means of a complete stability analysis, we have shown that for sufficiently high values of user demand, route recommendations only partially satisfy the user demand, hence creating congestion.

Future work is headed towards two main directions. The first one is extending our analysis to the case of more complex network topologies, e.g., origin-destination pairs connected by intersecting or multiple routes. The second one is to extend the model and the stability analysis to account for the users to receive imperfect and/or delayed information about the current state of traffic.

Fig. 5. The plots refer to Section 3.2 and they show how system (1)-( 5) (solid lines) fails to meet the user demand after ϕ reaches ( Fα ) 2 = min{( Fα ) 1 , ( Fα ) 2 }. On the contrary, the fixed routing ratio pair r * α (dashed lines) is able to entirely satisfy ϕ. Magenta lines refer to route 1, blue lines refer to route 2.

Fig. 1 .

 1 Fig. 1. Graph representation of the origin-destination pair considered.

Fig. 2 .

 2 Fig. 2. The plot shows how the logit law depends on η.Notice how the logit law recommendations become more sensitive to variations in x2 B2 -x1 B1 as η decreases.

F 1 =

 1 3500 veh/h, C 1 = 41.2 veh/km, B 1 = 250 veh/km, F 2 = 1100 veh/h, C 2 = 22 veh/km, B 2 = 120 veh/km, and ϕ ∈ [0, F 1 + F 2 ]. These values have been chosen to represent realistic travel conditions in Grenoble (France), based on data from the GTL traffic platforms by Canudas de Wit et al. (2015); Rodriguez-Vega et al.

Table 1 .

 1 Route modes notation

		Route entry Route exit
	FF	free-flow	free-flow
	CF	congested	free-flow
	FC	free-flow	congested
	CC congested	congested