arXiv:1803.00367v1 [cs.SY] 1 Mar 2018

A BENCHMARK PROBLEM IN TRANSPORTATION
NETWORKS
SAMUEL COOGAN AND MURAT ARCAK

Abstract. In this note, we propose a case study of freeway traffic flow modeled as a hybrid system. We describe two general classes of networks that model
flow along a freeway with merging onramps. The admission rate of traffic flow
from each onramp is metered via a control input. Both classes of networks
are easily scaled to accommodate arbitrary state dimension. The model is
discrete-time and possesses piecewise-affine dynamics. Moreover, we present
several control objectives that are especially relevant for traffic flow management. The proposed model is flexible and extensible and offers a benchmark
for evaluating tools and techniques developed for hybrid systems.

1. Introduction
Traffic flow theory has its foundations in the Lighthill-Whitham-Richards (LWR)
model, a first-order partial differential equation in the form of a conservation law
that models traffic flow on a single road [1, 2]. Originally motivated by the need to
efficiently simulate traffic flow, the cell transmission model was proposed as a finitedimensional approximation to the LWR model [3, 4]. However, the cell transmission
model has since been established as an appropriate model of traffic flow in its own
right [5, 6, 7], and recent research has focused on studying the dynamical properties
of this model [8, 9, 10].
The cell transmission model considers traffic networks as interconnected links or
compartments with finite capacity to store vehicles. Vehicles flow from link to link
over time, and thus the occupancy of a link is time-varying. The cell transmission
model adopts a fluid approximation of traffic flow so that occupancy is not restricted
to integer values. Flow of vehicles from an upstream link to a downstream link is
restricted by the demand of vehicles on the upstream link to flow downstream, and
the supply of capacity available on the downstream link to accept incoming flow.
These restrictions give rise to a hybrid model as the behavior is different in the
supply-restricted regime. For junctions with multiple incoming links or multiple
outgoing links, demand is divided among the outgoing links and supply is divided
among the incoming links, and a variety of specific models for this division has been
proposed in the literature; see the above-cited references.
In this note, we present a particular instantiation of the cell transmission model
especially amenable to analysis and control as a hybrid system. We limit our
attention to models where each junction has a single incoming link and at most
two outgoing links (diverging junction), or at most two incoming links and a single
S. Coogan is with the School of Electrical and Computer Engineering and the School of
Civil and Environmental Engineering at the Georgia Institute of Technology, Atlanta, GA.
sam.coogan@gatech.edu. M. Arcak is with the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA. arcak@eecs.berkeley.edu.
1

2

SAMUEL COOGAN AND MURAT ARCAK

outgoing link (merging junction), and the result is a piecewise-affine traffic flow
model.
The purpose of this note is to distill existing traffic models into a simple but
extensible model of traffic flow and offer it as a practically motivated case study
in need of computationally efficient and scalable tools for control verification and
synthesis. The model presented here agrees with the various models presented in
the literature and cited above and illuminates the fundamental challenges.
The note is organized as follows. In Section 2, we present models for traffic flow
at merging and diverging junctions. These simple models can be interconnected
to create traffic networks with arbitrary topology. In Section 3, we suggest two
particular classes of network topologies and provide detailed models for both. In
Section 4, we present several control objectives for these two classes of networks
which are especially relevant for traffic networks. In Section 5, we identify several
properties of the traffic flow model and make connections to existing results in the
literature. Section 6 contains concluding remarks.
2. Traffic Flow at Junctions
We begin by discussing the two elemental traffic flow models: the merging junction where two traffic links merge to one downstream link as in Figure 1(a), and
the diverging junction where one link diverges to two downstream links as in Figure
1(b). These two junction models capture the essential dynamics exhibited by traffic
flow networks. In Section 3, we combine these models and propose two benchmark
network topologies. While this note considers networks with only merging nodes
and diverging nodes, the model is easily extended to accommodate nodes with
multiple incoming and outgoing links [11].
Let xi [t] denote the number of vehicles on link i at time t, that is, xi is the
occupancy of link i. We adopt a macroscopic modeling approach and assume that
xi [t] takes continuous values. The state of a traffic flow network is the collection of
link occupancies in the network so that, for the merging and the diverging junctions,
T
x[t] = x1 [t] x2 [t] x3 [t] is the system state.
The flow of traffic from link to link through merging and diverging junctions is
a function of the number of vehicles on a link wishing to flow downstream, which is
called the demand of the link, the available downstream road space to accommodate
these vehicles, which is called the supply of the link, and possibly a control input,
which is discussed below. Link demand is an increasing function in the number
of vehicles on the link, and the link supply is a decreasing function in the number
of vehicles on the link. In the transportation literature, the demand and supply
functions are referred to as the fundamental diagram relating link occupancy to
flow.
A common approach is to adopt a triangular fundamental diagram so that the
demand and supply functions are affine in xi with the additional restriction that the
demand saturates at some maximum value. Thus we model the demand function
D(x) and the supply function S(x) as
D(x) = min{c, vx}

