Modelling and Optimization of Traffic Flows on Networks

2limited capacity. This congestion determines queueing phenomena and
thus delay and, in the worst case, a wrongful use of the available infras-
tructures with reduced safety for drivers and increased environmental
pollution.
The aim of this Thesis is to present an optimization study of macro-
scopic models for traffic on a network, with applications to roads and
telecommunications. These models are based on conservation laws,
which are special partial differential equations, where the variable is a
conserved quantity, i.e. a quantity which can neither be created nor
destroyed.
Classically, the network models are assumed to be static, but these
models do not allow a complete simulation of congested networks. For
this reason, traffic engineers have been analyzing dynamic traffic as-
signment or within-day models, thus rendering necessary the use of
time advancing mathematical models. In the 1950s James Lightill and
Gerald Whitham, and independently P. Richards used the equations
describing the flow of water to describe the flow of car traffic. The
basic idea is to look at large scales so to consider cars as small particles
and to assume the conservation of the density as the number of cars.
The main advantages of the present approach, with respect to existing
ones, are the following:
• The fluid-dynamic models are completely evolutive, thus they are
able to describe the traffic situation of a network every instant of
time. This overcomes the difficulties encountered by many static
models.
• An accurate description of queues formation and evolution on the
network is possible.
• The theory permits the development of efficient numerical schemes
also for very large networks. This is possible since traffic at junc-
tions is modelled in a simple and computationally convenient way
(resorting to a linear programming problem).
A recurring phenomenon in fluid-dynamics is the formation of dis-
continuity surfaces, such as shock waves and rarefaction, through which
fluid’s properties as pressure, density and velocity change extremely
rapidly. Study of that surfaces’ dynamics has a long history, and a
major contribution was made by Riemann who analyzed, more than
3one hundred years ago, what happens to an ideal fluid that has, at
a starting time, planar discontinuities in fluid variables. This prob-
lem, known since then as the Riemann problem, provides four different
solutions, each corresponding to combinations of how shocks and rar-
efaction waves can propagate in opposite directions inside unperturbed
fluid. The solution to the classic Riemann problem was formulated in
Newtonian physics, and therefore it is valid for flows with low speed
when compared with speed of light in vacuum. When speeds fluid
reach very high values solution of the Riemann problem needs of the
Einstein’s relativity theory.
The attention of physicists and mathematicians for nontrivial phe-
nomena in highways traffic produced a wealth of models, among which
fluid-dynamic ones. The latter were mostly obtained starting from the
LWR model. The main aim is to reproduce some behaviour as: syn-
cronized flows, wide jams, relaxation times to equilibrium velocities,
etc. [31]. The typical features required to observe such phenomena
are those of highways: long and straight streets, high speeds (or big
differences in velocities), no flux interruption as traffic light or yielding
signs, etc.
The situation of urban traffic is quite opposite: short road seg-
ments, many flux interruptions, reduced speeds, intricate road net-
works, and so on. Classically, engineers used static models to capture
some features, but the latter were not able to capture the main issue of
urban traffic: queue formation and backward propagation. Thus, var-
ious within day models were considered and, only recently, the LWR
equation was completed with junction traffic assignments so to deal
with real networks. The obtained approach perfectly reproduces the
main issue of queue formation and backward propagation. Surprisingly
enough, more mathematically reach systems do not necessarily achieve
the same goal. Take, for instance, the celebrated AW - Rascle model
(which firstly solved the issue of backward travelling cars indicating by
Daganzo). In Eulerian coordinates, an invariant region can be found
prescribing the velocity bounds 0 ≤ v ≤ vmax (ρ), where ρ is the den-
sity, v the average velocity and vmax a suitable maximal velocity. If
we take constant initial data in such region on a road and put a traffic
light at the end, with red light, then cars would stop but not neces-
sarily reach the maximal density (this can be easily observed looking
at the reachable points with negative velocity waves, see [19], Chapter
46 and, specifically, Proposition 6.2.1 for details). Similar drawbacks
can be found for all models of two equation with relaxation or diffusive
terms added (since those do not affect much with the boundary value
problem solutions).
For the urban setting, the simple LWR model is sufficient to de-
scribe most of the important traffic behavior features and it is the only
one for which a fairly complete theory and numerics are available. In
this context, optimization problems were addressed: [23] is devoted to
traffic light regulation, while the work of [22], [24] is more related to our
analysis but focuses on the case of smooth solutions (not developing
shocks) and boundary control.
The model we considered in order to optimize the traffic parameters
is developed in [13]. Road networks consist of a finite set of roads, that
meet at some junctions. Junctions play a key role, as the system at
a junction is under-determined even after imposing the conservation
of cars. In order to uniquely solve the Riemann problem at junctions
(the problem with constant initial data on each road), the following
assumptions are made (as in [13]):
• the incoming traffic distributes to outgoing roads according to
fixed (statistical) distribution coefficients;
• drivers behave in order to maximize the through flux.
Such choice permits to solve uniquely Riemann problems at junctions
and to construct solutions via wave-front tracking (see [4, 19].) More
precisely, if the number of incoming roads is greater than that of out-
going roads, one has also to introduce some right of way parameters.
Once fixed the model for traffic on networks, we define three cost
functionals to measure the traffic behaviour. The first functional J1
measures the average velocity of drivers on the network, the second J2
measures the expected mean travelling time on the network and finally
the third J3 is the total flux though the network. The optimization
is done over the right of way parameters and the traffic distribution
coefficients.
The analysis of the performances of the network through these func-
tionals is a very delicate problem, since it is impossible a complete
mathematical study of a complex network, especially in particular con-
ditions, such as congested roads. For this reason, one prefers to com-
pute the asymptotic optimal algorithm for single junction networks;
5then, you can use such algorithm in a local way for every junction of
the network to analyze.
The optimization algorithm is able to operate a redirection of car
traffic so as not to make traffic conditions very heavy.
Ideas coming from classical fluid-dynamic approaches to describe
car traffic have been extended to treat data flows on telecommunica-
tions networks.
There exist various approaches to traffic flow on telecommunication
networks, especially for the Internet. A general discussion of the many
different Internet layers and modelling approaches can be found in [1].
Many papers focus on properties of control congestion algorithms as
TCP/IP, see for example [2, 26, 29, 38]. The idea is rather to look at the
physical layer and take a large number of nodes, which use some simple
routing algorithm. Via some limiting procedure, a partial differential
equation for the packet density on the network is obtained, with control
acting at nodes for the traffic distribution policy. A telecommunication
network is formed by a finite collection of transmission lines and nodes
(or routers). Assuming that each node receives and sends information
encoded in packets, each packet can thus be seen as a particle on the
network. Having in mind Internet as key model, it is assumed that:
1) Each packet travels on the network with a fixed speed and with
assigned final destination;
2) Nodes receive, process and then forward packets. Packets may
be lost with a probability increasing with the number of packets
to be processed. Each lost packet is sent again.
The behavior of a single straight transmission line on which there
are some consecutive nodes is modelled. Each node sends packets to
the following one a first time, then packets which are lost in this process
are sent a second time and so on, until they reach next node. Thus,
looking at macroscopic level, it is assumed that packets are conserved.
This leads for the microscopic dynamics to the simple model consisting
of a single conservation law:
ρt + f (ρ)x = 0, (0.0.1)
where ρ is the packet density, v is the velocity and f(ρ) = vρ is the flux.
Assigning a loss probability as function of the density, it is possible
6to derive an average transmission function and thus a flux function.
The conclusion is rigorously justified only for constant density, but is
assumed to hold in general. This corresponds to the hypotheses that
macroscopic density waves move at a velocity much smaller than the
packets transmission velocity. We derive a flux model that implies
equivalence between the total variation of density and of flux.
A first model for such a network is developed in [16].
The aim is then to consider complex networks, and to propose a
routing algorithm
(RA) Packets are processed by arrival time (FIFO policy) and are sent
to the outgoing lines in order to maximize the flux.
It simply send each packet to the outgoing line which is naturally chosen
according to the final destination of the packet itself. The algorithm is
blind to possible overloads of some outgoing lines and, by some abuse
of notation, is similar to the behavior of a ”switch”.
The routing algorithm (RA) can be described by two rules and was
already used in [13] for car traffic. In particular a traffic distribution
matrix A is given, which describes the percentage of packets from an
incoming line that are addressed to an outgoing one. For existence of
solutions to the Cauchy problem on the network, it is necessary to re-
strict on the case of simple nodes with two incoming and two outgoing
lines. In order to determine unique solutions to Riemann problems,
some additional parameters are introduced, called respectively priority
parameters, which describe priorities among incoming lines and traffic
distribution parameters, having the same meaning of the traffic distri-
bution matrix. In this context, we obtain an optimization with respect
to the priority parameter of a telecommunication network.
Plan of the Thesis
The Thesis is organized as follows.
Chapter 1 deals with hyperbolic systems of conservation laws. We
introduce the basic definitions and give the basic tool to prove existence
and uniqueness of solutions. Then we pass to consider, in Chapter 2,
an optimization of the parameters that describe a fluid-dynamic model
for traffic flow on road networks. The analogy with fluids comes from
considering cars as particles. The idea is to look at the network at an
intermediate time scale so that cars travelling happens at a faster level
7but the equilibria of the whole network are reached only as asymp-
totic. This permits to construct a model relying on a macroscopic
description. A routing algorithm has been analyzed in order to solve
Riemann problems at junctions. Particularly, some cost functionals,
that measure average velocity, average travelling time and total flux
of cars along the network, are defined for the optimization. Such cost
functionals provide an estimate about some phenomena, such as traffic
congestion, accidents and pollution.
The Chapter 3 is devoted to problems of car traffic flows in con-
gested roads of an urban network. Particularly, one wants to consider
how cars can be redirected in the case of high car densities on some
roads, with an opportune choice of some traffic coefficients. An opti-
mization technique of the traffic distribution parameters, that describe
a fluid - dynamic model for road networks, is considered. In this case,
with the term optimization, we refer to the possibility to improve traffic
conditions in presence of some factors due to congestion phenomena.
In the Chapter 4, we deal with the optimization techniques applied
to a fluid-dynamic model that describes data flows on telecommunica-
tions networks. The aim of this chapter is to present some results about
the optimal choice of the parameters, that describe a fluid-dynamic
model for data flow on telecommunication networks. In particular,
some cost functionals, that measure average velocity, average travel-
ling time and total flux of packets along the network, are defined. Such
cost functionals are useful to measure the performances of the network,
and to understand complex typical phenomena of telecommunication
networks, such as packets congestion.
For all examined cases study, some simulation results are provided
with accurate analysis and physical interpretation.