Macroscopic arc performance models with capacity constraints for within-day dynamic traffic assignment

Guido Gentile, Lorenzo Meschini and Natale Papola

Dipartimento di Idraulica, Trasporti e Strade

Università degli Studi di Roma “La Sapienza”

ABSTRACT

In this paper, we present a new nonstationary link-based macroscopic arc performance model with

capacity constraints, derived from an approximate solution to the simplified kinematic wave theory which

based on the assumption, often introduced in the algorithms solving Dynamic Traffic Assignment, that the

arc inflows are piecewise constant in time. Although the model does not require to introduce any spatial

discretization, it is capable of taking implicitly into account the variability of the flow state along the arc

accordingly to any concave fundamental diagram. To appreciate the effect of the approximation introduced,

the model has been compared in terms of efficiency and effectiveness with three typical existing models,

which have been to this end suitably modified and enhanced.

Keywords: link-based travel time function, simplified kinematic wave theory, nonstationary macroscopic

flow model, running link, bottleneck, within-day dynamic traffic assignment.

1 INTRODUCTION

Within-day Dynamic Traffic Assignment (DTA), regarded as a dynamic user equilibrium, can be

formalized and solved as a fixed point problem in terms of arc flow and arc performance temporal profiles,

accordingly with the model presented in Bellei, Gentile and Papola (2004) and depicted synthetically in

Figure 1.

[Figure 1 here]

The network travel time pattern plays a double role in DTA: on the demand side, it constitutes the main

attribute in the context of users’ path choice; on the supply side, it determines the arc flow pattern for given

path choices (dashed arrow in Figure 1). Thus, it is crucial to devise an arc performance model which is both

satisfactorily representative of the real phenomenon, and efficient when used in DTA, which is complex of

its own.

1
 In this paper we will focus on nonstationary macroscopic arc performance models that are based on the

fluid paradigm, where vehicles are represented as particles of a mono-dimensional partly compressible fluid

(Cascetta, 2001). These models can be classified into two major groups.

The models belonging to the first group, referred to as space continuous (e.g. METANET, Messmer and

Papageorgiou (1990); Cell Transmission Model, Daganzo, 1994, 1995a), are formulated through differential

equations in time and space and solved through finite difference methods. Their algorithmic implementation

relies on a thick space discretization and for this reason they are also referred to as point-based. Such models

yield accurate results and allow any fundamental diagram to be used, but require considerable computing

resources.

The models belonging to the second group, referred to as space discrete, do not require any spatial

discretization, and for this reason are also referred to as link-based. Such models can be, in turn, subdivided

in whole link models and wave models. Whole link models (e.g. Astarita, 1996; Ran et al., 1997), do not take

into account the propagation of flow states along the arc, since performances are assumed to depend on a

space-average state variable, such as density (Heydecker and Addison, 1998). This yields a poor

representation of travel times, which gets worse as the arc length increases (Daganzo, 1995b). Despite this

major deficiency, these models allow adopting any fundamental diagram, and are widely used in DTA

because of their simplicity (e.g. Friesz et al., 1993; Tong and Wong, 2000). Wave models, based on the

simplified kinematic wave theory of Lightill, Whitham and Richards (Daganzo, 1997), implicitly take into

account the propagation of flow states along the arc, yielding arc performances as a function of the traffic

conditions encountered while travelling throughout the link. So far, however, these models have been

developed only for bottlenecks; that is, when the fundamental diagram has a triangular shape and a capacity

constraint is introduced on the final section of the arc. In this case, only two speeds may occur on the arc: the

free-flow speed and the queue speed. Among them are the simplified kinematic wave model presented in

(Newell, 1993), the deterministic queuing models (Arnott, De Palma and Lindsey, 1990; Ghali and Smith,

1993), and the link-node model presented in Bellei, Gentile and Papola (2004). These models require

minimal computing resources, but yield realistic results only in urban contexts.

In this paper, we present a new wave model, named Average Kinematic Wave (AKW), which allows any

concave fundamental diagram to be used and presents a very favourable relation between the efficiency and

2
the effectiveness. By comparing the performances of the proposed model with those of the existing ones, we

will provide an accurate idea about its advantages. To make this comparisons internally consistent, a specific

typical model for each group is chosen – namely one Space Continuous (SC), one Whole Link (WL) and the

Simplified Kinematic Wave (SKW) – and is opportunely modified and enhanced in order to deal with any

concave fundamental diagram and with explicit capacity constraints.

2 MATHEMATICAL FRAMEWORK

In this section we recall some significant results of traffic flow theory and introduce the mathematical

framework underlying the four models discussed in this work.

The following notation will be used throughout the paper:

L arc length

x∈[0, L] generic section of the arc

Θ duration of the period of analysis

τ∈[0, Θ] generic instant of the period of analysis

q(x,τ) flow on arc section x at time τ

k(x,τ) density on arc section x at time τ

v(x,τ) speed on arc section x at time τ

Φ(x,τ) = [q(x,τ), k(x,τ), v(x,τ)] flow state on arc section x at time τ

w(x,τ) speed of the kinematic wave on arc section x at time τ

τ
Q ( x,τ ) = ∫ 0
q( x , σ ) ⋅ d σ cumulative flow on arc section x at time τ