(1)

S(x) = w(x̄ − x)

(2)

where c is the capacity, v is the free-flow speed, w is the congestion-wave speed, and
x̄ is the jam occupancy of a link [6]. Standard values for these parameters are given

A BENCHMARK PROBLEM IN TRANSPORTATION NETWORKS

Paramter
Link length
Period
c
v
w
x̄
β
α
ᾱ
Table 1.

3

Value Units
1
mile
0.5
min
40
veh/period
0.5
links/period
0.5/3 links/period
320
vehicles
0.75
—
1
—
5
—
Parameter values

in Table 1, which are appropriate for links modeling two lanes of traffic, with each
link one mile long, and a time step of 30 seconds [6].
We remark that it is common to consider different parameters for different links
to accommodate, e.g., varying road geometry, varying link lengths, etc. For notational convenience and to establish a consistent model, we assume all parameters
take the values shown in Table 1 for all links.
In traffic networks, link flow may be artificially restricted, or metered, via traffic
signaling devices, and, in this note, metering is considered to be the only available
control input. For example, metering is commonly encountered on freeway onramps
to control admittance to the freeway. In particular, if a link is metered via control
input u, then the traffic flow that exits the link cannot exceed u[t] at time t.
The fundamental rule governing the dynamics of traffic networks is that the flow
exiting a link should not exceed the link’s demand, nor the link’s metering rate if
the link is controlled, and it should also not exceed downstream supply. Thus, for
a junction consisting of one incoming link, labeled link 1, and one outgoing link,
labeled link 2, the state equations are
x1 [t + 1] = x1 [t] − min{D(x1 [t]), S(x2 [t])} + d[t],

(3)

x2 [t + 1] = x2 [t] + min{D(x1 [t]), S(x2 [t])} − D(x2 [t]),

(4)

where xi [t] is the state, i.e., occupancy, of link i ∈ {1, 2} at time t, d[t] is the
number of vehicles arriving on link 1 from upstream. We assume there are no links
downstream of link 2 so that the flow exiting link 2 is equal to demand.
We now extend this rule in a natural way for the merging junction and the
diverging junction shown in Figure 1.
2.1. Merge Junction. At the merging junction show in Figure 1(a), links 1 and
2 flow downstream to link 3. In this note, merging junctions are interpreted as
modeling a freeway entrance ramp that joins a freeway, and thus links 1 and 3
are the freeway and link 2 is the onramp. Link 2 is metered via control input u.
Let d1 [t] and d2 [t] be the exogenous, uncontrolled arrival of vehicles to links 1 and
2, respectively. A fraction β ≤ 1 of vehicles exiting link 1 join link 3, and the
remaining 1 − β fraction are assumed to exit the network via an unmodeled exit
link. All vehicles flowing from the onramp link 2 join link 3.
Moreover, it is assumed that the supply of link 3 available to link 1 (respectively,
link 2) is determined by a fixed weight α > 0 (respectively, ᾱ > 0). The values for
β, α, and ᾱ used in this note are reported in Table 1.

