Hassan Sabbah

Mickaël Carlos

Christine Joblin

Characterization of Large Carbonaceous Molecules in Cosmic Dust Analogues and Meteorites

Keywords: Astrochemistry, dust, solar system: formation, methods: laboratory, methods: analytical

We present a new experimental setup called AROMA (The Aromatic Research of Organics with Molecular Analyzer) based on the use of laser mass spectrometry techniques. We demonstrate the potential of AROMA for the analysis of meteoritic samples and cosmic dust analogues. Tens of peaks are identified in the mass spectra with notable discrepancies across the different samples. These discrepancies provide clues on the chemical history of each sample and are not a bias of our analysis. A double bound-equivalent (DBE) method is applied to sort the detected carbonaceous molecules into families of compounds. It reveals in addition of polycyclic aromatic hydrocarbons, the presence of other populations such as mixed aromatic-aliphatic species and carbon clusters.

Introduction

Most of our knowledge on the chemical composition and evolution of carbonaceous cosmic matter is based on astronomical observations. Still, Solar System objects such as meteorites, interplanetary dust particles (IDPs) and samples from return missions can provide direct information on this matter. Meteorites are the most available type of extraterrestrial material on Earth and are representative of the early Solar System. Analysis of Murchison, the most studied carbonaceous chondrite, shows the extensive variety of organics (up of tens of thousands of different molecular species) in meteorites amongst which heterocycle compounds and aromatic hydrocarbons (Schmitt-Kopplin et al. 2010). Other studies have shown the capability of laser mass spectrometric techniques to specifically target the aromatic species in extraterrestrial materials, including meteorites and IDPs as well as cometary coma dust [START_REF] Spencer | Proc. Natl. Acad. Sci[END_REF].

The AROMA setup

AROMA (Sabbah et al. 2017), is an experimental set-up developed in the framework of the Nanocosmos ERC synergy project. Its main purpose is to analyze the carbonaceous molecular content of cosmic dust analogues and meteoritic samples. The experimental setup consists of a laser desorption ionization (LDI) source and an ion trap connected to an orthogonal time of flight mass spectrometer. The ion source offers the possibility to study large carbonaceous molecules such as polycyclic aromatic hydrocarbons (PAHs) that are embedded in a variety of solid samples by performing LDI in a single or/and double steps. The trap allows studying the structure of desired species by collision induced dissociation (CID) and UV photodissociation studies. Finally the ion signal is monitored using an orthogonal time-of-flight mass analyzer equipped with a two-stage reflectron and a fast microchannel plate (MCP) detector, thus providing high mass resolution (m/∆m=10 4 ).

We have previously reported (Sabbah et al. 2017) the capabilities of the apparatus and its high sensitivity to aromatic species (100 of femtograms). We also detected the PAH distribution in the Murchison meteorite, which is made of a complex mixture of extraterrestrial organic compounds. A key molecule in the PAH family is m/z=202.08. In order to identify the dominant isomeric structure at this position, we investigated the fragmentation pattern of this molecule employing the CID technique. We firmly identified the main peak at m/z=202 as due to pyrene. Combining CID experiments and double bound-equivalent (DBE) plot representation, we identified a series of methylated pyrene species.

From mass spectrum to DBE

In order to explore the diversity of carbonaceous molecules in meteorites, a fragment of a few milligrams of the Almahata Sitta meteorite (Jenniskens et al. 2009) was powdered and introduced in AROMA. Figure 1 shows the mass spectrum recorded for this sample in the same mass range as for the Murchison analysis. Peaks are annotated with their corresponding chemical formula. We found a distribution of carbonaceous species ranging from m/z=100 to 360. The mass spectrum reveals the co-existence of aromatic species with carbon clusters. In order to investigate the chemical diversity in both meteorites we applied the DBE method.

An elemental formula was associated to each detected mass peak with a signal-to-noise ratio (S/N) greater than 10. This is achieved employing the mMass software (Strohalm et al. 2008), an open source mass spectrometry tool. The DBE is then calculated using the following equation :

Double bond equivalent (C c H h N n O o S s ) = c -h/2 + n/2 + 1
Aromatic species in meteorites 3

