Trip Assignment - (contd...)
Lecture Notes in Transportation Systems Engineering
Contents
_________________________________________________________________________________________
1 Introduction
This chapter covers a numerical method to solve traffic assignmenr by user equilibrium or system
optimum method. The method is known as Frank-Wolfe algorithm or convex combination
algorithm.
2 Frank-Wolfe Algorithm for UE
- Step 0: Initilize
- Set n = 1, ta = ta(0) ∀a
- Do AON →{xan}
- Step 1: Update
- Set tan = t
a(xan)
- Step 2: Direction finding
- Do AON based on tan →{y
an}
- where {yan} is the auxiliary flow
- Step 3: Line search
- Find αn* that solves

- Step 4: Move
- Set xan+1 = x
an + α
n*(y
an - x
an)
- Step 5: Convergence
- If |xan+1 - x
an|≤ ϵ ∀a then STOP
- else set n = n + 1, go to step 1.
2.1 Numerical Example
To demonstrate the Frank-Wolfe algorithm, consider an example network give in figure 1. This
network has two nodes having two paths as links. The travel time is a function of link flow for both
the links and is given as: t1 = 10 + 3x1 and t2 = 15 + 2x2, and total flows from 1 to 2 is given as
q12 = 12. Do an UE assignment using Frank-Wolfe algorithm and show two full iterations.
Solution
- Step 0: Initilize
- Set n = 1, t11 = t
11(0) = 10, t
21 = t
21(0) = 15
- Doing AON
x11 = 12, x
21 = 0
- Step 1: Update
- Setting t11 = t
1(x11) = t
1(15) = 10 + 3 × 15 = 46
- and t21 = t
2(x21) = t
2(0) = 15 + 2 × 0 = 15
- Step 2: Direction finding
- Doing AON based on t11 and t
21
y
11 = 0, y
21 = 12.
- Step 3: Line search
- Setting u1 = x11 + α
1(y11 - x
11) = 12 + α
1(0 - 12) = 12 - 12α1,
- Setting u2 = x21 + α
1(y21 - x
21) = 0 + α
1(12 - 0) = 12α1,
- Writing the objective function in terms of α1*
- Solving by taking
= 0
α* = 0.517
- Step 4: Move
- Get x1 = 12 - 12α = 12 - 12 × 0.517 = 5.796
- Get x2 = 12α = 12 × 0.517 = 6.204
- Step 5: Convergence
- If |xan+1 - x
an|≤ ϵ ∀a then STOP
- else set n = n + 1, go to step 1.
Exercises
- Not Available
References
- R Thomas. Traffic Assignment Techniques. Avebury Technical publication,England,
1991.
Acknowledgments
I wish to thank several of my students and staff of NPTEL for their contribution in this lecture. I
also appreciate your constructive feedback which may be sent to tvm@civil.iitb.ac.in
Prof. Tom V. Mathew
Department of Civil Engineering
Indian Institute of Technology Bombay, India
____________________________________________________________________________________________
Thu Jan 10 12:41:24 IST 2019