t(x, y,τ) time when the vehicle traversing section x at time τ reaches section y

Based on the fluid paradigm, the First In First Out (FIFO) rule holds (Cascetta, 2001); then we have:

Q ( x,τ ) = Q ( y, t ( x, y ,τ ) ) (1.1)

or equivalently

∂ t ( x, y,τ )
q( x,τ ) = q ( y, t ( x, y ,τ ) ) ⋅ (1.2)
∂τ

which is obtained differentiating (1.1) with respect to time.

3
 The simplified kinematic wave theory is based on the following relations:

q( x,τ ) = k ( x,τ ) ⋅ v( x,τ ) (2)

∂k ( x,τ ) ∂q ( x,τ )
+ =0 (3)
∂τ ∂x

where (2), defining stationary traffic, is assumed to be valid also for nonstationary conditions, and (3) stems

from vehicle conservation. Moreover, the existence of a direct relation between speed and density is

assumed, which, being the arc a homogenous channel, does not depend directly on the arc section, i.e.

v( x,τ ) = v ( k ( x,τ ) ) (4.1)

or equivalently

k ( x,τ ) = k ( v( x,τ ) ) (4.2)

Based on (2), equations (4) define also a relation between flow and density, called fundamental diagram:

q( x,τ ) = q ( k ( x,τ ) ) (5.1)

and a relation between flow and speed:

q( x,τ ) = q ( v( x,τ ) ) (5.2)

In the following, we assume relations (4) to be such that equation (5.1) is concave. In this case, the

density at which equation (5.1) takes its maximum value divides the flow states in hypocritical and

hypercritical. As it will be cleared later on, we need to model explicitly only hypocritical states; then,

referring to the latter states, it is possible to derive the following inverse relations as one-valued functions:

k ( x,τ ) = k ( q ( x,τ ) ) (6.1)

v ( x ,τ ) = v ( q ( x ,τ ) ) (6.2)

It is shown in Newell (1989) that the solution in terms of flows to the system defined by (3) and (6.1) is

such that the generic hypocritical flow state:


Φ (x,τ ) = Φ (q(x,τ )) = [q(x,τ ) ,k(q(x,τ )) , v(q(x,τ ))] (7)

propagates forward along the arc at a constant speed (see Figure 2, left side):

1
w( x,τ ) = w ( q( x,τ ) ) =  (8)
d k(q ) d q

4
When two different flow states propagating on the arc at different speeds collide, a shockwave is generated,

which separates the fields where the first flow state overwhelms the second one and vice-versa.

Consequently, not all the flow states occurring on the generic section x reach a given section y > x.

[Figure 2 here]

The instant u(x,y,τ) when a given state Φ(q(x,τ)) present at time τ in section x would reach section y ≥ x

and the cumulative flow G ( x, y ,τ ) that would be observed at instant u(x,y,τ) on section y are given,

respectively, by (Daganzo, 1997):

u( x, y ,τ ) = τ + ( y − x ) w ( q( x,τ ) ) (9)

G ( x, y ,τ ) = Q ( x,τ ) + q( x,τ ) ⋅ 1 w ( q( x,τ ) ) − 1 v ( q( x,τ ) ) ⋅ ( y − x ) (10)

where the term q( x,τ ) ⋅ ∆τ , with ∆τ = [1/ w( q( x,τ )) − 1/ v( q( x,τ ))] ⋅ ( y − x ) , is the number of vehicles

travelling at speed v(q(x,τ )) ≥ w(q(x,τ)) that would pass an observer travelling at speed w(q(x,τ)), crossing

section x at time τ and section y at time u(x,y,τ) (see Figure 2, right side). The Newell-Luke minimum

principle (Daganzo, 1997 and Newell, 1993) states that, if the fundamental diagram is concave, among all

kinematic waves that pass through a given point in the time-space plane the one yielding the minimum

cumulated flow dominates the others; on this basis the actual cumulative flow on section y at time σ is given

by:

Q ( y ,σ ) = inf {G ( x, y ,τ ) : u( x, y ,τ ) = σ , x ∈ [0, y ]} (11)

By combining (10) and (11) it is possible to determine the cumulative flow temporal profile at a given

section y from the cumulative flow temporal profile at any previous section x < y.

In the following, without loss of generality, we adopt the Greenshields linear model (Huber, 1976), where

relations (4.1) and (4.2) have, respectively, the following form:

 k ( x,τ ) 
v ( x,τ ) = v0 ⋅ 1 −  (12.1)
 k j 


 v ( x,τ ) 
k ( x,τ ) = k j ⋅ 1 −  (12.2)
 v0 

5
with parameters v0 and kj representing, respectively, the free flow speed and the jam density. The linear

model (12) is plausible and, combined with equation (2), allows expressing in a closed form relations (5), (6)

and (8):

 k ( x ,τ ) 
q( x,τ ) = k ( x,τ ) ⋅ v0 1 −  (13.1)
 k j 


 v ( x ,τ ) 
q( x,τ ) = v( x,τ ) ⋅ k j  1 −  (13.2)
 v0 