The DBE is representative of the unsaturation level of the molecules and thus corresponds to a direct measure of their aromaticity. Its value is equal to the number of rings plus double bonds involving carbon atoms (because each ring or double bond results in a loss of two hydrogen atoms). In Figure 2 we represent the DBE versus carbon number for both meteorites, Murchison (top) and Almahata Sitta (down). Three linear curves are inserted in the graphs corresponding to carbon clusters (DBE(C clusters)= C+1), polyynes (DBE(polynnes)= C) and PAHs (DBE(PAHs)= 0.84×C -1.45). Species aligned horizontally and separated by one carbon number are indicative of substitutions by methyl group (-H +CH 3 ). The DBE plots are clearly very different. Murchison contains a large variety of aromatic species and mixed aromatic-aliphatic species whereas Almahata Sitta contains a specific PAH family aligned on the dashed line (Figure 2 bottom) and going up to C 27 H 14 . This observation is similar to previous work on this meteorite (Sabbah et al. 2010). Almahata Sitta contains also a series of carbon clusters spanning size from C=9 to 30 and even larger species (not shown here).

Conclusion and prospectives:

In this work, we investigated the aromatic content of two different meteorites, Murchison and Almahata Sitta, with the AROMA setup. We have been able to detect aromatic species in both samples in agreement with previous work (Callahan et al. 2008, Sabbah et al. 2010). Moreover, we report for the first time the co-existence of carbon clusters along with PAHs in the Almahata Sitta meteorite. Applying the DBE method we have been able to clearly identify chemical families. This observation has motivated us to undertake a systematic analysis of multiple Almahata Sitta samples to confirm the presence of carbon clusters and explore the chemical diversity across the different samples (Sabbah et al. in prep.). Enlarging the scope of this study to a larger collection of meteorites will also allow us building a database in order to compare populations of carbonaceous materials within different types of meteorites and cosmic dust analogues.

Figure 1 .

 1 Figure1. Mass spectrum of Almahata Sitta meteorite recorded using AROMA. A distribution of aromatic species and carbon clusters has been detected. Some peaks assignments are presented.

Figure 2 .

 2 Figure 2. DBE vs. carbon number plots for the Murchison meteorite (top) and Almahata Sitta (bottom) meteorites. PAHs are present in both meteorites whereas carbon clusters are only observed in Almahata Sitta. Species having the same DBE and differing by one carbon number include substitutions by methyl group (-H +CH3).

Acknowledgments

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Program (FP/2007-2013) ERC-2013-SyG, Grant agreement n. 610256 NANOCOSMOS. We acknowledge support from La Region Occitanie, Grant N • 15066466.


Dieter Fiems

Balakrishna Prabhu

Macroscopic modelling and analysis of rush-hour congestion

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 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.

Introduction

Most major cities 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 authorities in various cities 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, or, as is done in France, a restriction on the entry of old or more polluting vehicles during episodes of peak pollution.

Another mechanism for reducing congestion at bottlenecks is to take alternative paths. This has now become possible in real-time thanks to several online applications that can orient drivers towards paths of least travel times.

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 eco-friendly alternative to personal vehicle usage.

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 user 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 users are rational and choose the alternative with the least cost, we can estimate how many users 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

The main contribution of this paper is a queueing-theory-based method for the computation of travel times in road traffic networks. While the link between queueing theory and road traffic networks has been made 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]. In this paper, we generalise the travel-time analysis of [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF] to a network of neighbourhoods. In queueing theory parlance, this paper generalises the single server analysis in [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[END_REF] to a network of queues. This is similar to how Jackson networks [START_REF] Jackson | Jobshop-like queueing systems[END_REF] or BCMP networks [START_REF] Forest Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF] extended the single server models.

