User Equilibrium AssignmentTrip Assignment
Theory
User Equilibrium AssignmentThe user equilibrium assignment is based on Wardrop's first principle. If one ignores stochastic effects and concentrates on capacity restraint as a generator of a spread of trips on a network, one should consider a different set of models. For a start, capacity restraint models have to make use of functions relating flow to the cost (time) of travel on a link. These models usually attempt, with different degrees of success, to approximate to the equilibrium conditions as formally enunciated by Wardrop(1952):
Under equilibrium conditions traffic arranges itself in congested networks in such a way that no individual trip maker can reduce his path costs by switching routes. If all trip makers perceive costs in the same way (no stochastic effects): Under equilibrium conditions traffic arranges itself in congested networks such that all used routes between an O-D pair have equal and minimum costs while all unused routes have greater or equal cost.
This is usually referred to as Wardrop's first principle, or simply Wardrop's equilibrium. It is easy to see that if these conditions did not hold, at least some drivers would be able to reduce their costs by switching to other routes. This problem is equivalent to the following nonlinear mathematical optimization program,
$$\nonumber Minimize\ Z\ =\ \sum\limits_{a} \int_0^{x_a} t_a(x_a)dx$$ $$\nonumber Subject\ to\ \sum\limits_{k} f_k^{rs}\ =\ q_{rs}\ \: \ \forall r,s $$ $$\nonumber x_a = \sum\limits_{r}\sum\limits_{s}\sum\limits_{k} \delta_{a,k}^{rs} f_k^{rs}\ \:\ \forall a $$ $$\nonumber f_k^{rs}\ \geqslant 0\ \:\ \forall k,r,s $$ $$\nonumber x_a\ \geqslant 0\ \:\ a\epsilon A$$
$k$ is the path,$x_a$ equilibrium flows in link a, $t_a$ travel time on link a, $f_k^{rs}$ flow on path k connecting O-D pair r-s, $q_{rs}$ trip rate between r and s.
The equations above are simply flow conservation equations and non negativity constraints, respectively. These constraints naturally hold the point that minimizes the objective function. These equations state user equilibrium principle. The path connecting O-D pair can be divided into two categories : those carrying the flow and those not carrying the flow on which the travel time is greater than (or equal to)the minimum O-D travel time. If the flow pattern satisfies these equations no motorist can better off by unilaterally changing routes. All other routes have either equal or heavy travel times. The user equilibrium criteria is thus met for every O-D pair. The UE problem is convex because the link travel time functions are monotonically increasing function, and the link travel time a particular link is independent of the flow and other links of the networks. To solve such convex problem Frank Wolfe algorithm is useful.
The Bureau of Public Roads (BPR) developed a link congestion function as given below
$T = T_0\{ 1 + \alpha {(\dfrac{V}{C})}^\beta \}$
$\alpha$ = Multiplication coefficient (standard value = 0.25, range (0,1))
$\beta$ = Exponential coefficient (standard value = 4, range is positive real number)
Heuristic Equilibrium Techniques
- Capacity Restraint
- Incremental Assignment
Following are the algorithms for solving these assignment techniques
Capacity Restraint
- Step 0: Initialization,$t_a^0\ =t_a(0).$ Obtain $\{x_a^0\}$ by performing all or nothing assignment. Set $n=1$.
- Step 1: Update: Set $\eta_a^n\ =\ t_a(x_a^{n-1}),\forall a$.
- Step 2: Set $t_a^n\ =\ 0.75t_a^{n-1}\ +\ 0.25\eta_a^n,\ \forall a$.
- Step 3: Perform all or nothing assignment based on $\{t_a^n\}$ which yields $\{x_a^n\}$.
- Step 4: If $n = N$, go to step 5. Otherwise,set $n = n + 1$ and go to step 1.
- Step 5: Set $x_a^*\ =\ 0.25\sum\limits_{i=0}^3\ \forall a$ and stop. $\{x_a^*\}$ are link flows at equilibrium.
- Step 0: Divide each origin-destination entry into $N$ equal portions $(q_{rs}^n =\dfrac {q_{rs}}{N})$. Set $n=1$ and $x_a^0\ =\ 0,\ \forall a$.
- Step 1: Set $t_a^n = t_a(x_a^{n-1}),\ \forall a$.
- Step 2: Flow $\{w_a^n\}$ is obtained from all or nothing assignment based on $\{t_a^n\}$ and using trip rates $q_{rs}^n$ for each O-D pair.
- Step 3: Set $x_a^n= x_a^{n-1} + w_a^n$.
- Step 4: If $n=N$, stop otherwise set $n=n+1$ and go to step 1.
The Convex Combination Method
- Step 0: Initialization, $t_a^0=t_a(0)$. Obtain $\{x_a^0\}$ by performing all or nothing assignment. Set $n=1$.
- Step 1: Set $t_a^n=t_a(x_a^{n-1}),\ \forall a$.
- Step 2: Perform all or nothing based on $\{t_a^n\}$ which yields auxiliary flows $\{y_a^n\}$
- Step 3: Line search. Solve
$min_{\begin{subarray}{rl} {0 \le \alpha \le 1}\cr\end{subarray}} \sum \limits_{a} \int_a^{x_a^n + \alpha (y_a^n - x_a^n)}t_a(\omega)d\omega $. - Step 4: Set $x_a^n + \alpha (y_a^n - x_a^n)\ \forall a$.
- Step 5: If the convergence criteria is met stop the solution otherwise set $n = n + 1$ and go to step 1.
In this lab you can perform three types of user equilibrium experiments depending on the convergence criteria.
- Convergence criteria as $\alpha$ will be used to optimize the maximum optimum move size.
- Convergence criteria as Time
Let $u_{rs}^n$ = minimum path travel time between OD pair r-s at $n^{th}$ iteration.$\sum\limits_{rs} \dfrac{(| u_{rs}^n - u_{rs}^{n-1}|)}{u_{rs}^n}\le \kappa$
- Convergence criteria as Flow
$ \sqrt {\sum\limits_{a} \dfrac{{( x_a^{n+1} - x_a^n)}^2}{\sum\limits_{a} x_a^n}} \le \kappa $
Example
To demonstrate how the most common assignment works, an example network is considered. This network has two nodes having two paths as links.
Lets take a case where travel time functions for both the links is given by:
$t_1=10+3x_1$
$t_2=15+2x_2$
and total flows from 1 to 2.
$q_{12}=12$
Substituting the travel time in formulation of user equilibrium yield to
$min \colon Z( x ) = \int_0^{x_1}(10+3x_1)dx_1+\int_0^{x_2}(15+2x_2)dx_2 $
$10 x_1+(\dfrac{3 x_1^2}{2})+15 x_2+(\dfrac{2 x_2^2}{2})$
$st \colon x_1 + x_2 = 12$
Substituting, $x_2 = 12 - x_1$ in the above formulation will yield the unconstrained formulation as below :
$10x_1+(\dfrac{3x_1^2}{2})+15(12-x_1)+{(12-x_1)}^2$
Differentiate the above equation w.r.t $x_1$ and equate to zero, and solving for $x_1$ and then $x_2$ leads to the solution $x_1^*=5.8,x_2^*=6.2,Z(x^*)=239.0$
References Books
- J. De D. Ortuzar and L.G. Willumsen (1996), Modelling Transport. Wiley Publications, London.
- Y. Sheffi (1985), Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall Inc., Englewood Cliffs, New Jersey.