kj  4 ⋅ q( x,τ ) 
k ( x,τ ) = ⋅ 1 − 1 −  (14.1)
2  v0 ⋅ k j 
 

v0  4 ⋅ q( x,τ ) 
v ( x ,τ ) = ⋅ 1 + 1 −  (14.2)
2  v0 ⋅ k j 
 

4 ⋅ q ( x ,τ )
w( x,τ ) = v0 ⋅ 1 − (15)
v0 ⋅ k j

Based on (13.1), the maximum flow qmax, referred to as the arc capacity, is equal to 0.25 ⋅v0 ⋅kj.

3 ARC PERFORMANCE MODEL

In the following, the arc is divided into three parts: an initial bottleneck, which can be thought of as a link

with infinitesimal length δ located between the arc initial section 0 and section X = 0+δ; a final bottleneck,

located between section Y = L-δ and the arc final section L; a running link, located between sections X and Y.

The initial bottleneck, with a constant capacity CX = qmax, maintains the inflow on the running link below

the arc capacity, and then guarantees the consistency of the traffic flow model in the context of DTA, where

the arc inflow may assume any non-negative value. In order to avoid spillback modelling and to obtain a

spatially separable arc performance model, we assume that, when the initial bottleneck is active, a vertical

queue is present.

The final bottleneck, with a constant capacity CL ≤ qmax, models the one hypercritical flow state, referred

to as the queue, that is generated by a constant capacity reduction at the end of the arc. This is used in the

context of DTA to simulate the average effect of road intersections, since the details of the delay due to a

variable capacity constraint, such as a traffic light, can be ignored in most practical instances of the problem.

6
When the final bottleneck is active, the queue propagates backward on the running link and becomes vertical

whenever it exceeds the arc length.

The running link models the congestion due to vehicles’ interaction along the arc while travelling under

hypocritical conditions; it consists of a homogeneous channel where flow states are determined based on the

simplified kinematic wave theory.

Note that, due to the initial bottleneck and to the homogeneity hypothesis, no hypercritical flow state can

be generated on the running link. Moreover, it will be shown that when a queue is present on the final

bottleneck, the arc exit time temporal profile is completely determined by its capacity and by the arc inflow

temporal profile, while the outflow and the exit time of the running link loose their physical meaning.

In order to device a numerical method implementing the arc performance models at hand, the period of

analysis is divided into I time intervals identified by a sequence of instants τ = (τ 0 = 0, … , τ i, … , τ I = Θ)

and, when needed, the running link is divided into Z sections identified by a sequence of progressives

x = (x 0 = δ, … , x z, … , x Z = L-δ).

Let txi denote the exit time from section x∈{0, X, Y, L} for the vehicle entering the arc at time τ i, and qxi

denote the flow on section x at time txi. In compact form it is: tx = (tx0, … , txI ), qx = (qx1, … , qxI ), and clearly

holds: t0 = τ . We assume the following two hypotheses:

i) the arc inflow temporal profile is approximated through the following piece-wise constant function:

q(0,τ) = q0i, τ∈(τ i-1, τ i] , i = 1, … , I (16)

ii) the exit time temporal profile of the generic sub model (x, y)∈{(0, X), (X, Y), (Y, L)} is approximated

through the following piece-wise linear function:

t y i − t y i −1
t ( x, y ,τ ) = t y i −1 + (τ − t x i −1 ) ⋅ , τ∈(txi-1, txi ], i = 1, … , I (17)
t x i − t x i −1

Based on the above hypotheses and relation (1.2) it follows that for each sub model (x, y) the outflow

temporal profile is piece-wise constant and can be expressed as:

t x i − t x i −1
q(y, τ) = qyi = qx i ⋅ i i −1
, τ∈(tyi-1, tyi], i = 1, … , I (18)
ty − ty

In the following we present some numerical methods for determining the vectors ty and qy from the

vectors tx and qx for each sub model (x, y). On this basis, the arc exit time, which is by definition:

7
t (0, L,τ ) = t (Y , L, t ( X , Y , t (0, X ,τ ) ) ) (19)

can be evaluated, along with the arc outflow temporal profile, through the following procedure:

sub arc_exit_time(t0, q0 ; tL, qL)

call bottleneck(CX, t0, q0 ; tX, qX)
call running_link(tX, qX ; tY, qY)
call bottleneck(CL, tY, qY ; tL, qL)
end sub

The procedures bottleneck and running_link will be specified in sections 4 and 5, respectively.

4 BOTTLENECK MODEL

Based on the simplified kinematic wave theory and on the Newell-Luke minimum principle, the

cumulative outflow at time τ of the generic bottleneck (x, y) of infinitesimal length, for a given cumulative

inflow temporal profile, is given by:

Q ( y ,τ ) = min {Q ( x,σ ) + (τ − σ ) ⋅ C y : σ ≤ τ } (20)

which expresses the fact that the cumulative outflow cannot increase faster than the capacity.

On the basis of Figure 3, it is immediate that the exit time t(x, y, τ), implicitly expressed by the system of

equations (1.1) and (20), can be made explicit as follows:

t ( x, y ,τ ) = max {σ + (Q ( x,τ ) − Q ( x,σ ) ) C y : σ ≤ τ } (21)

