Traffic Assignment
   HOME

TheInfoList



OR:

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 Transportation forecasting is the attempt of estimating the number of vehicles or people that will use a specific transportation facility in the future. For instance, a forecast may estimate the number of vehicles on a planned road or bridge, the r ...
model, following
trip generation Trip generation is the first step in the conventional four-step transportation forecasting process used for forecasting travel demands. It predicts the number of trips originating in or destined for a particular traffic analysis zone (TAZ). Trip g ...
,
trip distribution Trip distribution (or destination choice or zonal interchange analysis) is the second component (after trip generation, but before mode choice and route assignment) in the traditional four-step transportation forecasting model. This step matches ...
, and
mode choice Mode choice analysis is the third step in the conventional four-step transportation forecasting model of transportation planning, following trip distribution and preceding route assignment. From origin-destination table inputs provided by trip dist ...
. The zonal interchange analysis of trip distribution provides origin-destination trip tables. Mode choice analysis tells which travelers will use which
mode Mode ( la, modus meaning "manner, tune, measure, due measure, rhythm, melody") may refer to: Arts and entertainment * '' MO''D''E (magazine)'', a defunct U.S. women's fashion magazine * ''Mode'' magazine, a fictional fashion magazine which is ...
. 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
highway A highway is any public or private road or other public way on land. It is used for major roads, but also includes other public roads and public tracks. In some areas of the United States, it is used as an equivalent term to controlled-access ...
s and
transit Transit may refer to: Arts and entertainment Film * ''Transit'' (1979 film), a 1979 Israeli film * ''Transit'' (2005 film), a film produced by MTV and Staying-Alive about four people in countries in the world * ''Transit'' (2006 film), a 2006 ...
systems and a proposed addition. We first want to know the present pattern of
traffic Traffic comprises pedestrians, vehicles, ridden or herded animals, trains, and other conveyances that use public ways (roads) for travel and transportation. Traffic laws govern and regulate traffic, while rules of the road include traffic ...
delay and then what would happen if the addition were made.


General Approaches


Long-standing techniques

The problem of estimating how many users are on each route is long standing. Planners started looking hard at it as
freeways A controlled-access highway is a type of highway that has been designed for high-speed vehicular traffic, with all traffic flow—ingress and egress—regulated. Common English terms are freeway, motorway and expressway. Other similar terms i ...
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 Level of service may refer to: * Levels of service in asset management * Level of service (transportation) in transportation and traffic * Something agreed on in a Service-level agreement A service-level agreement (SLA) is a commitment between a ...
. The
Chicago Area Transportation Study (''City in a Garden''); I Will , image_map = , map_caption = Interactive Map of Chicago , coordinates = , coordinates_footnotes = , subdivision_type = List of sovereign states, Count ...
(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 In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...
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 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 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 A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
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 The Federal Highway Administration (FHWA) is a division of the United States Department of Transportation that specializes in highway transportation. The agency's major activities are grouped into two programs, the Federal-aid Highway Program a ...
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
Bureau of Public Roads The Federal Highway Administration (FHWA) is a division of the United States Department of Transportation that specializes in highway transportation. The agency's major activities are grouped into two programs, the Federal-aid Highway Program a ...
(BPR) developed a link (arc) congestion (or volume-delay, or link performance) function, which we will term ''Sa(va)'' S_a \left( \right) = t_a \left( \right) *ta = free flow travel time on link ''a'' per unit of time *va = volume of traffic on link ''a'' per unit of time (somewhat more accurately: flow attempting to use link ''a''). *ca = capacity of link ''a'' per unit of time *Sa(va) 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
Wardrop equilibrium John Glen Wardrop (1922–1989), born in Warwick, England, was an English mathematician and transport analyst who developed what became known as Wardrop's first and second principles of equilibrium in the field of traffic assignment. He studied ...
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 In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or sta ...
problem \min \sum_a dx subject to: v_a = \sum_i \sum_r v_a \geq 0,\;x_^r \geq 0 where x_^r 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'' \alpha _^ = 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. S_a = 15\left( \right) S_b = 20\left( \right) v_a + v_b = 8000 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.


Integrating travel choices

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 Land-use forecasting undertakes to project the distribution and intensity of trip generation, trip generating activities in the metropolitan area, urban area. In practice, land-use models are demand-driven, using as inputs the aggregate informatio ...
. 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 Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
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 t_c_=C where the c_ are the link travel costs, t_ 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

It has long been recognized that travel demand is influenced by network supply. The example of a new
bridge A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...
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 A thesis ( : theses), or dissertation (abbreviated diss.), is a document submitted in support of candidature for an academic degree or professional qualification presenting the author's research and findings.International Standard ISO 7144: ...
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) Capacity or capacities may refer to: Mathematics, science, and engineering * Capacity of a container, closely related to Volume#Related terms, the volume of the container * Capacity of a set, in Euclidean space, the total charge a set can hold wh ...
for a transportation study of
Toronto Toronto ( ; or ) is the capital city of the Canadian province of Ontario. With a recorded population of 2,794,356 in 2021, it is the most populous city in Canada and the fourth most populous city in North America. The city is the ancho ...
. 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

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 Emme may refer to: People: * Ivan Fyodorovich Emme (1763–1839), Russian lieutenant general in the Napoleonic Wars * Otto J. Emme, American politician and World War I veteran * Emme Gerhard (1872–1946), American photographer * Emme Rylan, Am ...
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 In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are ...
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 Civil engineering is a professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including public works such as roads, bridges, canals, dams, airports, sewage ...
-– hydraulics, structures, and construction. (See Hendrickson and Janson 1984).


Empirical Studies of Route Choice

Route assignment models are based at least to some extent on empirical studies of how people choose routes in a
network Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...
. Such studies are generally focused on a particular
mode Mode ( la, modus meaning "manner, tune, measure, due measure, rhythm, melody") may refer to: Arts and entertainment * '' MO''D''E (magazine)'', a defunct U.S. women's fashion magazine * ''Mode'' magazine, a fictional fashion magazine which is ...
, and make use of either stated preference or
revealed preference Revealed preference theory, pioneered by economist Paul Anthony Samuelson in 1938, is a method of analyzing choices made by individuals, mostly used for comparing the influence of policies on consumer behavior. Revealed preference models assume t ...
models.


Bicycle

Cyclists Cycling, also, when on a two-wheeled bicycle, called bicycling or biking, is the use of Bicycle, cycles for transport, recreation, Physical exercise, exercise or sport. People engaged in cycling are referred to as "cyclists", "bicyclists", ...
have been found to prefer designated
bike lane Bike lanes (US) or cycle lanes (UK) are types of bikeways (cycleways) with lanes on the roadway for cyclists only. In the United Kingdom, an on-road cycle-lane can be firmly restricted to cycles (marked with a solid white line, entry by motor v ...
s and avoid steep hills.


Public Transport

Public transport Public transport (also known as public transportation, public transit, mass transit, or simply transit) is a system of transport for passengers by group travel systems available for use by the general public unlike private transport, typical ...
has long been considered in the context of route assignment and many studies have been conducted on transit route choice. Among other factors, transit users attempt to minimize total travel time, time or distance walking, and number of transfers.


See also

* Route choice (disambiguation)


Notes


General References

* 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. * 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 {{Transportation-planning Transportation planning