# Speed limit and ramp meter control for traffic flow networks

Paola Goatin, Simone Göttlich, Oliver Kolb

<figure><img src="image_1.png" /></figure>

To cite this version:

Paola Goatin, Simone Göttlich, Oliver Kolb. Speed limit and ramp meter control for traffic flow networks. Engineering Optimization, 2016, 48 (7), pp.1121-1144. hal-01081762

HAL Id: hal-01081762

https://inria.hal.science/hal-01081762

Submitted on 10 Nov 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
Speed limit and ramp meter control for traffic
flow networks

Paola Goatin,* Simone Göttlich,** Oliver Kolb**

November 8, 2014

Abstract

The control of traffic flow can be related to different applications. In
this work, we introduce how to manage variable speed limits combined
with coordinated ramp metering within the framework of the LWR net-
work model. Following a “first discretize then optimize” approach, we
derive the first order optimality system and explain the switch of speeds
at certain fixed points in time and the boundary control for the ramp
metering as well. Sequential quadratic programming methods are used
to solve the control problem numerically. For application purposes, we
present experimental setups where variable speed limits are used as a
traffic guidance system to avoid traffic jams on highway interchanges and
on-ramps.

**AMS Classification.** 90B20, 49K20

**Keywords.** Traffic flow network, control of discretized PDEs, adjoint based optimization

# 1 Introduction

Traffic flow networks based on scalar conservation laws have been investigated
from various perspectives during the last years, see for instance [4, 17] for the-
oretical results or [2] for numerical considerations. In the case of nonlinear
traffic flow networks where the dynamics obey the Lighthill-Whitham-Richards
equations [22,26], the crucial point is the modeling of intersections. Assuming
conservation of mass leads to a flux maximization problem at nodes to obtain
unique admissible solutions. This approach results in appropriate Riemann so-
lutions that can be directly specified, see [7]. We will use this mathematical
formulation and framework to describe the dynamics for the traffic system.

For many applications, not only the numerical simulation of the nonlinear
dynamics is of interest but also optimization or control issues. To set up the
optimization problem, a cost functional and control variables must be identi-
fied, while the constraints are given by the above mentioned traffic flow net-
work equations. There exists a broad range of practical aspects including the

<footnote>*INRIA Sophia Antipolis - Méditerranée, 06902 Sophia-Antipolis, France (paola.goatin@inria.fr).</footnote>

<footnote>**University of Mannheim, Department of Mathematics, 68131 Mannheim, Germany ({goettlich, kolb}@uni-mannheim.de).</footnote>
optimal routing of traffic [12], traffic light control [11] or coordinated ramp me-
tering [25] for the LWR network model. Since these optimal control problems
are constrained by nonlinear conservation laws, relaxed models with simplified
dynamics have been investigated instead, cf. [16].

Reduced models usually rely on linear approximations leading to control
methodologies such as linear optimization [23], feedback control [24] or Lya-
punov stability [1], respectively. However, nonlinear control techniques as for
instance adjoint calculus [25] or model predictive control [14] represent a suitable
and natural choice to treat traffic network control problems.

We concentrate on the variable speed limit (VSL) problem coupled to ramp metering. From a mathematical point of view, the control variable, i.e. the maximal velocity for the VSL problem, varies and must be evaluated at discrete points in time. This leads to conservation laws with time-dependent discontinuous coefficients [5]. On the other hand, the on-ramp metering problem corresponds to a discussion of boundary conditions at junctions [8, 9]. Setting up the corresponding control problems is then a combination of two control issues directly influencing each other in the sense that time-dependent speed limits reduce congestions and hence the travel times. This kind of problem have been for example considered in [6, 13, 23] and references therein. In contrast to our approach, the latter either follow a model predictive control where the optimization is obtained using sequential quadratic programming (SQP) or are restricted to the presentation of (numerical) results for one road/one on-ramp only.

To the best of our knowledge, the variable speed limit control problem com-
bined with ramp metering has never been solved for the full LWR model on
complex network topologies in a rigorous manner. In this article, we will close
this gap from a modeling and computational point of view. We will stick to con-
tinuous optimization techniques where usually the first order optimality system
is derived and solved by a descent type method [18,27]. We apply the so-called
discretize-then-optimize approach, meaning that a suitable numerical discretiza-
tion is chosen such that the original problem leads to a finite-dimensional op-
timality system [12]. In this way, we automatically include information about
the current traffic situation into the control framework (open loop control) and
look for the best traffic management. This procedure was originally introduced
for aerodynamic shape design [10].

We proceed as follows: We briefly recall the LWR network model in Section 2.
Then, in Section 3, we explain how we model variable speed limits and ramp
metering. We address the optimal control problem and its solution procedure by
discretizing the governing equations in space and time. The numerical results
are collected in Section 4. In particular, we point out benefits and drawbacks of
our approach. We also observe that variable speed limits help to navigate the
traffic flow, so that short travel times and high system outflows are maintained
even if the ramp metering is unable to prevent congestion.

2 Traffic Flow Network Modeling

Following the ideas in [4, 7], we typically model a traffic flow network as a
directed graph $G = (V, E)$, where the edges $E$ correspond to roads and the
vertices $V$ to junctions or intersections. Each edge $e \in E$ is associated with an
interval $[0, L_e]$ and $\rho_e(x, t)$ denotes the density of cars on road e.

Given some initial state $\rho_e(x, 0)$ on all roads, the dynamics are described by

$$ \partial_t \rho_e(x, t) + \partial_x f_e(\rho_e(x, t), t) = 0 \quad \forall e \in E, x \in (0, L_e), t \in [0, T] \quad (1) $$

with Lighthill-Whitham-Richards flux [22, 26]

$$ f_e(\rho, t) = \rho v_e^{\max}(t) \left( 1 - \frac{\rho}{\rho_e^{\max}} \right), $$