[Figure 3 here]

Under hypotheses i) and ii) the outflow and the exit time temporal profiles are determined by means of

the following procedure:

sub bottleneck(Cy , tx , qx ; ty , qy)

ty0 = tx0 + Ny0 / Cy
for i = 1 to I
{
t y i = max t x i , t y i −1 + (t x i − t x i −1 ) ⋅ qx i C y } (22)
q y i = qx i ⋅ (t x i − t x i −1 ) (t y i − t y i −1 )
next i
end sub

where it is assumed that at time tx0 there is a queue of Ny0 vehicles at the bottleneck.

When the final bottleneck is active, based on (22), by applying recursively (18) we have:

q0i
tLi = tLi −1 + (τ i − τ i −1 ) ⋅ , (23)
CL

8
which shows, as previously stated, that when the queue is present at the final bottleneck the arc exit time

depends only on the final bottleneck capacity and on the arc inflow temporal profile, and thus depends

neither on the arc length, nor on the flow model adopted for the running link.

5 RUNNING LINK MODELS

In this section we specify the generic running link model (x, y) in four different ways. As initial condition,

a uniform flow state Φ(q0) is considered on the whole running link.

5.1 Space Continuous model

The SC model considered here is a simplification of METANET (Messmer and Papageorgiou, 1990),

where the first order relation (12) is employed instead of the second order relation utilized by the authors.

The model is implemented by the following procedure:

sub running_link_SC(tx , qx ; ty , qy)

Q0 = 0, E 0 = 0 (24.1)
for z = 0 to Z
q z,0 = q0 (24.2)
k z ,0
(
= 0.5 ⋅ k j ⋅ 1 − 1 − 4 ⋅ q z ,0
(v0 ⋅ k j ) ) (24.3)
next z
for i = 1 to I
q 0,i = qxi (24.4)
for z = 1 to Z
k z ,i = k z ,i −1 − (t xi − t xi −1 ) ⋅ ( q z ,i −1 − q z −1,i −1 ) ( x z − x z −1 ) (25)
z ,i z ,i z ,i
q =k ⋅ v0 ⋅ (1 − k kj) (26)
next z
Q i = Q i −1 + q 0,i ⋅ (t xi − t xi −1 ) (27)
i −1
E = E +q i Z ,i
⋅ (t xi − t xi −1 ) (28)
next i
call exit_time_and_outflow(tx , Q, tx , E ; ty , qy)
end sub

where both the cumulative inflow Q i = Q(x, txi ) and outflow E i = Q(y, txi ) are referred to the running link

entrance time, qz,i = q(xz, τ i), kz,i = k(xz, τ i), with z = 0, … , Z, i = 0, … , I. (24) are the boundary conditions;

(25) and (26) result, respectively, from the discretization of (3) and (13.1) over a grid of points on the space-

time plane; (27) and (28) yield the cumulative inflow and outflow temporal profile through the couples of

vectors (tx , Q) and (tx , E ), respectively.

9
 Note that, in order to achieve a correct propagation of flow states through equation (25), the discretization

grid must satisfy the following condition:

x z − x z −1 1
≥ max {w ( q ) : q ∈ [0,qmax ]} =  = v0 (29)
i
tx − txi −1
dk ( 0 ) dq

If, for example, we have v0 = 25 m/sec and ( x z − x z −1 ) = 25 m, then (txi - txi-1) must be smaller than 1 sec.

Clearly, such a thick time discretization is critical for DTA, where usually the period of analysis covers

several hours.

The exit time and outflow temporal profiles are determined on the basis of the cumulative inflow and

outflow temporal profiles, by means of the following procedure:

sub exit_time_and_outflow(tx , Q, σ , E; ty , qy)

Q -1 = 0, E J+1 = Q I , σ J+1 = ∞
j=1
for i = 0 to I
do until E j ≥ Q i (30)
j=j+1
loop
if Q i = Q i-1 then
{
t iy = max t iy−1 , t xi + L v0 } (31)
qiy = 0
else
t iy = σ j −1
( )(
+ (Q i − E j −1 ) E j − E j −1 ⋅ σ j − σ j −1
) (32)

(
q y i = Q i − Q i −1 ) (t i
y − t iy−1 ) (33)
end if
next i
end sub

where Q i = Q(x, txi), i = 0, … , I, and E j = Q(y, σ j ), j = 0, … , J ; while the components Q -1, σ -1, E J+1, σ J+1

are introduced only for algorithmic reasons. The “do loop” cycle determines j such that E j-1 < Q i ≤ E j, as

depicted in Figure 4; (31) enforces the FIFO rule when the inflow is null; (32) derives from (1.1) based on

hypothesis (17); (33) derives from (18). Note that, based on condition (30), in (32) it is always E j > E j-1,

while in (33), based on (32), because Q i > Q i-1 it is always ty j > ty j-1; this avoids divisions by zero.

[Figure 4 here]

The SC model gives very accurate results, so that in this paper it will be used as a term of reference to

evaluate the efficacy of the other models.

10
5.2 Whole Link model

The WL model considered here is based on the arc performance model proposed in Astarita (1996),

where the travel time of a vehicle entering the running link at time τ is determined as a function of the

