Editing Route assignment (section)

==General Approaches==
===Long-standing techniques===

The problem of estimating how many users are on each route is long standing.  [[Urban planner|Planners]] started looking hard at it as [[Controlled-access highway|freeways]] and expressways began to be developed.  The freeway offered a superior level of service over the local street system, and diverted traffic from the local system.  At first, diversion was the technique.   Ratios of travel time were used, tempered by considerations of costs, comfort, and [[Level of service (transportation)|level of service]].

The [[Chicago Area Transportation Study]] (CATS) researchers developed diversion curves for freeways versus local streets.  There was much work in California also, for California had early experiences with freeway planning.  In addition to work of a diversion sort, the CATS attacked some technical problems that arise when one works with complex networks.  One result was the [[Bellman–Ford–Moore algorithm]] for finding [[shortest path]]s on networks.

The issue the diversion approach did not handle was the feedback from the quantity of traffic on links and routes.  If a lot of vehicles try to use a facility, the facility becomes [[Traffic congestion|congested]] and travel time increases.  Absent some way to consider feedback, early planning studies (actually, most in the period 1960-1975) ignored feedback.  They used the Moore algorithm to determine [[Shortest path problem|shortest paths]] and assigned all traffic to shortest paths.  That is called [[all or nothing assignment]] because either all of the traffic from ''i'' to ''j'' moves along a route or it does not.

The all-or-nothing or shortest path assignment is not trivial from a technical-computational view.  Each traffic zone is connected to ''n - 1'' zones, so there are numerous paths to be considered.  In addition, we are ultimately interested in traffic on links.  A link may be a part of several paths, and traffic along paths has to be summed link by link.

An argument can be made favoring the all-or-nothing approach. It goes this way: The planning study is to support investments so that a good level of service is available on all links. Using the travel times associated with the planned level of service, calculations indicate how traffic will flow once improvements are in place. Knowing the quantities of traffic on links, the capacity to be supplied to meet the desired level of service can be calculated.

===Heuristic procedures===
To take account of the effect of traffic loading on travel times and traffic equilibria, several [[heuristic]] calculation procedures were developed.  One heuristic proceeds incrementally.  The traffic to be assigned is divided into parts (usually 4).  Assign the first part of the traffic.  Compute new travel times and assign the next part of the traffic.  The last step is repeated until all the traffic is assigned.  The CATS used a variation on this; it assigned row by row in the O-D table.

The heuristic included in the [[Federal Highway Administration|FHWA]] collection of computer programs proceeds another way.
*0. Start by loading all traffic using an all or nothing procedure.
*1. Compute the resulting travel times and reassign traffic.
*2. Now, begin to reassign using weights.  Compute the weighted travel times in the previous two loadings and use those for the next assignment.  The latest iteration gets a weight of 0.25 and the previous gets a weight of 0.75.
*3. Continue.

These procedures seem to work "pretty well," but they are not exact.

===Frank-Wolfe algorithm===
Dafermos (1968) applied the [[Frank-Wolfe algorithm]] (1956, Florian 1976), which can be used to deal with the traffic equilibrium problem.  Suppose we are considering a highway network.  For each link there is a function stating the relationship between resistance and volume of traffic.  The [[Federal Highway Administration|Bureau of Public Roads]] (BPR) developed a link (arc) congestion (or volume-delay, or link performance)  function, which we will term  ''S<sub>a</sub>(v<sub>a</sub>)''

<math>
S_a \left( {v_a } \right) = t_a \left( {1 + 0.15\left( {\frac{{v_a }}
{{c_a }}} \right)^4 } \right)
</math>

*t<sub>a</sub> = free flow travel time on link ''a'' per unit of time
*v<sub>a</sub> = volume of traffic on link ''a'' per unit of time (somewhat more accurately: flow attempting to use link ''a'').
*c<sub>a</sub> = capacity of link ''a'' per unit of time
*S<sub>a</sub>(v<sub>a</sub>) is the average travel time for a vehicle on link ''a''
	
There are other congestion functions.  The CATS has long used a function different from that used by the BPR, but there seems to be little difference between results when the CATS and BPR functions are compared.

===Equilibrium assignment===
To assign traffic to paths and links we have to have rules, and there are the well-known [[John Glen Wardrop|Wardrop equilibrium]] conditions.<ref>{{Cite conference|last=Wardrop|first=J. G.|year=1952|title=Some Theoretical Aspects of Road Traffic Research|url=https://trid.trb.org/view/120659|conference=Institution of Civil Engineers|pages=325–378|volume=1}}</ref>  The essence of these is that travelers will strive to find the shortest (least resistance) path from origin to destination, and network equilibrium occurs when no traveler can decrease travel effort by shifting to a new path. These are termed user optimal conditions, for no user will gain from changing travel paths once the system is in equilibrium.

The user optimum equilibrium can be found by solving the following [[nonlinear programming]] problem

<math>
\min \sum_a {\int_0^{v_a} {S_a \left( x \right)} } dx
</math>
						

subject to:

<math> v_a  = \sum_i {\sum_j {\sum_r {\alpha _{ij}^{ar} x_{ij}^r } } }  </math>

<math>
\sum_r {x_{ij}^r  = T_{ij} } 
</math>

<math>
v_a \geq 0,\;x_{ij}^r  \geq 0
</math>

where
<math>
x_{ij}^r 
</math>
is the number of vehicles on path ''r'' from origin ''i'' to destination ''j''.  So constraint (2) says that all travel must take place –''i = 1 ... n; j = 1 ...  n''

<math>\alpha _{ij}^{ar} </math> = 1  if link  a is on path  r  from  i  to  j ; zero otherwise.  So constraint (1) sums traffic on each link.  There is a constraint for each link on the network.  Constraint (3) assures no negative traffic.

===Example===
An example from Eash, Janson, and Boyce (1979) will illustrate the solution to the nonlinear program problem. There are two links from node 1 to node 2, and there is a resistance function for each link (see Figure 1).  Areas under the curves in Figure 2 correspond to the integration from 0 to ''a'' in equation 1, they sum to 220,674.  Note that the function for link ''b'' is plotted in the reverse direction.

<math>
S_a  = 15\left( {1 + 0.15\left( {\frac{{v_a }}{{1000}}} \right)^4 } \right) 
</math>

<math> 
S_b  = 20\left( {1 + 0.15\left( {\frac{{v_b }}{{3000}}} \right)^4 } \right)
</math>

<math>
v_a  + v_b  = 8000
</math>

Figure 1: Two Route Network
[[Image:TwoRouteNetwork.png|center|500px|Figure 1 - Two Route Network]]

Figure 2: Graphical Solution to the Equilibrium Assignment Problem
[[Image:EquilibriumAssignment2.png|center|500px|Figure 2 - Graphical Solution to the Equilibrium Assignment Problem]]

Figure 3: Allocation of Vehicles not Satisfying the Equilibrium Condition
[[Image:EquilibriumAssignment3.png|center|500px|Figure 3 - Allocation of Vehicles not Satisfying the Equilibrium Condition]]

At equilibrium there are 2,152 vehicles on link ''a'' and 5847 on link ''b''.  Travel time is the same on each route: about 63.

Figure 3 illustrates an allocation of vehicles that is not consistent with the equilibrium solution.  The curves are unchanged.  But with the new allocation of vehicles to routes the shaded area has to be included in the solution, so the Figure 3 solution is larger than the solution in Figure 2 by the area of the shaded area.