where $v_e^{\max}(t)$ is the (piecewise constant) maximal speed limit and $\rho_e^{\max}$ is the maximal car density corresponding to the jammed situation. See for instance Figure 1 for an illustration of the dependencies of the velocity and the flow rate with respect to the density in case of different speed limits. We also denote by $f_e^{\max}$ the maximal flux:

$$ f_e^{\max} = f_e(\rho_e^c), \quad \text{with } \rho_e^c = \rho_e^{\max}/2. $$

<figure><img src="image_2.png" /><figcaption>Figure 1: Velocity and flow rate for different speed limits.</figcaption></figure>

We also see in Figure 1 that different maximal velocities $v_e^{\max}(t)$ lead to conservation laws on networks with time-dependent discontinuous coefficients. Note that general existence results for these type of conservation laws on networks are not available at the moment. The network consideration requires the extension of the well-posedness result given in [5] for the standard Cauchy problem on the real line. Nevertheless, in the specific application considered in this work, the time-dependence is piecewise constant, and therefore classical existence results on networks can be applied [8].

## Coupling Conditions at Junctions

The description of the whole network dynamics requires the definition of the corresponding boundary and coupling conditions at junctions $v \in V$ to basically ensure the conservation of mass. Therefore, we introduce the demand and supply functions that are given respectively by

$$ D_e(\rho) = \begin{cases} f_e(\rho) & \text{if } \rho \le \rho_e^c, \\ f_e^{\max} & \text{if } \rho \ge \rho_e^c, \end{cases} \quad \text{and} \quad S_e(\rho) = \begin{cases} f_e^{\max} & \text{if } \rho \le \rho_e^c, \\ f_e(\rho) & \text{if } \rho \ge \rho_e^c. \end{cases} $$

For simplicity and in view of the applications considered in this work, we will only consider the cases of one-to-one junctions, the merging of two roads into one, and the dispersing of one road into two, see Fig. 2.
<figure><img src="image_3.png" /><figcaption>Figure 2: Different types of junctions.</figcaption></figure>

In the case of a junction between only an incoming road $e = 1$ and an outgoing one $e = 2$, the appropriate fluxes at the junction are simply obtained through the minimization between demand and supply:

$$ \hat{\gamma}_1 = \hat{\gamma}_2 = \min \{D_1(\rho_1), S_2(\rho_2)\}. \quad (2) $$

Let us now consider more involved cases, e.g. the case of a dispersing junction with one incoming road $e = 1$ and two outgoing roads $e = 2, e = 3$. Here, the distribution of cars must be externally prescribed by so-called distribution rates $\alpha_{2,1} \ge 0$ and $\alpha_{3,1} \ge 0$ (and $\alpha_{2,1} + \alpha_{3,1} = 1$).

Contrarily to what is proposed in [7], we make the choice of applying NON-FIFO rules, thus allowing for some flow through the junction even if one of the outgoing roads is blocked. This is more reasonable for highway networks than a classical FIFO model. The fluxes at the junction are computed as (see also [15,21])

$$ \hat{\gamma}_2 = \min \{\alpha_{2,1} D_1(\rho_1), S_2(\rho_2)\}, \quad (3a) $$

$$ \hat{\gamma}_3 = \min \{\alpha_{3,1} D_1(\rho_1), S_3(\rho_3)\}, \quad (3b) $$

$$ \hat{\gamma}_1 = \hat{\gamma}_2 + \hat{\gamma}_3. \quad (3c) $$

Finally, we focus on the case of a merging junction of ingoing two roads $e = 1, e = 2$ and outgoing one $e = 3$. In this case, a priority parameter $P \in (0, 1)$ is introduced so that $\hat{\gamma}_1 = P\hat{\gamma}_3$ and $\hat{\gamma}_2 = (1-P)\hat{\gamma}_3$. This is necessary to define a unique solution in the supply constrained cases, see [7, Section 5.2.2] for more details. The corresponding fluxes are then

$$ \hat{\gamma}_1 = \min \{D_1(\rho_1), \max\{PS_3(\rho_3), S_3(\rho_3) - D_2(\rho_2)\}\}, \quad (4a) $$

$$ \hat{\gamma}_2 = \min \{D_2(\rho_2), \max\{(1-P)S_3(\rho_3), S_3(\rho_3) - D_1(\rho_1)\}\}, \quad (4b) $$

$$ \hat{\gamma}_3 = \hat{\gamma}_1 + \hat{\gamma}_2. \quad (4c) $$

The model equations (1)-(4) can be further coupled to inflow conditions at roads entering or leaving the network. As we will see later on, this modeling framework can be extended to describe the ramp metering.

## Inflow and Outflow Conditions

Let us consider an arc $e$ connected to the network only at its right node. Given a desired inflow rate $f_e^{in}$, the actual inflow to the road $e$ is given by

$$ \gamma_e^{in} = \min \{f_e^{in}, S_e(\rho_e)\}. \quad (5) $$
We assume there is a queue at the left node of arc e with length $l_e(t)$. Then, the inflow to the road is given by

$$ \gamma_e^{\text{in}} = \min\{D_e(l_e), S_e(\rho_e)\} \qquad (6) $$

with the demand function dependent on the length $l_e(t)$

$$ D_e(l_e) = \begin{cases} f_e^{\text{max}} & \text{if } l_e(t) > 0, \\ \min\{f_e^{\text{in}}, f_e^{\text{max}}\} & \text{if } l_e(t) = 0. \end{cases} \qquad (7) $$

As usual, the evolution of the queue-length $l(t)$ obeys the rate equation

$$ \frac{dl(t)}{dt} = f_e^{\text{in}} - \gamma_e^{\text{in}} \qquad (8) $$

for an initial state $l_e(0)$.

Conversely, on arcs connected only on their left to the network, we prescribe absorbing boundary conditions up to a given maximum flow rate $f_e^{\text{out}}$ in the form

$$ \gamma_e^{\text{out}} = \min\{f_e^{\text{out}}, D_e(\rho_e)\}, \qquad (9) $$