As in [START_REF] Fiems | Travel times, rational queueing and the macroscopic fundamental diagram of traffic flow[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 time-varying 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.

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 see the vehicle as a customer in a queueing network, and 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 MFD has an inverted cup shape (like a concave function) as shown in 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.

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 first when the number of vehicles in the network is small. We then obtain the corresponding equations in the fluid limit when the number of cars 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. Finally, we close with some conclusions in Section 5

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 represent the number of cars in a neighbourhood of the city. 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 cars as described by the macroscopic fundamental diagram.

Markov model

Consider a city and a set of neighbourhoods N = {1, 2, . . . , N }, for which the arrival rate statistics and the macroscopic fundamental diagram are known. A neighbourhood could, in theory, be the entire city itself. We shall assume that new vehicles arrive at the nth neighbourhood in accordance to a Poisson process with time dependent rate λ n (t), n ∈ N .

The duration of a journey depends on the length of the journey as well as on the speed during the journey. We assume that the lengths are independently and identically exponentially distributed with rate 1, taking some other value being equivalent to rescaling time. The speed of vehicles inside the different neighbourhoods at a given time instant will depend upon the average density within the neighbourhood in accordance with the macroscopic fundamental diagram (MFD). Moreover, the number of vehicles that either leave the neighbourhood or reach their destination will also depend on the density, or equivalently, on the number of vehicles in the area. Let α mn denote the probability that a vehicle in neighbourhood m leaves for another neighbourhood n, and let α m0 denote the probability that a vehicle in neighbourhood m reaches its destination in neighbourhood m. To simplify notation, we will further assume that a mm = 0 for all m ∈ N .

Let Q n (t) denote the number of vehicles (moving around) in neighbourhood n at time t, let

Q(t) = [Q n (t)] n∈N , and let π(i; t) = Pr[Q 1 (t) = i 1 , . . . , Q N (t) = i N ] = Pr[Q(t) = i]
denote the probability that there are i 1 vehicles in neighbourhood 1 at time t, i 2 vehicles in neighbourhood 2 at time t, . . . , and i N vehicles in neighbourhood N at time t, with i = [i 1 , . . . , i N ] ∈ N N . The density in a neighbourhood being proportional to the queue size in that neighbourhood, and the number of departures from the neighbourhood being proportional to the density, the departure rate in neighbourhood m equals,

µ m (Q m (t)) = θ m F m (Θ m Q m (t)) ,
where θ m and Θ m are given constants and F m denotes the macroscopic fundamental diagram of neighbourhood m.

In view of the assumptions above, we have the following transitions from state i ∈ N N :

• There is a new arrival in neighbourhood n ∈ N with rate λ n (t). Such an arrival induces a transition to state i + e n . Here, , e m = [1 {m=n} ] n∈N is a vector of zeroes, apart from its mth element which is one.

• A vehicle moves from neighbourhood m to neighbourhood n with rate µ m (i m )α mn , the new state being i + e n -e m .

• A vehicle reaches its destination in neighbourhood m with rate µ m (i m )α m0 , the new state being ie m .

The description of the state transitions then immediately yields the following set of forward Chapmann-Kolmogorov equations,

∂ ∂t π(i; t) = m∈N n∈N * π(i -e n + e m ; t)µ m (i m + 1)α mn + m∈N π(i -e m ; t)λ m (t) - m∈N π(i; t)µ m (i m ) - m∈N λ m (t)π(i; t) ,
with N * = N ∪ {0}, and with π(i; t) = 0 for i / ∈ N N . Note that the notation implies that e 0 = 0.

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

ν n (τ, t + h|i) = m∈N ν n (τ + h, t|i + e m )λ m (t)h + m∈N \{n} k∈N * ν n (τ + h, t|i -e m + e k )µ m (i m )α mk h + m∈N * ν n (τ + h, t|i -e n + e m )µ n (i n )α nm 1 - 1 i n h + m∈N ν m (τ + h, t|i -e n + e m )µ n (i n )α nm 1 i n h + ν n (τ + h, t|i) 1 - m∈N λ m (t)h - m∈N µ m (i m )h + o(h) ,
Here we 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). Hence, in queueing terms, we assume that the "server" uses a processor sharing or random order of service discipline. Sending h → 0, we further have,

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

