Dieter Fiems
email: dieter.fiems@ugent.be

Balakrishna J Prabhu
email: balakrishna.prabhu@laas.fr

We consider a Markovian queueing model for computing the traffic density and travel times in a city at a macroscopic scale during rush hour. Accounting for the speed/density relation of the macroscopic fundamental diagram of traffic flow, we assume that the service rates of the queueing model at hand are state-dependent. We focus on the fluid limit and obtain a set of differential equations that describe the evolution of the traffic density at the level of neighbourhoods. We also calculate the time-dependent travel times for specific flows in the city and consider the rational time-dependent choice between public and private transport, assuming that there is a congestion-free public alternative to private transportation. Numerical examples reveal that a small reduction in peak traffic can significantly reduce the average travel times.

Macroscopic modelling and analysis of flows during rush-hour congestion 1 Introduction

Most major urban areas suffer from traffic congestion during the morning and evening commutes. Apart from a waste of time, congestion is a major source of pollution and a health hazard [START_REF] Levy | Evaluation of the public health impacts of traffic congestion: a health risk assessment[END_REF]. Several types of remedial measures have been adopted by local authorities to reduce congestion and its impact on the society. These measures take the form of a congestion charge like is the case in cities such as London or Stockholm [START_REF] Anas | The cost of congestion and the benefits of congestion pricing: A general equilibrium analysis[END_REF], or, as is done in France and Belgium, a restriction on the entry of vehicles during episodes of peak pollution -either based on the age of the vehicle and its pollution metrics or alternating between even and odd number platesin certain parts of the city. Proposing alternative paths is another mechanism for reducing congestion at bottlenecks. This has now become possible in real-time thanks to several online applications that can orient drivers towards the paths which offer the least expected travel times. The users of such applications send travel information to a central server. If there are sufficient users of the application in an area, the aggregation of the collected data yields an accurate assessment of the traffic situation in that area. For each user, optimal paths are then calculated and the corresponding travel advice is returned to the users [START_REF] Hoseinzadeh | Quality of location-based crowdsourced speed data on surface streets: A case study of waze and bluetooth speed data in sevierville[END_REF][START_REF] De O. Ramos | Analysing the impact of travel information for minimising the regret of route choice[END_REF].

A third mechanism is to incentivise public transport. For such schemes to work, the public transport network has to be dense, reliable, and, more importantly, better in terms of travel times and cost. A properly dimensioned public transport network can provide an ecologically friendly alternative to personal vehicle usage. Moreover, public and private transportation can be successfully combined by park-and-ride systems [START_REF] Ortega | An integrated model of park-and-ride facilities for sustainable urban mobility[END_REF]. A park-and-ride system combines an easily accessible parking area with good connectivity to the public transport network.

For the second and third mechanisms to work, it is important to be able to accurately estimate the travel times between major hubs. If a commuter can see in real-time that it will be faster (or less costly) to travel by public transport, it will give an additional incentive to use the public transport network. Further, if we assume that commuters are rational and choose the alternative with the least cost, we can estimate how many commuters will take the public transport. Such estimates can then be used to dimension the public transport network by appropriately choosing the frequencies and the vehicle sizes on different bus routes.

Contributions and related work

The main contribution of this paper is a queueing-theory-based method for the computation of travel times for certain flows in road traffic networks. Road traffic modelling has a rich history with models on both macroscopic scales (vehicular flows are modeled as fluids) as well as on microscopic scales (vehicles are discrete entities) [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF][START_REF] Schadschneider | Stochastic Transport in Complex Systems[END_REF][START_REF] Prigogine | Kinetic theory of vehicular traffic[END_REF][START_REF] Kerner | The Physics of Traffic -Empirical Freeway Pattern Features, Engineering Applications, and Theory[END_REF]. While the link between queueing theory and road traffic networks has been established previously [START_REF] Vandaele | A queueing based traffic flow model[END_REF][START_REF] Chen | A traffic breakdown model based on queueing theory[END_REF][START_REF] Boon | Applications of polling systems[END_REF], it was only recently that this connection was used to compute travel times at the level of a single neighbourhood [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF]. The results were then generalised to networks of neighbourhoods in [START_REF] Fiems | Macroscopic modelling and analysis of rush-hour congestion[END_REF]. This is similar to how Jackson networks [START_REF] Jackson | Jobshop-like queueing systems[END_REF] or BCMP networks [START_REF] Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF] extend single server queueing models.

In this paper, we extend the travel-time analysis of [START_REF] Fiems | Macroscopic modelling and analysis of rush-hour congestion[END_REF] by introducing a richer description of the state of the road traffic network, which allows for separating different flows in the network and for calculating the expected travel times for individual flows. The model in [START_REF] Fiems | Macroscopic modelling and analysis of rush-hour congestion[END_REF] had a single flow with its routing matrix whereas the current paper allows for multiple flows with distinct routing matrices. As in our previous work [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF] and [START_REF] Fiems | Macroscopic modelling and analysis of rush-hour congestion[END_REF], based on the travel-time analysis, we also study a public transport game in which commuters can choose between using their own vehicles or taking public transport. The main assumption in this game is that public transport networks are not impacted by congestion and their travel times are thus easier to estimate. This assumption is certainly true for subways and tramways, and is becoming more realistic for buses in cities with dedicated bus corridors. For a given fixed cost of travel by the public transport network, the Wardrop equilibrium is computed in order to determine the fraction of commuters in each neighbourhood that will switch from private vehicles to public transport. One can then compute the influence of pricing on the congestion and, as a consequence, on the travel times and the pollution. In addition, for a certain set of parameters, we also numerically compute the Price of Anarchy (PoA) which is the ratio of the social cost at the Wardrop equilibrium to the optimum social cost. For this, an optimal control problem is first formally defined. Since this problem does not have a closed-form solution, the PoA is obtained by using numerical solvers.

The Wardrop equilibrium concept under study explicitly depends on time. This equilibrium concept differs from the classic Wardrop equilibrium in two important ways. Firstly, the intensity of newly arriving vehicles can vary over time, such that also the decision to opt for public transport varies over time. Secondly, vehicles remain in the neighbourhood for some time, contributing to the vehicle density. This not only means that the time-dependent Wardrop equilibrium relies on a considerably more detailed queueing analysis, but also that public transport decisions at some point in time can be affected by both past and future decisions. Apart from our previous work [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF][START_REF] Fiems | Macroscopic modelling and analysis of rush-hour congestion[END_REF], models with time-dependent demand have been considered in [START_REF] Daniele | Time-dependent traffic equilibria[END_REF][START_REF] Nagurney | The internet, evolutionary variational inequalities, and the time-dependent Braess paradox[END_REF][START_REF] Aussel | Existence of time-dependent traffic equilibria[END_REF]. These authors show the existence of a time-dependent Wardrop equilibrium where the cost of a decision at a point in time depends on the distribution of the load over the complete time-interval under consideration. In particular, the problem is mathematically defined by a cost operator that maps the demand functions on cost functions for the different routes. This operator must be pseudomonotone or hemicontinuous in [START_REF] Daniele | Time-dependent traffic equilibria[END_REF], hemicontinuous in [START_REF] Nagurney | The internet, evolutionary variational inequalities, and the time-dependent Braess paradox[END_REF], and quasimonotone in [START_REF] Aussel | Existence of time-dependent traffic equilibria[END_REF]. These properties are not easy to verify for our cost operator since, as will be seen later, the mean travel times are obtained as the solution of a set of non-linear differential equations. Therefore, in this paper, we shall assume that the equilibrium exists and satisfies the form in [START_REF] Daniele | Time-dependent traffic equilibria[END_REF].