which ensures that the flow reaching the end of such a road is able to leave the network without being stopped if it is below the given maximum flow rate.

In the next section, we describe the optimization problem we intend to solve. We also comment on the discretization and the numerical implementation.

## 3 Optimal Control Problem

For optimization purposes, we are interested in controlling the traffic flow through a network by adjusting maximal speed limits and on-ramp fluxes as well.

The overall goal of optimization is to choose the controls in such a way that the total travel time is minimized and/or the outflow of the system is maximized, i.e.

$$ \min J(l_e, \rho_e, f_e^{\text{out}}) = \sum_e \beta_e \int_0^T \left( l_e(t) + \int_0^{L_e} \rho_e(x, t) dx \right) dt - \sum_e \gamma_e \int_0^T f_e^{\text{out}}(t) dt. \qquad (10) $$

Here, $\beta_e$ and $\gamma_e$ denote non-negative weights. Note that we later consider additional terms in the objective function such that $J$ will further explicitly depend on the control variables introduced in the following. The constraints of the optimization problem are mainly determined by the traffic flow network model introduced in Section 2. Further, we consider upper bounds for queue lengths below. These inequality constraints will be explicitly passed to the applied optimization procedure and not integrated by additional penalty terms in the objective function. However, we need to explain how the two controls are integrated into the model equations. That means, we have to modify the flux in (1) for the speed limit and (8) for the ramp metering control. Since the optimization problem under consideration is constrained by differential equations, we first use suitable numerical methods to discretize the equations and then propose a nonlinear optimization technique. This results in a so-called *discretize-then-optimize approach*.
## Variable Speed Limits

As already mentioned and shown in Figure 1, the maximal velocities $v_e^{\max}(t)$ on each road $e \in E$ may change in time. Therefore, we assume that $v_e^{\max}(t)$ is a time-dependent control variable restricted by box constraints,

$$v_e^{\text{low}} \le v_e^{\max}(t) \le v_e^{\text{high}} \quad \forall t \in [0, T].$$

To get a finite dimensional optimization problem and also for practical reasons, we introduce control points $\nu^k \in [0, T]$ ($k \in \{0, \dots, Nu\}$) and corresponding control variables $z_e^k$ for each road. We take $v_e^{\max}(t)$ piecewise constant on the control grid:

$$v_e^{\max}(t) = z_e^{k+1} \quad \forall t \in (\nu^k, \nu^{k+1}]. \quad (11)$$

The choice of the control grid will be investigated in Section 4.1. Note that, in order to avoid high fluctuations in the control function, a penalty term can be added to (10). This issue is also addressed in Section 4.1.

## Ramp Metering

The control of on-ramps can be recast in the framework of merging junctions, i.e. we consider a two-to-one merge as in Figure 2(c). We aim at controlling the main lane access from the on-ramp, where we assume that the index $e = 2$ corresponds to the on-ramp, now described by a queue (7). The time-dependent control variable $w_e = w_e(t)$ is used to control the inflow from the on-ramp into the main lane by rewriting equations (4). Mathematically, we define the controlled demand function

$$D_e^c(l_e) = w_e(t)D_e(l_e), \quad (12)$$

for $D_e(l_e)$ given by (7). Then we plug (12) in (4) and end up with

$$\hat{\gamma}_1 = \min \{D_1(\rho_1), \max\{PS_3(\rho_3), S_3(\rho_3) - D_2^c(l_2)\}\}, \quad (13a)$$

$$\hat{\gamma}_2 = \min \{D_2^c(l_2), \max\{(1-P)S_3(\rho_3), S_3(\rho_3) - D_1(\rho_1)\}\}, \quad (13b)$$

$$\hat{\gamma}_3 = \hat{\gamma}_1 + \hat{\gamma}_2. \quad (13c)$$

Correspondingly, the evolution of the on-ramp buffer changes to

$$\frac{dl(t)}{dt} = f_2^{\text{in}} - \hat{\gamma}_2, \quad (14)$$

where $f_2^{\text{in}}$ is the external boundary inflow at the on-ramp.

Similar to the speed control (11) we also assume a piecewise constant control function for the ramp metering:

$$w_e(t) = w_e^{k+1} \quad \forall t \in (\nu^k, \nu^{k+1}]. \quad (15)$$

A reasonable extension is to put queue length limits on (14). This case is presented in Sections 4.2 and 4.3.

Summarizing, the speed limit and ramp metering control problem for traffic flow networks reads as follows:

$$\begin{array}{ll} \min_{z_e, w_e} & J(l_e, \rho_e, f_e^{\text{out}}, z_e, w_e) \\ \text{s.t.} & (1)-(9), (11), (12)-(15). \end{array} \quad (16)$$
This is a nonlinear optimization problem which can be solved within an adjoint-based optimization framework. To this end, we fully discretize (16) in a straightforward way. Then, the first order optimality system and the associated gradient information is obtained by evaluations of forward and backward (or adjoint) equations. Details of this procedure can be found in Section 3.2.

## 3.1 Discretization

For the numerical solution of the described model, we consider a finite number of time points $t^n = n\Delta t$ with $\Delta t = \frac{T}{Nt}$. Note that the $t^n$ may differ from the control points $\nu^k$ above. Further, we divide each road $e$ into $Nx_e$ cells of equal size $\Delta x_e = \frac{L_e}{Nx_e}$.

Hence, the objective function (10) is discretized by quadrature formulas as follows:

$$ \min \sum_{e} \beta_{e} \sum_{n=1}^{Nt} \left( l_{e}^{n} + \sum_{j=1}^{Nx_{e}} \rho_{e,j-0.5}^{n} \Delta x_{e} \right) \Delta t - \sum_{e} \gamma_{e} \sum_{n=1}^{Nt} f(\rho_{e,Nx_{e}}^{n}) \Delta t. \quad (17) $$

The constraints are discretized by following the structure of Section 2. For the discretization of (1), we use a staggered Lax-Friedrichs scheme (leaving out the index $e$ for the road and the time dependency of the flux function for a better reading):