Wn (τ ) = i∈N N π(i; t) ∞ 0 ν n (τ, t|i + e n )dt .
Here we used the observation that the mean travel time of a vehicle arriving at time τ in neighbourhood n while there are i vehicles in the different neighbourhoods equals the mean remaining travel time of a vehicle in nieghbourhood n when there are i + e 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 w(τ, t|i). Moreover, numerically solving these equations is computationally demanding. We however 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 λ n (t)K in the nth neighbourhood and study q n (t) = lim K→∞ Q K n (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 n 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 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.

Let μn (x) denote the departure rate from the nth neighbourhood in the fluid regime, that is,

μn (x) = lim K→∞ µ n ( Kx ) K .
Then, by writing the evolution of Q 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 n (t) adheres the following ordinary differential equation,

qn (t) = λ n (t) -μn (q n (t)) + m∈N μm (q m (t))α mn . (1)
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 K n (τ ) denote the travel time from neighbourhood n at time τ for the Kth model, and w n (τ, t) be the complimentary waiting time distribution in the fluid limit,

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

∂ ∂t w n (τ, t) - ∂ ∂τ w n (τ, t) = -w n (τ, t) μn (q n (τ )) q n (τ ) + m∈N w m (τ, t)α nm μn (q n (τ )) q n (τ ) .
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,

wn (τ ) = ∞ 0 w n (τ, t)dt .
Combining the former expressions also yields the following differential equation for the mean waiting times,

d dτ wn (τ ) = wn (τ ) μn (q n (τ )) q n (τ ) -1 - m∈N wm (τ )α nm μn (q n (τ )) q n (τ ) . (2)
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 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 λ 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 n (T ) ≈ lim τ →∞ w n (τ ). For ease of notation, introduce ωn (τ ) = wn (T -τ ). We then obtain the following system of ordinary differential equations for ωn ,

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

ωn (0) μn (q n (T )) q n (T ) = 1 + m∈N ωm (0)α nm μn (q n (T )) q n (T ) . (3)

Remark 1

The assumptions on the functions λ n do not constrain the problems that can be solved by the method at hand. Indeed, if λ 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.

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.

Let λ i (t) denote the arrival rate (AR) in area i ∈ {2, 3, 4}. 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 when there is no congestion). Vehicles leave for the centre neighbourhood 1 with probability ψ, to any of its neighbours with probability φ or park in the neighbourhood with probability 1 -ψ -2φ.

Figure 3 shows the evolution of the traffic density and the expected waiting times in the fluid limit regime for φ = 0.1 and ψ = 0.4 and for λ 3 (t) = λ 2 (t) and λ 4 (t) = λ 2 (t), with λ 2 (t) as depicted. 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λ i , where K is sufficiently large.

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 not unexpected as all traffic towards the centre needs to cross the outside neighbourhoods, such that peak traffic is delayed. This is also reflected in the travel times in the centre area. Congestion in the centre starts when the congestion in the outside neighbourhoods is already resolving. Finally, it is readily seen that the maximum traffic density exceeds 30% in some cases. 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 timedependent waiting times, and compares these curves with the expected waiting times, conditional on the system content. That is, for these simulation results, we draw a single sample path of the traffic densities over time, and then use Monte Carlo simulation to estimate the mean waiting time at various points in time for this sample path. 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 to small to be properly depicted. We considered 3 distinct scale values K. Practically, the values K = 500, K = 1000 and K = 5000 correspond to having a peak arrival intensity at the city of 35, 70 and 350 vehicles per minute, respectively.

For K = 500, the simulation results considerably deviate from the fluid limit. This reflects the remaining randomness in the traffic density process for smaller K. For K = 1000, the correspondence between simulation results and the fluid limit are already good, while the correspondence is very good for K = 5000. Even for K = 5000, the traffic intensity is not that 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 users 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 certain number of users may switch from personal vehicles to the PTS. Assuming users are rational, that is, they choose the mode of transport that minimises their travel times, we use concepts from game theory to compute the number (or the fraction) of users 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 may depend upon 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 , let C 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.

Dynamic Wardrop equilibrium

We investigate the strategies of rational users when the choice of each user has a negligible impact on the travel times of the population, a solution concept introduced in game theory by Wardrop [18] 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 dynamic Wardrop equilibrium, the choice at time t not only depends on the choices of the other users at time t, but also on the choices of other users (both prior and later than time t).