4

SAMUEL COOGAN AND MURAT ARCAK

2
1

1
3

2

3
(a)

(b)

Figure 1. (a) At a merging junction, traffic flow from two incoming links merge and flow downstream to an outgoing link. It
is common for one of the incoming links (dashed) to model an
onramp for which the rate of traffic flow can be controlled using
signaling devices, thus providing a control input to the system.
(b) At a diverging junction, traffic flows from one incoming link to
two outgoing links. Diverging junctions exhibit the first-in-firstout property whereby congestion (lack of supply) on one outgoing
link reduces flow to the other outgoing link.

The state-update equations for the merge junction are given by


α
x1 [t + 1] = x1 [t] − min D(x1 [t]), S(x3 [t]) + d1 [t],
β
x2 [t + 1] = x2 [t] − min {D(x2 [t]), ᾱS(x3 [t]), u[t]} + d2 [t],


(5)
(6)

x3 [t + 1] = x3 [t] − D(x3 [t]) + min {βD(x1 [t]), αS(x3 [t])}
+ min {D(x2 [t]), ᾱS(x3 [t]), u[t]} .

(7)

Remark 1. Note that w1 S(xi [t]) = (x̄ − xi [t]) is the available space on link i
at time t so that we interpret wα (respectively, wᾱ) as the fraction of this space
available to link 1 (respectively, link 2). Thus, occupancy will not exceed x̄ so long
as wα + wᾱ ≤ 1, which holds for the values in Table 1. The model is referred to as
an asymmetrical cell transmission model since ᾱ > 1 and therefore flow from link
2 may exceed supply [5, 6].
2.2. Diverge Junction. A diverge junction models the division of flow from one
incoming link to two outgoing links. We assume that the outgoing flow of link 1 in
Figure 1(b) divides evenly among the outgoing links 2 and 3. We do not assume
any of the links in the diverging junction are metered.
Diverging junctions in traffic flow networks have been empirically observed to
obey a first-in-first-out (FIFO) property whereby congestion on one outgoing link
restricts flow to the other outgoing link, that is, lack of supply on link 2 restricts flow
to link 3 and vice-versa. The intuition for this phenomenon is that traffic waiting to
move downstream to link 2 blocks traffic destined for link 3, even though link 3 has
adequate supply. This intuition has been empirically observed to extend to traffic
flow on multi-lane freeways [12]. In the present model, we assume a full FIFO
property whereby complete congestion on one outgoing link completely restricts
flow to other outgoing links. This is a common assumption in transportation flow
models and can be relaxed to obtain partial FIFO models [13].

A BENCHMARK PROBLEM IN TRANSPORTATION NETWORKS

5



α
(11)
x1 [t + 1] = x1 [t] − min D(x1 [t]), S(x2 [t]) + d1 [t],
β
xN [t + 1] =xN [t] − D(xN [t]) + min {βD(xN −1 [t]), αS(xN [t])}

+ min D(x(N −1)′ [t]), ᾱS(xN [t]), u(N −1)′ [t] ,
(12)


α
xi [t + 1] =xi [t] − min D(xi [t]), S(xi+1 [t]) + min {βD(xi−1 [t]), αS(xi [t])}
β

+ min D(x(i−1)′ [t]), ᾱS(xi [t]), u(i−1)′ [t]
for i = 2, . . . , N − 1,
(13)
xi′ [t + 1] =xi′ [t] − min {D(xi′ [t]), ᾱS(xi+1 [t]), ui′ [t]} + di′ [t]
for i′ = 1′ , . . . , (N − 1)′ .

(14)

Figure 2. State-update equations for the simple freeway.
1
1′

2
2′

3
3′

4
4′

···

N

(N − 1)′