$$ \rho_{0.5}^{n+1} = \frac{1}{4}(3\rho_{0.5}^{n} + \rho_{1.5}^{n}) - \frac{\lambda}{2}[f(\rho_{1.5}^{n}) + f(\rho_{0.5}^{n}) - 2f(\rho_{0}^{n})], \quad (18a) $$

$$ \rho_{j-0.5}^{n+1} = \frac{1}{4}(\rho_{j-1.5}^{n} + 2\rho_{j-0.5}^{n} + \rho_{j+0.5}^{n}) - \frac{\lambda}{2}[f(\rho_{j+0.5}^{n}) - f(\rho_{j-1.5}^{n})], \quad (18b) $$

$$ \rho_{Nx-0.5}^{n+1} = \frac{1}{4}(\rho_{Nx-1.5}^{n} + 3\rho_{Nx-0.5}^{n}) - \frac{\lambda}{2}[2f(\rho_{Nx}^{n}) - f(\rho_{Nx-0.5}^{n}) - f(\rho_{Nx-1.5}^{n})], \quad (18c) $$

where $\lambda = \Delta t/\Delta x$ and

$$ \rho_{e,j-0.5}^{n} \approx \frac{1}{\Delta x_{e}} \int_{(j-1)\Delta x_{e}}^{j\Delta x_{e}} \rho_{e}(x, t^{n}) dx \quad \text{for } j \in \{1, \dots, Nx_{e}\}, n \in \{0, \dots, Nt\}. $$

Concerning (10), $f_e^{\text{out}}(t)$ corresponds to $f(\rho_{Nx}^n)$. The inflow $f(\rho_0^n)$ and the outflow $f(\rho_{Nx}^n)$ directly result from the applied coupling and boundary conditions.

### Coupling conditions at junctions

At a simple junction connecting two roads $e = 1$ (incoming) and $e = 2$ (outgoing), we use

$$ f(\rho_{1,Nx_1}^n) = f(\rho_{2,0}^n) = \min \{D_1(\rho_{1,Nx_1-0.5}^n), S_2(\rho_{2,0.5}^n)\}, \quad (19) $$

according to (2).

For junctions with one incoming road $e = 1$ and two outgoing roads $e = 2$ and $e = 3$, and non-negative distribution rates $\alpha_{2,1}$ and $\alpha_{3,1}$ (with $\alpha_{2,1} + \alpha_{3,1} = 1$), we apply (referring to (3))

$$ f(\rho_{2,0}^n) = \min \{\alpha_{2,1}c_1, c_2\}, \quad (20a) $$

$$ f(\rho_{3,0}^n) = \min \{\alpha_{3,1}c_1, c_3\}, \quad (20b) $$

$$ f(\rho_{1,Nx_1}^n) = f(\rho_{2,0}^n) + f(\rho_{3,0}^n), \quad (20c) $$
with

$$c_1 = D_1(\rho_{1,Nx_1-0.5}^n), \quad c_2 = S_2(\rho_{2,0.5}^n), \quad c_3 = S_3(\rho_{3,0.5}^n).$$

For junctions with two incoming roads $e = 1$ and $e = 2$, one outgoing road $e = 3$, and priority parameter $P \in (0, 1)$, we use (according to (4))

$$f(\rho_{1,Nx_1}^n) = \min\{c_1, \max\{Pc_3, c_3 - c_2\}\}, \quad (21a)$$

$$f(\rho_{2,Nx_2}^n) = \min\{c_2, \max\{(1-P)c_3, c_3 - c_1\}\}, \quad (21b)$$

$$f(\rho_{3,0}^n) = f(\rho_{1,Nx_1}^n) + f(\rho_{2,Nx_2}^n), \quad (21c)$$

with

$$c_1 = D_1(\rho_{1,Nx_1-0.5}^n), \quad c_2 = D_2(\rho_{2,Nx_2-0.5}^n), \quad c_3 = S_3(\rho_{3,0.5}^n).$$

Note that $c_2 = D_2^e(l_2^n)$ in the case of a controlled on-ramp junction as described in (12) and (13).

## Inflow conditions

According to (5), we apply

$$f(\rho_{e,0}^n) = \min\{f_e^{\text{in}}(t^n), S_e(\rho_{e,0.5}^n)\} \quad (22)$$

at an inflow boundary with a desired inflow rate $f_e^{\text{in}}(t^n)$. In the presence of a queue, according to (6), (7), (8) and (12), we use

$$f(\rho_{e,0}^n) = \min\{c_{\text{queue}}, S_e(\rho_{e,0.5}^n)\} \quad (23)$$

with

$$c_{\text{queue}} = w_e(t^n) \min \left\{ f_e^{\text{in}}(t^n) + \frac{l_e^n}{\Delta t}, f_e^{\text{max}} \right\},$$

and

$$l_e^{n+1} = l_e^n + \Delta t (f_e^{\text{in}}(t^n) - f(\rho_{e,0}^n)), \quad (24)$$

where $l_e^n \approx l_e(t^n)$.

At an outflow boundary at edge $e$ with maximum outflow rate $f_e^{\text{out}}(t^n)$, we use (see (9))

$$f(\rho_{e,Nx}^n) = \min\{f_e^{\text{out}}(t^n), D_e(\rho_{e,Nx-0.5}^n)\}. \quad (25)$$

## Entire Simulation Procedure

For given initial conditions for the traffic flow network and prescribed speed limits and ramp controls, the presented discretizations allow for an approximate solution of our model. The basic steps of this procedure are given in Algorithm 1. Starting from the initial state at time $t^0 = 0$, one may iteratively compute the flow rates at the current time $t^n$ (for $n = 0, \dots, Nt - 1$), and subsequently the density values and queue lengths at the next time $t^{n+1}$.
**Algorithm 1** Numerical Simulation