average density along the running link at the same instant. The linear time-density function utilized by the

author is here replaced with the hyperbolic function that results from equation (12) assuming that the speed

corresponding to the average density is maintained throughout the running link.

The model is implemented by the following procedure:

sub running_link_WL(tx , qx ; ty , qy)

ty-1 = 0 , Q -1 = 0
Q0 = 0 (34.1)
0
(
K = 0.5 ⋅ k j ⋅ 1 − 1 − 4 ⋅ q0 ( v0 ⋅ k j ) ) (34.2)
V 0 = v0 ⋅ (1 − K 0 k j )
t 0y = t x0 + L V 0
j=0
for i = 1 to I
do until tyj ≥ txi (35)
j = j +1
loop
Q i = Q i −1 + qxi ⋅ (t xi − t xi −1 )
E i = Q j −1 + (t xi − t yj −1 ) ⋅ (Q j − Q j −1 ) (t yj − t yj −1 ) (36)
K i = (Q i − E i ) L
V i = v0 ⋅ (1 − K i k j )
t iy = t xi + L V i
if tyi = tyi-1 then (37)
i
qy = 0
else
(
q y i = Q i − Q i −1 ) (t i
y − t iy−1 ) (38)
end if
next i
end sub
i
where K is the average density along the running link at time txi , V i
is the corresponding speed,

Q i = Q(x, txi) = Q(y, tyi) and Ē i = Q(y, txi), with i = 0, … , I ; while the components ty-1 and Q -1 are introduced

only for algorithmic reasons. (34) are the initial conditions; the “do loop” cycle determines j such that
j-1
ty < txi ≤ ty j, (36) yields the cumulative outflow at time txi based on the piece-wise linear cumulative

outflow temporal profile defined through the couple of vectors (ty , Q), as depicted in Figure 5. Note that,

11
based on condition (35), within (36) it is always ty j > ty j-1, while, based on condition (37), within (38) it is

always tyi > tyi-1 ; this avoids divisions by zero.

[Figure 5 here]

Note that j must be always smaller than i, otherwise, when ty j needs, it is still unknown. This implies:

t iy−1 ≥ t xi , i = 1,..., I { } {
⇒ min t iy − t xi : i = 0,..., I = L v0 ≥ max t xi − t xi −1 : i = 1,..., I } (39)

Condition (39) yields an upper bound for the duration of the time intervals, which is analogous to (29)

relative to the SC model.

5.3 Simplified Kinematic Wave model

We here present a solution method of the simplified kinematic wave theory based on cumulative flows,

which is capable of handling any concave fundamental diagram. A similar approach can be found in Newell

(1996), where, however, the solution method is provided only for the triangular-shaped fundamental

diagram.

The approach consists in evaluating the cumulative flow temporal profile at a given section based only on

boundary or initial conditions, without evaluating any state variable at intermediate sections. Referring to the

fundamental diagram (13.1), the cumulative outflow temporal profile is evaluated here through equations (9),

(10) and (11).

The model is implemented by the following procedure:

sub running_link_SKW(tx , qx ; ty , qy)

Q 0 = 0, G 0 = 0 (40.1)
w0 = v0 ⋅ 1 − 4 ⋅ q0 ( v0 ⋅ k j ) (40.2)
u 0 = tx0 + L / w0
for i = 1 to I
Q i = Q i −1 + qxi ⋅ (t xi − t xi −1 )
wi = v0 ⋅ 1 − 4 ⋅ qxi ( v0 ⋅ k j ) (41)
u i = t xi + L wi (42)

(
v i = 0.5 ⋅ v0 ⋅ 1 + 1 − 4 ⋅ qxi ( v0 ⋅ k j ) ) (43)

G i = Q i + qxi ⋅ (1 wi − 1 v i ) ⋅ L (44)
next i
call lower_envelop(u, G ; θ, Ẽ )
call exit_time_and_outflow(tx , Q, θ, Ẽ ; ty , qy)
end sub

12
where u i = u(x, y, txi), G i = G(x, y, txi), w i = w(x, txi) and v i = v(x, txi), with i = 0, … , I. (40) are initial

conditions are set in, (41), (42), (43) and (44) derive, respectively, from equations (15), (9), (14.1) and (10).

The procedure exit_time_and_outflow is described in section 5.1. The procedure lower_envelop, described in

detail in Gentile, Meschini and Papola (2003), aims at determining the cumulative outflow temporal profile

by selecting a non-dominated subset of points from (u , G), yielding (θ , Ẽ̃), with Ẽ j = Q(y, θ j ), j = 0, … , J.

In order to ensure that a point is not dominated, all successive points must be examined, which implies in the

worst case 0.5⋅(I-1)⋅I checks. Finally, note that the solution of equation (11) for a triangular-shaped

fundamental diagram becomes trivial.

5.4 The Average Kinematic Wave model

The proposed model is derived from an approximate solution to the simplified kinematic wave theory

which is valid in the case where the arc inflow temporal profile is piecewise constant, coherently with

hypotheses i) – ii) and with equation (18). The main idea underlying this new model is to determine, at each

instant when the inflow changes, a fictitious flow state, which synthesizes previous flow states occurring