Finally, we show how to compute a congestion-based cost of the public transport network so that the Wardrop equilibrium matches the social optimum in the fixed cost setting. For time-invariant congestion games, it is known that tolls or taxes can be imposed to achieve a socially optimum behaviour in a game setting (see, e.g., [START_REF] Cole | Pricing network edges for heterogeneous selfish users[END_REF]). We derive an analogous result for the time-varying case and for the specific traffic game considered here. This is something that was not done in [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF] for the single neighbourhood model.

The macroscopic fundamental diagram

To compute the travel time of a vehicle in a road traffic network, we shall model the vehicle as a customer in a queueing network, while neighbourhoods will be assigned the role of servers. The specificity of road traffic networks is that the arrival rates of vehicles are time-dependent and the departure rates of vehicles depend on the congestion (or the state) of the network. The higher the congestion, the lower is the rate at which vehicles exit the network. This relationship between the exit rate (or flow in vehicles per minute) and the vehicle density (vehicles per unit length) is captured by what is known as the macroscopic fundamental diagram (MFD) which was first introduced in [START_REF] Daganzo | Urban gridlock: Macroscopic modeling and mitigation approaches[END_REF] for single-lane traffic. Here macroscopic refers to the spatial scale of neighbourhoods. This is in contrast to the microscopic fundamental diagram which gives this relationship at the spatial scale of road segments [START_REF] Lehmann | Distribution function properties and the fundamental diagram in kinetic traffic flow theory[END_REF][START_REF] Kerner | The Physics of Traffic -Empirical Freeway Pattern Features, Engineering Applications, and Theory[END_REF][START_REF] Kühne | Transportation Research Circular E-C149 (75 Years of the Fundamental Diagram for Traffic Flow Theory: Greenshields Symposium[END_REF]. These macroscopic diagrams have in fact been validated using measurements carried out, for example, in Yokohama [START_REF] Geroliminis | Existence of urban-scale macroscopic fundamental diagrams: Some experimental findings[END_REF] and Toulouse [START_REF] Buisson | Exploring the impact of homogeneity of traffic measurements on the existence of macroscopic fundamental diagrams[END_REF]. The rescaled and interpolated MFDs for these two cities are shown in Figure 1.

A typical flow-density MFD has an inverted cup shape (like a concave function) as shown in the left pane of Figure 1. When the vehicular density is small (towards the left edge of the curve), the flow initially increases with the density because congestion is yet to form and vehicles are travelling at the maximum permissible speed. As the density increases further, congestion sets in, and the vehicular speed reduces. This leads to an inversion in the average flow which starts to decrease and becomes very small in case of traffic jams. This type of rate curves are not very typical in classic queueing networks.

The flow-density MFD gives the total rate at which vehicles leave the neighbourhood. To compute the travel times, we need the velocity of individual vehicles, which is µ(q)/q. The intuitive explanation of this formula is as follows. Consider a vehicle that enters a small strip of length . The time it takes for this vehicle to traverse the strip will be the time required for all the vehicles that were present in this strip at the time of the entry to leave the strip (assuming no overtaking). At density q, there are q vehicles, and at an average flow of µ(q) vehicles/min, it will take q /µ(q) minutes to traverse the strip of length . This gives a velocity of µ(q)/q. The decrease of the velocities with increasing densities is shown in the speed-density macroscopic diagram in Figure 1. This plot shows the velocity of a vehicle as a function of the density, relative to the free-flow velocity (q = 0).

For numerical examples, we shall use the MFD obtained from measurements in the city of Yokohama as the state-dependent service rate of servers.

Organisation

The rest of the paper is organised as follows. In Section 2, we introduce a Markovian model for vehicles in a road network. A set of partial differential equations for the distribution of the travel times are derived. We then obtain the corresponding equations in the fluid limit when the number of vehicles becomes large. This regime also leads to a simpler set of differential equations for the mean travel times. Section 3 presents the Wardrop equilbrium for the game with public transport as an alternative. The Wardrop equilibrium is then compared to the socially optimal travel choice and the PoA is calculated in the Section 4. We then close with some conclusions in Section 5. Some results are deferred to appendices. In A, we formally prove the fluid limit of Section 2. B then derives the structure of the optimal control policy of Section 4. Finally, C provides in additional illustrative numerical example.

Macrosocopic queueing model

We propose a Markovian queueing network with random routing for modelling congestion in a city at a macroscopic level. To be more precise, we model a city as a finite set of interconnected queues, where each queue represents a neighbourhood of the city, the number of vehicles in the neighbourhood being the queue content. In contrast to classic Jackson networks, the service rate of each queue depends on the queue size, to reflect the relation between the speed and density of vehicles as described by the macroscopic fundamental diagram as discussed in section 1.2.

Markov model

Consider a city and a set of neighbourhoods N = {1, 2, . . . , N } within that city. A neighbourhood could, in theory, be the entire city itself. Traffic arriving at the neighbourhoods stem from different flows, let F = {1, 2, . . . , F } denote the set of these flows. For flow f ∈ F, vehicles arrive at the city in accordance with a Poisson process with time-dependent arrival rate λ f (t). A vehicle from flow f enters the city in neighbourhood n ∈ N with probability r f n , independent from the other vehicles. The vehicles then move from neighbourhood to neighbourhood till they reach their destination. We introduce the following notation for describing how vehicles are routed through the city. For a vehicle of flow f ∈ F in neighbourhood m ∈ N , let r f mn denote the probability that it leaves for another neighbourhood n, and let r f m0 denote the probability that the vehicle reaches its destination in neighbourhood m.

The duration of a journey depends on the total distance of the journey as well as on the speed during the journey. The distances the cars travel within each neighbourhood (either to their destination or to another neighbourhood) are assumed to constitute a sequence of independently and identically exponentially distributed random variables with rate 1. With this assumption, vehicles leave with probabilities proportional to their speed. Moreover, taking some other rate is equivalent to rescaling time. The speed of vehicles inside the different neighbourhoods at a given time instant depends on the average density within the neighbourhood in accordance with the macroscopic fundamental diagram (MFD). Therefore, the number of vehicles that leave the neighbourhood or that reach their destination will also depend on the density, or equivalently, on the number of vehicles in the area. More specifically, as the density in a neighbourhood is proportional to the queue size in that neighbourhood, and the number of departures from the neighbourhood is proportional to the density, the departure rate in neighbourhood m equals,

µ m (q) = θ m F m (Θ m q) ,
when there are q vehicles in neighbourhood m. Here, θ m and Θ m are given constants and F m denotes the macroscopic fundamental diagram of neighbourhood m. As µ m (q) is the departure rate of all vehicles in the area, the departure rate of an individual vehicle equals µ m (q)/q.

We can now study the evolution of the number of vehicles in the different neighbourhoods.

Let Q f n (t) denote the number of vehicles of flow f (moving around) in neighbourhood n at time t, let Q(t) = [Q f n (t)] n∈N ,f ∈F , and let π(i; t) = Pr[Q f n (t) = i f n , n ∈ N , f ∈ F] = Pr[Q(t) = i] denote the probability that there are i f n vehicles of flow f in neighbourhood n at time t, for n ∈ N and f ∈ F, with i = i f n n∈N ,f ∈F ∈ N N F . For further use, for a given state vector i, let i m denote the number of cars in neighbourhood m, i m = f ∈F i f m .
In view of the assumptions above, we have the following transitions from state i ∈ N N F :

There is a new arrival of flow f ∈ F in neighbourhood n ∈ N with rate λ f (t)r f n . Such an arrival induces a transition to state i + e f n .
Here, e g m = [1 {n=m} 1 {f =g} ] n∈N ,f ∈F is a vector of zeroes, apart from the element corresponding to neighbourhood m and flow g which is one.

A vehicle of flow f moves from neighbourhood m to neighbourhood n with rate µ m (i m )(i f m /i m )r f mn , the new state being i + e f ne f m . Here, µ m (i m ) is the total outflow from neighbourhood m, the factor (i f m /i m ) is the probability that a random car that is leaving from the neighbourhood belongs to flow f , and r f mn is the probability that this vehicle moves to neighbourhood n. Hence, we implicitly assume that each vehicle in the neighbourhood is equally likely to depart from the neighbourhood (either by arriving at the destination or by leaving for another neighbourhood). In queueing terms, we assume that the "server" uses a processor sharing or random order of service discipline. Since vehicles are moving simultaneously with the same velocity, they can be thought of receiving service simultaneously with the same rate, matching with the processor-sharing discipline.

Finally, a vehicle of flow f reaches its destination in neighbourhood m with rate µ m (i m )(i f m /i m )r f m0 , the new state being ie f m . The description of the state transitions then immediately yields the following set of forward Chapmann-Kolmogorov equations,

∂ ∂t π(i; t) = f ∈F m∈N n∈N * π(i -e f n + e f m ; t)µ m (i m + 1) i f m + 1 i m + 1 r f mn + f ∈F m∈N π(i -e f m ; t)λ f (t)r f m - m∈N π(i; t)µ m (i m ) - f ∈F λ f (t)π(i; t) ,
with N * = N ∪ {0}, and with π(i; t) = 0 for i / ∈ N F N . In the expression above, we assumed e f 0 = 0 which is in line with our definition above. For Markov chains with non-homogeneous rates, a sufficient condition for the existence of a unique solution to the forward equations is that the transition rates are continuous in time [START_REF] Ye | Existence and regularity of a nonhomogeneous transition matrix under measurability conditions[END_REF]. In the present section, the arrival rates are assumed to be continuous and the MFD is independent of time. However, when the transition rates are not continuous due to, for example, a control mechanism (see Sections 3 and 4), other conditions like measurability of the transition rates and the integrability of the rate of leaving a state need to be verified [START_REF] Ye | Existence and regularity of a nonhomogeneous transition matrix under measurability conditions[END_REF]. In the remainder of this paper, we assume that our control policies satisfy these conditions.

Let W f n (τ ) denote the remaining travel time of a vehicle of flow f in neighbourhood n at time τ , and let

ν f n (τ, t|i) = Pr[W f n (τ ) > t|Q(τ ) = i]
denote the complementary distribution function of the remaining travel time of this vehicle, conditioned on having Q(τ ) = i vehicles of the different flows in the different neighbourhoods at time τ . Conditioning on the possible events in the interval (τ, τ + h], we can express ν f n (τ, t + h|i) as follows,

ν f n (τ, t + h|i) = g∈F m∈N ν f n (τ + h, t|i + e g m )λ g (t)r g m h + g∈F m∈N \{n} k∈N * ν f n (τ + h, t|i -e g m + e g k )µ m (i m ) i g m i m r g mk h + g∈F \{f } m∈N * ν f n (τ + h, t|i -e g n + e g m )µ n (i n ) i g n i n r g nm h + m∈N * ν f n (τ + h, t|i -e f n + e f m )µ n (i n ) i f n -1 i n r f nm h + m∈N ν f m (τ + h, t|i -e f n + e f m )µ n (i n )r f nm 1 i n h + ν n (τ + h, t|i)   1 - g∈F λ g (t)h - m∈N µ m (i m )h   + o(h) ,
Note that we again assume that each vehicle in the neighbourhood is equally likely to depart. Sending h → 0, we further have,

∂ ∂t ν f n (τ, t|i) - ∂ ∂τ ν f n (τ, t|i) = g∈F m∈N ν f n (τ, t|i + e g m )λ g (t)r g m + g∈F m∈N \{n} k∈N * ν f n (τ, t|i -e g m + e g k )µ m (i m ) i g m i m r g mk + g∈F \{f } m∈N * ν f n (τ, t|i -e g n + e g m )µ n (i n ) i g n i n r g nm + m∈N * ν f n (τ, t|i -e f n + e f m )µ n (i n ) i f n -1 i n r f nm + m∈N ν f m (τ, t|i -e f n + e f m )µ n (i n )r f nm 1 i n -ν f n (τ, t|i)   g∈F λ g (t) + m∈N µ m (i m )   ,
Finally, the expected travel time of a vehicle that arrives at time τ in neighbourhood n is,

W f n (τ ) = i∈N N F π(i; t) ∞ 0 ν f n (τ, t|i + e f n )dt .
Here we used the observation that the mean travel time of a vehicle of flow f arriving at time τ in neighbourhood n while there are i vehicles of the different flows in the different neighbourhoods equals the mean remaining travel time of a vehicle in neighbourhood n when there are i + e f n vehicles in the different neighbourhoods.

Fluid limit

As the fundamental diagram translates to state-dependent service rates, there is no simple analytic solution for the infinite systems of differential equations for π(i; t) and ν f n (τ, t|i). Moreover, numerically solving these equations is computationally demanding. The process Q(t) is a timeinhomogenous density dependent population process; see e.g. [START_REF] Mukherjee | Optimal service elasticity in large-scale distributed systems[END_REF][START_REF] Horváth | Mean field analysis of join-below-threshold load balancing for resource sharing servers[END_REF][START_REF] Van Spilbeeck | On the impact of job size variability on heterogeneityaware load balancing[END_REF] for recent queueing theoretic applications of such processes. We can study the fluid limit of the system, that is, we consider a sequence of models Q K (t), the Kth model having arrival rate λ f (t)K for the f th flow and departure rate K μn (x/K) from the nth neighbourhood when there are x vehicles in that neighbourhood. We then study the process q(t) = lim K→∞ Q K (t)K -1 . The parameter K is the scale at which we are making measurements. As the scale becomes large, the number of vehicles also grows proportionally, and hence we have to divide Q f n (t) by K to obtain a quantity which goes to a finite limit. This quantity can be thought of as the density of the vehicles. By the functional strong law of large numbers, the randomness of the movement of individual vehicles is washed out by the scaling. This leads to a considerable reduction of the complexity of the analysis since we are no longer dealing with individual cars but instead deal with a large number of cars which behave in a similar way.

Then, by writing the evolution of Q f n (t) as the difference of randomly time-changed Poisson processes and applying the functional strong law of large numbers for Poisson processes, we find that the limiting process q f n (t) adheres the following set of ordinary differential equations (ode),

qf n (t) = λ f (t)r f n -μn (q n (t)) q f n (t) q n (t) + m∈N ,qm(t)>0 μm (q m (t)) q f m (t) q m (t) r f mn , (1)
for n ∈ N and f ∈ F, and with,

q m (t) = f ∈F q f m (t) .
We formally prove the fluid limit and discuss the conditions on λ f n and µ n in more detail in appendix A.

For the travel time calculations, we scale the arrival process and service process as before. However, we retain the randomness of the random order of service (or processor sharing) discipline. Hence, in the limit, the travel times are still random, let W f n,K (τ ) denote the travel time from neighbourhood n at time τ for the Kth model, and w f n (τ, t) be the complimentary waiting time distribution in the fluid limit,

w f n (τ, t) = lim K→∞ Pr[W f n,K (τ ) > t] .
By evaluating the limit above, we obtain the following set of differential equations for these complimentary travel time distributions,

∂ ∂t w f n (τ, t) - ∂ ∂τ w f n (τ, t) = -w f n (τ, t) μn (q n (τ )) q n (τ ) + m∈N w f m (τ, t)r f nm μn (q n (τ )) q n (τ ) . (2)
This equation can also be obtained directly by conditioning on whether or not the vehicle under consideration departs, remains in the neighbourhood, or leaves for another neighbourhood in the interval (τ, τ + h]. As the remaining travel time at time τ only exceeds t + h, if there is no departure in (τ, τ + h] and the remaining travel time at time τ + h exceeds t, we have,

w f n (τ, t + h) = 1 - μn (q n (τ )) q n (τ ) h w f n (τ + h, t) + m∈N w f m (τ + h, t)r f nm μn (q n (τ )) q n (τ ) h + o(h) .
Substracting w f n (τ + h, t) from both sides of the equation above, dividing by h and taking the limit h → 0 yields equation [START_REF] Anas | The cost of congestion and the benefits of congestion pricing: A general equilibrium analysis[END_REF].

Finally, the mean travel time of a vehicle arriving at time τ in neighbourhood n can then be computed by integrating w n (τ, t) over t, that is,

wf n (τ ) = ∞ 0 w f n (τ, t)dt . (3)
Integrating both sides of (2) over t, and using (3), we find the following differential equation for the mean travel times,

d dτ wf n (τ ) = wf n (τ ) μn (q n (τ )) q n (τ ) -1 - m∈N wf m (τ )r f nm μn (q n (τ )) q n (τ ) . (4)
Observe that we do not need to solve (2) to solve (4). The mean travel times can be obtained independently by solving (4) directly.

In contrast to the system of differential equations for the traffic densities (1), the differential equation above cannot be used to numerically calculate the time-dependent travel times. Indeed, in order to numerically solve the system of ordinary differential equations, the initial expected travel times w f n (0) are needed. Note that these do depend on the future evolution of the traffic densities. To overcome this difficulty, we will reverse time. Assuming that λ f n is constant for t sufficiently large, the traffic density in the different neighbourhoods (in the fluid regime) and the corresponding travel times will become approximately constant as well. We therefore choose a sufficiently large T and approximate the mean travel times at time T by the asymptotic mean travel times w f n (T ) ≈ lim τ →∞ w f n (τ ). For ease of notation, introduce ζf n (τ ) = wf n (Tτ ). We then obtain the following system of ordinary differential equations for ζf n ,

d dτ ζf n (τ ) = 1 -ζf n (τ ) μn (q n (T -τ )) q n (T -τ ) + m∈N ζf m (τ )r f nm μn (q n (T -τ )) q n (T -τ ) . (5)
In contrast to the system of equations ( 4), the initial value of the ode can now be calculated. Indeed, by assuming that λ f n (t) is constant and by sending t → ∞, we find that the initial value of the ode solves the linear system of equations,

ζf n (0) μn (q n (T )) q n (T ) = 1 + m∈N ζf m (0)r f nm μn (q n (T )) q n (T ) . ( 6
)
Remark 1. The assumptions on the functions λ f n do not constrain the problems that can be solved by the method at hand. Indeed, if λ f n is not constant for large time values in the time interval under study, it is straightforward to extend the interval such that this is the case. This should not affect the results in the original time interval of interest. The time interval needs to be large enough such that any future traffic patterns do not affect the travel times in the region of interest. For given fixed arrival rates, the differential equations describing the evolution of the densities typically have multiple fixed points. Therefore, one cannot decide on the stationary behaviour by solving a fixed point equation. However, for a given traffic scenario, the solution of the differential equations is unique under mild assumptions (see appendix A), so that there is no problem identifying the fixed point the ode's converge to, if the arrival rates are kept constant for a long time.

Numerical example

We now illustrate our approach by a numerical example. We consider a city divided into 4 neighbourhoods as depicted in Figure 2. Traffic only arrives in the outer areas 2 to 4. We consider three distinct flows. The first flow serves as background load for the other flows. Let λ 1 (t) denote the arrival rate (AR) in area i ∈ {2, 3, 4}:

λ 1 2 (t) = λ 1 3 (t) = λ 1 4 (t) = λ 1 (t).
Vehicles of this flow leave for the centre neighbourhood 1 with probability ψ = 0.4, to any of its neighbours with probability φ = 0.1 or park in the neighbourhood with probability 1ψ -2φ. There is no random routing for flows 2 and 3. All vehicles of flow 2 arrive at neighbourhood 2 with rate λ 2 (t) = λ 2 2 (t), and cross this neighbourhood to reach their destination in neighbourhood 1. All vehicles of flow 3 arrive at neighbourhood 2 with rate λ 3 (t) = λ 2 3 (t) which is their final destination. Finally, departures in each area are governed by the MFD of Yokahama, which is properly rescaled to reflect realistic travel times (around 15 minutes in total for flow 1 when there is no congestion).

Figure 3 shows the evolution of the traffic density and the expected waiting times in the fluid limit regime with arrival rates as depicted. In the left pane, most traffic is background traffic (flow 1). In the right pane, there is still considerable background traffic, but in neighbourhood 2, most of the traffic comes from flows 2 and 3. Notice that the arrival rates in the fluid regime are very small. This is not unexpected: the fluid limit is a deterministic approximation for the city with arrival rates Kλ f i , where K is sufficiently large. On both panes, the arrival rate curve reaches its maximum value at t = 60, while the peaks of the traffic density and expected travel times are somewhat later. This is most pronounced for the traffic density in the centre neighbourhood 1. This is expected as all traffic towards the centre needs to cross the outside neighbourhoods, such that peak traffic is delayed. For the travel times, the maximum is reached slightly later than then the peak of the arrival rate, and average travel times typically drop more slowly. Finally, it is readily seen that the maximum traffic density exceeds 30% in some cases. This is typical in real traffic scenarios: at such traffic densities, the average flow decreases for increasing densities, see Figure 1.

To assess the accuracy of the fluid approximation, Figure 4 again shows the time-dependent waiting times, and compares these curves with the expected waiting times in the pre-limit process for different values of K as depicted. We rely on Monte-Carlo simulation to calculate these expected travel times. To be precise, we first simulated a single trajectory for the traffic densities of the different flows in the different neighbourhoods. For this trajectory, we then used Monte Carlo simulation to estimate the mean waiting time at various points in time. That is, for each time instant, we sampled the waiting time 5000 times (recall that the waiting time for a given evolution of the traffic densities is a random variable as the vehicle that leaves at a certain instant is randomly selected). We also calculated the 99% confidence intervals for the estimators of the conditional mean waiting times, but omitted these from the figure as their sizes are too small to be properly depicted. We considered 3 distinct scale values K. Practically, the values K = 1000, K = 5000 and K = 10000 correspond to having a peak arrival intensity at the city of 380, 1900 and 3800 vehicles per minute for the rates in the left pane, respectively. The corresponding rates on the right pane are 300, 1500 and 3000 vehicles per minute. For K = 1000, the simulation results considerably deviate from the fluid limit for the curves on the left pane. This is most prominent for the mean travel times for flow 2 and 3. This reflects the remaining randomness in the traffic density process for smaller K, which is most visible for the flows with smaller arrival rates. For K = 5000, the correspondence between simulation results and the fluid limit are already good, while the correspondence is very good for K = 10000. Even for K = 10000, the traffic intensity is not extremely high at the scale of a city. Hence we can conclude that the fluid approximation works in parameter settings of interest.

Public transport game

The derivations above not only allow for estimating the travel times of the vehicles in the city. Our results can also be used for dimensioning the capacity of public transport systems, and for assessing the impact of the public transport cost on congestion. In this section, we consider a scenario in which commuters have access to travel time estimates both for commuting by personal vehicles as well as by public transport. If the public transport system (PTS) offers a faster ride, a number of commuters may switch from personal vehicles to the PTS. Assuming commuters are rational, that is, they choose the mode of transport that minimises their expected travel times, we use concepts from game theory to compute the number (or the fraction) of commuters that will switch to the PTS. This can be used to estimate the load on the PTS and dimension its capacity accordingly. For simplicity, assume that taking the PTS incurs a cost, which depends on the flow, the neighbourhood and the time of departure, but not on the congestion in the road network. This cost includes the travel time in the public transport system, the travel time to the access points of the public transport system, the inconvenience of using public transport, costs related to possible disruptions of the service, etc. We assume that this cost can be expressed in terms of travel times: the cost of the public transportation system is the maximal travel time one is willing to undergo by private transport. For n ∈ N and f ∈ F, let C f n (t) denote the cost of the PTS at time t for a vehicle starting in neighbourhood n.

Remark 2. Note that the assumption that the travel cost does not depend on congestion is natural in case the public transportation system has dedicated lines. This can be either completely separated from the road network like a metro network, or consist of separate lanes embedded in the road network.

Time-dependent Wardrop equilibrium

We investigate the strategies of rational commuters when the choice of each commuter has a negligible impact on the travel times of the population, a solution concept introduced in game theory by Wardrop [30] in the context of choosing routes in road traffic networks. Known as the Wardrop equilibrium, it says that at the equilibrium choice of routes is such that the cost on each used route is the same and the cost on the unused ones is larger than that of the used ones. In contrast to the classic Wardrop equilibrium, our equilibrium explicitly depends on time. For this time-dependent Wardrop equilibrium, the choice at time t not only depends on the choices of the other commuters at time t, but also on the choices of other commuters (both prior and later than time t).

Let p f n (t) ∈ [0, 1] denote the fraction of commuters of flow f entering neighbourhood n that opt for private transport at time t. The function p f n is the time-dependent routing strategy for arrivals of flow f in neighbourhood n. For further use, let p = [p f n ] n∈N ,f ∈F be the set of routing strategies for the different flows in the different neighbourhoods. Such a set of routing strategies p = [p f n ] n∈N ,f ∈F constitutes a Wardrop equilibrium if, for each n ∈ N and f ∈ F such that λ f (t)r f n > 0, we have the following constraints on the travel times (see [START_REF] Daniele | Time-dependent traffic equilibria[END_REF], e.g.):

     wf n (t; p) < C f n (t) then pf n (t) = 1 , wf n (t; p) = C f n (t) then 0 < pf n (t) < 1 , wf n (t; p) > C f n (t) then pf n (t) = 0 . (7)
Here w f n (t; p) denotes the expected travel time for flow f in neighbourhood n, assuming that the arrival intensity of flow f in neighbourhood n equals λ f (t)r f n pf n (t). As mentioned in section 1.1, we do not prove the existence and the uniqueness of the equilibrium. It can be seen from ( 4) that, in general, there is no explicit expression for wf n (t; p), and showing properties like quasimonotonicity and/or hemicontinuity is not a trivial task for our cost operator that maps p to w.

The first equation states that all commuters in neighbourhood n prefer private transport if the cost of the PTS exceeds the expected travel time. The second equation states that if a non-zero fraction of commuters opt for PTS and a non-zero fraction of commuters opt for private transport, the cost of both should be equal. Finally, the last equality states that everyone uses the PTS if the cost of private transport exceeds that of the PTS.

To the best of our knowledge, the functions pf n (n ∈ N , f ∈ F) have no nice and easy analytical solution. Therefore, we resort to the following iterative numerical algorithm for their computation. Given the arrival curves λ f (t) and probabilities r f n , the fundamental diagrams μn (x) and the routing probabilities r f mn , we set p f n (t) = 1, and then update these probabilities according to

p f n (t) ← min 1, p f n (t)e -βn(w f n (t;p)-C f n (t)) , for λ f (t)r f n = 0, such that p f n → pf n .
Here β n is a parameter which determines the speed of convergence of the recursion. Small β n corresponds to conservative updates, such that convergence is slow. In contrast, for large β n , the update rule may never converge. Finally, note that for λ f (t)r f n = 0, the value pf n (t) has no meaning as there is no choice to be made in the absence of traffic.

Numerical example

We now calculate the Wardop equilibrium for the traffic scenarios of section 2.3 and consider public transport offerings for flows 2 and 3. The scenario on the left pane of Figure 5 corresponds to the scenario on the left pane of Figure 3, but now includes a PTS offering in neighbourhood 2, with a fixed cost of 25 minutes for flow 2 and 15 minutes for flow 3. As before, we depict the arrival rates, the traffic densities and the travel times. For comparison, we depict the arrival rates, traffic densities and travel times without the PTS offering in grey. Similarly, the scenario on the right pane of Figure 5 corresponds to the scenario of the right pane of Figure 3 with a PTS offering in neighbourhood 2, with a cost of 25 and 14 minutes for flow 2 and 3, respectively. For both scenario's, we used the same β n = 0.15 for all flows, and observed quick convergence to an approximate solution after about 50 iterations. The more accurate solution which is shown however required considerably more iterations (about 500). When the Wardrop conditions are almost satisfied, the probabilities pf n are only slightly modified in each iteration, such that many are required.

In both scenarios we can easily verify that the travel times never exceed the PTS cost. Moreover, once the travel times hit the PTS cost, either a fraction of commuters or all commuters of the flow opt for the PTS. This reduction of traffic is not only beneficial for the travel times for these flows. Also the travel time for flow 1 decreases as this flow benefits from the reduction in traffic as well.

Social optimum

When commuters choose selfishly between two options, it can lead to inefficiencies in terms of the social cost function defined by taking the average cost over all commuters. Since each commuter is minimising its own cost which is different from that of the other commuters, it fails to sufficiently account for the adverse impact it can have on the other commuters' costs. In our public transport dimensioning problem, there is a natural concept of social cost as well as a central authority (the city hall, for example) that may want to leverage its public transport system to arrive at the optimal social cost. However, implementing the optimal public transport strategy may not be that easy. For example, it may force certain commuters to take public transport which may be unpopular with the electorate or may require upgrading the infrastructure. The central authority may thus have to find a good balance between reducing the social cost while letting the commuters take decisions.

In this section, we investigate two issues. First, we investigate how inefficient the Wardrop equilibrium is. If the inefficiency is small, it may not be worth the effort to look for alternatives to reduce the cost. The concept of Price of Anarchy (PoA) [START_REF] Koutsoupias | Worst-case equilibria[END_REF] was introduced precisely for quantifying these inefficiencies. It is defined as the ratio of the social cost at the Wardrop equilibrium to that of the socially optimum cost. A higher value of the PoA implies that the inefficiency due to individual decision making is higher, which can be interpreted as a higher price for decentralised decision making.

Second, we investigate how the central authority can adjust the public transport infrastructure (fare, travel times, etc.) so that the Wardrop equilibrium coincides with the social optimum.

In game theory literature, this is known as mechanism design. The basic principle is to allow individuals to make decisions but design the game in such a way that the outcome of the game is precisely the social optimum. We shall show how this can be achieved by adjusting the cost of the public transport system during rush hour.

Optimal control problem

We begin by formulating the optimal control problem that the transport authority has to solve. Let p f n (t) be the probability with which a commuter of flow f entering in neighbourhood n uses her vehicle. Then, the mean transportation cost K f n (t) at time t of this commuter assuming policy p(t

) := [p f n (t)] f,n is K f n (t; p) := wf n (t; p)p f n (t) + (1 -p f n (t))C f n (t) . (8)
Note that the cost depends upon the entire function p and not just the function p evaluated at time t, p(t). Here, we allow the cost of public transport to depend upon the point of entry and the flow type of the commuter as well as the time of the day. In certain cities (like Paris), the fare depends on the number of subdivisions (called zones) that are traversed by the commuters.

A flow can correspond to commuters going between two different zones, for example. Their fare will then depend on their origin and destination zones.

The socially optimal policy is the one that minimises the total weighted mean cost, and is given by

p = arg inf p T2 T1 n,f λ f n (t)K f n (t; p)dt (9)
where [T 1 , T 2 ] is the rush hour interval. Note that the expression above includes the arrival rates λ f n (t) as the travel cost impacts more commuters if there are proportionally more arrivals. With p(t) as the solution of the set of equations ( 7), the PoA is then defined as,

PoA = T2 T1 n,f λ f n (t)K n (t; p)dt T2 T1 n,f λ f n (t)K n (t; p)dt .
As was the case in [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF], [START_REF] Kerner | The Physics of Traffic -Empirical Freeway Pattern Features, Engineering Applications, and Theory[END_REF] is not an optimal control problem for a general λ f n (t) because w(0) cannot be determined independently of q (see the discussion below (4)). In order to solve this problem, we shall make the same assumption as was made for obtaining [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF]. That is, we shall assume that λ f n (t) goes to a constant as t → ∞. Taking T 2 to be sufficiently large so that the system is stationary, we can then approximate (9) by the solution of following optimal control problem:

min p(t)∈[0,1] T2 T1 n,f λ f n (t)K f n (t; p)dt , (10)
subject to

d dt q f n (t) = λ f n (t)p f n (t) -μn (q n (t)) q f n (t) q n (t) + m∈N μm (q m (t)) q f m (t) q m (t) r f mn , (11)
d dt wf n (t) = wf n (t) μn (q n (t)) q n (t) -1 - m∈N r f nm wf m (t) μn (q n (t)) q n (t) , (12)
with the initial values of q n (0) computed using the steady state solution of (1) and with w(T ) obtained as the solution of ( 6).

Numerical example

We now give the social optimum policy, PoA, and the congestion-based pricing for the two traffic scenarios of section 3.2. The arrival rate profiles of the flows, the parameters of the MFD, and the routing within the city are the ones described in section 2.3. Recall that in the first scenario, the uncontrolled flow 1 has a much larger volume than the two controlled flows 2 and 3. The PTS cost for flow 2 is C 2 = 25, and for flow 3 is C 3 = 15. In the second scenario, the controlled flows have a much larger volume compared to the uncontrolled flow. The PTS costs for this scenario are C 2 = 25 and C 3 = 14. The optimal control problem (10) was solved using the software BOCOP.

The left (resp. right) pane of Figure 6 depicts the effective arrival rates of the three flows in neighbourhood 2 (top figure), the traffic density in the three neighbourhoods (middle figure), and the mean travel times in three neighbourhoods (bottom figure) for scenario 1 (resp. scenario 2). For the second scenario, we add an inset with the effective arrival of flows 1 and 2 since a part of the flow 2 curve is hidden behind that of flow 3. In scenario 1, most of the congestion is due to the uncontrolled flow 1. Since flow 2 traverses two neighbourhoods where flow 1 is present, it starts shifting towards the PTS much earlier than flow 3 which sees flow 1 in only one neighbourhood. In scenario 2, it are flows 2 and 3 that create most of the congestion. Here, the PTS cost of 3 is slightly lower than in scenario 1, so it is not surprising that it moves to PTS earlier. However, surprisingly, once flow 2 shifts to PTS, a fraction of flow 3 goes back to using personal vehicles again since the congestion is now reduced due to the absence of flow 2 vehicles.

The PoA for these particular scenarios was found to be 1.036 and 1.070 for the left and right pane, respectively, that is the average social cost at the Wardrop equilibrium was 3.6% and 7% higher than at the social optimum for the respective scenarios. Here the PoA was calculated over the time interval [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]100] which covers the congested period.

