Analysis and control of an (almost) intersection-free model for traffic flow on networks

Analysis and control of an (almost) intersection-free model for traffic flow on networks

E. Cristiani

(with G. Bretti, M. Briani, F. S. Priuli, S. Sahu)

Istituto per le Applicazioni del Calcolo Consiglio Nazionale delle Ricerche

ANCONET 2016 March 9-11, 2016

1 The LWR model on networks: classical approach

2 The LWR model on networks: path-based approach

3 Path-based model as many-particle limit of FTL on networks

4 Using path-based model for traffic optimal control

Traffic flow on network, classical approach with LWR

LWR model on arcs = roads

∂

∂tρ + ∂

∂xf (ρ) = 0, f (ρ) = ρv (ρ), v (ρ) = vmax− vmax

ρmax

ρ

What about nodes = junctions?

Junctions: the case 2 incoming → 2 outgoing

γ_maxⁱ (ρ(b_i, t)) =

 f (ρ(bi, t)), if ρ(bi, t) ∈ [0, σ],

f (σ), if ρ(b_i, t) ∈ (σ, ρ_max], i = 1, 2 γ_max^j (ρ(aj, t)) =

 f (σ), if ρ(a_j, t) ∈ [0, σ],

f (ρ(aj, t)), if ρ(aj, t) ∈ (σ, ρmax], j = 3, 4.

Junctions: the case 2 ingoing → 2 outgoing

A =

 α3,1 α3,2

α4,1 α4,2



αji=% cars going from road i to road j

Traffic flow on network, path-based approach with LWR

p = 1

Traffic flow on network, path-based approach with LWR

p = 2

Traffic flow on network, path-based approach with LWR

p = 3

Traffic flow on network, path-based approach with LWR

p = 4

Path-based model: the equations

The natural equations

µ^p = density of cars following the p-th path (p-th population)

∂

∂tµ^p(x , t) + ∂

∂x µ^p(x , t) v ( )
= 0, x ∈ P^p, t > 0, where ω(x , t) :=PNP

q=1µ^q(x , t) = total density at any point or, equivalently,

∂

∂tµ^p(x , t) + ∂

∂x

 µ^p(x , t)

ω(x , t) f ω(x , t)



= 0, x ∈ P^p, t > 0,

Path-based model: the equations

The natural equations

µ^p = density of cars following the p-th path (p-th population)

∂

∂tµ^p(x , t) + ∂

∂x µ^p(x , t) v ω(x , t)

= 0, x ∈ P^p, t > 0, where ω(x , t) :=PNP

q=1µ^q(x , t) = total density at any point or, equivalently,

∂

∂tµ^p(x , t) + ∂

∂x

 µ^p(x , t)

ω(x , t) f ω(x , t)



= 0, x ∈ P^p, t > 0,

Path-based model: the equations

The natural equations

µ^p = density of cars following the p-th path (p-th population)

∂

∂tµ^p(x , t) + ∂

∂x µ^p(x , t) v ω(x , t)

= 0, x ∈ P^p, t > 0, where ω(x , t) :=PNP

q=1µ^q(x , t) = total density at any point or, equivalently,

∂

∂tµ^p(x , t) + ∂

∂x

 µ^p(x , t)

ω(x , t) f ω(x , t)



= 0, x ∈ P^p, t > 0,

Junctions disappear but... we face a system of CLs with discontinuous flux We do not investigate the well-posedness of the system

The path-based model: the numerical scheme

The natural discretization

µ^n,p_k = density of p-th population at time n at cell k ωⁿ_k :=PNP

q=1µ^n,q_k = total density at any cell µ^n+1,p_k = µ^n,p_k − ∆t

∆x µ^n,p_k

ωⁿ_k G (ω_kⁿ, ωⁿ_k+1) −µ^n,p_k−1

ω_k−1ⁿ G (ω_k−1ⁿ , ωⁿ_k)

!

with G the classical numerical Godunov flux.

THAT’S ALL

The path-based model: the numerical scheme

The natural discretization

µ^n,p_k = density of p-th population at time n at cell k ωⁿ_k :=PN_P

q=1µ^n,q_k = total density at any cell µ^n+1,p_k = µ^n,p_k − ∆t

∆x µ^n,p_k

ωⁿ_k G (ω_kⁿ, ωⁿ_k+1) −µ^n,p_k−1

ω_k−1ⁿ G (ω_k−1ⁿ , ωⁿ_k)

!

with G the classical numerical Godunov flux.

Which solution is actually

computed?

Classical vs. multipath approach

Claim

The solution computed by the path-based LWR model coincides with the solution of the classical algorithm when

1 flux is maximized;

