TRAFFIC ASSIGNMENT

Traffic Assignment
 Outline
2

1. Introduction
2. Assignment types and modeling methods
3. User equilibrium (UE) assignment
4. Solution methods and issues
5. Validation
 Overview
3

 The procedure used to obtain

expected traffic volume on the
network is known as trip assignment.
Traffic Assignment
 Final step: Traffic assignment
 What: When a person decides where to go and which
mode to use, he/she has to decide on the route to take
 Alternatives: The set of O-D routes in the route choice
set for the person
 Why: Traffic assignment estimates the route/link flows
and travel times in the network
Traffic Assignment
 Traffic assignment
 How: By distributing the total O-D demand between
various routes for that O-D pair
 Network loading mechanism: The process of loading O-
D trip table to the network links
 Difficulty: Individuals are not homogenous
 Behavior: Different individuals behave differently based on
their socio-economic characteristics and past experience
 Choice set: Different individuals may have different route
choice sets
 Objective: Routing objective may differ across individuals
 Assignment Definition
6

 Given
 A graph representation of the urban transportation network
 The associated link performance functions, and

 An origin-destination matrix

 Find
 the flow and the associated travel time on each of the
network links.
 This problem is known as that of traffic assignment as
the objective is to assign the O-D matrix onto the
network.
Significance
 Significance of traffic assignment
 Represents the “basic” level of what we mean by “traffic
conditions”
 Essential to make planning, operational, renewal, and policy
decisions
 Provides “feedback” to trip distribution and mode split steps
of the 4-step model
 Provides input to assess and influence energy and
environmental impacts
 Aids transportation operators in making “supply” decisions
 Key methodological engine for intelligent transportation
systems (ITS) applications
Cost Function
 Conventional Economics: Demand (D) and Supply (S)
 Equilibrium between D&S defines the price
 Equilibrium point
 Marginal cost=Marginal revenue f
 In TA Cost is a function of a number of attributes
 Distance
 Free Flow Speed
 Capacity
 Speed-Flow Relationship
 Fares, Fuel, ………
 Demand=Origin-Destination (OD) matrix
 Supply=Network Capacity
Dimensions
 Some dimensions of traffic assignment
 Mode: Non-scheduled, scheduled (transit)
 Time: Static, dynamic
 Randomness/uncertainty: Deterministic, stochastic
(demand and/or supply)
 Objective: User equilibrium (UE), system optimal (SO),
boundedly-rational (BR)
 Behavior: Several factors (such as familiarity, risk
willingness, etc.)
 Function: Descriptive, prescriptive
Dimension-Mode
 (Road) Traffic assignment
 Assign non-scheduled O-D trip demand for each O-D pair
 Transit assignment
 Assign passengers who use the routes on a transit network
using the transit O-D demand
 Increasing future importance as transit (bus, rail, etc.)
becomes a preferred solution
 Intermodal assignment
 Assign intermodal trips (such as park-and-ride, ferry and
bus)
 Increasingly important in the future
 Future research needs
Dimension-Time
 Static traffic assignment
 Time is not a consideration
 O-D trip rate is constant
 Link travel times are constant
 Appropriate for analysis of “off-peak” and/or homogenous conditions
 Useful for long-term planning purposes

 Dynamic traffic assignment (DTA)

 Time-dependency of traffic conditions is explicitly considered
 O-D trip demand and travel times (flows) are time-dependent
 Appropriate for “peak-period” analyses and to capture time-dependency when
it is a significant aspect of the analysis
 Useful for real-time operations and management, including for assessing various
ITS strategies
 In recent years, used for planning applications
Dimension-Objective
 User equilibrium assignment
 Will be discussed in detail later
 User behavior is “selfish”
 Reasonable estimate of actual driver behavior
 Equilibrium
 Adequate for long-term planning
 System optimal assignment
 “Socially optimal”
 Seeks best system performance
 Behaviorally untenable; not an equilibrium
 Requires coordination and/or collaboration
 Provides a benchmark for comparing various traffic management strategies
 Useful for developing prescriptive traffic strategies
 Useful for many ITS applications
Dimension- Objective
 Deterministic assignment
 Demand, supply, performance aspects are known a priori
 Focus is on randomness, not time-dependency

 Stochastic assignment
 One or more of demand, supply, and performance
characteristics have randomness
 Useful for modeling heterogeneity in individuals

 For example, stochastic user equilibrium (SUE) assumes that

individuals perceive link/route travel times differently
(based on their behavioral tendencies)
Assignment Types
Trip
Assignment

Transit Traffic
Assignment Assignment

Static TA

Dynamic
TA
Static Traffic Assignment-Assumptions

 Standard assumptions
 O-D demand is constant (does not vary with time)
 Link travel times are time-invariant

 A route flow exists on all the links comprising that route