**Input:** initial conditions $\rho_{e,j}^0$ and $l_e^0$ at time $t^0$; speed limits $v_e^{\max}(t)$ and ramp controls $w_e(t)$.

**Output:** state variables $\rho_{e,j}^n$ and $l_e^n$ for all times $t^n$ with $n \in \{1, \dots, Nt\}$.
**for** $n = 0, \dots, Nt-1$ **do**

1. Compute inflow and outflow rates at the nodes at time $t^n$ according to (22), (23), (25), (19), (20) and (21).

2. Compute density values $\rho_{e,j}^{n+1}$ and queue lengths $l_e^{n+1}$ at time $t^{n+1}$ according to (18) and (24).

**end for**

## 3.2 Optimization approach

Based on the presented discretization and the simulation procedure shown in Algorithm 1, we want to solve the underlying (finite dimensional) optimization task with an SQP solver [28,29]. This necessitates the evaluation of the objective function and the computation of gradient information. The (discretized) objective function (17) can be directly evaluated after running a simulation according to Algorithm 1. For the necessary gradient information we apply a first-discretize adjoint approach. The main steps of the underlying procedure are given in Algorithm 2.

**Algorithm 2** Gradient Computation

**Input:** initial conditions $\rho_{e,j}^0$ and $l_e^0$ at time $t^0$; speed limits $v_e^{\max}(t)$ and ramp controls $w_e(t)$ given by a control vector $u$ containing all $z_e^k$ and $w_e^k$ (for $k \in \{1, \dots, Nu\}$).

**Output:** total derivative $\frac{d}{du}J(u, y(u))$.

1. Run numerical simulation according to Algorithm 1.

2. Solve adjoint equation (26).

3. Compute gradient $\frac{d}{du}J(u, y(u))$ according to (27).

To describe the applied adjoint approach, we consider the objective function $J(u, y)$ (in our case given by (17)), where $u$ contains all control variables of the discretized model equations (the speed limits $z_e^k$ and the ramp controls $w_e^k$) and $y$ all state variables (densities $\rho_e^n$, flow rates $f(\rho_e^n)$, queue lengths $l_e^n$). Further, we summarize all discretized model equations, or constraints respectively, as $E(u, y) = 0$. Assuming that for given control variables $u$ the model equations $E(u, y)$ have a unique solution, one may consider $y = y(u)$ and the so-called reduced problem with the objective function $J(u) = J(u, y(u))$. Note that the solution of $E(u, y) = 0$ corresponds to running Algorithm 1.

With the so-called adjoint state $\xi$ given by the solution of the adjoint equation

$$ \left( \frac{\partial}{\partial y} E(u, y(u)) \right)^T \xi = - \left( \frac{\partial}{\partial y} J(u, y(u)) \right)^T, \qquad (26) $$

one can efficiently compute the cost gradient as

$$ \frac{d}{du} J(u, y(u)) = \frac{\partial}{\partial u} J(u, y(u)) + \xi^T \frac{\partial}{\partial u} E(u, y(u)). \qquad (27) $$
In fact, the partial derivatives of *J* and *E* with respect to *u* and *y* can be easily computed and (26) is a single linear system with a special structure that can be easily exploited (see for instance [19, 20]). Incidentally, we remark that the solution given by the gradient descent method is only locally optimal.

As already noted above, the time points $t^n$ of the discretization may differ from the control points $v^k$. The values of the controls $v_e^{\max}(t)$ and $w_e(t)$ at $t = t^n$, which are needed within Algorithms 1 and 2, are computed according to (11) and (15). Regarding the computation of gradient information with Algorithm 2, this necessitates the application of the chain rule (cf. again [19]), where in our case the “inner derivatives” equal zero or one due to the piecewise constant control functions.

# 4 Numerical Results

This section collects the numerical results corresponding to three different scenarios. The first example is concerned with variable speed limits to control traffic flow on a road network similar to the *Frankfurter Kreuz*, which is a famous German Autobahn interchange. Here we vary discretization as well as control grid parameters to study their influence on the optimal solution. In the second example we consider the combined optimization of variable speed limits (VSL) and ramp metering. The topology of the third example is quite similar to the second one, but refers to a real world case study.

## 4.1 Variable Speed Limits

Inspired by the Autobahn interchange in Frankfurt, Germany, we present a corresponding topology of the road network (including distribution rates $\alpha$ and priority parameters $P$) in Figure 3. Further road properties as well as the initial conditions are given in Table 1. Additionally, Figure 4 shows the inflow profiles within the considered time horizon of 1000 seconds.

<figure><img src="image_4.png" /><figcaption>Figure 3: Road network with two main roads.</figcaption></figure>

For the described setting we consider the following experiments:

1. Optimization for a fixed discretization ($\Delta x = 50$, $\Delta t = 0.5$) and various numbers of control points $Nu$.
<table><caption>Table 1: Properties of the roads in Figure 3</caption><thead><tr><th>road</th><th>length</th><th>ρ<sub>max</sub></th><th>v<sub>low</sub></th><th>v<sub>high</sub></th><th>initial density</th></tr></thead><tbody><tr><td>roadA1</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>0.3</td></tr><tr><td>roadA2</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>0.3</td></tr><tr><td>roadA3</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>0.3</td></tr><tr><td>roadB1</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>0.3</td></tr><tr><td>roadB2</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>1.2</td></tr><tr><td>roadB3</td><td>1000</td><td>2</td><td>20</td><td>30</td><td>1.2</td></tr><tr><td>roadAB</td><td>200</td><td>0.5</td><td>10</td><td>20</td><td>0.1</td></tr><tr><td>roadBA</td><td>200</td><td>0.5</td><td>10</td><td>20</td><td>0.1</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Figure 4: Inflow profiles for the network in Figure 3.</figcaption></figure>

2. Optimization for a fixed number of control points ($Nu = 20$) and various discretization parameters.

3. We finally consider the same experiment as in 1. with a fixed discretization but an additional penalty term with weight $\delta_e \ge 0$ in (17):