Finally, Figure 7 shows the congestion-based pricing of ( 14) for these two scenarios. The adjoint functions γ 2 2 (t) and γ 3 2 (t) were computed by BOCOP. For both scenarios, the pricing is in fact a subsidy since it involves reducing the cost of public transport at peak hours. Further, the subsidy is higher during periods of higher travel times (or higher congestion).

Conclusions

Drawing on queueing network theory and accounting for the macroscopic fundamental diagram of traffic flow, we have proposed a Markovian queueing network model for computing the time-dependent travel times during rush hour in a congested area. The model at hand was characterised by two non-typical properties: queue-dependent departure rates to reflect the macroscopic fundamental diagram and time-dependent arrival intensities which are typical in rush-hour scenarios. As the traffic intensity is high during rush hour, we study the fluid limit of the queueing network model at hand. Numerical experiments show that the travel time can be reduced significantly if a reasonable fraction of commuters switches to public transport. Relying on game theory, we show how our model can be used to assess the impact of public transport systems on congestion and compare the game-theoretical and socially optimal traffic mixes. Finally, a simple congestion-based cost mechanism is proposed that modifies the game and steers its equilibrium to the social optimum of the problem with the original costs. when the jump rates do not depend on time. We here adapt this theorem to allow for jump rates that depend on both time and density. The fluid result for the traffic densities is then an easy corollary.