2 incoming roads are assigned equal priority.

Classical vs. multipath approach

Claim

The solution computed by the path-based LWR model coincides with the solution of the classical algorithm when

1 flux is maximized;

2 incoming roads are assigned equal priority.

We have

the proof in the case of a MERGE;

numerical evidence for the other cases.

The path-based model: other theoretical properties

Theorem (conservation of total mass)

The numerical solution of the path-based model preserves the total mass X

k

ω_kⁿ⁺¹=X

k

ωⁿ_k

Theorem (admissibility of the solution) Under the following CFL-like condition

N_inc^max∆t

∆x sup

ρ∈(0,ρmax)

|f⁰(ρ)| ≤ 1,

we have

ω ≤ ρ_max ∀t > 0

The path-based model: other theoretical properties

Theorem (conservation of total mass)

The numerical solution of the path-based model preserves the total mass X

k

ω_kⁿ⁺¹=X

k

ωⁿ_k

Theorem (admissibility of the solution) Under the following CFL-like condition

N_inc^max∆t

∆x sup

ρ∈(0,ρmax)

|f⁰(ρ)| ≤ 1,

we have

ω ≤ ρ_max ∀t > 0 (provided the initial conditionsP

pµ^p(x , 0) ≤ ρ_max).

Classical vs. multipath approach: merge

Classical vs. multipath approach: the case 2 → 2

The path-based model: main drawback

Main drawback

The number of paths increase exponentially with the size of the network

⇒ The numerical solution can be unfeasible.

Partial solution: a local version of the model We apply the classical model inside the roads;

We split vehicles in populations just before the junction;

We merge populations just after the junction.

BUT... THE GLOBAL BEHAVIOR OF DRIVERS IS LOST

Classical vs. multipath approach















∂

∂tu +_∂x^∂f (u) = 0, x < 0, t > 0,

∂

∂tv +_∂x^∂ f (v ) = 0, x < 0, t > 0,

∂

∂tz + _∂x^∂ h(z, x , t; u, v , w )= 0, 0 < x < ∆x , t > 0,

∂

∂tw + _∂x^∂f (w ) = 0, x > ∆x , t > 0,

flux at x = 0:

min{Gf(u(0−, t), σ), Gf(σ, z(0+, t))} + min{Gf(v (0−, t), σ), Gf(σ, z(0+, t))}, flux at x = ∆x :

min{Gh(z(∆x −, t), σ), Gf(σ, w (∆x +, t))}

Application on real network in Rome

328 km, ∆x = 100 m, ∆t = 2.5 s, T_f = 45 m, CPU=0.5 s

Connection with follow-the-leader model (single road)

n cars one after the other, `<sub>n</sub>=car’s length (`_n→ 0 for n → +∞) First-order FTL model on a single road

 ˙y_i(t) = w (δ_i(t)), i = 1, . . . , n − 1

˙yn(t) = vmax,

where δ_i(t) := y_{i +1}(t) − y_i(t) and w is such that

w : [`<sub>n</sub>, +∞) → [0, v<sub>max</sub>], w (δ) := v `n

δ



, (C)

with v ∈ C¹([0, 1]; [0, v_max]) any function such that v⁰(r ) < 0, v (0) = v_max, v (1) = 0.

LWR model on a single road

∂_tρ + ∂_x(ρv (ρ)) = 0, t > 0, x ∈ R.

Connection with follow-the-leader model (single road)

n cars one after the other, `<sub>n</sub>=car’s length (`_n→ 0 for n → +∞) First-order FTL model on a single road

 ˙y_i(t) = w (δ_i(t)), i = 1, . . . , n − 1

˙yn(t) = vmax,

where δ_i(t) := y_{i +1}(t) − y_i(t) and w is such that