$$ \sum_{e} \delta_{e} \sum_{n=1}^{Nt} \Delta t \left( \frac{v_{e}^{\max}(t^n) - v_{e}^{\max}(t^{n-1})}{v_{e}^{\max} \Delta t} \right)^2 $$

in order to get smoother controls. This is similar to [14].

Table 2 and Figure 5 show the results for the first test. While the discretization parameters are kept fixed, we consider an increasing number of control points $Nu$ and run the optimization once for minimizing the total travel time (with $\beta_e = 10^{-3}$) and once for maximizing the accumulated outflow at the nodes outA and outB (with $\gamma_e = 10^{-1}$). As expected one gets lower travel times / larger outflows for an increasing number of control points. In particular, compared to the uncontrolled case, where all speed limits are taken at the upper bound, we achieve an improvement of 1.28% / 0.03%. Exemplarily, Figure 6 compares the traffic density in the middle of roadB2 with and without optimization of speed limits (with respect to the total travel time). The computing time for a single simulation with the given discretization parameters is roughly one second on an Intel(R) Core(TM) i5-3340M CPU with 2.70GHz.
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>Figure 5: Optimal control of $v_{max}$ for an increasing number of control points.</figcaption></figure>
<table><caption>Table 2: Optimal travel times / outflows for different numbers of control points</caption><thead><tr><th>Nu</th><th>Δx / Δt</th><th>min. travel time</th><th>max. outflow</th></tr></thead><tbody><tr><td>-</td><td>50 / 0.5</td><td>2336.698921</td><td>1844.762416</td></tr><tr><td>5</td><td>50 / 0.5</td><td>2307.370375</td><td>1845.023309</td></tr><tr><td>10</td><td>50 / 0.5</td><td>2307.157634</td><td>1845.030866</td></tr><tr><td>20</td><td>50 / 0.5</td><td>2306.863796</td><td>1845.289234</td></tr><tr><td>40</td><td>50 / 0.5</td><td>2306.778537</td><td>1845.290014</td></tr><tr><td>80</td><td>50 / 0.5</td><td>2306.694086</td><td>1845.353672</td></tr></tbody></table>

<figure><img src="image_17.png" /><figcaption>Figure 6: Density on roadB2 with and without optimization of speed limits.</figcaption></figure>

In the second experiment we vary the discretization parameters and keep the number of control points constant for the minimization of the total travel time / maximization of the outflow. Table 3 and Figure 7 show the results for these computations. Note that the presented values of the objective function (scaled travel times / outflows) are evaluated using a simulation with the finest discretization parameters.

<table><caption>Table 3: Optimal travel times / outflows for different discretizations</caption><thead><tr><th>Nu</th><th>Δx (max.) / Δt</th><th>min. travel time</th><th>max. outflow</th></tr></thead><tbody><tr><td>-</td><td>-</td><td>2330.987519</td><td>1846.918574</td></tr><tr><td>20</td><td>200 / 0.500</td><td>2369.960626</td><td>1825.869588</td></tr><tr><td>20</td><td>100 / 0.500</td><td>2333.714043</td><td>1836.601771</td></tr><tr><td>20</td><td>50 / 0.500</td><td>2306.708163</td><td>1845.327369</td></tr><tr><td>20</td><td>25 / 0.250</td><td>2300.563136</td><td>1846.649973</td></tr><tr><td>20</td><td>12.5 / 0.125</td><td>2297.448274</td><td>1847.150023</td></tr></tbody></table>

Similar to above, the finer the discretization parameters are, the better the computed optimal solutions are. For the (too) coarse discretizations, one actually gets “optimal controls”, which are worse than the “no control” case (all speed limits at the upper bound). Note that this may only happen because we
<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /><figcaption>Figure 7: Optimal control of $v_{\text{max}}$ for different discretizations.</figcaption></figure>
<figure><img src="image_29.png" /><figcaption>Figure 8: Optimal control of $v_{max}$ with and without penalty term (min. travel time).</figcaption></figure>
finally evaluate the computed controls by a simulation using the finest grid.

The results of the third experiment are shown in Figure 8. Obviously, the additional penalty term, which penalizes variations in the control, leads to smoother optimal solutions.

## 4.2 VSL meets Coordinated Ramp Metering

In our second example, we consider the combined optimization of variable speed limits and ramp metering. The topology of the underlying network is shown in Figure 9 and the corresponding parameters are given in Table 4. The priority parameter at the on-ramp is $P = 0.5$ and we take $f^{max} = 1.5$. Figure 10 shows the inflow profiles and the maximum outflow. For the discretization we apply $\Delta t = 1.5$ and $\Delta x = 100$. A single simulation with these parameters takes about 2.3 seconds (for the considered time horizon of 3 hours). For the optimization we use $Nu = 36$ control points.

The objective for this scenario is to minimize the total travel time, i.e. $\gamma_e = 0$ in (17), subject to the following constraints: We allow a maximum size of the queue at the inflow of the main road (node “in”) of 50 cars and a maximum size of the queue at the on-ramp of 600 cars. Both constraints are violated without optimization ($v_{max}$ at the upper bound and $w(t) = 1$ at the on-ramp). Note that the gradients of these constraints, which are necessary for the applied SQP solver, are computed exactly in the same manner as the gradients of the objective (as described in Section 3.2).

<figure><img src="image_30.png" /><figcaption>Figure 9: Road network with an on-ramp at the node “on-ramp”.</figcaption></figure>

<table><caption>Table 4: Properties of the roads in Figure 9</caption><thead><tr><th>road</th><th>length</th><th>ρ<sub>max</sub></th><th>v<sub>low</sub></th><th>v<sub>high</sub></th><th>initial density</th></tr></thead><tbody><tr><td>road1a</td><td>2000</td><td>2</td><td>30</td><td>30</td><td>0.1</td></tr><tr><td>road1b</td><td>2000</td><td>2</td><td>10</td><td>30</td><td>0.1</td></tr><tr><td>road2</td><td>4000</td><td>2</td><td>30</td><td>30</td><td>0.1</td></tr></tbody></table>

