# Frank Wolfe Algorithm User Equilibrium Assignment

**Route assignment**, **route choice**, or **traffic assignment** concerns the selection of routes (alternative called paths) between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting model, following Trip Generation, Destination Choice, and Mode Choice. The zonal interchange analysis of trip distribution provides origin-destination trip tables. Mode choice analysis tells which travelers will use which mode. To determine facility needs and costs and benefits, we need to know the number of travelers on each route and link of the network (a route is simply a chain of links between an origin and destination). We need to undertake traffic (or trip) assignment. Suppose there is a network of highways and transit systems and a proposed addition. We first want to know the present pattern of travel times and flows and then what would happen if the addition were made.

## Link Performance Function[edit]

The cost that a driver imposes on others is called the marginal cost. However, when making decisions, a driver only faces his own cost (the average cost) and ignores any costs imposed on others (the marginal cost).

where is the total cost, and is the flow.

### BPR Link Performance Function[edit]

Suppose we are considering a highway network. For each link there is a function stating the relationship between resistance and volume of traffic. The Bureau of Public Roads (BPR) developed a link (arc) congestion (or volume-delay, or link performance) function, which we will term *S _{a}(Q_{a})*

*t _{a} = free-flow travel time on link a per unit of time*

*Q _{a} = flow (or volume) of traffic on link a per unit of time (somewhat more accurately: flow attempting to use link* a

*)*

*c _{a} = capacity of link a per unit of time*

*S _{a}(Q_{a})* 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.

## Can Flow Exceed Capacity?[edit]

On a link, the capacity is thought of as “outflow.” Demand is inflow.

If inflow > outflow for a period of time, there is queueing (and delay).

For Example, for a 1 hour period, if 2100 cars arrive and 2000 depart, 100 are still there. The link performance function tries to represent that phenomenon in a simple way.

## Wardrop's Principles of Equilibrium[edit]

### User Equilibrium[edit]

Each user acts to minimize his/her own cost, subject to every other user doing the same. Travel times are equal on all used routes and lower than on any unused route.

### System optimal[edit]

Each user acts to minimize the total travel time on the system.

## Price of Anarchy[edit]

