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 All-OR-Nothing Assignment

Numerical illustartion: under preparation.

3 Frank-Wolfe Algorithm for UE

1. Step 0: Initilize

   1. Set \(n=1\), \(t_a=t_a(0)~~~\forall a\)
   2. Do \(AON \rightarrow \{x_a^n\}\)

2. Step 1: Update

   1. Set \(t_a^n=t_a(x_a^n)\)

3. Step 2: Direction finding

   1. Do \(AON\) based on \(t_a^n \rightarrow \{y_a^n\}\)
   2. where \(\{y_a^n\}\) is the auxiliary flow

4. Step 3: Line search

   1. Find \(\alpha _n^*\) that solves \[\min _{0\le \alpha _n \le 1} \sum _a \int _{o}^{x_a^n+\alpha _n(y_a^n-x_a^n)} t_a(x)dx\]

5. Step 4: Move

   1. Set \(x_a^{n+1}=x_a^n+\alpha _n^* (y_a^n-x_a^n)\)

6. Step 5: Convergence

   1. If \(| x_a^{n+1}-x_a^n |\le \epsilon ~~~\forall a\) then STOP
   2. else set \(n=n+1\), go to step 1.

3.1 Numerical Example

To demonstrate the Frank-Wolfe algorithm, consider an example network give in figure 2. 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: \(t_1=10+3x_1\) and \(t_2=15+2x_2\), and total flows from 1 to 2 is given as \(q_{12}=12\). Do an UE assignment using Frank-Wolfe algorithm and show two full iterations.

Solution

1. Step 0: Initilize

   1. Set \(n=1\), \(t_1^1=t_1^1(0)=10\), \(t_2^1=t_2^1(0)=15\)
   2. Doing \(AON \implies x_1^1=12, ~ x_2^1=0\)

2. Step 1: Update

   1. Setting \(t_1^1=t_1(x_1^1)=t_1(15)=10+3\times 15=46\)
   2. and \(t_2^1=t_2(x_2^1)=t_2(0)=15+2\times 0=15\)

3. Step 2: Direction finding

   1. Doing \(AON\) based on \(t_1^1\) and \(t_2^1\) \(\implies y_1^1=0,~y_2^1=12\).

4. Step 3: Line search

   1. Setting \(u_1=x_1^1+\alpha _1(y_1^1-x_1^1)=12+\alpha _1(0-12)=12-12\alpha _1\),
   2. Setting \(u_2=x_2^1+\alpha _1(y_2^1-x_2^1)=0+\alpha _1(12-0)=12\alpha _1\),

   3. Writing the objective function in terms of \(\alpha _1^*\)

      \begin {eqnarray*} \min _{0\le \alpha _1 \le 1} Z &=& \sum _a \int _{0}^{u_1} (10+3\times x)~dx + \int _{0}^{u_2} (15+2\times x)~dx \\ &=&\left .{10x_1+\frac {3x_1^2}{2}}\right \vert _{0}^{u_1}+ \left .{15x_1+\frac {2x_2^2}{2}}\right \vert _{0}^{u_2}\\ &=&10(12-12\alpha )+\frac {3}{2}(12-12\alpha )^2+15(12\alpha )+(12\alpha )^2 \end {eqnarray*}
   4. Solving by taking \(\frac {dz}{d\alpha }=0\) \(\implies \alpha ^*=0.517\)

5. Step 4: Move

   1. Get \(x_1=12-12\alpha =12-12\times 0.517=5.796\)
   2. Get \(x_2=12\alpha =12\times 0.517=6.204\)

6. Step 5: Convergence

   1. If \(| x_a^{n+1}-x_a^n |\le \epsilon ~~~\forall a\) then STOP
   2. else set \(n=n+1\), go to step 1.

Exercises

1. Not Available

References

1. Yosef Sheffi. Urban transportation networks: Equilibrium analysis with mathematical programming methods. New Jersey, 1984.
2. 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 Instiute of Technology Bombay, India.