Traffic Assignment

Lecture notes in Transportation Systems Engineering

4 August 2009

1 Introduction

The process of allocating given set of trip interchanges to the specified transportation system is usually refered to as traffic assignment. The fundamental aim of the traffic assignment process is to reproduce on the transportation system, the pattern of vehicular movements which would be observed when the travel demand represented by the trip matrix, or matrices ,to be assigned is satisfied. The major aims of traffic assignment procedures are:

1. To estimate the volume of traffic on the links of the network and possibly the turning movements at intersections.
2. To furnish estimates of travel costs between trip origins and destinations for use in trip distribution.
3. To obtain aggregate network measures, e.g. total vehicular flows, total distance covered by the vehicle, total system travel time.
4. To estimate zone-to-zone travel costs(times) for a given level of demand.
5. To obtain reasonable link flows and to identify heavily congested links.
6. To estimate the routes used between each origin to destination(O-D) pair.
7. To analyse which O-D pairs that uses a particular link or path.
8. To obtain turning movements for the design of future junctions.

The types of traffic assignment models are all-or-nothing assignment, incremental assignment, capacity restraint assignment, user equilibrium assignment (UE), stochastic user equilibrium assignment (SUE), system optimum assignment (SO), etc. These frequently used models are discussed here.

1.1 All-or-nothing assignment

In this method the trips from any origin zone to any destination zone are loaded onto a single, minimum cost, path between them. This model is unrealistic as only one path between every O-D pair is utilised even if there is another path with the same or nearly same travel cost. Also, traffic on links is assigned without consideration of whether or not there is adequate capacity or heavy congestion; travel time is a fixed input and does not vary depending on the congestion on a link. However, this model may be reasonable in sparse and uncongested networks where there are few alternative routes and they have a large difference in travel cost. This model may also be used to identify the desired path : the path which the drivers would like to travel in the absence of congestion. In fact, this model's most important practical application is that it acts as a building block for other types of assignment techniques.It has a limitation that it ignores the fact that link travel time is a function of link volume and when there is congestion or that multiple paths are used to carry traffic.

1.2 Incremental assignment

Incremental assignment is a process in which fractions of traffic volumes are assigned in steps.In each step, a fixed proportion of total demand is assigned, based on all-or-nothing assignment. After each step, link travel times are recalculated based on link volumes. When there are many increments used, the flows may resemble an equilibrium assignment ; however, this method does not yield an equilibrium solution. Consequently, there will be inconsistencies between link volumes and travel times that can lead to errors in evaluation measures. Also, incremental assignment is influenced by the order in which volumes for O-D pairs are assigned, raising the possibility of additional bias in results.

1.3 Capacity restraint assignment

Capacity restraint assignment attempts to approximate an equilibrium solution by iterating between all-or-nothing traffic loadings and recalculating link travel times based on a congestion function that reflects link capacity. Unfortunately, this method does not converge and can flip-flop back and forth in loadings on some links.

1.4 User equilibrium assignment (UE)

The user equilibrium assignment is based on Wardrop's first principle, which states that no driver can unilaterally reduce his/her travel costs by shifting to another route. If it is assumed that drivers have perfect knowledge about travel costs on a network and choose the best route according to Wardrop's first principle, this behavioural assumption leads to deterministic user equilibrium. This problem is equivalent to the following nonlinear mathematical optimization program,

$${\mathrm Minimize  }Z = \sum_{a}\int_0^{x_{a}}t_{a}(x_{a})dx,$$ (1)

$${\mathrm subject  to  } \sum_{k}f_k^{rs} = q_{rs} :\forall r,s$$

$$x_a = \sum_r \sum_s \sum_k \delta_{a,k}^{rs}f_k^{rs} :\forall a$$

$$f_k^{rs} \geq 0 : \forall  k,r,s$$

$$x_a \geq 0 : a \in 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.

1.5 System Optimum Assignment (SO)