w : [`<sub>n</sub>, +∞) → [0, v<sub>max</sub>], w (δ) := v `n

δ



, (C)

with v ∈ C¹([0, 1]; [0, v_max]) any function such that v⁰(r ) < 0, v (0) = v_max, v (1) = 0.

LWR model on a single road

Connection with follow-the-leader model (single road)

Commuting operator: macro → micro En[r (·)] := y =







y_n= max(supp(r )), y_i = max



z ∈ R : Z y_{i +1}

z

r (x )dx = `n



, i = n − 1, . . . , 2, 1

Commuting operator: micro → macro Cn[y] := rn=

n−1

X

i =1

`_n δi

χ_{[yi,yi +1)},

Theorem

ρ0

−−−→ ρPDE ←−−−− ρ^n→+∞ _n←− y^Cn ←−−− y^ODE ₀←− ρ^En ₀

R. M. Colombo and E. Rossi, Rend. Sem. Mat. Univ. Padova, 131 (2014), 217–235.

M. Di Francesco and M. D. Rosini, Arch. Rational Mech. Anal., 217 (2015), 831–871.

The follow-the-leader model on networks

The follow-the-leader model can be easily extended on networks. No special management of junctions is needed.

The distance δi is defined considering the next car along the path followed by car i .

The follow-the-leader model on networks

The follow-the-leader model can be easily extended on networks. No special management of junctions is needed.

The distance δ_i is defined considering the next car along the path followed by car i .

The follow-the-leader model on networks

The follow-the-leader model can be easily extended on networks. No special management of junctions is needed.

The distance δ_i is defined considering the next car along the path followed by car i .

Which is the limit solution?

Connection between FTL and path-based model on ntwk

FTL model on network (path-based view)

 ˙y_{i ,p}(t) = w (∆^p_{i ,p}(t)), if (i , p) is not leader

˙yi ,p(t) = vmax, if (i , p) is leader Path-based LWR model on network

∂_tµ^p+ ∂_x(µ^pv (ω)) = 0, t > 0, x ∈ R.

For every fixed p (assuming the other populations are given), we have Theorem

µ^p₀ −−−→ µ^{PDE p} ←−−−− µ^{n→+∞ p}_n←− y^{Cn p}←−−− y^{ODE p}₀ ←− µ^{En p}₀

E. Cristiani and S. Sahu, On the micro-to-macro limit for first-order traffic flow models on networks, Netw. Heterog. Media, 11 (2016), to appear.

Connection between FTL and path-based model on ntwk

FTL model on network (path-based view)

 ˙y_{i ,p}(t) = w (∆^p_{i ,p}(t)), if (i , p) is not leader

˙yi ,p(t) = vmax, if (i , p) is leader Path-based LWR model on network

∂_tµ^p+ ∂_x(µ^pv (ω)) = 0, t > 0, x ∈ R.

For every fixed p (assuming the other populations are given), we have Theorem

µ^p₀ −−−→ µ^{PDE p} ←−−−− µ^{n→+∞ p}_n←− y^{Cn p}←−−− y^{ODE p}₀ ←− µ^{En p}₀

E. Cristiani and S. Sahu, On the micro-to-macro limit for first-order traffic flow models

Numerical test: merge

ρ¹(0, x ) = 0.5, ρ²(0, x ) = 0.3, ρ³(0, x ) = 0.

10 20 30 40 50 60 70 80 90 100

0 0.5 1

road 1

10 20 30 40 50 60 70 80 90 100

0 0.5 1

road 2

10 20 30 40 50 60 70 80 90 100

0 0.5 1

road 3

Numerical test: diverge

ρ¹(0, x ) = 0.5, ρ³(0, x ) = 0, ρ⁴(0, x ) = 0.

P_1→3 = 0.8, P_1→4 = 0.2.

0 10 20 30 40 50 60 70 80 90 100

0 0.5

road 1

0 10 20 30 40 50 60 70 80 90 100

0 0.5

road 3

0.5

road 4

Numerical test: 2-in-2

ρ¹(0, x ) = 0.4, ρ²(0, x ) = 0.5, ρ³(0, x ) = 0, ρ⁴(0, x ) = 0.

P_1→3= 0.7, P_1→4 = 0.3, P_2→3 = 0.6, P_2→4 = 0.4.

0 20 40 60 80 100

0 0.5 1

road 1

0 20 40 60 80 100

0 0.5 1

road 2

0 20 40 60 80 100

0 0.5 1

road 3

0 20 40 60 80 100

0 0.5 1

road 4

Comments about the micro-to-macro limit

The connection with the microscopic model promotes the solution computed by the path-based model as ”more natural”, while the one computed by maximizing the flux should be seen as the ”most desirable”, to be achieved by means of ad hoc traffic regulations.

Have we found the ”entropy solution” of the LWR model on network?

Current research

Extending path-based approach to second-order models and establishing the micro-macro connection.

Open problem

Which kind of microscopic rules should be imposed to get the classical

Comments about the micro-to-macro limit

The connection with the microscopic model promotes the solution computed by the path-based model as ”more natural”, while the one computed by maximizing the flux should be seen as the ”most desirable”, to be achieved by means of ad hoc traffic regulations.

Have we found the ”entropy solution” of the LWR model on network?

Current research

Extending path-based approach to second-order models and establishing the micro-macro connection.

Open problem

Which kind of microscopic rules should be imposed to get the classical model as limit model?

A destination-preserving model for traffic flow on networks

The path-based LWR model can be used as building block to create a destination-preserving traffic flow model. The unknowns are the densities

ρ^d(x , t), d = 1, . . . , ND,

defined on the network, of the vehicles aiming at the destination node d . Vehicles moving towards d can be found everywhere in the network.

The path-to-d can change runtime.

Main idea

Solve _∂t^∂ρ^d+_∂x^∂  ρ^dv

P

d⁰ρ^d0

= 0 inside each arc.

d p

A destination-preserving model for traffic flow on networks

The path-based LWR model can be used as building block to create a destination-preserving traffic flow model. The unknowns are the densities

ρ^d(x , t), d = 1, . . . , ND,

defined on the network, of the vehicles aiming at the destination node d . Vehicles moving towards d can be found everywhere in the network.

The path-to-d can change runtime.

Main idea

Solve _∂t^∂ρ^d+_∂x^∂  ρ^dv

P

d⁰ρ^d0

= 0 inside each arc.

Rearrange ρ^d’s in populations µ^p’s before each junction, solve the junction, go back to ρ^d’s after the junction.

Optimal control and Wardrop equilibria on networks

We can model three different behaviors:¹ basic behavior

Drivers can only choose their path on the basis of the geometry of the network. Each group chooses at start the path to follow as if no other cars are present.

rational behavior (Hughes style)

Drivers know in real time the current distribution of cars on each arc of the road and they can react to the modification of the traffic density in the network by updating their path.

highly rational behavior

Drivers are not only informed of the current distribution of cars on each arc of the network, but they can also forecast accurately the evolution of

Optimal control and Wardrop equilibria on networks

We can model three different behaviors:¹ basic behavior

Drivers can only choose their path on the basis of the geometry of the network. Each group chooses at start the path to follow as if no other cars are present.

rational behavior (Hughes style)

Drivers know in real time the current distribution of cars on each arc of the road and they can react to the modification of the traffic density in the network by updating their path.

highly rational behavior

Drivers are not only informed of the current distribution of cars on each arc of the network, but they can also forecast accurately the evolution of such distribution.

1Cf. Cristiani, Priuli, Tosin, SIAM J. Appl. Math., 75 (2015), 605–629.

Optimal control and Wardrop equilibria on networks

We can model three different behaviors:¹ basic behavior

Drivers can only choose their path on the basis of the geometry of the network. Each group chooses at start the path to follow as if no other cars are present.

rational behavior (Hughes style)

Drivers know in real time the current distribution of cars on each arc of the road and they can react to the modification of the traffic density in the network by updating their path.

highly rational behavior

Drivers are not only informed of the current distribution of cars on each arc of the network, but they can also forecast accurately the evolution of

Optimal control and Wardrop equilibria on networks

highly rational behavior

Drivers are not only informed of the current distribution of cars on each arc of the network, but they can also forecast accurately the evolution of such distribution.

In this case we enter the field of mean field games:

1 Assume the network is empty.

2 Compute the path for each destination from every point, solving a minimum time problem on the graph (via DPP).

3 Compute ρ^d(x , t), ∀d , x , t.

4 Go back to 2 until convergence (Wardrop equilibrium², if it exists).

2“Under equilibrium conditions, traffic arranges itself in congested networks in such a way that no individual trip maker can reduce his path costs by switching routes.”

Optimal control and Wardrop equilibria on networks

Conclusions

The path-based LWR model

it is easy to implement (it does not require ad hoc management of junctions);

the model selects automatically a solution at junctions such that on each single path the density is maximized (user optimum). Therefore, the scheme does not compute in general the maximal flow that could possibly be transferred over the node (global optimum);

has some interesting connections with models with “buffer”;

computes the same solution of the FTL model on network;

it can be extended to non-fixed pathdynamics and paves the way to traffic optimization where controlsare the drivers’ choices at

junctions (keeping the final destination!).

References

M. Briani, E. Cristiani, An easy-to-use algorithm for simulating traffic flow on networks: theoretical study, Netw. Heterog. Media, 9 (2014), 519–552.

G. Bretti, M. Briani, E. Cristiani, An easy-to-use algorithm for simulating traffic flow on networks: numerical experiments, Discrete Contin. Dyn. Syst.

Ser. S, 7 (2014), 379–394.

E. Cristiani, F. S. Priuli, A destination-preserving model for simulating Wardrop equilibira in traffic flow on networks, Netw. Heterog. Media, 10 (2015) 857–876.

E. Cristiani, F. S. Priuli, A. Tosin, Modeling rationality to control self-organization of crowds: an environmental approach, SIAM J. Appl.

Math., 75 (2015), 605–629.

E. Cristiani, S. Sahu, On the micro-to-macro limit for first-order traffic flow