The reason we have congestion is that people are selfish. The cost of that selfishness (when people behave according to their own interest rather than society's) is the *price of anarchy*.

The ratio of system-wide travel time under User Equilibrium and System Optimal conditions.

Price of Anarchy =

For a two-link network with linear link performance functions (latency functions), Price of Anarchy is < 4/3.

Is this too much? Should something be done, or is 33% waste acceptable? [The loss may be larger/smaller in other cases, under different assumptions, etc.]

## Conservation of Flow[edit]

An important factor in road assignment is the conservation of flow. This means that the number of vehicles entering the intersection (link segment) equals the number of vehicles exiting the intersection for a given period of time (except for sources and sinks).

Similarly, the number of vehicles entering the back of the link equals the number exiting the front (over a long period of time).

## Auto assignment[edit]

### Long-standing techniques[edit]

The above examples are adequate for a problem of two links, however real networks are much more complicated. The problem of estimating how many users are on each route is long standing. Planners started looking hard at it as freeways and expressways (motorways) 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.

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 Moore algorithm for finding shortest paths on networks.

The issue the diversion approach didn’t 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 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 paths and assigned all traffic to shortest paths. That’s 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[edit]

To take account of the affect 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 FHWA collection of computer programs proceeds another way.

- Step 0: Start by loading all traffic using an all or nothing procedure.
- Step 1: Compute the resulting travel times and reassign traffic.
- Step 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.
- Step 3. Continue.

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

### Frank-Wolfe algorithm[edit]

Dafermos (1968) applied the Frank-Wolfe algorithm (1956, Florian 1976), which can be used to deal with the traffic equilibrium problem.

### Equilibrium Assignment[edit]

To assign traffic to paths and links we have to have rules, and there are the well-known Wardrop equilibrium (1952) conditions. 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

subject to:

where 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*

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

## Transit assignment[edit]

There are also methods that have been developed to assign passengers to transit vehicles.^{[1]} In an effort to increase the accuracy of transit assignment estimates, a number of assumptions are generally made. Examples of these include the following:

- All transit trips are run on a set and predefined schedule that is known or readily available to the users.
- There is a fixed capacity associated with the transit service (car/trolley/bus capacity).
^{[2]}

## Examples[edit]

### Example 1[edit]

**Problem:**

Solve for the flows on Links *a* and *b* in the Simple Network of two parallel links just shown if the link performance function on link *a*:

and the function on link *b*:

where total flow between the origin and destination is 1000 trips.

**Solution:**

Time (Cost) is equal on all used routes so

And we have Conservation of flow so,

### Example 2[edit]

**Problem:**

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.

Show graphically the equilibrium result.

**Solution:**

At equilibrium there are 2,152 vehicles on link *a* and 5,847 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.

### Example 3[edit]

**Problem:**

Assume the traffic flow from Milwaukee to Chicago, is 15000 vehicles per hour. The flow is divided between two parallel facilities, a freeway and an arterial. Flow on the freeway is denoted , and flow on the two-lane arterial is denoted .

The travel time (in minutes) on the freeway () is given by:

The travel time on the arterial () is given by

Apply Wardrop's User Equilibrium Principle, and determine the flow and travel time on both routes.

**Solution:**

The travel times are set equal to one another

The total traffic flow is equal to 15000

Solve for

## Thought Questions[edit]

- How can we get drivers to consider their marginal cost?
- Alternatively: How can we get drivers to behave in a “System Optimal” way?

## Sample Problem[edit]

## Variables[edit]

## Abbreviations[edit]

- VDF - Volume Delay Function
- LPF - Link Performance Function
- BPR - Bureau of Public Roads
- UE - User Equilbrium
- SO - System Optimal
- DTA - Dynamic Traffic Assignment
- DUE - Deterministic User Equilibrium
- SUE - Stochastic User Equilibrium
- AC - Average Cost
- MC - Marginal Cost

## Key Terms[edit]

- Route assignment, route choice, auto assignment
- Volume-delay function, link performance function
- User equilibrium
- System optimal
- Conservation of flow
- Average cost
- Marginal cost

## External Exercises[edit]

Use the ADAM software at the STREET website and try Assignment #3 to learn how changes in network characteristics impact route choice.

## Additional Questions[edit]

## Videos[edit]

## References[edit]

- Dafermos, Stella. C. and F.T. Sparrow The Traffic Assignment Problem for a General Network.” J. of Res. of the National Bureau of Standards, 73B, pp. 91-118. 1969.
- Florian, Michael ed., Traffic Equilibrium Methods, Springer-Verlag, 1976.
- Wardrop, J. C. Some Theoretical Aspects of Road Traffic Research,” Proceedings, Institution of Civil Engineers Part 2, 9, pp. 325–378. 1952
- Eash, Ronald, Bruce N. Janson, and David Boyce Equilibrium Trip Assignment: Advantages and Implications for Practice, Transportation Research Record 728, pp. 1–8, 1979.
- Evans, Suzanne P. . "Derivation and Analysis of Some Models for Combining Trip Distribution and Assignment." Transportation Research, Vol 10, pp 37–57 1976
- Hendrickson, C.T. and B.N. Janson, “A Common Network Flow Formulation to Several Civil Engineering Problems” Civil Engineering Systems 1(4), pp. 195–203, 1984

## Further reading[edit]

For other uses, see Route choice (disambiguation).

**Route assignment**, **route choice**, or **traffic assignment** concerns the selection of routes (alternative called paths) between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting model, following trip generation, trip distribution, and mode choice. The zonal interchange analysis of trip distribution provides origin-destination trip tables. Mode choice analysis tells which travelers will use which mode. To determine facility needs and costs and benefits, we need to know the number of travelers on each route and link of the network (a route is simply a chain of links between an origin and destination). We need to undertake traffic (or trip) assignment. Suppose there is a network of highways and transit systems and a proposed addition. We first want to know the present pattern of traffic delay and then what would happen if the addition were made.

## Auto assignment[edit]

### Long-standing techniques[edit]

The problem of estimating how many users are on each route is long standing. Planners started looking hard at it as 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.

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 paths on networks.

The issue the diversion approach didn’t 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 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 paths and assigned all traffic to shortest paths. That’s 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[edit]

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 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[edit]

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 Bureau of Public Roads (BPR) developed a link (arc) congestion (or volume-delay, or link performance) function, which we will term *S _{a}(v_{a})*

- t
_{a}= free flow travel time on link*a*per unit of time - v
_{a}= volume of traffic on link*a*per unit of time (somewhat more accurately: flow attempting to use link*a*). - c
_{a}= capacity of link*a*per unit of time - S
_{a}(v_{a}) 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[edit]

To assign traffic to paths and links we have to have rules, and there are the well-known Wardrop equilibrium (1952) conditions. 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

subject to:

where 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*

= 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[edit]

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.

Figure 1: Two Route Network

Figure 2: Graphical Solution to the Equilibrium Assignment Problem

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.

## Transit assignment[edit]

There are also methods that have been developed to assign passengers to transit vehicles.

## Integrating travel choices[edit]

The urban transportation planning model evolved as a set of steps to be followed, and models evolved for use in each step. Sometimes there were steps within steps, as was the case for the first statement of the Lowry model. In some cases, it has been noted that steps can be integrated. More generally, the steps abstract from decisions that may be made simultaneously, and it would be desirable to better replicate that in the analysis.

Disaggregate demand models were first developed to treat the mode choice problem. That problem assumes that one has decided to take a trip, where that trip will go, and at what time the trip will be made. They have been used to treat the implied broader context. Typically, a nested model will be developed, say, starting with the probability of a trip being made, then examining the choice among places, and then mode choice. The time of travel is a bit harder to treat.

Wilson’s doubly constrained entropy model has been the point of departure for efforts at the aggregate level. That model contains the constraint

where the are the link travel costs, refers to traffic on a link, and C is a resource constraint to be sized when fitting the model with data. Instead of using that form of the constraint, the monotonically increasing resistance function used in traffic assignment can be used. The result determines zone-to-zone movements and assigns traffic to networks, and that makes much sense from the way one would imagine the system works – zone-to-zone traffic depends on the resistance occasioned by congestion.

Alternatively, the link resistance function may be included in the objective function (and the total cost function eliminated from the constraints).

A generalized disaggregate choice approach has evolved as has a generalized aggregate approach. The large question is that of the relations between them. When we use a macro model, we would like to know the disaggregate behavior it represents. If we are doing a micro analysis, we would like to know the aggregate implications of the analysis.

Wilson derives a gravity-like model with weighted parameters that say something about the attractiveness of origins and destinations. Without too much math we can write probability of choice statements based on attractiveness, and these take a form similar to some varieties of disaggregate demand models.

## Integrating travel demand with route assignment[edit]

It has long been recognized that travel demand is influenced by network supply. The example of a new bridge opening where none was before inducing additional traffic has been noted for centuries. Much research has gone into developing methods for allowing the forecasting system to directly account for this phenomenon. Evans (1974) published a doctoral dissertation on a mathematically rigorous combination of the gravity distribution model with the equilibrium assignment model. The earliest citation of this integration is the work of Irwin and Von Cube, as related by Florian et al. (1975), who comment on the work of Evans:

"The work of Evans resembles somewhat the algorithms developed by Irwin and Von Cube [“Capacity Restraint in Multi-Travel Mode Assignment Programs” H.R.B. Bulletin 347 (1962)] for a transportation study of Toronto, Canada. Their work allows for feedback between congested assignment and trip distribution, although they apply sequential procedures. Starting from an initial solution of the distribution problem, the interzonal trips are assigned to the initial shortest routes. For successive iterations, new shortest routes are computed, and their lengths are used as access times for input the distribution model. The new interzonal flows are then assigned in some proportion to the routes already found. The procedure is stopped when the interzonal times for successive iteration are quasi-equal."

Florian et al. proposed a somewhat different method for solving the combined distribution assignment, applying directly the Frank-Wolfe algorithm. Boyce et al. (1988) summarize the research on Network Equilibrium Problems, including the assignment with elastic demand.

## Discussion[edit]

A three link problem can not be solved graphically, and most transportation network problems involve a large numbers of nodes and links. Eash et al., for instance, studied the road net on DuPage County where there were about 30,000 one-way links and 9,500 nodes. Because problems are large, an algorithm is needed to solve the assignment problem, and the Frank-Wolfe algorithm (with various modern modifications since first published) is used. Start with an all or nothing assignment, and then follow the rule developed by Frank-Wolfe to iterate toward the minimum value of the objective function. (The algorithm applies successive feasible solutions to achieve convergence to the optimal solution. It uses an efficient search procedure to move the calculation rapidly toward the optimal solution.) Travel times correspond to the dual variables in this programming problem.

It is interesting that the Frank-Wolfe algorithm was available in 1956. Its application was developed in 1968, and it took almost another two decades before the first equilibrium assignment algorithm was embedded in commonly used transportation planning software (Emme and Emme/2, developed by Florian and others in Montreal). We would not want to draw any general conclusion from the slow application observation, mainly because we can find counter examples about the pace and pattern of technique development. For example, the simplex method for the solution of linear programming problems was worked out and widely applied prior to the development of much of programming theory.

The problem statement and algorithm have general applications across civil engineering -– hydraulics, structures, and construction. (See Hendrickson and Janson 1984).

## See also[edit]

## References[edit]

- Dafermos, Stella. C. and F.T. Sparrow The Traffic Assignment Problem for a General Network.” J. of Res. of the National Bureau of Standards, 73B, pp. 91-118. 1969.
- Florian, Michael ed., Traffic Equilibrium Methods, Springer-Verlag, 1976.
- Wardrop, J. C. Some Theoretical Aspects of Road Traffic Research,” Proceedings, Institution of Civil Engineers Part 2, 9, pp. 325–378. 1952
- Eash, Ronald, Bruce N. Janson, and David Boyce Equilibrium Trip Assignment: Advantages and Implications for Practice, Transportation Research Record 728, pp. 1–8, 1979.
- Evans, Suzanne P. . "Derivation and Analysis of Some Models for Combining Trip Distribution and Assignment." Transportation Research, Vol 10, pp 37–57 1976
- Hendrickson, C.T. and B.N. Janson, “A Common Network Flow Formulation to Several Civil Engineering Problems” Civil Engineering Systems 1(4), pp. 195–203, 1984

## 0 comments