Figure 3. A simple freeway network consists of only merging
junctions and models a length of freeway with onramps. The
length-N simple freeway consists of (2N − 1) links, (N − 1) of
which model onramps and thus possess control inputs. Therefore,
the state dimension of the network is (2N − 1), and the input
dimension is (N − 1).
The state-update equations for the diverge junction are given by
x1 [t + 1] = x1 [t] − min {D(x1 [t]), 2S(x2 [t]), 2S(x3 [t])} + d1 [t],

(8)

x2 [t + 1] = x2 [t] + min {0.5D(x1 [t]), S(x2 [t]), S(x3 [t])} − D(x2 [t]),

(9)

x3 [t + 1] = x3 [t] + min {0.5D(x1 [t]), S(x2 [t]), S3 (x[t])} − D(x3 [t]).

(10)

3. Two Network Topologies
We now use the merge and diverge junction models presented in Section 2 as
building blocks to construct two classes of traffic networks. These two classes
provide an extensible benchmark problem for analysis and control of hybrid systems.
3.1. Simple Freeway Network. The first class of benchmark networks consists
of only merging junctions and models a length of freeway with onramps. This class
of network topologies is commonly encountered in studies of ramp metering for
freeways [5, 6, 14]. Given parameter N , the length-N simple freeway is composed
of 2N − 1 freeway links, N − 1 of which model onramps and thus possess control
inputs, as shown in Figure 3. The state dimension of the network is (2N − 1) and
the input dimension is (N − 1).
The state-update equations for the length-N simple freeway are given in Figure
2.

6

SAMUEL COOGAN AND MURAT ARCAK



α
x(−M) [t + 1] = x(−M) [t] − min D(x(−M) [t]), S(x(−M+1) [t]) + d(−M) [t],
β
x0 [t + 1] = x0 [t] − min {D(x0 [t]), 2S(x1 [t]), 2S(xN +1 [t])}

(15)

+ min {βD(x−1 [t]), αS(x0 [t])}
(16)
+ min {D(x−1′ [t]), ᾱS(x0 [t]), u−1′ [t]} ,


α
xi [t + 1] = xi [t] − min D(xi [t]), S(xi+1 [t])
β
+ min {0.5D(x0 [t]), S(x1 [t]), S(xN +1 [t])} for i = 1, N + 1,
(17)


α
xi [t + 1] = xi [t] − min D(xi [t]), S(xi+1 [t]) + min {βD(xi−1 [t]), αS(xi [t])}
β

+ min D(x(i−1)′ [t]), ᾱS(xi [t]), u(i−1)′ [t]
for i = −M + 1, . . . , −1, 2, . . . , N − 1, N + 2, . . . , 2N − 1, (18)

xi [t + 1] = xi [t + 1] + min {βD(xi−1 [t]), αS(xi [t])}

+ min D(x(i−1)′ [t]), ᾱS(xi [t]), u(i−1)′ [t] − D(xi [t])
for i = N, 2N

(19)

xi′ [t + 1] = xi′ [t] − min {D(xi′ [t]), ᾱS(xi+1 [t]), ui′ [t]} + di′ [t]
for i′ = −M ′ , . . . , −1′ , 1′ , 2′ , . . . , (N − 1)′ ,
(N + 1)′ , . . . , (2N − 1)′ .

(20)

Figure 4. State-update equations for the length-(M, N ) diverging freeway.
Remark 2. The simple freeway model may be modified to arrive at various alternative configurations. For example, for fixed N , the number of states and inputs
may be reduced by eliminating some onramps from the model.
3.2. Diverging Freeway Network. The second class of benchmark networks
models a freeway that diverges into two freeways. Given parameters M and N , the
length-(M, N ) diverging freeway is composed of 2M + 4N − 1 links, M + 2(N − 1)
of which model onramps and thus possess control inputs, as shown in Figure 5.
The state-update equations for the length-N diverging freeway are given in Figure 4.
Remark 3. As with the previous benchmark network, the diverging freeway model
may be easily modified by eliminating onramps, which reduces the number of states
and inputs of the model.
Remark 4. The incoming flows to the onramps and to the first link of the network
( i.e., link 1 for the simple freeway and link −M for the diverging freeway) are not
subject to supply restrictions. The motivation for doing so is that the model is able
to accommodate arbitrary exogenous flows as discussed in Section 3.3.
3.3. Exogenous Inputs. For the simple freeway model, let

