Trip Assignment - (contd...)

Lecture Notes in Transportation Systems Engineering

Prof. Tom V. Mathew

Contents

1 Introduction
2 Frank-Wolfe Algorithm for UE
 2.1 Numerical Example
Exercises
References
Acknowledgments
_________________________________________________________________________________________

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

  1. Step 0: Initilize
    1. Set n = 1, ta = ta(0)   ∀a
    2. Do AON →{xan}
  2. Step 1: Update
    1. Set tan = t a(xan)
  3. Step 2: Direction finding
    1. Do AON based on tan →{y an}
    2. where {yan} is the auxiliary flow
  4. Step 3: Line search
    1. Find αn* that solves
      ∑ ∫ xna+αn(yna-xna) min ta(x)dx 0≤ αn≤1 a o
  5. Step 4: Move
    1. Set xan+1 = x an + α n*(y an - x an)
  6. Step 5: Convergence
    1. If |xan+1 - x an|≤ ϵ   ∀a then STOP
    2. 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.

PIC

Figure 1: Two link problem for solving UE assignment by Franl-Wolfe algorithm

Solution

  1. Step 0: Initilize
    1. Set n = 1, t11 = t 11(0) = 10, t 21 = t 21(0) = 15
    2. Doing AON= ⇒x11 = 12, x 21 = 0
  2. Step 1: Update
    1. Setting t11 = t 1(x11) = t 1(15) = 10 + 3 × 15 = 46
    2. and t21 = t 2(x21) = t 2(0) = 15 + 2 × 0 = 15
  3. Step 2: Direction finding
    1. Doing AON based on t11 and t 21 =⇒y 11 = 0, y 21 = 12.
  4. Step 3: Line search
    1. Setting u1 = x11 + α 1(y11 - x 11) = 12 + α 1(0 - 12) = 12 - 12α1,
    2. Setting u2 = x21 + α 1(y21 - x 21) = 0 + α 1(12 - 0) = 12α1,
    3. Writing the objective function in terms of α1*
      ∑ ∫ u1 ∫ u2 min Z = (10 + 3 × x) dx + (15 + 2 × x) dx 0≤α1≤1 a 0 0 3x2||u1 2x2 ||u2 = 10x1 + --1|| + 15x1 + ---2|| 2 0 2 0 3- 2 2 = 10 (12 - 12 α) + 2(12 - 12α ) + 15 (12α) + (12α)
    4. Solving by taking ddzα = 0 =⇒α* = 0.517
  5. Step 4: Move
    1. Get x1 = 12 - 12α = 12 - 12 × 0.517 = 5.796
    2. Get x2 = 12α = 12 × 0.517 = 6.204
  6. Step 5: Convergence
    1. If |xan+1 - x an|≤ ϵ   ∀a then STOP
    2. else set n = n + 1, go to step 1.

Exercises

  1. Not Available

References

  1. 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