Let p • n (t) denote the fraction of users that opt for private transport at time t. The function p • n is the time-dependent routing strategy for arrivals in neighbourhood n. The set of routing strategies constitutes a Wardrop equilibrium if, for each n ∈ N such that λ n (t) > 0, we have the following constraints on the travel times:

     wn (t; p • n ) < C n (t) for p • n (t) = 1 , wn (t; p • n ) = C n (t) for 0 < p • n (t) < 1 , wn (t; p • n ) > C n (t) for p • n (t) = 0 . (4)
The first equation states that all users in neighbourhood n prefer private transport if the cost of the PTS exceeds the expected travel time. The second equation states that if a nonzero fraction of users opt for PTS and a non-zero fraction of users 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 p • n (n ∈ N ) have no nice and easy analytical solution. Therefore, we resort to the following iterative numerical algorithm for their computation. Given the arrival curves λ n (t), the fundamental diagrams μn (x) and the routing probabilities α mn , we set p n (t) = 1, and then update it according to p n (t) ← min 1, p n (t)e -βn(ω(t;p)-Cn(t)) , for λ n (t) = 0, such that p n → p • 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 λ n (t) = 0, the value p • 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 some traffic scenarios. We retain the assumptions on the arrival traffic and the random routing within the city of section 2.3 and consider two different public transport offerings. In the first scenario, there is a PTS offering in all neighbourhoods with a fixed cost of 25 minutes. The traffic densities and travel times for this symmetric scenario are depicted in Figure 5. Note that we only depict results for neighbourhoods 1 and 2, as the results for neighbourhoods 2, 3 and 4 are identical by symmetry. In the second scenario, there is a PTS offering in neighbourhoods 2 and 3, but none in neighbourhood 4. Moreover, the PTS cost differs: C 2 (t) = 20 minutes and C 3 (t) = 25 minutes. The results for this asymmetric scenario are depicted in Figure 6.

In both scenario's we can easily verify that the travel times never exceed the PTS cost. Moreover, once the travel times hit the PTS cost, a considerable fraction of users opt for the PTS. This reduction of traffic is not only beneficial for the travel times from the outer neighbourhoods. Also the travel time within the centre decreases as there is also a reduction of traffic there. To facilitate comparisons, the traffic densities and travel times without the availability of the PTS are also depicted in Figure 5 (by dotted curves). Finally, in Figure 6, we also observe a reduction in travel times for neighbourhood 4 where there is no PTS offering. This is not unexpected, as users from other neighbourhoods that opt for the PTS reduce the overall traffic in neighbourhood 4 as well.

Social optimum

When users choose selfishly between two options, it often leads to inefficiencies in terms of the overall cost function. In this section, we quantify these inefficiencies using the concept of Price of Anarchy (PoA) [START_REF] Koutsoupias | Worst-case equilibria[END_REF]. The PoA is defined as the ratio of the cost at the Wardrop equilibrium and the cost at the social optimum. A higher value of PoA implies that the cost of allowing for individual decision making is higher, which can be interpreted as the price that is paid for decentralised decision making.

Optimal control problem

Let p n (t) be the probability with which a user entering in neighbourhood n uses her vehicle. Then, the mean transportation cost K n (t) at time t of a user entering neighbourhood n assuming policy p equals K n (t; p) := i wn (t; p)p n (t) + (1 -p n (t))C(t) .

(5) Here, we have assumed that the cost of public transport does not depend upon the point of entry and exit of the user. The socially optimal policy is the one that minimises the total weighted mean cost given by

p * = arg inf p T2 T1 n λ n (t)K n (t; p)dt (6)
where [T 1 , T 2 ] is the rush hour interval. Note that the expression above includes the arrival rates λ n (t) as the travel cost impacts more users if there are many arrivals. With p • (t) as the solution of the set of equations ( 4). The PoA is then defined as:

PoA = T2 T1 n λ(t) i K n (t; p • )dt T2 T1 n λ 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], ( 6) is not an optimal control problem for a general λ n (t) general because w(0) cannot be determined independently of q (see the discussion below ( 2)). In order to solve this problem, we shall make the same assumption as was made for obtaining [START_REF] Buisson | Exploring the impact of homogeneity of traffic measurements on the existence of macroscopic fundamental diagrams[END_REF]. That is, we shall assume that λ n (t) goes to a constant as t → ∞. Taking the T 2 to be sufficiently large so that the system is in stationarity, we can then approximate (6) by the solution of following optimal control problem:

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

d dt q n (t) = λ n (t) -μn (q n (t)) + m∈N μm (q m (t))α mn , (8)
d dt wn (t) = wn (t) μn (q n (t)) q n (t) -1 - m∈N wm (t)α nm μn (q n (t)) q n (t) , (9)
with the initial values of q n (0) computed using the steady state solution of (1) and w(T ) obtained as the solution of (3).

Congestion-based pricing

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 these decisions on individuals. 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 with different costs. 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 fixed cost setting that was computed in the subsection above.

Let Ĉ(t) be the congestion-based cost of the public transport network, and let p• n (t) be the equilibrium probability in neighbourhood n of the game (4) with the cost replaced by Ĉ. For p• n to be equal to p * n (which is the solution of ( 6)), it needs to satisfy certain conditions that are determined by the Pontryagin's maximum principle [START_REF] Geering | Optimal Control with Engineering Applications[END_REF].

When the maximum principle is applied to [START_REF] Daganzo | Urban gridlock: Macroscopic modeling and mitigation approaches[END_REF], it follows that (we skip the details)

     wn (t; p * n ) < C n -γ n (t) for p * n (t) = 1 , wn (t; p * n ) = C n -γ n (t) for 0 < p * n (t) < 1 , wn (t; p * n ) > C n -γ n (t) for p * n (t) = 0 , (10)
where γ n (t) is the adjoint (or the co-state) variable for q n (t) and is the multiplier of (8). Comparing ( 10) and ( 4) in which C n (t) = Ĉn (t), we obtain

Ĉn (t) = C n -γ n (t) , ∀n. (11)
That is, congestion-based pricing for the game to have a PoA of 1 is the sum of the fixed original cost C n and a congestion-based cost γ n (t) in neighbourhood n. We can interpret γ n (t) as the toll (or subsidy if is negative) that the transport authority should impose to induce a PoA of 1.

Numerical example

We now calculate the social optimum policy, PoA, and the congestion-based pricing for the symmetric traffic scenario of Section 3.2. The assumptions on the arrival traffic and the routing within the city are the ones described in Section 2.3 and there is a PTS offering in all neighbourhoods with a fixed cost of 25 minutes. The optimal control problem (7) was solved using the software BOCOP which is a specialised numerical solver for such problems [START_REF]BOCOP: an open source toolbox for optimal control[END_REF].

In Figure 7, we depict the optimal arrival rate in neighbourhood 2 (top figure), the traffic density in neighbourhoods 1 and 2 (middle figure), and the mean travel times in neighbourhoods 1 and 2 (bottom figure). Also, due to symmetry of the arrival rates, traffic densities and travel times in neighbourhoods 3 and 4 are identical to those in neighbourhood 2, and are therefore omitted.

The PoA for this particular example was found to be 1.081, that is the average social cost at the Wardrop equilibrium was 8% higher than at the social optimum.

Finally in Figure 8 we show the congestion-based pricing of [START_REF] Kerner | The Physics of Traffic -Empirical Freeway Pattern Features, Engineering Applications, and Theory[END_REF] for this example that leads to the social optimum. The adjoint function γ n (t) was computed by BOCOP. Observe that, for this example, 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 users 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.

Figure 1 :

 1 Figure 1: Macroscopic fundamental diagram

Figure 2 :

 2 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.

Figure 3 :Figure 4 :

 34 Figure 3: Evolution of the arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour.

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: Arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour in Wardrop equilibrium (symmetric public transport costs).

Figure 7 :

 7 Figure 7: Socially optimal arrival rate (AR), traffic density (TD) and travel times (TT) during rush hour (symmetric public transport costs).

Figure 8 :

 8 Figure 8: Congestion-based cost function that acheives a PoA of 1 (symmetric public transport costs).