d[t] = d1 [t], d1′ [t], d2′ [t], . . . , d(N −1)′ [t] ∈ RN ,

(21)

A BENCHMARK PROBLEM IN TRANSPORTATION NETWORKS

1′
1
−M

···

−M ′

2′
2

7

(N−1)′

···

N

0

−1′

N +1
(N+1)′

N +2
(N+2)′

···

2N

(2N−1)′

Figure 5. A diverging freeway network models a freeway that
diverges to two freeways. The length-(M, N ) diverging freeway is
composed of 2M + 4N − 1 links, M + 2(N − 1) of which model
onramps and thus possess control inputs.
and, for the diverging freeway model, let
d[t] = (d(−M) [t], d(−M)′ [t], d(−M+1)′ , . . . , d(−1)′ ,
d1′ [t], . . . , d(N −1)′ [t], d(N +1)′ [t], . . . , d(2N −1)′ [t])
∈ RM+2N −1

(22)

so that d[t] is the vector of exogenous flows into the network at time t. Similarly,
for the simple freeway, let

(23)
u[t] = u1′ [t], u2′ [t], . . . , u(N −1)′ [t] ∈ RN −1
and, for the diverging freeway, let

u[t] = (u(−M ′ ) [t], . . . , u(−1)′ , u1′ [t], . . . , u(N −1)′ [t],
u(N +1)′ [t], . . . , u(2N −1)′ [t])

∈ RM+2(N −1)

(24)