Theorem 1. Consider a sequences of processes in R d ,

X K (t) = X K (0) + K -1 Y K t 0 β (X K (s), s) ds , (15)
defined in terms of unit rate Poisson processes Y that count state jumps ⊂ L ∈ R d , with |L| < ∞. Further, suppose that the rates β (x, t) are bounded by β , and that for F (x, t) = β (x, t) we have the Lipschitz condition,

|F (x, t) -F (y, t)| ≤ M |x -y| , x, y ∈ R d , 0 ≤ t ≤ T .
Suppose that X n satisfies, lim n→∞ X n (0) = x 0 , and x satisfies

x(t) = x 0 + t 0 F (x(s), s)ds . (16)
Then, for every 0

≤ t ≤ T , lim K→∞ sup 0≤t≤T |X K (t) -x(t)| = 0 a.s. (17)
Proof. First note that the Lipschitz condition ensures that the solution of ( 16) is unique by the Picard-Lindelöf theorem. With Y (t) = Y (t)t, subtracting ( 16) from ( 15) gives,

X K (t)-x(t) = X K (0)-x 0 + K -1 Y K t 0 β (X K (s), s) ds + t 0 (F (X K (s), s)-F (x(s), s))ds , such that for t ≤ T , |X K (t) -x(t)| ≤ |X K (0) -x 0 | + η K + t 0 M |X K (s) -x(s)|ds . (18)
with,