along the running link and is employed, in turn, for determining successive flow states.

[Figure 6 here]

Based on the simplified kinematic wave theory, vehicles change their speeds instantaneously. As depicted

in Figure 6, when the inflow temporal profile is piece-wise constant, vehicle trajectories are piece-wise linear

and the space-time plane comes out to be subdivided into flow regions characterized by homogeneous flow

states and delimited by linear shock waves. The slope W ij of the shockwave separating two flow states Φ(q i)

and Φ(q j) is:

q j − qi
W ij =  j  i (45)
k(q ) − k(q )

Expressing (45) in terms of the speeds v(qi ) and v(q j ) through (12.2) and (13.2), yields:

W ij = v(qi ) + v(q j ) − v0 (46)

In theory, given a piece-wise constant inflow temporal profile, using (14.2) and (46) it is possible to

determine the trajectory of a vehicle entering the running link at the generic instant τ, and thus its exit time

t(x,y,τ). However, Figure 6 shows that it may be extremely cumbersome to determine these trajectories, in
13
fact: a) many shockwaves may be active on the generic running link at the same time; b) shockwaves may be

generated either at the initial section by flow discontinuities at times tx i, i = 0, … , I, or on any running link

section at any time by shockwave intersections; c) the generic vehicle may cross many shockwaves while

travelling on the running link, and all the crossing points have to be explicitly evaluated in order to determine

its trajectory.

In order to overcome these difficulties, as depicted in Figure 7, we assume that at each instant

tx i, i = 0, … , I, a fictitious shockwave is generated at section x separating the actual flow state Φ(qxi+1) and

the fictitious flow state corresponding to the average speed λi = L /(tyi - txi) of the vehicle entered at instant txi.

Fictitious shockwaves are very easy to deal with, in fact: a) they never meet each other, and thus are all

generated on the running link initial section only at time tx i, i = 0, … , I; b) each vehicle meets at the most the

last generated fictitious shockwave, so that its trajectory is very easy to be determined, as it will be showed

in the computation procedure.

Based on (46), the slope W i of the generic fictitious shockwave is:

W i = λ i + v(qxi +1 ) − v0 (47)

[Figure 7 here]

Note that the trajectory of a vehicle entering the running link at time τ∈(txi - txi+1] is directly influenced

only by the average trajectory of the vehicle entered at time txi , which synthesizes the previous history of

flows states.

The approximation introduced has little effect on the model efficacy, as it will be showed in the next

section. Moreover, it has no effect with respect to the FIFO rule, which is still ensured between the running

link initial and final sections, while local violations that may occur within intermediate sections are of no

interest.

The model is implemented by the following procedure:

sub running_link_AKW(tx , qx ; ty , qy)

(
λ 0 = 0.5 ⋅ v0 ⋅ 1 + 1 − 4 ⋅ q0 ( v0 ⋅ k j ) ) (48)
ty = + L / λ
0
tx0 0

for i = 1 to I
(
v i = 0.5 ⋅ v0 ⋅ 1 + 1 − 4 ⋅ qxi ( v0 ⋅ k j ) ) (49)
W i −1 = λ i −1 + v i − v0 (50)

14
 ( ) (
if t xi − t xi −1 ⋅ W i −1 ⋅ v i ≥ L ⋅ v i − W i −1 then ) (51)
t iy = t xi + L v i
else
ω i = (t xi − t xi −1 ) ⋅ W i −1 ( v i − W i −1 ) (52)
t = t +ω + (L −ω ⋅v
i
y
i
x
i i i
) λ i −1
(53)
end if
if tyi = tyi-1 then
q yi = 0
else
qiy = qix ⋅ (t xi − t xi −1 ) (t iy − t iy−1 )
end if
λ i = L (t iy − t xi ) (54)
next i
end sub

where v i is the speed, corresponding to the inflow qxi , of the vehicle entering the running link at time

tx i, i = 0, … , I, and tx i +ω i is the instant when this vehicle reaches the fictitious shockwave. At this point, the

vehicle changes its speed from v i to λ i-1. Condition (51) ensures that this happens before the end of the

running link; (49) is based on (14.2), (50) is based on (47), while (52), (53) and (54) are made clear by

Figure 8.

[Figure 8 here]

The generalization of this model to any concave fundamental diagram is trivial; in fact, since (45) holds

in general, (47) can be substituted by the following equation:

qi +1 − q( λ i )
W i =  xi +1 (55)
k(qx ) − k( λ i )

6 COMPARISON OF MODELS AND CONCLUSIONS

In this section we compare, with respect to their efficiency and effectiveness, the different models

presented in the paper. The effectiveness of the point based model presented in subsection 5.1 can be

reasonably assumed as a term of reference, as it yields results close enough to reality, while the efficiency

will be evaluated both analysing the complexity of the algorithms and comparing calculation times.

Each model has been used to simulate the traffic flow over an arc 10,000 meters long; the Greenshields

fundamental diagram was adopted with a free-flow speed of 90 km/h, a jam density of 0,09 veh/m, and thus

a capacity of 2025 veh/h. With reference to the point-based SC model, the arc was divided into Z = 40