The system optimum assignment is based on Wardrop's second principle, which states that drivers cooperate with one another in order to minimise total system travel time. This assignment can be thought of as a model in which congestion is minimised when drivers are told which routes to use. Obviously, this is not a behaviourally realistic model, but it can be useful to transport planners and engineers, trying to manage the traffic to minimise travel costs and therefore achieve an optimum social equilibrium.

$${\mathrm Minimize  }Z = \sum_{a} x_{a}t_{a}(x_{a})$$ (2)

$${\mathrm subject  to  } \sum_{k}f_k^{rs} = q_{rs} :\forall r,s$$

$$x_a = \sum_r \sum_s \sum_k \delta_{a,k}^{rs}f_k^{rs} :\forall a$$

$$f_k^{rs} \geq 0 : \forall  k,r,s$$

$$x_a \geq 0 : a \in A$$

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

1.6 Example 1

To demonstrate how the most common assignment works, an example network is considered. This network has two nodes having two paths as links.

Let us suppose a case where travel time is not a function of flow as shown in other words it is constant as shown in the figure below.

Figure 1: Two Link Problem with constant travel time function

1.6.1 All or nothing

The travel time functions for both the links is given by:

$$\begin{eqnarray*} t_1 &=& 10\\ t_2 &=& 15 \end{eqnarray*}$$

and total flows from 1 to 2.

$$\begin{eqnarray*} q_{12} &=& 12 \end{eqnarray*}$$

Since the shortest path is Link 1 all flows are assigned to it making $x_1^*$ =12 and $x_2^*$ = 0.

1.6.2 User Equilibrium

Substituting the travel time in equations 1 - 5 yield to

$$\begin{eqnarray*} min:   Z(x)&=& \displaystyle\int^{x_1}_0 10 dx_1 + \int^{x_2}_0 15 dx_2 \\ &=& 10x_1 + 15x_2 \\ st:   x_1 + x_2 &=& 12. \end{eqnarray*}$$

Substituting $x_2= x_1-12$, in the above formulation will yield the unconstrained formulation as below :

$$\begin{eqnarray*} min Z(x)&=&10x_1 + 15(12-x_1) \end{eqnarray*}$$

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^*$ = 12, $x_2^*$ = 0.

1.6.3 System Optimization

Substituting the travel time in equation: (6-8), we get the following:

$$\begin{eqnarray*} min:  Z(x) &=& {x_1}\times({10}) + {x_2}\times({15}) \\ & =& 10{x_1} + 15{x_2} \end{eqnarray*}$$

Substituting $x_2=12-x_1$ the above formulations takes the following form:

$$\begin{eqnarray*} min:   Z(x)&=&10{x_1} + 15{(12-x_1)} \end{eqnarray*}$$

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^*$ = 12, $x_2^*$= 0, and $Z(x^*)$ = 120.

1.6.4 Comparison of results

After solving each of the formulations the results are tabulated in Table 1. One can infer that if the travel time is independent of the flow, then essentially there in no difference between the various assignment types.

Table 1: Comparison of results for example 1

Type	$t_1$	$t_2$	$x_1$	$x_2$	$Z(x^*)$	TSTT
AON	10	15	12	0	120	120
UE	10	15	12	0	120	120
SO	10	15	12	0	120	120

1.7 Example 2

Figure 2: Two Link Problem with variable travel time function

Lets now take a case where travel time functions for both the links is given by:

$$\begin{eqnarray*} t_1 &=& 10+3x_1\\ t_2 &=& 15+2x_2 \end{eqnarray*}$$

and total flows from 1 to 2.

$$\begin{eqnarray*} q_{12} &=& 12 \end{eqnarray*}$$

1.7.1 All or Nothing Assignment

Assume $x_1,x_2=0$ which makes $t_1=1$0 and $t_2=15$. Since the shortest path is Link 1 all flows are assigned to it making $x_1$ =12 and $x_2$ = 0.

1.7.2 User Equilibrium

Substituting the travel time in equations 1 - 5 yield to