η K = | |K -1 sup t≤T Ŷ K t 0 β (X K (s), s)ds
By Gronwall's inequality, (18) implies for t ≤ T ,

|X K (t) -x(t)| ≤ (|X K (0) -x 0 | + η K ) exp(t) or, sup t≤T |X K (t) -x(t)| ≤ (|X K (0) -x 0 | + η K ) exp(T ) . (19)
Moreover, by the bounds on β , η K is bounded by

η K ≤ | |K -1 sup t≤T Ŷ K β t .
The functional strong law of large numbers for Poisson processes then yields sup t≤T Ŷ K β t → 0 for K → ∞, which shows that η K → 0 for K → ∞ as well. As |X K (0)x 0 | → 0 a.s. for K → ∞ by assumption, [START_REF] Daniele | Time-dependent traffic equilibria[END_REF] follows from [START_REF] Aussel | Existence of time-dependent traffic equilibria[END_REF]. Corollary 1. Assume that (i) that the arrival rates λ f (t) of the different flows are bounded; (ii) that the service rates µ n (q n ) are bounded in all neighbourhoods, and (iii) that the service rate per flow µ n (q n )q f n /q n is Lipschitz continuous. Then, with the notation of section 2.2, we have,

1 2 3 λ 1 1 (t) λ 2 1 (t) λ 3 1 (t) λ 6 3 (t) λ 5 3 (t) λ 4 3 (t)
lim K→∞ sup t≤T |K -1 Q K (t) -q(t)| = 0 , a.s.