simultaneously
 Performance function: Travel time on a link depends
only on the flow on that link and does not depend on
flows on other links (though this assumption is not
necessary)
Link Performance Functions
 Mathematical Relationship Between Traffic Flow and
16
Travel Time
Linear Relationship Non-Linear Relationship
Route Travel Time

Capacity
Free-Flow
Travel Time
Traffic Flow Traffic Flow
 Link Performance Functions
17

 A steady-state link performance function is a

positive, increasing, and convex curve.

 Typical link performance functions do not consider

queued vehicles in the traffic stream
 Link Performance Functions
18

1.2
Travel time on link

1.2
1
Travel time on link

0.81
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0 500 1,000 1,500 2,000 2,500
0 500 1,000 1,500 2,000 2,500
Volume in Vehicles/hour
  0.15,   4.0 Volume in Vehicles/hour

 
V 
V=volume, C=capacity, t0=free flow travel time
t  t0 1     
  C  
Static UE Assignment
Static Traffic
Assignment

Stochastic Deterministic
Approach Approach

User User
equilibrium Equilibrium

System System
optimal Optimal
 Definition of Equilibria
20

 To solve the traffic assignment problem, it is

required that the rule by which motorists choose a
route be specified.
 It is reasonable to assume that every motorist will
try to minimize his or her own travel time when
traveling form origin to destination.
 A stable condition is reached only when no traveler
can improve his/her travel time by unilaterally
changing routes.
 Equilibrium
21

 UE definition implies that

 motorists have full information (choice set and travel times),
 motorists consistently make the correct route choice decision

 all motorists are identical in their behavior

 These assumptions can be partially relaxed in the

context of route choice under information provision.
 distinction between the travel time that individuals perceive
and the actual travel time
 This definition characterizes the stochastic-user-equilibrium
(SUE) condition.
 Wardrop’s Equillibrium
22

 Flow allocation rules

 Wardrop's first principle
“For each O-D pair, the journey times on all used routes are
equal, and less than or equal to those on any unused route”
 Defines User Equilibrium (UE) flow

 Wardrop's Second principle

“The total system travel time is minimum (that is, the average
journey time is minimum)”
 Defines System Optimal (SO) flow
UE Characteristics
 Characteristics
 At user equilibrium, the travel time on all used routes
are equal and less than or equal to those on any
unused route
 At user equilibrium, no user can improve his/her travel
time by unilaterally switching routes
UE-Assumptions
 Assumptions
 Individuals have full knowledge of travel times on all
possible routes
 All individuals are identical in their behavior (for
example, perceive travel time identically)
 Travel time is the only factor in the decision-making (all
individuals unilaterally seek to decrease their travel
times)
UE-Concept
 Example
 Given
 Network with 1 O-D pair and 2 routes (each route has just
one link)
 O-D demand = 10
 Link performance functions (shown on next slide)

 Determine UE:
 Route flows
 Travel times
 A simple example of UE
26
Link 1

O D qOD = x1 +x2

Link 2
t
t2(x2) t1(x1)

x
x2 x1
 Operational UE
27

Path 1 Path 2
Cost Cost

Trips on Path 1 Trips on Path 2

Operational definition of UE:

For each O-D pair, at user equilibrium, the travel time on all used paths is
equal, and (also) less than or equal to the travel time that would be
experienced by a single vehicle on any unused path.
 Example UE
28