$$\begin{eqnarray*} min:   Z(x)&=& \int^{x_1}_0 (10+3x_1) dx_1\\ && + \int^{x_2}_... ...x_1^2}{2} + 15x_2 + \frac{2x_2^2}{2},\\ st:   x_1 + x_2 &=& 12. \end{eqnarray*}$$

Substituting $x_2=12-x_1$, in the above formulation will yield the unconstrained formulation as below:

$$\begin{eqnarray*} min:  Z(x)&=& 10x_1 + \frac{3x_1^2}{2}, \\ && + 15(12-x_1) + \frac{2(12-x_1)^2}{2}. \end{eqnarray*}$$

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.

1.7.3 System Optimization

Substituting the travel time in equation: (6-8), we get the following:

$$\begin{eqnarray*} min:  Z(x)&=& {x_1}\times({10+3x_1}) + {x_2}\times({15+2x_2}) \\ &=& 10{x_1}+3{x_1}^2 + 15{x_2}+2{x_2}^2 \end{eqnarray*}$$

Substituting $x_2= x_1-12$

$$\begin{eqnarray*} min:  Z(x) &=& 10{x_1}+3{x_1}^2\\ &+& 15{(12-x_1)}+2{(12-x_1)}^2 \end{eqnarray*}$$

Differentiate the above equation w.r.t zero, and solving for $x_1$ and then $x_2$ leads to the solution $x_1^*$ = 5.3, $x_2^*$= 6.7, and $Z(x^*)$ = 327.55.

1.7.4 Comparison of results

After solving each of the formulations the results are tabulated in Table 2. One can infer that unlike earlier, the various assignment types shows considerable differences in the performace. AON has obviously the worst solution and SO has the best.

Table 2: Comparison of results for example 2

Type	$t_1$	$t_2$	$x_1$	$x_2$	$Z(x^*)$	TSTT
AON	10	15	12	0	467.44	552
UE	27.4	27.4	5.8	6.2	239.0	328.8
SO	30.1	25.6	5.3	6.7	327.5	327.5

1.8 Stochastic user equilibrium assignment

User equilibrium assignment procedures based on Wardrop's principle assume that all drivers percieve costs in an identical manner. A solution to assignment problem on this basis is an assignment such that no driver can reduce his journey cost by unilaterally changing route. Van Vilet considered as stochastic assignmnet models, all those models which explicitly allows non minimum cost routes to be selected. Virtually all such models assume that drivers perception of costs on any given route are not identical and that the trips between each O-D pair are divided among the routes with the most cheapest route attracting most trips. They have important advantage over other models because they load many routes between individual pairs of network nodes in a single pass through the tree building process,the assignments are more stable and less sensitive to slight variations in network definitions or link costs to be independent of flows and are thus most appropriate for use in uncongested traffuc conditions such as in off peak periods or lightly trafficked rural areas.

1.9 Dynamic Assignment

Dynamic user equilibrium,expressed as an extension of Wardrop's user equilibrium principle, may be defined as the state of equilibrium which arises when no driver an reduce his disutility of travel by choosing a new route or departure time,where disutility inclues, schedule delay in addition in to costs generally considered. Dynamic stochastic equilibrium may be similarly defined in terms of percieved utility of travel. The existence of such equilibria in complex networks has not been proven theoretical and even if they exist the question of uniqueness remains open.

2 Limitation of conventional assignment models

The specific limitations of the assignment models are highlighted below.

1. Most of the cost functions, such as the BPR function, do not take into consideration emission-related factors.
2. Interactions between links are not considered; the travel time on one link is independent of the volumes on other links. This is an obvious oversimplification. At intersections, link travel times are affected by volumes on other approaches and opposing left turns. On freeways, merging and weaving conditions can greatly affect travel times. Queuing caused by bottlenecks on other links can also be a factor. Queues build as volumes approach the bottleneck
3. Although some software packages allow node-based capacities, delays, or performance functions which allows for better modeling of intersection dynamics. However, many of the problems described above cannot be eliminated through network solutions. Some of these issues can be addressed by considering the effects of flows on other links and the delays at a junction, on the link under investigation.

Bibliography

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.