B Derivation of (13)

The optimal control problem (10) can be rewritten compactly as min

p(t)∈[0,1] T2 T1 n,f λ f n (t)K f n (t; p)dt (20)
subject to ẋ(t) = g(x, p)

where x = [q f n , w f n ] n,f is the state of the system and p is the control variable. Recall that γ f n (t) is the co-state vector for q f n (t). The Pontryagin Maximum Principle states that if x * and γ * is an optimal trajectory then

p * = inf p H(x, p, γ), (22)
where

H = γ • g + n,f λ f n (t)K f n (t; p) (23)
is the Hamiltonian. Since both the running cost [START_REF] Vandaele | A queueing based traffic flow model[END_REF] as well as the dynamics (( 11) and ( 12)) are linear in p f n , so is the Hamiltonian. Substituting for the g and K, we obtain the coefficient of p f n in H as:

λ t n (t) • ( wf n (t) -C n (t) + γ f n (t)). (24)
That is at each time t, we are solving a linear optimization problem to determine p * (t). Since the problem is one of minimization, we set p f n to 1 if the ( 24) is less than 0, and p f n to 0 if (24) is positive. This reasoning gives us (13).

C Additional numerical example

To further illustrate our approach, we present a second numerical example. Consider a city divided into 3 neighbourhoods in tandem as depicted in Figure 8, with arrivals in neighbourhoods Figure 9: Arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour without public transport alternative. Fluid limit (left). Pre-limit (right).