(40 min)
100
(40
(30 min)

110 100
(65 min)

User Equilibrium is reached when no traveler can improve his

travel time by unilaterally changing routes.
UE-Example
Route 1

Demand = 10
O D

Route 2

  x1  
4

t1  10 1  0.15   

  2   t denotes time x
  x2  
 25 1  0.15 
4
denotes flow
t2  

  3  
Ref: Sheffi (1984)
UE-Example Concept
1000 600
link 1
900 x2 = 10 – x1
link 2 500
800
700
400
Travel time (t)

600
500 300
400
200
300
200
100
100
0 0
0 2 4 6 8 10
Flow (x)
UE-Example Concept

100 100
link 1
90 90
link 2
80 80
70 70
Travel time (t)

60 60
50 50
40 40
30 30
20 20
10 10
0 0
0 2 4 6 8 10
(x1)
Flow (x)
 Flow on link 2 (x2) = 10-x1

 x1=4.8, x2=5.2 ; t1=t2=59 (approx)

UE-Example Concept
100 100
link 1
90 Suppose that the 90
flow on link 1 is link 2
80 80
higher than the
70 equilibrium flow 70
Travel time (t)

60 60
Excess area
50 50
40 40
30 30
20 20
10 10
0 0
0 2 4 6 8 10
(x1)
Flow (x)

 Sum of area under the curves is minimum at equilibrium

point
Graphical Approach
 Problem with graphical approach
 Cannot be used when an O-D pair has more than two
routes
 Cannot be used when routes have more than one link,
and when some links are common to routes on the same
or different O-D pair
UE Approaches
 Heuristic methods (we will not talk in this presentation)
 All-or-nothing (AON)
 Capacity restraint

 Incremental assignment

 Analytical methods (Feasible direction methods)

 Frank-Wolfe (F-W) algorithm
 Link-based methods
 Modified F-W methods
 Origin-based methods
 Path-based methods
Analytical Approach
 Feasible direction methods
 Mathematical formulation for UE problem as an
optimization problem
 Consists of objective function and constraints

 Equivalency of optimization problem and UE conditions

 Formulating the Assignment Problem
36

 NOTATIONS
 Network G (N,A)
 N is set of consecutively numbered nodes
 A is a set of consecutively numbered arcs (links)
 R denote the set of origin centroids (which are the nodes at
which flows are generated)
 S denote the set of destination centroids (which are the nodes
at which flows terminate)
 qrs is the trip rate between origin “r” and destination “s” during
the period of analysis
 xa and ta, represent the flow and travel time, respectively, on link
a
 Formulating the Assignment Problem
37
NOTATIONS
ta  ta ( xa ) : where ta . represents the relationship between flow and travel time for link a
f krs : represents flow on path k connecting origin r and destination s such that path k  K rs
ckrs : is travel time on path k is the sum of the travel time on the links comprising this path.

ckrs   ta 
rs
k  K rs , r  R, s  S
a k

where
 krs  1 if link is part of path k connecting O-D pair r  s
 0 otherwise

Using the same indicator variable, the link flow can be expressed as
a function of the path flow, that is

xa   f krs ars,k

a r s
 User Equilibrium Formulation
38

xa

min z(x) =   t ( ) d
a
a
0

subject to
flow conservation constraint
f k
k
rs
 qrs  r, s
Non negativity constraint
f k
rs
0  k , r, s
xa   f  k
rs rs
a ,k a
a r s
𝑟𝑠 1 𝑖𝑓 𝑙𝑖𝑛𝑘 𝑎 𝑖𝑠 𝑜𝑛 𝑝𝑎𝑡ℎ 𝑘 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜 − 𝑑 𝑝𝑎𝑖𝑟 𝑟𝑠
𝛿𝑎,𝑘 =
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 definitional constraints
 Significance of User Equilibrium
39

 Significance:
 Reasonable assumption for representation of human
behavior
 In order to asses the network performance for given
demands UE conditions are assumed
 Limitations:
 Assumption that each user minimizes travel time implies
each user has perfect information on all conditions and
routes
 Individuals are assumed to behave identically
UE-Solution Method
 Developments
 Beckmann et al. (1956) proved the equivalency
between their transformation and UE problem
 They also proved that their formulation has unique
solution in terms of link flows
 Frank-Wolfe (F-W) algorithm (1956) was used to solve
Beckmann’s UE formulation (most commonly used)
 Since then many researchers have contributed to this
field and many algorithms have developed
F-W Formulation
 In Frank-Wolfe algorithm, the updated route flows in each iteration are
obtained by combining the current set of route flows with current all-or-
nothing assignment flows:
𝑛
(𝑛+1) 1 − 𝛼 𝑓𝑘𝑖𝑗 𝑘𝑖𝑗 ≠ 𝑘𝑖𝑗 ∗
𝑓𝑘𝑖𝑗 = 𝑛
1 − 𝛼 𝑓𝑘𝑖𝑗 + 𝛼𝑓𝑖𝑗 𝑘𝑖𝑗 = 𝑘𝑖𝑗 ∗

 In each iteration, the flow on minimum cost route increases and that on
other routes decreases for an O-D pair
 The shift of flows from expensive routes to the cheapest route is
proportional to current flow and step size
 The route flows are used to generate the link flows
 In terms of the link flows:
F-W Merits

 Merits
Easy to implement
Converges very fast in early iterations
Solution is much better than heuristic
techniques such as incremental
assignment
Requires less memory (RAM)
F-W Limitations

 Limitations
Tails badly into creep and is very slow
in reaching objective function minimum
(less efficient)
Provides only link flows, but for many
planning applications, we need route
flows
 UE Note
44

 Demand for travel depends on the activity pattern,

and hence not uniform over time and space.
 However transportation planners analyze networks
only for certain periods of the day – morning
peaks, evening peaks etc. depending on objective
of analysis
 => O-D flows are considered constant for such
analysis (steady-state) -> static assignment
 Flow is present simultaneously on all links of a path
(static conditions)
 System Optimal Assignment
45
xa
Total system travel time
min z(x)==
minz(x) xtaa (ta ()xda )
aa 0

subjecttoto
subject
flow conservation constraint
f f
kk
rsrs
kk qqrsrs r r, s, s
Non negativity constraint
f f 00
rsrs
kk kk, r, r, s, s
xa   f krs ars,k a Definitional constraint
a r s

𝑟𝑠 1 𝑖𝑓 𝑙𝑖𝑛𝑘 𝑎 𝑖𝑠 𝑜𝑛 𝑝𝑎𝑡ℎ 𝑘 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜 − 𝑑 𝑝𝑎𝑖𝑟 𝑟𝑠

𝛿𝑎,𝑘 =
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
 SO Properties
46

 The SO formulation is subject to the same set of

constraints as the UE problem and differs only in its
objective function

 The SO flow pattern does not generally represent

an equilibrium solution in congested networks

 Consequently, the SO flow pattern is not an

appropriate descriptive model of actual user
behavior
 Significance of System Optimal
47

1. In many transportation system analysis problem it is

useful to know the best performance possible for
the network and OD demand

2. This is useful for control action (pricing, tolling) as

well as to compare alternative solution strategies

3. Solution procedures for SO are virtually identical to

those for UE
 Solving UE
48
 Solving UE
49

 Substitute x2= 12-x1

 Differentiate w.r.t x1 and equate to zero

 x1= 5.8, x2 = 6.2.
 Solving SO
50

 Let us consider the same example

 For SO
 Solving SO
51

 Substitute x2= 12-x1

 Differentiate the equation and set it to zero

 x1 = 5.3,x2= 6.7
 Comparison of Methods
52

Type t1 t2 x1 x2 UE Z(x) SO Z(x)

AON 10.00 15.00 12.00 0.00 336.00 552.00
UE 27.40 27.40 5.80 6.20 239.90 328.80
SO 30.10 25.60 5.30 6.70 240.53 327.55
 Stochastic Methods
53

 Emphasize the variability in driver perception of cost

 Need to consider second best routes
 No perfect information about network characteristics
 Different travel costs perception
 Eliminates “zero volume” links
 Requires large number of iterations and hence a longer
run time
 See more in Modeling Transport by Ortuzar and Williumsen,
Chapter 10. or Sheffi (1984) Chapter 7
Stochastic Methods
 Need to consider second-best routes (in terms of
engineering or modelled costs);
 Generates additional problems as the number of
alternative second-best routes between each O–D
pairmay be extremely large
Stochastic Methods
 Several methods have been proposed to
incorporate these aspects but only two have
relatively widespread acceptance:
 simulation-based methods
 Uses ideas from stochastic (Monte Carlo) simulation to
introduce variability in perceived costs.
 proportion-based methods
 allocates flows to alternative routes from proportions
calculated using logit-like expressions.
Simulation Based Methods
 There is a distribution of perceived costs for each
link with the engineering costs as the mean
Simulation Based Methods
 Assumptions
 The distributions of perceived costs are assumed to be
independent.
 Drivers are assumed to choose the route that minimizes
their perceived route costs, which are obtained as the
sum of the individual link costs.
Proportional Stochastic Methods
 Virtually all these methods are based on a loading
algorithm which splits trips arriving at a node
between all possible exit nodes,
 as opposed to the all-or-nothing method which assigns
all trips to a single exit node.
 Very often the implementation of these methods
reverses the problem so that the division of trip at a
node is actually based upon where the trips are
coming from rather than where they are going to.
Proportional Based Methods
 Consider node B in Figure; there are a number of
possible entry points denoted by A1, A2, A3, A4
and A5 for trips from I to J.
 Splitting functions
 Model Validation
60

 Truck counts
 By vehicle class
 By facility type

 By time of day

 Screen lines

 Cordon lines

 Develop RMSE, R2 or other goodness-of-fit

measures
 Screenlines Example
61

Share of counts
per screenline

> 75%
50% - 75%
< 50%
 Model Validation Example
62

 All vehicles all day

140,000

120,000

100,000
R² = 0.7826

80,000
Simulation

60,000

40,000

20,000

0
0 20,000 40,000 60,000 80,000 100,000 120,000 140,000
Count
 63
Daily VMT Millions

10
20
30
40
50
60

0
Interstate

Freeways/
Observed

Expressways
Modeled

Other Principal
Arterial

Minor Arterial
VMT based comparison

Collector

Local
 Volume class comparison
64

140%

120%

100%

80%
%RMSE

60%

40%

20%

0%
<5,000 5,000- 10,000- 20,000- 30,000- 40,000- 50,000- 60,000- 70,000- 80,000- 90,000- >100,000
10,000 20,000 30,000 40,000 50,000 60,000 70,000 80,000 90,000 100,000
Volume Class