Figure 11 shows the inflow to the main road from the on-ramp in the uncontrolled case, nicely validating the different situations that may occur at an on-ramp: Initially the full inflow goes to the main road ($f^{in} = 0.75$). Due to the congestion at road2, the inflow drops down to $P \cdot f^{out} = 0.5$ (outflow at the node “out” is 1.0 and priority parameter $P = 0.5$). When the maximum possible outflow at the node “out” increases, also the flow on the on-ramp increases up the maximum flow level ($f^{max} = 1.5$). When the queue at the on-ramp is empty, the inflow to the main road from the on-ramp decreases to the inflow at this node again ($f^{in} = 0.75$).

Finally, Figures 12 and 13 show the computed optimal control and the queue lengths at the inflow of the main road and at the on-ramp in the uncontrolled and the optimized cases.
<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /><figcaption>Figure 10: Inflow/max. outflow profiles for the network in Figure 9.</figcaption></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /><figcaption>Figure 11: Inflow on the main road at the on-ramp without optimization.</figcaption></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /><figcaption>Figure 12: Optimal control of $v_{\text{max}}$ on road1b and $w(t)$ at the on-ramp.</figcaption></figure>
<figure><img src="image_37.png" /><figcaption>Figure 13: Queue at the node “in” and the on-ramp with and without optimization.</figcaption></figure>

## 4.3 Real World Example: From Antibes to Nice

<figure><img src="image_38.png" /><figcaption>Figure 14: (Taken from [3].) A8 highway's scheme between Antibes and Nice St. Isidore. Blue spots indicate loop detectors' locations. Light blue lines indicate toll stations' locations. Black arrows indicate the direction of cars flow, where those on the bottom are on and off ramps. Highway's sections limited by green lines are those where the maximal speed limit is 110 km/h, while in the orange ones is 90 and in the red one is 70 km/h. Width is proportional to the number of lanes: 2, 3 or 4. For further details see [3].</figcaption></figure>

Numerical simulations performed in this section correspond to sections 1 to 4.

Inspired by the real network depicted in Figure 14, we consider a stretch of highway of 9 km long divided in cells of $\Delta x = 100$ m each as follows:

* a section of 5 km between $x_0 = 0$ km and $x_1 = 5$ km consisting of 3 lanes ($\rho_1^{\max} = 450$ cars/km) with maximal speed $v_1^{\max} = 110$ km/h;

* a section of 3 km between $x_1 = 5$ km and $x_2 = 8$ km consisting of 4 lanes ($\rho_2^{\max} = 600$ cars/km) with maximal speed $v_2^{\max} = 110$ km/h;

* a section of 1 km between $x_2 = 8$ km and $x_3 = 9$ km consisting of 3 lanes ($\rho_3^{\max} = 450$ cars/km) with maximal speed $v_3^{\max} = 90$ km/h.
Moreover, an on-ramp link is connected to the mainline at the node $x_1$ (with priority parameter $P = 0.25$). We know that traffic is hindered downstream, that is, we impose a maximum outflow at $x_3$. The inflow and maximum outflow values are given in Figure 15. The computing time for a single simulation with $\Delta t = 1.5$ seconds for a 5 hour time horizon is roughly 5 seconds.

<figure><img src="image_39.png" /><figcaption>Figure 15: Inflow/max. outflow profiles for considered network part of Figure 14.</figcaption></figure>

The speed limits $v_1^{\text{max}}$, $v_2^{\text{max}}$ and $v_3^{\text{max}}$ are imposed by the authorities. We are interested in comparing the current situation resulting from the above choice of the parameters with the controlled one. We use the current speed limits as upper bound for the speed controls and 50 km/h as lower bound for all roads.

The objective is again to minimize the total travel time subject to the following constraints:

* maximum size of the queue in Antibes: 120 cars,

* maximum size of the queue at the on-ramp: 50 cars.

Figure 16 shows the traffic density on the entire section at different times in the uncontrolled case. Due to the limited outflow, a traffic jam is building at (roughly) 7:15 (corresponding to $t = 1.25$ hours, first plot), almost arriving at $x_0$ at about 8:30 (third plot) and having vanished approximately further 2 hours later. Unfortunately, the optimization procedure is not able to (significantly) improve the total travel time for the given scenario. Nevertheless, by controlling the speed limits and the metering rate, we are able to find a solution fulfilling the constraints above while maintaining the total travel time. The optimal solution
found for the controls is plotted in Figure 17, the queues in the uncontrolled
and the optimized case are shown in Figure 18.

5 Conclusion

In this work we have considered variable speed limits combined with coordi-
nated ramp metering within the framework of the LWR network model. On one
hand, the first order LWR model can be considered the most simple PDE model
for traffic flow, which also allows for congestions. Nevertheless, the simulation
results for the real world example presented in Section 4.3 agreed well with the
observed real situation. To improve the current situation, we applied a first
discretize then optimize adjoint approach and sequential quadratic program-
ming. While the fulfillment of prescribed constraints was successful within this
framework, the optimization procedure was not able to (significantly) improve
the current situation in terms of total travel time. Probably, this is a drawback
of the applied first order model. This assumption is motivated by our results
in Section 4.2, since for similar scenarios as in [13], where a “discrete second
order model” but also a different model for the on-ramp flow are used, speed
control and coordinated ramp metering yield a significant improvement of the
total travel time. Accordingly, in future work we are going to extend the pre-
sented framework to a second order PDE model and also to consider different
models for the on-ramp flow.

Acknowledgments

This work was financially supported by the project "Transport network mod-
eling and analysis" co-funded by DAAD (Project-ID 57049018) and the PHC
Procope (Project no. 30715QA).

References

[1] G. BASTIN, B. HAUT, J.-M. CORON, AND B. D'ANDRÉA-NOVEL, *Lya-
punov stability analysis of networks of scalar conservation laws*, Netw. Het-
erog. Media, 2 (2007), pp. 751–759.