1 and 3. There are separate flows for each neighbourhood, such that the total number of flows equals 6. We again assume that the departures in the different neighbourhoods are governed by the MFD of Yokohama, as used in the preceding example, which is properly rescaled to reflect realistic travel times (around 15 minutes in total for flow 1 when there is no congestion). The routes taken by all the flows in this example are deterministic. Vehicles of flow 1 enter in neighbourhood 1 at rate λ 1 1 (t) and reach their destination in this neighbourhood. Flow 2 enters neighbourhood 1 at rate λ 2 1 (t) and exits in neighbourhood 2 while flow 3 enters in 1 at rate λ 3 1 (t) and exits in 3. Flows 4, 5, and 6 have analogous rates and routes as shown Figure 8. In the game and the optimal control part, only flows 1, 2, and 3, that is those entering neighbourhood 1, participate in the optimisation. The other flows are not controlled but nevertheless influence the queues and the travel times in the neighbourhoods. In the numerical experiments, we assume that the arrival rates of the flows entering the same neighbourhood are the same. That is, λ 1 1 (t) = λ 2 1 (t) = λ 3 1 (t) = λ 1 (t), and λ 3 4 (t) = λ 3 5 = λ 6 3 (t) = λ 3 (t). Figure 9 shows the arrival rates (top row), the queue lengths in the three neighbourhoods (second row), as well as the mean travel times of the six flows (bottom two rows) in the fluid limit (left pane) when there is no public transport alternative. The notation wf (resp. q n ) indicates the mean travel for flow f (resp. total queue length in neighbourhood n). The accuracy of the fluid limit is shown in the right pane for K = 10000. As with the other example, the fluid limit is accurate during congestion periods but not when the traffic densities are low. Recall that the simulation only considers a single trajectory for the densities, and that the depicted travel times are the mean travel times, conditional on that single trajectory.