15
sections 250 meters long; this required, based on (29), to divide the period of analysis, 30 minutes long, into

ISC = 180 intervals of 10 seconds. With reference to the link-based models, where spatial discretization is not

necessary, the same number of time intervals was adopted in order to compare the efficiencies.

The different running link models have been tested with three inflow temporal profiles lower than the arc

incoming and outgoing capacities: flow gradually increasing, gradually decreasing, and fluctuating around an

average value. The relative output is depicted in Figures 10, 11 and 12, respectively.

[Figure 9 here]

[Figure 10 here]

[Figure 11 here]

The above results show that the SKW and AKW models behave much closer to the SC model than the

WL model, especially with reference to the arc travel time, which is the relevant variable when performing

DTA. In particular, the WL model shows a sort of “inertia” in representing travel times when the inflow

varies rapidly.

In order to investigate the effect of time discretization size on the solution quality, a varying inflow

temporal profile is processed with the AKW model assuming three different discretization sizes: I1 = ISC ,

I2 = ISC /3 = 60 intervals of 30 seconds, and I3 = ISC /9 = 20 intervals of 90 seconds. Results are compared in

Figure 12, showing a very favourable relation between effectiveness and efficiency, since large

improvements of the first determine small reductions of the second; this is important when applying the arc

performance model in real-size networks, where run time is a critical issue.

[Figure 12 here]

The complexity is equal to O(ISC ⋅Z) for the SC model, O(I) for the WL model, O(I 2) for the SKW model

and O(I) for the AKW model; thus the AKW model has the least complexity. A numerical analysis aimed at

evaluating their actual efficiency has confirmed this theoretical evidence. In fact, the CPU time in seconds

needed to run 1,000,000 times each one of the four models for two different time discretization sizes, ISC / 6

and ISC, resulted to be respectively: 293 for the SC, 9 and 27 for the WL, 17 and 291 for the SKW, 6 and 21

for the AKW. The WL model and the AKW model are definitely more efficient than the SC model in both

cases, while the efficiency of the SKW model deteriorates rapidly when the number of time intervals

increases, due to its quadratic complexity.

16
 The average kinematic wave model developed in this paper can be considered an overcoming of the

simplified kinematic wave model obtained through the introduction of the concepts of fictitious flow state

and fictitious shockwave that allow improving markedly its performances while having a very favourable

relation between the efficiency and the effectiveness of the model, i.e., large improvements of the first in

exchange for small reductions of the second.

17
 REFERENCES

Arnott R., De Palma A., Lindsey R. (1990) “Departure time and route choice for the morning commute”,

Transportation Research B 24, 209-228.

Astarita V. (1996) “A continuous time link model for dynamic network loading based on travel time

function”, in Proceedings of the 13th International Symposium on the Theory of Traffic Flow, Lyon, 87-102.

Bellei G., Gentile G., Papola N. (2004) “A within-day dynamic traffic assignment model for urban road

networks”, Transportation Research B, in press, corrected proofs, available online.

Cascetta E. (2001) Transportation systems engineering: theory and methods, Kluwer Academic

Publisher, Boston, MA, 374-379.

Daganzo C.F. (1994) “The cell transmission model: a dynamic representation of highway traffic

consistent with hydrodynamic theory”, Transportation Research B 28, 269-287.

Daganzo C.F. (1995a) “The cell transmission model, part II: network traffic”, Transportation Research B

29, 79-93.

Daganzo C.F. (1995b) “Properties of link travel time functions under dynamic loads”, Transportation

Research B 29, 95-98.

Daganzo C.F. (1997) Fundamentals of transportation and traffic operations, Pergamon, Oxford, UK,

chapter 4.

Friesz T.L., Bernstein D., Smith T.E., Tobin R.L., Wie B.W. (1993) “A variational inequality formulation

of the dynamic network user equilibrium problem”, Operations Research 41, 179-191.

Gentile G., Meschini L., Papola N. (2003) “Macroscopic arc performance models for within-day dynamic

traffic assignment”, in Proceedings of the Transportation Research Board 82nd Annual Meeting,

Washington D.C., US.

Ghali M.O., Smith M.J. (1993) “Traffic assignment, traffic control and road pricing”, in Transportation

and Traffic Theory, ed. C.F. Daganzo, Elsevier, Amsterdam, The Netherlands, 147-169.

Heydecker B.G., Addison J.D. (1998) “Analysis of traffic models for dynamic equilibrium traffic

assignment”, in Transportation networks: recent methodological advances, ed. Bell M.G.H., Pergamon,

Oxford, UK, 35-49.

18
 Huber M.J. (1976) “Traffic flow theory”, Transportation and Traffic Engineering Handbook, Chapter 15,

Prentice-Hall.

Messmer A., Papageorgiou M. (1990) “METANET: a macroscopic simulation program for motorway

networks”, Traffic Engineering & Control 31, 466-470 and 10, 549.

Newell G.F. (1989) “Comments on traffic dynamics”, Transportation Research B 23, 386-389.

Newell G.F. (1993) “A simplified theory of kinematic waves in highway traffic, part I: general theory;

part II: queuing at freeway bottlenecks; part III: multi-destination flows”, Transportation Research B 27,

281-313.

