Ph.D. Course Transportation Modeling Prof. Dr.

Zainab Alkaissi
Lecture 8 2022-2023

Basic Static Assignment to Transportation Networks

Congested Networks

Introduction
Equilibrium assignment is generally expressed by fixed point models, that is, systems of nonlinear
equations, or by variation inequalities. Hence only asymptotically converging algorithms are
available.
We consider here the situation where O-D demands are fixed, but link performance measures and
costs depend on link flows through the performance and cost functions. Conversely, link flows
depend on link costs through the path choice probabilities, as described by the uncongested
network assignment map. The user equilibrium approach to the study of the supply-demand
interactions assumes that the state of the real-world system can be represented by a configuration
of path flows that is consistent with the corresponding path costs. Equilibrium path flows and costs
are defined by a system of nonlinear equations obtained by combining the supply model with the
demand model:
∗
𝑔𝑜𝑑 = ∆𝑇𝑜𝑑 𝑐(∑𝑜𝑑 ∆𝑜𝑑 ℎ𝑜𝑑
∗ 𝑁𝐴∗
) + 𝑔𝑜𝑑 ∀𝑜𝑑
∗ ∗
𝑉𝑜𝑑 = −𝑔𝑜𝑑 ∀𝑜𝑑
∗ ∗ )
ℎ𝑜𝑑 = 𝑑𝑜𝑑 𝑝𝑜𝑑 (𝑉𝑜𝑑 ∀𝑜𝑑
Or
∗
𝑔𝑜𝑑 = ∆𝑇𝑜𝑑 𝑐(∑𝑜𝑑 ∆𝑜𝑑 ℎ𝑜𝑑
∗ ) 𝑁𝐴∗
+ 𝑔𝑜𝑑 ∀𝑜𝑑
∗ ∗ )
ℎ𝑜𝑑 = 𝑑𝑜𝑑 𝑝𝑜𝑑 (−𝑔𝑜𝑑 ∀𝑜𝑑
Equivalent equilibrium assignment models expressed in terms of link variables can be formulated
by the system of nonlinear equations obtained by combining the uncongested network assignment
map with the flow-dependent cost functions:
𝑐 ∗ = 𝑐(𝑓 ∗ )
𝑓 ∗ = ∑𝑜𝑑 𝑑𝑜𝑑 ∆𝑜𝑑 𝑝𝑜𝑑 (−∆𝑇𝑜𝑑 𝑐 ∗ − 𝑔𝑜𝑑
𝑁𝐴
)
Or
𝑐 ∗ = 𝑐(𝑓 ∗ )
𝑓 ∗ = 𝑓𝑈𝑁 (𝑐 ∗ ; 𝑑)
Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

The above system of equations shows that, in congested networks, link flows may depend
nonlinearly on on-demand flows (unlike uncongested network assignments). Thus, in this case, the
effect of each O-D pair cannot be evaluated separately.
The circular dependence between flows and costs expressed by the equilibrium approach is
depicted in Fig. 1. This figure particularizes the general framework for the fixed demand
assumption role of the uncongested network assignment model in the equilibrium framework.
The formulation and analysis of the theoretical properties of equilibrium flows (and costs) depend
on the type of model adopted to simulate path choices: probabilistic or deterministic. This selection
defines, respectively, stochastic and deterministic equilibrium assignment models and
corresponding solution algorithms, which are the subjects of the following sections.

Fig. 1 Schematic representation of fixed demand equilibrium assignment

models.

In general, algorithms for calculating equilibrium flows are based on recursive equations which,
starting from an initial feasible link flow vector f 0 ∈ Sf, generate a sequence of feasible link flow
vectors:
𝑓 𝑘 = ∅(𝑓 𝑘−1 ) ∈ 𝑆𝑓

In each step, an assignment algorithm attempts to improve the solution estimate obtained in the
preceding steps, but an exact equilibrium solution will not generally be found in a finite number
Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

of steps. However, if at any step k the equilibrium flow vector is generated, all subsequent elements
of the sequence will remain equal to the equilibrium vector:

𝑓𝑘 = 𝑓 ∗ → 𝑓𝑗 = 𝑓 ∗ 𝑗>𝑘
Furthermore, if link flow vectors in two successive steps are equal, they are the equilibrium vector:
𝑓 𝑘 = 𝑓 𝑘−1 → 𝑓 𝑘 = 𝑓 ∗
Under certain assumptions on the cost functions and the path choice model, it can be demonstrated
that the sequence defined by the recursive equations converges to the equilibrium flow vector 𝑓 ∗ ,
provided that it is unique:
lim 𝑓 𝑘 = 𝑓 ∗
𝑘→∞

Models for Stochastic User Equilibrium

Stochastic User Equilibrium (SUE) assignment is obtained by applying the equilibrium approach
to congested networks under the assumption of probabilistic path choice behavior. The resulting
path flows h∗ corresponds to the condition in which, for each O-D pair, the perceived cost of the
paths used at equilibrium is less than or equal to the perceived cost of every other path. Equilibrium
path flows can be expressed as the solution of a fixed-point model defined on the feasible path
flow set Sh and obtained by combining the supply model with the demand model:
∗
ℎ𝑜𝑑 = 𝑑𝑜𝑑 𝑝𝑜𝑑 (−∆𝑇𝑜𝑑 𝑐(∑𝑜𝑑 ∆𝑜𝑑 ℎ𝑜𝑑 ∗ ) 𝑁𝐴
− 𝑔𝑜𝑑 ∀𝑜𝑑 1
∗
ℎ∗ = [ℎ𝑜𝑑 ]𝑜𝑑 ∈ 𝑆ℎ
An equivalent fixed-point model using link flow variables f ∗ (and therefore defined on the feasible
link flow set Sf) can be obtained by combining the stochastic uncongested network assignment
function (disaggregated here by O-D pair to facilitate the analysis) with the flow-dependent cost
functions:
𝑓 ∗ = 𝑓𝑆𝑈𝑁 (𝑐(𝑓 ∗ ) 𝑜𝑟 𝑓 ∗ = ∑𝑜𝑑 𝑑𝑜𝑑 ∆𝑜𝑑 𝑝𝑜𝑑 (−∆𝑇𝑜𝑑 𝑐(𝑓 ∗ ) − 𝑔𝑜𝑑𝑁𝐴
) 2
With:
𝑓 ∗ ∈ 𝑆𝑓
An example of stochastic equilibrium using a logit path choice model for a two-link/path network
is given in Fig. 2. The stochastic equilibrium pattern is obtained at the intersection of the curves
representing the supply and (inverse) demand equations. Note that the stochastic equilibrium
configuration does not correspond to equal (systematic) costs on the two paths, which means that
the intersection point of the two curves does not correspond to a zero value of the difference g1 −
g2. In other words, at stochastic equilibrium, some travelers have higher (systematic) path costs
than others. This result obviously depends on the assumptions made about path choice behavior.
The perceived path cost is modeled as a random variable and therefore some users may choose
higher (systematic) cost paths because they perceive them as the least cost.
Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

Fig. 2 Example of Stochastic User Equilibrium (SUE; θ = 100).

Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

Existence of Stochastic User Equilibrium Link Flows. The fixed-point model has at least one
solution if the cost function c = c (f) and the path choice function pod = pod (Vod) (which defines
the stochastic uncongested network assignment function f = f SUN(c; d)) are both continuous.
The equilibrium solution f ∗ is a fixed point of the composite function y = f SUN(c(x)) which, under
the above assumptions (and for a connected network), is a continuous function defined over the
nonempty, compact, and convex set Sf. Furthermore, the function y = f SUN(c(x)) assumes values
only in the feasible set Sf.
Monotonicity of the Stochastic Uncongested Network Assignment Function. If the path choice
model is defined by a nondecreasing monotone function of the systematic utility, as in the case of
the additive probabilistic model, the stochastic uncongested network assignment function is
monotone nonincreasing with respect to link costs. Thus, if the cost of one or more of the links
increases, the flow (or flows) on these links decreases, and vice versa. This property is formally
expressed as:
́ (c ′ − c ′′)≤ 0
(𝑓𝑆𝑈𝑁 (𝑐) − 𝑓𝑆𝑈𝑁 ∀c ′, c ′′
Given any two link cost vectors c ′ and c ′′, consider the following notation.
g ′𝑜𝑑 = ∆𝑇𝑜𝑑 c ′ + 𝑔𝑜𝑑
𝑁𝐴
V ′ 𝑜𝑑 = −g ′𝑜𝑑 P ′𝑜𝑑 = 𝑝𝑜𝑑 (V ′𝑜𝑑 )
h ′𝑜𝑑 = 𝑑𝑜𝑑 p ′𝑜𝑑 f ′ = ∑𝑜𝑑 ∆𝑜𝑑 h ′𝑜𝑑
g′′𝑜𝑑 = ∆𝑇𝑜𝑑 c ′′ + 𝑔𝑜𝑑
𝑁𝐴
V′′𝑜𝑑 = −g ′′ 𝑜𝑑 p′′ 𝑜𝑑 = 𝑝𝑜𝑑 (V ′′ 𝑜𝑑 )

h′′𝑜𝑑 = 𝑑𝑜𝑑 p′′𝑜𝑑 f ′′ = ∑𝑜𝑑 ∆𝑜𝑑 h′′𝑜𝑑

From the monotonicity of the cost functions, with f ′ = 𝑓1∗ ≠ f ′′ = 𝑓2∗ , it also follows that:
[𝑐1∗ − 𝑐2∗ ]𝑇 (𝑓1∗ − 𝑓2∗ ) > 0

Models for Deterministic User Equilibrium

Deterministic User Equilibrium (DUE) assignment is obtained by applying the equilibrium
approach for congested networks under the assumption of deterministic path choice behavior.
Deterministic equilibrium link flows f ∗ , path flows h ∗ , and the corresponding costs c ∗ and g ∗ can
be determined with a fixed-point model obtained by simultaneously applying the supply model
and the demand model, as in the stochastic equilibrium case (an alternative is to utilize the
deterministic uncongested network assignment map and flow-dependent cost functions). In this
case, however, there are some mathematical complications arising from the fact that the
deterministic demand model is expressed (such as the corresponding deterministic uncongested
network assignment map) by a one-to-many map.
Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

For this reason, the properties of deterministic equilibrium are usually studied through indirect
formulations. The most general is the variation inequality formulation based on the specification
of the deterministic demand model as the system of inequalities (7):
𝑔(ℎ∗ )𝑇 (ℎ − ℎ∗ ) ≥ 0 ∀ℎ ∈ 𝑆ℎ 3
By combining the demand model obtained by summing all O-D pairs with the supply model,
expression (3) is obtained. In the case of congested networks, therefore, the resulting path (or link)
flows correspond to the condition expressed by Wardrop’s first principle.
Equivalent variation inequality models expressed in terms of link flows are obtained by combining
the link cost functions with the inequality systems that represent deterministic uncongested
network assignment:
𝑐(𝑓 ∗ )𝑇 (𝑓 − 𝑓 ∗ ) ≥ 0 ∀𝑓 ∈ 𝑆𝑓 4

𝑐(𝑓 ∗ )𝑇 (𝑓 − 𝑓 ∗ ) + (𝑔𝑁𝐴 )𝑇 (ℎ − ℎ∗ ) ≥ 0 ∀𝑓 = ∆ℎ, ∀ℎ ∈ 𝑆ℎ 5

Expressions (4) and (3) apply, respectively, to cases with zero and nonzero nonadditive path costs.
Note that expressions (3)–(5) are different from those used for deterministic uncongested
assignments in that the path and link costs depend on flows. In the presence of nonadditive path
costs in terms of links, f ∗ and of the total nonadditive cost GNA∗ at deterministic equilibrium:
𝑐(𝑓 ∗ )𝑇 (𝑓 − 𝑓 ∗ ) + (𝐺 𝑁𝐴 − 𝐺 𝑁𝐴∗ ) ≥ 0
∀𝑓 = ∆ℎ, 𝐺 𝑁𝐴 = (𝑔𝑁𝐴 )𝑇 ℎ, ∀ℎ ∈ 𝑆ℎ 6
An example of deterministic user equilibrium assignment for a two-link/path network is shown in
Fig. 3. Note that the deterministic equilibrium flows correspond to the intersection point of the
supply and demand curves (in this case, step curves) and the result in costs that are equal for the
two paths since both are used.
Conditions ensuring the existence and uniqueness of deterministic equilibrium link flows and costs
are similar to those described for stochastic equilibrium. In particular, the continuity and
monotonicity of the cost functions guarantee, respectively, the existence and uniqueness of the
solution. It should be noted once again that these existence and uniqueness conditions are only
sufficient; there may exist nonmonotone cost functions that give rise to a unique equilibrium
vector.
Existence of Deterministic User Equilibrium Link Flows. The variation inequalities (3)–(5) have
at least one solution if the cost functions are continuous functions defined on the nonempty,
compact, and convex set of the feasible path flows Sh or link flows Sf.
The considerations regarding the continuity of cost functions discussed for SUE models apply also
for DUE models. The existence of equilibrium link flows ensures the existence of the
corresponding link costs c ∗ = c (f∗), and of path costs and flows g ∗ and h ∗.
Ph.D. Course Transportation Modeling Prof. Dr. Zainab Alkaissi
Lecture 8 2022-2023

Fig. 3 Example of Deterministic User Equilibrium (DUE).