Next, we introduce a public transport alternative which costs C 1 = 20 for flow 1, C 2 = 35 for flow 2 and C 3 = 50 for flow 3. This reflects higher costs for longer travel distances, as well as a fixed cost for the inconvenience of switching to the PTS. The comparison of the Wardrop equilibrium and optimal control solution is shown in Figure 10. For reference, we also depict the curves without the public transport alternative (as shown in Figure 9) in gray. For better readability, we use the same notation in the legend for both the left and the right panes. Here, it is implicit that the variable in the left pane (resp. right pane) is the one obtained from the Wardrop equilibrium (resp. optimal control solution).

The inset of the arrival rate plot of the optimal control solution shows the rate of flow 3. The travel times for this flow starts to approach and go over its PTS cost of 50 units around t = 30. In anticipation of the congestion that will be created by increased arrival rates of the flows 4, 5, 6 when the flow 3 will reach neighbourhood 3, the optimal control solution switches this flow to its PTS at a relatively early point in time and keeps it there until the congestion in neighbourhood 3 starts to wane. The PoA for this example (for the interval [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]120]) is 1.036, which corresponds to an additional cost of 3.6%. The congestion based pricing curves have a similar shape as the ones of the first example and have been omitted.

Figure 1 :

 1 Figure 1: Flow-density (left) and Speed-density (right) macroscopic fundamental diagrams

flow 1 1 flow 3 destination in neighbourhood 2 Figure 2 :

 1122 Figure 2: City with four neighbourhoods. There are arrivals in the outer areas, and only transitions between neighbouring areas, and towards the centre of the city. Three flows are considered, with routing as indicated.

3 Figure 3 :

 33 Figure 3: Evolution of the arrival rate (AR) for the flows, the traffic density (TD) in the neighbourhoods and travel times (TT) of the flows during rush hour.

Figure 4 :

 4 Figure 4: Accuracy of the mean travel times in the fluid approximation for different K as indicated. The mean travel times are calculated for a single sample of the queue size processes.

Figure 5 :

 5 Figure 5: Arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour in Wardrop equilibrium (symmetric public transport costs).

Figure 6 :

 6 Figure 6: Socially optimal arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour.

Figure 7 :

 7 Figure 7: Congestion-based cost function that achieves a PoA of 1.

Figure 8 :

 8 Figure 8: City with three neighbourhoods. There are arrivals in areas 1 and 3, with destinations in all different areas.

21

 21

Figure 10 :

 10 Figure 10: Arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour with a public transport alternative. Wardrop equilibrium (left). Optimal control solution (right).

The optimal control problem (10) can be solved using numerical solvers such as BOCOP [START_REF]BOCOP: an open source toolbox for optimal control[END_REF]. Once the solution is obtained, the PoA can then computed numerically for any set of input parameters (arrival rates, MFD, PTS costs,. . . ). In Section 4.3, we present the solution of [START_REF] Vandaele | A queueing based traffic flow model[END_REF] and the corresponding PoA for the two scenarios considered in Section 3.2.

Congestion-based pricing

Now we address the second issue of designing the PTS game in such a way that the Wardrop equilibrium of this new game coincides with the social optimum of the original problem. In the previous subsection, the price (or cost) of public transport was taken to be the same as the one in the game of Section 3. The numerical example in Section 4.3 illustrates that the PoA in this setting is larger than 1. That is, selfish decision making induces inefficiencies from the point of view of the social cost.

One way to remove these inefficiencies is to impose the optimal decisions on individual commuters. However, this forced choice can be seen as too authoritarian. Another method is impose tolls or taxes on certain routes or resources. Here, the individuals still make selfish decisions, but in a game where the costs are modified by tolls. In static congestion games, that is games in which arrival rates are constant, it is known that by introducing appropriate tolls, one can obtain the social optimum in a game setting [START_REF] Cole | Pricing network edges for heterogeneous selfish users[END_REF]. In this subsection, we follow this method and compute a congestion-based pricing of public transport such that the equilibrium of the dynamic congestion game with modified costs will be same as the social optimum for the cost setting that was computed in the preceding subsection.

Let Ĉf n (t) be the congestion-based cost of the public transport network, and let pf n (t) be the equilibrium probability of flow f at neighbourhood n of the game [START_REF] Schadschneider | Stochastic Transport in Complex Systems[END_REF] with the cost C f n replaced by Ĉf n . For pf n to be equal to pf n (which is the solution of ( 9) with cost C f n ), it needs to satisfy certain conditions that are determined by Pontryagin's maximum principle [START_REF] Geering | Optimal Control with Engineering Applications[END_REF].

When the maximum principle is applied to [START_REF] Kerner | The Physics of Traffic -Empirical Freeway Pattern Features, Engineering Applications, and Theory[END_REF], it follows that (see B)

where γ f n (t) is the adjoint (or the co-state) variable for q f n (t) and the multiplier of [START_REF] Chen | A traffic breakdown model based on queueing theory[END_REF]. The mechanism design problem is to construct a PTS cost Ĉf n (t) for the game so that its equilibrium [START_REF] Schadschneider | Stochastic Transport in Complex Systems[END_REF] with PTS cost Ĉf n is the same as solution of the optimal control problem (13) with the original PTS cost C f n . Comparing ( 13) and ( 7), it can be seen that by setting the right-hand side of ( 13) to Ĉf n (t), the equilibrium of the modified game can be made the same as the desired optimal control. That is, by setting the PTS cost in the game to be

the social cost at the modified equilibrium will coincide with the social cost of the original optimal control problem. The modified cost for flow f entering neighbourhood n, Ĉf n , is the sum of the original cost C f n and a congestion-based cost γ f n (t). We can interpret γ f n (t) as the toll (or subsidy if it is positive) that the transport authority should impose to induce a PoA of 1.

A Fluid limit

For completeness, we here formally state and prove the fluid limit result. To this end, note that the process Q(t) can be expressed in terms of randomly time-changed Poisson processes

Here the processes A f n and D f nm are unit rate Poisson processes, counting the number of arrivals of flow f in neighbourhood n, and the number of departures of flow f from neighbourhood n to m, respectively.

The stochastic process above is a time-inhomogenous density-dependent population process. A fluid limit result for this type of processes is provided in Theorem 2.1 of [START_REF] Ethier | Markov processes, characterization and convergence[END_REF]Chapter 11],