Workshop

## ANalysis and COntrol on NETworks:

## trends and perspectives

Padova, March 9-11, 2016

## Optimization based control of networks of discretized

## PDEs: application to road traffic management

## Associated Team “ORESTE”

ORESTE (Optimal RErouting Strategies for Traffic mangEment) is an associated team between Inria project-team OPALE and the Connected Corridors project at UC Berkeley.

I Paola Goatin (PI)

I Maria Laura Delle Monache ^{I} Alexandre Bayen (PI)

I Jack Reilly

I Samitha Samaranayake

I Walid Krichene

## ORESTE project goals

I Optimize traffic flow in corridors

I ramp metering

I re-routing strategies

I Modeling approach:

I macroscopic traffic flow models

I discrete adjoint method for gradient computation

## SUMMARY

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

6. Conclusion and perspectives

1. Macroscopic models for road traffic

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

1. Macroscopic models for road traffic

## LWR model

[Lighthill-Whitham ’55, Richards ’56]Non-linear transport equation: PDE for mass conservation

∂*t*ρ + ∂*x**f (ρ) = 0* *x* *∈ R, t > 0*

I ρ∈ [0, ρ^{max}] mean traffic density

I *f (ρ) = ρv (ρ) flux function*

Empirical flux-density relation: fundamental diagram

ρ

ρcr ρmax

*f*^{max}
*f (ρ)*

0

**Greenshield ’35**

ρ

ρcr ρmax

*f*^{max}
*f (ρ)*

*v*f *f*^{max}
ρmax−ρcr

**Newell-Daganzo**

1. Macroscopic models for road traffic

## Extension to networks

m incoming arcs n outgoing arcs junction

I LWR on networks:

[Holden-Risebro, 1995; Coclite-Garavello-Piccoli, 2005; Garavello-Piccoli, 2006]

I LWR on each road

I Optimization problem at the junction

I Modeling of junctions with a buffer:

[Herty-Lebacque-Moutari, 2009; Garavello-Goatin, 2012; Bressan-Nguyen, 2015]

1. Macroscopic models for road traffic

## Extension to networks

m incoming arcs n outgoing arcs junction

I LWR on networks:

[Holden-Risebro, 1995; Coclite-Garavello-Piccoli, 2005; Garavello-Piccoli, 2006]

I LWR on each road

I Optimization problem at the junction

I Modeling of junctions with a buffer:

[Herty-Lebacque-Moutari, 2009; Garavello-Goatin, 2012; Bressan-Nguyen, 2015]

I Junction described with one or more buffers

I Suitable for optimization and Nash equilibrium problems

1. Macroscopic models for road traffic

## A model for ramp metering

I Two incoming links:

I *Upstream mainline I*1=] − ∞, 0[

I *Onramp R*1

I Two outgoing links:

I *Downstream mainline I*2=]0, +∞[

I *Offramp R*2

*I*1 *I*2

1. Macroscopic models for road traffic

## A model for ramp metering

Coupled PDE-ODE model:

I *Classical LWR on each mainline I*1*, I*2

∂*t*ρ + ∂*x**f (ρ) = 0,* *(t, x )*∈ R^{+}*× I** ^{i}*,

I Dynamics of the onramp described by an ODE (buffer)

*dl (t)*

*dt* *= F*in*(t)*− γ^{r1}*(t),* *t*∈ R^{+},

I *l (t) ∈ [0, +∞[ length of the onramp queue*

I *F*in*(t) flux entering the onramp*

I γr1*(t) flux leaving the onramp (through the junction)*

I Coupled at junctionwith an LP-optimization problem

1. Macroscopic models for road traffic

## A model for ramp metering

Coupled PDE-ODE model:

I *Classical LWR on each mainline I*1*, I*2

∂*t*ρ + ∂*x**f (ρ) = 0,* *(t, x )*∈ R^{+}*× I** ^{i}*,

I Dynamics of the onramp described by an ODE (buffer)
*dl (t)*

*dt* *= F*in*(t)*− γ^{r1}*(t),* *t*∈ R^{+},

I *l (t) ∈ [0, +∞[ length of the onramp queue*

I *F*in*(t) flux entering the onramp*

I γr1*(t) flux leaving the onramp (through the junction)*

1. Macroscopic models for road traffic

## A model for ramp metering

Coupled PDE-ODE model:

I *Classical LWR on each mainline I*1*, I*2

∂*t*ρ + ∂*x**f (ρ) = 0,* *(t, x )*∈ R^{+}*× I** ^{i}*,

I Dynamics of the onramp described by an ODE (buffer)
*dl (t)*

*dt* *= F*in*(t)*− γ^{r1}*(t),* *t*∈ R^{+},

I *l (t) ∈ [0, +∞[ length of the onramp queue*

I *F*in*(t) flux entering the onramp*

I γr1*(t) flux leaving the onramp (through the junction)*

I Coupled at junctionwith an LP-optimization problem

1. Macroscopic models for road traffic

## Junction solver: Demand & Supply

δ(ρ1) =

*f (*ρ1) if 0≤ ρ^{1}< ρ^{cr},
*f*^{max} ifρ^{cr}≤ ρ^{1}≤ 1,

ρ
*, f (ρ)*

δ(ρ)
*f*^{max}(ρ)

*d (F*in*, l) =*

θγ_{r1}^{max} *if l (t)*> 0,
*min (F*in*(t),*θγ^{max}_{r1} ) *if l (t) = 0,*

θ∈ [0, 1]control parameter

*f*^{max} if 0≤ ρ^{2}≤ ρ^{cr},

*, f (ρ)*
σ(ρ)

*f*^{max}(ρ)

1. Macroscopic models for road traffic

## Junction solver: flux maximization

1. Mass conservation: *f (ρ*1*(t, 0*−)) + γ^{r1}*(t) = f (ρ*2*(t*, 0+)) + γr2*(t)*
2. *f (ρ*2*(t, 0+)) maximum subject to 1. and*

*f (ρ*2*(t, 0+)) = min*

(1− β)δ(ρ^{1}*(t, 0−)) + d(F*^{in}*(t), l(t)), σ(ρ*2*(t*, 0+))

3. * Right of way parameter P*∈ ]0, 1[ to ensure uniqueness:

*f (*ρ2*(t, 0+)) = P f*1(*ρ(t, 0−)) + (1 − P) γ** ^{r 1}*
4. Offramp treated as a sink (infinite capacity)

5. No flux from the onramp to the offramp is allowed

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

Different situations can occur:

I Demand limited case

I Supply limited case

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

Ω

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

Different situations can occur:

I Demand limited case

I Supply limited case

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

demand limited

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

Different situations can occur:

I Demand limited case

I Supply limited case

1. Macroscopic models for road traffic

## Riemann solver: feasible set

*To find a solution of the problem we solve an LP-optimization problem*

Γr1

Γ1

δ(ρ1)

*d (F*in*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

supply limited

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Demand limited case**

*The optimal point Q is the point of maximal demands*

Γr1

Γ_{1}
δ(ρ1)

*d (F*_{in}*,¯l)*

Γ1(1− β) + Γ^{r1}= Γ2

Ω
*Q*

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω

**−→ Optimal point: S**

*S*

Γ1

δ(ρ1) Γ2

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω

**−→ Optimal point: S**

*S*

Γr1

*d (F*in*,¯l)*
Γ1

δ(ρ1) Γ2

Γ1=_{1−P}* ^{P}* Γr1

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω

**−→ Optimal point: S**

*S*

Γ1

δ(ρ1) Γ2

Γ1= * ^{P}* Γr1

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω

**−→ Optimal point: S**

*Q*

*S*

Γr1

*d (F*in*,¯l)*
Γ1

δ(ρ1) Γ2

Γ2

Γ1=_{1−P}* ^{P}* Γr1

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω

**−→ Optimal point: S**

*S*

Γ1

δ(ρ1) Γ2

Γ1= * ^{P}* Γr1

1. Macroscopic models for road traffic

## Riemann solver: optimal point

**Supply limited case**

I **We introduce the right of way parameter**

I *We set optimal point Q to be the point of intersection*

I Different situations can occur depending on the value of the intersection point

I *Q ∈ Ω*

I *Q /*∈ Ω **−→ Optimal point: S**

*Q*
*S*

Γr1

*d (F*in*,¯l)*
Γ1

δ(ρ1) Γ2

Γ1=_{1−P}* ^{P}* Γr1

1. Macroscopic models for road traffic

## Difference with

[Coclite-Garavello-Piccoli, 2005]## model

*The traffic distribution across the junction is given by the distribution matrix A:*

*A =*1 − β 1

β 0

Γ1

δ(ρ1,0)

*Q*

Γ_{1}

δ(ρ1,0) Γ_{1}=_{1−P}* ^{P}* γ

*r 1*

*Q*

1. Macroscopic models for road traffic

## Riemann solver: theorem

### Theorem

Delle Monache& al., SIAP, 2014*Fix P* ∈ ]0, 1[. For every ρ^{1,0},ρ2,0*∈ [0, 1] and l*^{0}∈ [0, +∞[, there exists a
unique admissible solution (ρ1*(t, x ), ρ*2*(t, x ), l(t)) satisfying the priority*
*(possibly in an approximate way). Moreover, for a.e. t*> 0, it holds

(ρ1*(t*, 0−), ρ^{2}*(t*, 0+)) =R* ^{l (t)}*(ρ1

*(t*, 0−), ρ

^{2}

*(t*, 0+))

¯*t*
*t*

0 *x*

ρ1,0 ρ2,0

ρˆ_{1} ρˆ_{2}

ρ¯2

ρ¯1

1. Macroscopic models for road traffic

## Modified Godunov scheme

I *At some ∆t** ^{n}*, we might have multiple shocks exiting the junction at ¯

*t*

I *We divide the time step ∆t*^{n}*= (t*^{n}*, t** ^{n+1}*) into two sub-intervals

*∆t**a**= (t*^{n}*, ¯t) and ∆t**b*= (¯*t, t** ^{n+1}*)

I We solve in one time step two different Riemann Problems at the junction

I *For ∆t**a***: Classical Godunov flux update**

ρ^{n+1}* _{J}* = ρ

^{n}*J*−

*∆t*

*a*

*∆x*(ˆΓ1*− F (ρ*^{n}*J−1*, ρ^{n}*J*))
ρ^{n+1}_{0} = ρ* ^{n}*0−

*∆t*

*a*

*∆x(F (ρ** ^{n}*0, ρ

*1) − ˆΓ2)*

^{n}I *For ∆t**b***: Modified flux update**

1. Macroscopic models for road traffic

## Numerical simulations

2. Discretized system

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

2. Discretized system

*Ramp metering discretized system H(~* *ρ, ~u) = 0*

*i* *i*

*on-ramp i*

*i + 1*
*f*_{i}^{in}*(k)* *f*_{i}^{out}*(k)* *f**i +1*^{in} *(k)*

*r**i**(k)*
*D**i**(k)*

β*i**(k) f*_{i}^{out}*(k)*

*f**i +1*^{out}*(k)*
. . .

*block i*

I Dynamics and junctions solutions based on the model described earlier

I Piecewise affine system

I *Control parameter u**i* *is a constraint on the ramp inflow r**i**(k)*

2. Discretized system

*Ramp metering discretized system H(~* *ρ, ~u) = 0*

*Lower triangular forward system H(~ρ, ~u) = 0:*

I *h**i ,k*=ρ*i**(k)*− ρ^{i}*(k− 1) − {flux update eq. for cell i and time step k}*

I *H system of concatenated h**i ,k*

I *H lower triangular*

I *Very efficient to solve H*^{T}*x = b*

2. Discretized system

*Lower triangular forward system H(~* *ρ, ~u) = 0*

Figure: ^{∂H}_{∂~}_{ρ} matrix

3. Quick review of the adjoint method

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

3. Quick review of the adjoint method

## Optimization of a PDE-constrained system

Optimization problem

minimize~*u∈U* *J (~ρ, ~u)*
subject to *H(~ρ, ~u) = 0*

I ~ρ∈ X ⊆ R* ^{NT}*: state variables

I *~u* ∈ U ⊆ R* ^{MT}*: control variables

Gradient descent: How to compute the gradient *∂J*

∂~ρ

∂~ρ

*∂~u* +*∂J*

*∂~u* ?
*On trajectories, H(~ρ, ~u) = 0 constant, thus*

*∂H*

∂~ρ

∂~ρ

*∂~u* +*∂H*

*∂~u* = 0 *O(T*^{2}*N*^{2}*M)*

3. Quick review of the adjoint method

## Discrete adjoint method

Consider the Lagrangian

*L(~ρ, ~u, λ) = J(~ρ, ~u) + λ*^{T}*H(~ρ, ~u)*
thus∇^{~}^{u}*L =*∇^{~}^{u}*J :*

∇^{u}*L(~ρ, ~u, λ) =* *∂J*

*∂~u* +*∂J*

∂~ρ

∂~ρ

*∂~u* +λ^{T}* ∂H*

*∂~u* +*∂H*

∂~ρ

∂~ρ

*∂~u*

= *∂J*

*∂~u* +λ^{T}*∂H*

*∂~u* +* ∂J*

∂~ρ+λ^{T}*∂H*

*∂~u*

∂~ρ

*∂~u*
Compute λs.t.

*∂H*

∂~ρ

*T*

λ=−*∂J*

∂~ρ

*T*

*O(T*^{2}*N*^{2})

3. Quick review of the adjoint method

## Exploiting system structure

The structure of the forward system influences the efficiency adjoint system solving

### Solving for λ

*∂H*

∂~ρ

*T*

λ=−*∂J*

∂~ρ

*T*

Since ^{∂H}_{∂~}_{ρ} is lower triangular, ^{∂H}_{∂~}_{ρ}* ^{T}* is an upper triangular matrix

=⇒ The adjoint system can be solved efficiently using backward substitution

*Complexity reduction from O(T*

^{2}

*NM) to O(NT + MT )*

3. Quick review of the adjoint method

## Exploiting system structure

The structure of the forward system influences the efficiency adjoint system solving

### Solving for λ

*∂H*

∂~ρ

*T*

λ=−*∂J*

∂~ρ

*T*

Since ^{∂H}_{∂~}_{ρ} is lower triangular, ^{∂H}_{∂~}_{ρ}* ^{T}* is an upper triangular matrix

=⇒ The adjoint system can be solved efficiently using backward substitution

3. Quick review of the adjoint method

## Optimization algorithm

**Algorithm 1 Gradient descent loop**
Pick initial control*~u**init* *∈ U*^{ad}
**while not converged do**

~

*ρ = forwardSim(~u, IC , BC )* solve for state trajectory (forward system)
*λ = adjointSln(~ρ, ~u)* solve for adjoint parameters (adjoint system)

∇^{u}*J =*λ^{T ∂H}_{∂~}* _{u}* +

^{∂J}_{∂~}

*compute the gradient (search direction)*

_{u}*~u← ~u − α∇*^{u}*J ,*α*∈ (0, 1) s.t. ~u ∈ U*^{ad}update the control*~u (update step)*
**end while**

3. Quick review of the adjoint method

## Remarks on descrete adjoint

Strengths:

I Requires only one solution of adjoint system, independent of dim(~u) (unlike finite differences or sensitivity analysis).

I Extends existing simulation code

I General technique, can be applied in very different settings

Weaknesses:

I Optimization of the discretized problem, rather than approximation of the optimal solution of the continuous problem

I No proof of convergence

4. Numerical results

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

6. Conclusion and perspectives

4. Numerical results

## Numerical Results: case study

Figure: I15 South, San Diego: 31 km

*N = 125 links and M = 9 onramps*
*T = 1800 time-steps*

*∆t = 4 seconds (120 minutes time interval)*

4. Numerical results

## Numerical Results

Density and queue lengths without control

Density and queue difference with control

4. Numerical results

## Model Predictive Control

Performance undernoisy input data: MPC loop

I *initial conditions at time t and boundary fluxes on T** _{h}*(noisy inputs)

I *optimal control policy on T*_{h}

I *forward simulation on T*_{u}*≤ T** ^{h}* using optimal controls and exact initial and
boundary data

I *t* *→ t + T*^{u}

Comparison with Alinea (local feedback control without boundary conditions)

0.5 1.0 1.5 2.0 2.5 3.0 3.5

ReducedCongestion(%)

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0

ReducedCongestion(%) Adjoint

Alinea

4. Numerical results

## Running time

Convergence

10^{−1} 10^{0} 10^{1} 10^{2} 10^{3}

Running time (ms) 226

227 228 229 230 231 232 233 234

Totaltraveltime(veh-s) Finite differences

Adjoint

Simulation time

0 50 100 150 200 250 300 350 400 450 Running time (seconds)

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5

ReducedCongestion(%)

Adjoint Alinea

5. Application to optimal re-routing

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

5. Application to optimal re-routing

## Application to optimal re-routing

System Optimal Dynamic Traffic Assignment problem with Partial Control:

Multi-commodity flow:

ρ*i**(k) =*X

*c∈C*

ρ*i ,c**(k)*

*accounting for compliant c**c* *∈ CC and non-compliant c** ^{n}*users

I full Lagrangian paths known for the controllable agents

I knowledge of the aggregate split ratios for the non-controllable (selfish) agents.

### Goal: Control compliant users to optimize traffic flow

5. Application to optimal re-routing

## Application to optimal re-routing

System Optimal Dynamic Traffic Assignment problem with Partial Control:

Multi-commodity flow:

ρ*i**(k) =*X

*c∈C*

ρ*i ,c**(k)*

*accounting for compliant c**c* *∈ CC and non-compliant c** ^{n}*users

I full Lagrangian paths known for the controllable agents

I knowledge of the aggregate split ratios for the non-controllable (selfish) agents.

### Goal: Control compliant users to optimize traffic flow

5. Application to optimal re-routing

## Numerical study: synthetic network

[Ziliaskopoulos, 2001]I Normal conditions: link capacity between cell 3 and cell 4 = 6 Optimal total travel time: 178

I Incident between cell 3 and cell 4: capacity goes to 0 Optimal total travel time: 211 (otherwise 244)

5. Application to optimal re-routing

## Synthetic network: partial control

5. Application to optimal re-routing

## Numerical study: real case

Figure: I210 with parallel arterial route, Arcadia (13 km)

*N = 24 links*
1 hour time-horizon

*∆t = 30 seconds*

5. Application to optimal re-routing

## Numerical Results

50% capacity drop between min 10 and min 30

5. Application to optimal re-routing

## Numerical Results

Arterial capacity used:

6. Conclusion and perspectives

## Outline of the talk

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

6. Conclusion and perspectives

## In summary

Results:

I Definition of appropriate junction solvers for ramp metering and multi-commodity

I Formulation of the corresponding finite horizon optimal control problems

I *Gradient computation with O(NT + MT ) complexity*

I Numerical tests showing the benefits on real field applications

Possible extensions:

I Variable speed limit, maximal queue length, ...

I Selfish agents response (Stackelberg games)

6. Conclusion and perspectives

## References

I M.L. Delle Monache, J. Reilly, S. Samaranayake, W. Krichene, P.Goatin
and A. Bayen. *A PDE-ODE model for a junction with ramp buffer, SIAM*
J. Appl. Math., 74(1) (2014), 22-39.

I J. Reilly, S. Samaranayake, M.L. Delle Monache, W. Krichene, P. Goatin
and A. Bayen. *Adjoint-based optimization on a network of discretized*
*scalar conservation law PDEs with applications to coordinated ramp*
*metering, J. Optim. Theory Appl., 167(2) (2015), 733-760.*

I S. Samaranayake, W. Krichene, J. Reilly, M.L. Delle Monache, P. Goatin
and A. Bayen. *Discrete-time system optimal dynamic traffic assignment*
*(SO-DTA) with partial control for horizontal queuing networks, in review.*