Ran B., Rouphail N.M., Tarko A., Boyce D.E. (1997) “Toward a class of link travel time functions for

dynamic assignment models on signalised networks”, Transportation Research B 31, 277-290.

Tong C.O., Wong S.C. (2000) “A predictive dynamic traffic assignment model in congested capacity-

constrained road networks”, Transportation Research B 34, 625-644.

19
 LIST OF FIGURES

Figure 1. Dynamic Traffic Assignment.

Figure 2. Right side: fundamental diagram. Left side: Flow traversing a kinematic wave.

Figure 3. Cumulative outflow and exit time from a bottleneck of infinitesimal length.

Figure 4. Evaluation of the running link exit time from the piece-wise linear cumulative flows.

Figure 5. Evaluation of point E i = Q(y, txi) from the piece-wise linear cumulative flows.

Figure 6. Flow pattern given by the simplified kinematic wave theory.

Figure 7. Flow pattern given by the Averaged Kinematic Wave model.

Figure 8. Running link exit time determined by the Averaged Kinematic Wave model.

Figure 9. Results for an increasing inflow.

Figure 10. Results for a decreasing inflow.

Figure 11. Results for a varying inflow.

Figure 12. Outflows and travel times obtained by the AKW model for different time discretization sizes.

20
 demand
OD flows

network loading map

path choice
model

path path
flows performances

network flow path performance

propagation model model

arc arc
flows performances

arc perf.
function
arc performance
model

Figure 1. Dynamic Traffic Assignment.

21
 (y-x) / w
density

space
kj (y-x) / v
∆τ
y
hypercritical
flow states

k
hypocritical
flow states
v w
v w x
v0 
k (q)
q qmax time
flow τ u(x, y,τ)

Figure 2. Right side: fundamental diagram. Left side: Flow traversing a kinematic wave.

22
 vehicles
Q(x,τ) = Q(y, t(x,y,τ)) Cy
Q(y,τ) = Q(x,σ) + (τ -σ)⋅Cy
Q(x,σ)

σ τ t(x,y,τ) time

Figure 3. Cumulative outflow and exit time from a bottleneck of infinitesimal length.

23
 vehicles
cumulative
inflow

cumulative
Ej
outflow
Qi
E j-1

txi σ j-1 tyi σj time

Figure 4. Evaluation of the running link exit time from the piece-wise linear cumulative flows.

24
 vehicles
cumulative
inflow
Qi
cumulative
Qj outflow
Ei
Q j-1

ty j-1 txi ty j time

Figure 5. Evaluation of point E i = Q(y, txi) from the piece-wise linear cumulative flows.

25
 trajectory of the vehicle entering the running link at time tx i, i = 0, … , I
shockwaves
space

outflow profile
L

W1,4

v0

v1 v4
v5
v2 v3
W0,1 W1,2 W2,3 W3,4 W4,5
q x1 2 q x3 q x4 q x5 inflow profile time
qx

tx0 tx1 tx2 tx3 tx4 tx5

Figure 6. Flow pattern given by the simplified kinematic wave theory.

26
 average trajectory of the vehicle entering the running link at time txi, i = 0, … , I
fictitious shockwaves
space

outflow profile
L
λ0
λ1
λ3
λ0 λ2
v1 λ5
λ 4

2
λ 1
v

W0 W1 W2 W3 W4
q x1 q x3 q x4 q x5 inflow profile
q x2 time

tx0 tx1 tx2 tx3 tx4 tx5

Figure 7. Flow pattern given by the Averaged Kinematic Wave model.

27
 tyi-1 tyi

space
λ i-1
λ i-1
ω i
L

W i-1 vi
txi-1 txi time

Figure 8. Running link exit time determined by the Averaged Kinematic Wave model.

28
 flow Inflow SC WL SKW AKW
[veh/h]
outflow
0.50
0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00
0 300 600 900 1200 1500 1800

travel time [sec]

travel
600

550

500

450

400

350
0 180 360 540 720 900 1080 1260 1440 1620 1800
time [sec]

Figure 9. Results for an increasing inflow.

29
 flow Inflow SC WL SKW AKW
[veh/h]
outflow
0.50
0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00
0 300 600 900 1200 1500 1800

travel time
travel time [sec]
600

550

500

450

400

350
0 180 360 540 720 900 1080 1260 1440 1620 1800
time [sec]

Figure 10. Results for a decreasing inflow.

30
 flow Inflow SC WL SKW AKW
[veh/h]
outflow
0.50
0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00
0 300 600 900 1200 1500 1800

travel
travel time [sec]
550
530
510
490
470
450
430
410
390
370
350
0 180 360 540 720 900 1080 1260 1440 1620 1800
time [sec]

Figure 11. Results for a varying inflow.

31
 2000 veh/h Outflow

1500

1000

500

0
0 200 400 600 800 1000 1200 1400 1600 1800
sec
Inflow I = Isc I = Isc / 3 I = Isc / 9
600 sec
Travel time

500

400

300
0 200 400 600 800 1000 1200 1400 1600 1800
sec
I = Isc I = Isc / 3 I = Isc / 9

Figure 12. Outflows and travel times obtained by the AKW model for different time discretization sizes.

32