[2] G. BRETTI AND B. PICCOLI, *A tracking algorithm for car paths on road networks*, SIAM J. Appl. Dyn. Syst., 7 (2008), pp. 510–531.

[3] A. CABASSI AND P. GOATIN, *Validation of traffic flow models on processed GPS data*, Research Report RR-8382, 2013.

[4] G. M. COCLITE, M. GARAVELLO, AND B. PICCOLI, *Traffic flow on a road network*, SIAM Journal on Mathematical Analysis, 36 (2005), pp. 1862–1886.

[5] G. M. COCLITE AND N. H. RISEBRO, *Conservation laws with time dependent discontinuous coefficients*, SIAM J. Math. Anal., 36 (2005), pp. 1293–1309.
<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /><figcaption>Figure 16: Traffic density between Antibes and Nice at different times.</figcaption></figure>
<figure><img src="image_45.png" /><figcaption>Figure 17: Optimal control of $v_{max}$ on road1, road2 and road3, and $w(t)$ at the on-ramp.</figcaption></figure>

[6] A. CSIKOS, I. VARGA, AND K. M. HANGOS, *Freeway shockwave control using ramp metering and variable speed limits*, 21st Mediterranean Conference on Control & Automation, (2013), pp. 1569–1574.

[7] M. GARAVELLO AND B. PICCOLI, *Traffic flow on networks*, Springfield, MO: American Institute of Mathematical Sciences (AIMS), 2006.

[8] ——, *Conservation laws on complex networks*, Ann. Inst. Henri Poincaré, Anal. Non Linéaire, 26 (2009), pp. 1925–1951.

[9] M. GARAVELLO AND B. PICCOLI, *Time-varying Riemann solvers for conservation laws on networks*, J. Differential Equations, 247 (2009), pp. 447–464.

[10] M. B. GILES AND N. A. PIERCE, *An introduction to the adjoint approach to design*, Flow Turbul. Combust., 65 (2000), pp. 393–415.

[11] S. GÖTTLICH AND U. ZIEGLER, *Traffic light control: a case study*, Discrete Contin. Dyn. Syst., Ser. S, 7 (2014), pp. 483–501.

[12] M. GUGAT, M. HERTY, A. KLAR, AND G. LEUGERING, *Optimal control for traffic flow networks*, J. Optimization Theory Appl., 126 (2005), pp. 589–616.
<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /><figcaption>Figure 18: Queue at the node “in” and the on-ramp with and without optimization.</figcaption></figure>

[13] A. HEGYI, B. D. SCHUTTER, AND H. HELLENDOORN, *Model predictive control for optimal coordination of ramp metering and variable speed limits*, Transportation Research Part C, 13 (2005), pp. 185–209.

[14] A. HEGYI, B. D. SCHUTTER, AND J. HELLENDOORN, *Optimal coordination of variable speed limits to suppress shock waves*, IEEE Transactions on Intelligent Transportation Systems, 6 (2005), pp. 102–112.

[15] M. HERTY AND A. KLAR, *Modeling, simulation, and optimization of traffic flow networks*, SIAM Journal on Scientific Computing, 25 (2003), pp. 1066–1087.

[16] ——, *Simplified dynamics and optimization of large scale traffic networks*, Mathematical Models and Methods in Applied Sciences (M3AS), 14 (2004), pp. 579–601.

[17] H. HOLDEN AND N. H. RISEBRO, *A mathematical model of traffic flow on a network of unidirectional roads*, SIAM Journal on Mathematical Analysis, 26 (1995), pp. 999–1017.

[18] C. T. KELLEY, *Iterative methods for optimization*, Society for Industrial and Applied Mathematics, Philadelphia, 1999.

[19] O. KOLB, *Simulation and Optimization of Gas and Water Supply Networks*, PhD thesis, TU Darmstadt, 2011.

[20] O. KOLB AND J. LANG, *Mathematical optimization of water networks*, vol. 162 of Internat. Ser. Numer. Math., Birkhäuser/Springer Basel AG, 2012, ch. Simulation and continuous optimization, pp. 17–33.

[21] J. LEBACQUE AND M. KHOSHYARAN, *First order macroscopic traffic flow models for networks in the context of dynamic assignment*, in *Transportation Planning, M. Patriksson and M. Labb, eds.*, vol. 64 of Applied Optimization, Springer US, 2002, pp. 119–140.
[22] M. J. LIGHTHILL AND G. B. WHITHAM, *On Kinematic Waves. II. A Theory of Traffic Flow on Long Crowded Roads*, Royal Society of London Proceedings Series A, 229 (1955), pp. 317-345.

[23] A. MURALIDHARAN AND R. HOROWITZ, *Optimal control of freeway networks based on the Link Node Cell Transmission model*, American Control Conference, (2012), pp. 5769-5774.

[24] M. PAPAGEORGIOU, H. HADJ-SALEM, AND J.-M. BLOSSEVILLE, *ALINEA: A local feedback control law for on-ramp metering*, Transportation Research Record, 1320 (1991), pp. 58-64.

[25] J. REILLY, W. KRICHENE, M. L. D. MONACHE, S. SAMARANAYAKE, P. GOATIN, AND A. M. BAYEN, *Adjoint-based optimization on a network of discretized scalar conservation law pdes with applications to coordinated ramp metering*, submitted, (2014).

[26] P. RICHARDS, *Shock waves on the highway*, Operations research, 4 (1956), pp. 42-51.

[27] P. SPELLUCCI, *Numerische Verfahren der Nichtlinearen Optimierung*, Birkhäuser-Verlag, Basel, 1993.

[28] ——, *A new technique for inconsistent QP problems in the SQP method*, Mathematical Methods of Operations Research, 47 (1998), pp. 355-400.

[29] ——, *An SQP method for general nonlinear programs using only equality constrained subproblems*, Mathematical programming, 82 (1998), pp. 413-448.