so that u[t] is the vector of inputs for the network at time t. Furthermore, let
(
2N − 1
for the simple freeway,
n=
(25)
2M + 4N − 1 for the diverging freeway,
(
N −1
for the simple freeway,
m=
(26)
M + 2(N − 1) for the diverging freeway,
(
N
for the simple freeway,
q=
(27)
M + 2N − 1 for the diverging freeway
be the state, input, and disturbance dimensions, respectively.
We say that the sequence d[t] for t ≥ 0 is feasible if there exists a sequence u[t]
for t ≥ 0 such that, for some constant C > 0, xi [t] < C for all t ≥ 0 and for
all i ranging over the indices of links in the network. The sequence d[t] is said
to be infeasible otherwise. In other words, the sequence d[t] is feasible if there
exists a control sequence that fully accommodates the exogenous incoming flow.
It is straightforward to show that if xi [0] ≤ x̄, then xi [t] ≤ x̄ for all t ≥ 0 for
any link with an upstream link (i.e., i ∈ {2, 3, . . . , N } for the simple freeway or
i ∈ {−M + 1, −M + 2, . . . , 2N } for the diverging freeway). Thus traffic may only
accumulate at onramps or the first link of the network (i.e., link 1 for the simple

8

SAMUEL COOGAN AND MURAT ARCAK

freeway and link −M for the diverging freeway), and therefore these are the only
links for which it may not be possible to find C satisfying xi [t] < C for all t ≥ 0.
Infeasible exogenous flows are useful for modeling situations in which the freeway
network has inadequate capacity, such as during rush hour periods when a large
influx of vehicles arrives at the network. Of course, in actual traffic networks, such
periods do not last indefinitely, but it may nonetheless be valuable to model such
scenarios using an infinite time horizon to provide insights into, e.g., equilibrium
conditions that may arise for extended periods of time [6].
For example, [6] suggests exogenous flows that are infeasible but on the cusp of
feasibility. Specifically, for the simple freeway network, such a choice is
d1 [t] = 40 ∀t
di [t] = 10 + ǫi

(28)
∀t,

′

′

′

i ∈ {1 , 2 , . . . , (N − 1) }.

(29)

When ǫi = 0 for all i, the demand is feasible and the outgoing flow for link i ∈
{1, 2, . . . , N } is 40 vehicles per period at equilibrium. Of these, 30 = β40 advance
downstream to link i + 1, joined by 10 additional vehicles from link i′ . However, the
flow is infeasible when ǫi > 0 for some i since the outgoing flow of link i + 1 cannot
exceed c = 40 vehicles per period. In the case of infeasible flows, it has been shown
that ramp metering can increase throughput of the network [6]. Similar choices
for exogenous flow can be made for the diverging freeway network. Moreover,
it is suggested in [15] to model the exogenous flow as belonging to a set, e.g.,
di [t] ∈ [10 − δi , 10 + δi ] for some δi > 0 for all i ∈ {1′ , 2′ , . . . , (N − 1)′ }.
4. Performance Specifications
We now suggest several performance metrics that are natural for traffic networks.
Total Travel Time
The total travel time (TTT) of the network up to time T is defined as
TTT[T ] =

T X
X
t=0

xi [t]

(30)

i

where i is assumed to vary over all state indices of the network. Total travel time is
a useful metric when considering finite time horizons for which we seek to minimize
the total travel time at the end of the horizon.
Throughput
Another common performance metric is throughput at time t, denoted W [t], and
defined as
 X

X
α
D(xi [t])
(31)
W [t] =
(1 − β) min D(xi [t]), S(xi+1 [t]) +
β
i∈F

i∈E

where



for the simple freeway,
{1, 2, . . . , N − 1}
F = {−M, −M + 1, . . . , −1, 1, 2, N − 1, N + 1, . . . , 2N − 1}


for the diverging freeway,
(
{N }
for the simple freeway,
E=
{N, 2N } for the diverging freeway.

(32)

(33)

A BENCHMARK PROBLEM IN TRANSPORTATION NETWORKS

9

Throughput is a measure of the number of vehicles that exit the network in a given
time step, and total throughput over a horizon T is
J[T ] =

T
X

W [t].

(34)

t=0

Throughput is a useful metric in cases when the exogenous flow is infeasible or the
time horizon is infinite, in which case a discounted or average reward function may
be defined as
∞
T
X
1 X
J=
γ t W [t] or J = lim sup
W [t],
(35)
T →∞ T t=0
t=0
where γ < 1 is a discount factor. Alternatively we may require, for example, that
throughput remain above a given threshold for all time.
Congestion
Notice that D(xcrit ) = S(xcrit ) for


c wx̄
= 80
xcrit = max x̄ − ,
w v+w

(36)

where the second equality is valid for the values reported in Table 1. Link i is said
to be congested if xi > xcrit .
A third possible performance specification for the system is that xi ≤ xcrit for
all i. Motivated by specifications expressible in temporal logic [16, 17], we may
require that this conditions holds for all time, or eventually at some time in the
future and forever thereafter, or at infinitely many time instants in the future, etc.
For example, it is possible to characterize a degree of robustness for the system by
considering these various possibilities [18].
5. Discussion
We now point to some important properties of the traffic model proposed in
this note. First, we note that the arguments of the minimization functions that
appear in (1), (5)–(7), and (8)–(10) are all affine so that the model is piecewise
affine (PWA), that is, there exists a partition P1 , . . . , PM of Rn and collections of
n×n
n×m
matrices {Ai }M
and {Bi }M
such that
i=1 ⊂ R
i=1 ⊂ R
x[t + 1] = Ai x[t] + Bi u[t] + Ed[t]

(37)

whenever x[t] ∈ Pi , that is, the system dynamics are affine in each region of the
partition. The matrix E ∈ {0, 1}n×q is a binary matrix with no more than one
nonzero entry per row whose role is to ensure that the disturbance vector conforms
with the state vector appropriately.
Since the model is piecewise affine, it is, in principle, amenable to tools such
as model predictive control [19] and synthesis for linear temporal logic (LTL) objectives [20] which have been specialized to PWA systems. The latter approach is
considered in [11] to meet LTL specifications.
Next, it has been shown in [6, 8, 9] that traffic networks with only merging junctions are monotone dynamical systems for which trajectories maintain a partial
order on states [21, 22]. Moreover, general traffic networks with diverging junctions
possess dynamics that are mixed monotone [13], a generalization of monotone systems [23]. For such systems, reachable sets are over-approximated by evaluating a

10

SAMUEL COOGAN AND MURAT ARCAK

certain decomposition function, derived from the dynamics, at only two extremal
points, regardless of the state-space dimension. Thus, such systems are amenable
to efficient finite abstraction [24], a typical requisite for applying formal methods
techniques to control systems [25]. This efficiency is exploited in [15] to synthesize
control strategies for traffic networks. Additionally, it is shown in [26] that monotone systems are especially amenable to classes of temporal logic specifications that
encourage lower occupancies.
Moreover, the sparse interconnection structure of many traffic networks suggest
compositional techniques for further aiding scalability [27]. Finally, some works
have suggested that scalability can be improved by avoiding discretization of the
state space; in particular, [28] proposes computing abstraction based on sequences
of applied control inputs, and this approach is applied to a traffic flow model similar
to that presented here. Nonetheless, these formal approaches are only applicable
to relatively small networks (up to approximately 10 state dimensions).
6. Conclusions
We have presented a general, hybrid model of traffic flow in vehicular transportation networks and suggested two simple classes of networks that encompass
realistic scenarios. Both classes are easily scaled to allow networks of arbitrary size.
We have further characterized several performance metrics that are practically motivated and fit well into optimization or formal methods frameworks. Traffic flow
models have already proven to be effective case studies for new tools in hybrid systems, and it is our hope that the transportation network model detailed in this note
may offer a practical and extensible benchmark problem for applying new tools and
techniques for hybrid systems.
7. Acknowledgments
Research funded in part by the National Science Foundation under grant 1446145.
References
[1] M. J. Lighthill and G. B. Whitham, “On kinematic waves II. A theory of traffic flow on long
crowded roads,” Proceedings of the Royal Society of London. Series A. Mathematical and
Physical Sciences, vol. 229, no. 1178, pp. 317–345, 1955.
[2] P. I. Richards, “Shock waves on the highway,” Operations research, vol. 4, no. 1, pp. 42–51,
1956.
[3] C. F. Daganzo, “The cell transmission model, part II: Network traffic,” Transportation Research Part B: Methodological, vol. 29, no. 2, pp. 79–93, 1995.
[4] J. Lebacque, “The Godunov scheme and what it means for first order traffic flow models,”
in International symposium on transportation and traffic theory, pp. 647–677, 1996.
[5] G. Gomes and R. Horowitz, “Optimal freeway ramp metering using the asymmetric cell
transmission model,” Transportation Research Part C: Emerging Technologies, vol. 14, no. 4,
pp. 244–262, 2006.
[6] G. Gomes, R. Horowitz, A. A. Kurzhanskiy, P. Varaiya, and J. Kwon, “Behavior of the cell
transmission model and effectiveness of ramp metering,” Transportation Research Part C:
Emerging Technologies, vol. 16, no. 4, pp. 485–513, 2008.
[7] A. A. Kurzhanskiy and P. Varaiya, “Active traffic management on road networks: A macroscopic approach,” Philosophical Transactions of the Royal Society A: Mathematical, Physical
and Engineering Sciences, vol. 368, no. 1928, pp. 4607–4626, 2010.
[8] S. Coogan and M. Arcak, “A compartmental model for traffic networks and its dynamical
behavior,” IEEE Transactions on Automatic Control, vol. 60, no. 10, pp. 2698–2703, 2015.

A BENCHMARK PROBLEM IN TRANSPORTATION NETWORKS

11

[9] E. Lovisari, G. Como, A. Rantzer, and K. Savla, “Stability analysis and control synthesis for
dynamical transportation networks,” arXiv:1410.5956, 2014.
[10] M. Wright, R. Horowitz, and A. A. Kurzhanskiy, “A dynamic system characterization of
road network node models,” in IFAC Symposium on Nonlinear Control Systems, NOLCOS,
pp. 1072–1077, 2016.
[11] S. Coogan and M. Arcak, “Freeway traffic control from linear temporal logic specifications,”
in Proceedings of the 5th ACM/IEEE International Conference on Cyber-Physical Systems,
pp. 36–47, 2014.
[12] J. C. Munoz and C. F. Daganzo, “The bottleneck mechanism of a freeway diverge,” Transportation Research Part A: Policy and Practice, vol. 36, no. 6, pp. 483–505, 2002.
[13] S. Coogan, M. Arcak, and A. A. Kurzhanskiy, “Mixed monotonicity of partial first-in-first-out
traffic flow models,” in IEEE Conference on Decision and Control, pp. 7611–7616, 2016.
[14] J. Reilly, S. Samaranayake, M. L. Delle Monache, W. Krichene, P. Goatin, and A. M. Bayen,
“Adjoint-based optimization on a network of discretized scalar conservation laws with applications to coordinated ramp metering,” Journal of optimization theory and applications,
vol. 167, no. 2, pp. 733–760, 2015.
[15] S. Coogan, E. A. Gol, M. Arcak, and C. Belta, “Traffic network control from temporal logic
specifications,” IEEE Transactions on Control of Network Systems, vol. 3, pp. 162–172, June
2016.
[16] A. Pnueli, “The temporal logic of programs,” in 18th Annual Symposium on Foundations of
Computer Science, pp. 46–57, IEEE, 1977.
[17] C. Baier and J. Katoen, Principles of Model Checking. MIT Press, 2008.
[18] P. Tabuada and D. Neider, “Robust linear temporal logic,” arXiv preprint arXiv:1510.08970,
2015.
[19] F. Borrelli, Constrained optimal control of linear and hybrid systems, vol. 290. Springer,
2003.
[20] B. Yordanov, J. Tůmová, I. Černá, J. Barnat, and C. Belta, “Temporal logic control of
discrete-time piecewise affine systems,” IEEE Transactions on Automatic Control, vol. 57,
no. 6, pp. 1491–1504, 2012.
[21] M. Hirsch and H. Smith, “Monotone dynamical systems,” Handbook of differential equations:
Ordinary differential equations, vol. 2, pp. 239–357, 2005.
[22] D. Angeli and E. Sontag, “Monotone control systems,” IEEE Transactions on Automatic
Control, vol. 48, no. 10, pp. 1684–1698, 2003.
[23] H. Smith, “Global stability for mixed monotone systems,” Journal of Difference Equations
and Applications, vol. 14, no. 10-11, pp. 1159–1164, 2008.
[24] S. Coogan and M. Arcak, “Efficient finite abstraction of mixed monotone systems,” in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control,
pp. 58–67, 2015.
[25] P. Tabuada, Verification and control of hybrid systems: A symbolic approach. Springer, 2009.
[26] E. S. Kim, M. Arcak, and S. Seshia, “Directed specifications and assumption mining for
monotone dynamical systems,” in ACM Conference on Hybrid Systems: Computation and
Control, 2016.
[27] E. S. Kim, M. Arcak, and S. A. Seshia, “Compositional controller synthesis for vehicular
traffic networks,” in IEEE Conference on Decision and Control, pp. 6165–6171, 2015.
[28] E. Le Corronc, A. Girard, and G. Goessler, “Mode sequences as symbolic states in abstractions
of incrementally stable switched systems,” in Proceedings of the 52nd IEEE Conference on
Decision and Control, pp. 3225–3230, 2013.

