Towards Consistent Travel Demand Estimation in Transportation Planning: A Guide to the Theory and Practice of Equilibrium Travel Demand Modeling

7. Basic Theory

7.1 Transportation Systems as Markets

The basic idea underlying the network equilibrium approach to travel demand modeling is a view of transportation systems as markets. The network equilibrium approach embeds the elements typically found in the traditional, four-step approach into a market equilibrium framework. As in classical economic market theory, the task is to predict the short-run equilibrium levels of supply and demand, that is, the number of trips and level of transportation service in the study area (Fernandez and Friesz 1983).

While the concept of market equilibrium is straightforward, its application to transportation systems involves special considerations related to two features of these systems: i) the network basis of transportation systems; and, ii) the existence of demand externalities in the form of congestion. In the first case, supply functions are tied to network links; for example, consider the performance functions typically used to relate flow in a link to its travel time or cost (see below). However, the relevant unit of analysis is the individual trip between an origin and a destination; this trip will use a path consisting of multiple network links. Therefore, the equilibrium model must relate each transportation demand (i.e., trip) to multiple supply components. In the second case, each traveler's choice relates to the level of service provided by available paths between an O-D pair. In turn, these service levels are influenced by the choices of other travelers since the performance of service typically degrades as the number of users increase. These congestion externalities suggest that the level of service (supply) and flow (demand) between an origin-destination pair must, in general, consider the service levels and flows for all origin-destination pairs in the network (Fernandez and Friesz 1983).

Transportation market equilibrium occurs at two levels. First, the flows through the network correspond to some stated equilibrium criterion such as Wardrop's user-optimal principle (informally, no user can improve his/her cost by unilaterally changing routes; see below). This pattern corresponds to the NA phase of the traditional four step approach. The second equilibrium level corresponds to the TG, TD and MS components of the four step approach. Demand for these "higher-level" components is elastic, meaning that it is responsive to cost. Therefore, we can also specify a corresponding market equilibrium criterion at this level, e.g., no user can improve his/her travel cost by unilaterally changing generation rate, destination choice or mode choice. Note that these are tightly linked with the "lower level" network equilibrium since network flow costs affect the higher level demands while the higher level demands affect the amount of network congestion and therefore the network travel costs.

7.2 Basic Components

7.2.1 Network Characteristics

A directed graph represents the transportation system in the study area. The directed graph consists of a set of network nodes and a set of directed (i.e., "one-way") arcs connecting certain nodes (12-1). Some nodes represent travel origins (12-2) while others represent travel destinations (12-3); the remaining generally correspond to street intersections, modal transfer points and other flow "transfer" locations. A two node sequence represents each network arc in the standard "from-node, to-node" format (12-4).

Sequences of network arcs comprise network paths. These paths originate at origin nodes, terminate at destination nodes and are connected in the sense that the "to- node" of an arc is the "from-node" of the next arc in the sequence (12-5). An arc-path incidence variable indicates the relationship between individual arcs and paths (12-9): models use this variable directly to maintain consistent relationships between flows at the arc and path levels.

Travel demand models differ with respect to representation of multiple modes. Often, a model will use a single directed graph to represent all modal networks in a study area. In this case, different modal flows coexist within the same arc (12-10) or within the same path (12-15). In other cases, an explicit multimodal network is required, that is, each mode has a separate directed graph. "Transfer arcs" link these distinct modal networks.

Travel demand models estimate flows at either the arc or path level. Flow feasibility requirements ensure that solutions are realistic, consistent between the arc and path levels, and consistent with aggregate-level travel demands (that is, the known or estimated aggregate flows between O-D pairs). These requirements are: i) all path flows are non-negative (12-56); ii) the mode-specific flows on all paths between an O-D pair sum to the aggregate modal flows between that pair (12-57); and, iii) the mode-specific flows on all paths that use an arc sum to the total modal flow on that arc (12-58).

although travel demand models require consistency between flows at the arc and path level, an interesting theoretical result is that at equilibrium only arc flows and aggregate travel demands are unique: path flows are not unique (see Fernandez and Friesz 1983; Sheffi 1985, 66-69). That is, any set of path flows that are consistent with the equilibrium arc flows is allowable; in theory, this is an infinite set. From a practical perspective, this is not a major problem since we are primarily concerned with flow levels within given elements of the transportation infrastructure. However, one must keep in mind that path flow estimates from these models are not suitable for analysis.

7.2.2 Cost Functions

Similar to network flows, travel costs can be measured at the arc (12-13) or path levels. However, cost functions are usually specified at the arc level: path travel costs are simply the summed costs for all arcs that comprise that path (12-17).

Mode-specific arc travel costs are generally a function of flow, either the mode-specific flow on that arc (12-59) or a function of all modal flows across all arcs in the network (12-60). The former cost function is referred to as separable, i.e., the flows across different modes and different arcs can be meaningfully separated. The latter cost function is referred to as non-separable, i.e., flows across different modes and different arcs cannot be partitioned meaningfully into independent flows. Separable cost functions are not as realistic as non-separable functions. For example, a separable cost function assumes that different modes sharing an arc do not influence each other (e.g., automobile congestion on a link does not influence buses using the same link). Also, separable cost functions do not account for the interactions of flows on different arcs (e.g., congestion at intersections due to cross-traffic, interactions among two-way flows on a street). Non-separable cost functions can consider these interactions; however, solving the resulting travel demand model is much more difficult.

Typically, arc flow costs functions represent the generalized cost of travel within that element of the transportation infrastructure. For separable cost functions, a basic but typically invoked function is:

(7-1)

where is the out-of-pocket expense required for using mode k on arc a (this may also be a function of flow), is the mode k travel time on arc a associated with flow level , the mode k flow on arc a, and w is a value-of-time (VOT) parameter that translates travel time into equivalent monetary units, i.e., travelers' time cost. One of the two elements of (7-1) may not be present for a given mode within a given arc. For example, public transit fares may only be invoked in modal entry or transfer arcs. The VOT parameter may also be associated with the monetary expense variable instead of the travel time variable, if desired.

Various models require different restrictions on the behavior of cost functions with respect to flow levels. Given the basic format in (7-1), these restrictions are through the flow-based travel time function . A typically invoked format for this function is (Branston 1976):

(7-2)

where is the free-flow travel time, is the mode k capacity of arc a, and ₁, ₂ are empirically-estimated parameters.

7.2.3 Demand Functions

Demand functions relate the amount of O-D flow for each mode to travel costs. As with the arc cost functions, demand functions are either separable or non-separable. Separable demand functions relate the level of mode-specific flow between an O-D pair to the minimum cost for that mode and O-D pair only (12-61). In contrast, non-separable demand functions relate the mode-specific flow between an O-D pair to the minimum travel costs across all O-D pairs and modes (12-62). As with arc cost functions, non-separable demand functions are more realistic but result in model formulations that are more difficult to solve.

In some models, the O-D demands are fixed and exogenous, meaning that aggregate O-D flows are required as external data rather than predicted as a model outcome. Evans (1976) provides an example of an endogenous, separable demand function:

(7-3)

where D_ij is the aggregate flow between origin i and destination j, C_ij* is the minimum travel cost between the O-D pair, _ij is an estimated parameter, and A_i and B_j are "balancing factors" or parameters chosen so that outflows from origins and inflows to destinations sum to totals known from exogenous data (i.e., the total amount of travelers leaving each origin and the total amount of travelers entering each destination). This demand function is essentially a doubly constrained spatial interaction model, that is, a spatial interaction models whose origin outflows and destination inflows are constrained to match known sums (see Fotheringham and O'Kelly 1989; Wilson 1967, 1974).

7.3 Types of Transportation Equilibria

7.3.1 Network Equilibria

7.3.1.1 User Optimal (UO)

7.3.1.1.1 User Optimal-Strict (UO-S)

The most common type of network equilibria analyzed is the user optimal (UO), originally due the Wardrop (1952). The traditional, strict definition, referred hereafter as user optimal-strict (UO-S), is:

(UO-S) At network equilibrium, no traveler can reduce his or her travel costs by unilaterally changing routes (i.e., independently change routes without other users' route changes).

alternatively: All used routes between an O-D pair have the same, minimal cost and no unused route has a lower cost.

This implies the following network flow characteristics. First, positive flow for a mode on a route implies that it must have a travel cost equal to the minimum cost for that mode between the particular O-D (13-1). Second, any route with a cost greater than the minimum for a mode implies that the flow level for that mode is zero on that route (13-2). In other words, for each mode, flow only occurs on the minimum cost routes between each O-D pair, i.e., no traveler has a less costly alternative route (Smith 1979).

The UO-S conditions imply a tenable behavioral motivation but require strong assumptions about travelers reactions to conditions within the network. The fundamental behavioral postulate is that travelers follow the "cheapest" available route for their user class. While this basic motivation seems reasonable, strict adherence to this behavior at an individual-level is less tenable. The UO-S conditions imply travelers' perfect decision-making capabilities and perfect knowledge about network conditions. In other words, travelers know the exact cost on each available route and react to these costs with perfect accuracy. Nevertheless, many equilibrium models follow the UO-S conditions since they result in tractable formulations and provide a "best-guess" about traveler decisions lacking other behavioral data.

7.3.1.1.2 UO-General (UO-G)

Smith (1979) proposed a generalization of the UO conditions that imply less strict behavioral assumptions. Paraphrasing slightly, the user equilibrium-general (UO-G) conditions are:

(UO-G) Travelers change routes in the next time period in a manner that reduces total cost based on the current route costs.

Travelers change routes in the next time period (e.g., "tomorrow") based on the current time period's costs (e.g., "today"). Therefore, travelers do not react to network conditions instantaneously. Also, the current time period flow pattern influences, but does not determine, the flow pattern in the next time period. In general, a number of flow patterns rather than a single flow pattern in the next period will satisfy UO-G (Fernandez and Friesz 1983; Smith 1979).

Despite the temporal element in the definition, this principle can also characterize static flow patterns since it describes conditions for flow stability. The UO-G conditions state that a flow pattern is UO if any other flow pattern would result in higher total costs (13-3). This expands the UO-S conditions. If the network is at UO-S, the flow pattern will be stable since no traveler can switch routes in the next time period and reduce total cost. However, UO-G also allows flow patterns that do not satisfy UO-S but nevertheless are reasonable from a behavioral perspective. Under UO-G, individual travelers switch to more expensive routes only if that change does not lead to an increase in total cost across all travelers. Thus, some travelers are allowed to make "mistakes" if this does not "harm" other travelers in toto.

7.3.1.2 Dynamic User Optimal (DUO)

Static equilibria assume that the travel demand pattern in a given study area converge to a "steady-state" condition in which temporal fluctuations do not occur. Analysts recognize that temporal fluctuations in NA, MS, TD and TG do occur in reality. Since transportation planning is oriented traditionally towards infrastructure planning and broad policy evaluation, ignoring minor temporal fluctuations is defensible since these plans and policies attempt to accommodate the general travel demand pattern.

There have been recent attempts to incorporate dynamic properties of travel demand patterns. These attempts are motivated by the U.S. federal policy shifts away from large infrastructure investments in urban area. Manifestations of this policy shift such as intelligent transportation systems (ITS) require detailed temporal predictions of traffic flows and congestion and the implementation of non-transportation, activity-based solutions such as flex-time and telecommuting. Another motivation for dynamic travel demand models is the difficulty in capturing adequately the environmental impacts of travel demand patterns in general and traffic congestion specifically. Assessing the impacts of traffic on ambient air quality requires estimates of behaviors such as engine cold-starts and speed variations. These factors affect air quality more than aggregate throughput per se (Kulkarni et al. 1996).

"Equilibrium" is a much broader concept in the dynamic realm. A fundamental consideration is the equilibrium's time frame. Time can be viewed as discrete (i.e., divided into finite intervals) or continuous. In addition, equilibrium conditions can be stated for "within-day" or intra-periodic, "day-to-day" or inter-periodic or combined intra/inter-periodic dynamics. Within-day dynamics capture daily fluctuations in travel demand both with respect to inherent fluctuations as well as unplanned disturbances such as road closings, accidents, etc. Within-day dynamics also allows modeling timing decisions for trip generation; this is important for discretionary travel as well as flex-time-based commuting in congested networks. Day-to-day dynamics capture the slower learning process of travelers as they acquire information about the travel environment. In addition, the existence of a traditional transportation equilibrium is not guaranteed, particularly with respect to continuous time dynamics. The system may converge to different attractors and display complex behavior as with dynamical systems in general (Cantrella and Cascetta 1995).

As the discussion in the previous paragraph implies, there is a wide-range of dynamic equilibrium formulations (e.g., Cantrella and Cascetta 1995; Friesz et al. 1994; Friesz, Bernstein and Stough 1996; Ran and Boyce 1994; Ran, Hall and Boyce 1996). Several of the continuous time formulations have similar structure to the UO-G conditions (more specifically, they share the structure of a variational inequality problem; see Nagurney 1993). Many are oriented specifically towards ITS rather than travel demand prediction. For example, the formulations of Ran and Boyce (1994) and Ran, Hall and Boyce (1996) assume that the amount of flow entering each transportation link are control variables in their dynamical system. Real-world manifestations of these variables could be traffic control and ITS devices such as variable message signs, variable time traffic lights and information provided to drivers that influence or direct their route choices.

Due to the orientation of this review towards pragmatic travel demand models, the dynamic user optimal (DUO) principle considered here is a discrete-time, within-day formulation by Janson (1991a, 1991b). This DUO formulation has resulted in a very practical dynamic NA model and solution procedure (to be discussed later). This DUO principle is:

(DUO) At network equilibrium, no traveler who departed during the same time interval can reduce his or her travel costs by unilaterally changing routes.

alternatively: All used routes between an O-D pair have the same, minimal cost and no unused route has a lower cost for travelers that departed during the same time interval.

This DUO principle implies the following network flow characteristics. First, positive flow on a route for users who departed during a given time interval implies that it must have a travel cost equal to the minimum cost for those users between the particular O-D pair (13-4). Second, any route with a cost greater than the minimum for users who departed during a given time interval implies that the flow level for those users is zero (13-5). Note that these conditions are a direct extension of the UO-S conditions. Indeed, UO-S is a special case of this DUO principle (Janson 1991).

DUO implies the same harsh behavioral assumptions as UO-S. In addition, the treatment of time as discrete limits the resolution of these dynamics. However, the introduction of a dynamic component increases the realism and usefulness of the UO equilibrium principle. Also, as stated above, this equilibrium principle does allow for a pragmatic dynamic NA model that is tractable computationally and has reasonable data requirements.

7.3.1.3 System Optimal (SO)

While the UO conditions minimize individual travel costs, it does not in general minimize total cost for travelers as a whole. The UO-S conditions only require that the flow pattern minimizes costs on an individual basis. The UO-G conditions allow flow changes that do not increase total cost but do not require this to be minimal for individuals. Minimizing individual costs does not equate to minimizing total costs when congestion is present in the network. Under these conditions, each traveler's route choice influences the costs of other travelers.

The UO-S principle assumes that travelers' do not consider the externalities of their decisions: travelers only perceive their personal travel cost and not the additional costs imposed on others by their route choices (Ortuzar and Willumsen 1990). To accommodate this additional decision principle, Wardrop (1952) formulated a second, system optimal (SO) principle:

(SO) At network equilibrium, the total (or average) travel cost is minimum.

A flow pattern that satisfies this principal is appealing from a society-wide perspective. An SO flow minimizes the total operating cost of the network, implying efficiency (Fernandez and Friesz 1983). Also, if we accept total cost as a surrogate for the system-wide use of energy resources and output of pollution, we can see that this pattern would minimize these negative impacts. However, this flow pattern is not likely to occur in practice since it requires travelers to make joint decisions to minimize total cost rather than their individual cost. At SO, it will be likely that travelers can unilaterally change routes to reduce their individual costs, meaning that the pattern will be difficult to sustain without some external control mechanism (Fernandez and Friesz 1983; Sheffi 1985).

The difference between UO-S and SO is clear when one considers the type of information required for travelers to achieve each pattern. UO-S postulates that travelers consider the average cost on routes: travelers choose the route between an O-D pair that has the minimum average cost for their user class (13-1), (13-2). In order to obtain the SO pattern, travelers only consider the marginal costs for routes, that is, the added cost of their entry into a route. The SO conditions imply that, at equilibrium, flow only occurs along routes whose marginal cost for the mode is minimum for that O-D pair (13-6), (13-7). Thus, travelers will only choose routes that minimize their impact on total travel cost.

SO-based model formulations have two valuable features. First, SO flow patterns provide a valuable benchmark for assessing the efficiency of other flow patterns (Sheffi 1985). In addition, while the SO principle has traditionally been viewed as an unrealistic ideal, the increasing popularity and sophistication of congestion pricing policies and ITS in general can make these conditions an obtainable goal for real-world settings.

7.3.1.4 Stochastic user optimal (SUO)

The stochastic user optimal (SUO) is a relaxation of a strict behavioral assumption implied by UO. In particular, SUO assumes cost minimization but allows cost perceptions to vary among travelers. The SUO principle is (Daganzo and Sheffi 1977):

(SUO) At network equilibrium, no traveler can reduce his or her perceived travel costs by unilaterally changing routes.

alternatively: no traveler believes he or she can reduce costs by unilaterally changing routes.

The SUO principle assumes that the route travel costs include random components that reflect variations in travelers' perceptions. Randomness results from factors such as limited information, decision making inaccuracies or non-measured route attributes (Daganzo and Sheffi 1977). although random variables, travel costs are related in a systematic and rational manner to the actual travel costs; specifically, the random travel costs result from an "error" distribution around the actual route cost. The error has an expected value of zero, meaning that the expected value of the random route cost is equal to the actual cost (13-10), (13-11). Thus, we expect perceived route costs overall to be accurate but allow for variations in accuracy across travelers

The SUO conditions require a dispersed allocation of the flow between an O-D pair according to the probability that each route is cheapest for travelers (13-8), (13-9). Different assumed probability distributions for the error component result in different analytical models for calculating the route choice probabilities (e.g., Sheffi and Powell 1981, 1982). However, at equilibrium the actual route costs for used routes will not be equal and minimal as in the UO case (Sheffi 1985). In general, under SUO each route between an O-D pair will have a non-zero flow level, although it may be small in some cases.

although SUO has a realistic behavioral foundation, it is not as widely used as the UO principle in model formulations. This is due to the route enumeration problem. Calculating route choice probabilities generally requires specifying each possible route between an O-D pair: this set can be extremely large. SUO can be solved by identifying a subnetwork of likely routes rather than using all possible routes between an O-D pair, although this introduces some error (e.g., Damberg, Lundgren and Patriksson 1996; Dial 1971). In addition, the inherent nature of the stochastic flow pattern makes it difficult to search for an optimal solution to the model (Sheffi 1985). Finally, under highly congested conditions the SUO pattern closely resembles the UO-S pattern. As the network becomes congested, the equilibrium effects become stronger than the route dispersion effects due to the stochastic route choice component and the SUO solution begins to resemble the UO solution (see Sheffi 1985, 336-338 for a clear and intuitive demonstration). Nevertheless, recent breakthroughs in SUO techniques are making this theoretically appealing approach more viable from a practical perspective (e.g., Leurent 1995). Some of these techniques will be discussed below.

7.3.2 Market Equilibrium and the Shortcomings of the Four-Step Approach

The "higher-level" demand patterns for TG, TD and MS are linked very tightly to the equilibrium pattern at the network-level. This results from these demands being elastic (that is, responsive) to the network flow costs. For example, the flow generated from origins can be influenced by travel costs since travelers may postpone or substitute other activities (e.g., telecommuting or teleshopping) when costs are high. Similarly, the amount of flow attracted to a destination can affect its attractiveness, i.e., greater congestion makes a destination less attractive to travelers. The amount of flow on the street network will decrease if travel costs are high and travelers switch to other modes In turn, postponing trips and switching to other destinations or modes reduces the network flow levels and therefore can lower travel costs.

At market equilibrium, the travel pattern should exhibit stability that simultaneously encompasses all four of the travel demand components. For example, at a UO-type market equilibrium, no traveler should be able to unilaterally change his or her trip propensity (TG), destination choice (TD), modal choice (MS) nor route choice (NA) without incurring higher costs. As noted above, since these components are tightly linked it is impossible to solve for each component in isolation without considering its effects on the other components. (Note, however, that empirical measurement of linkages between daily trip generation rates and other travel demands has proven to be problematical; see Southworth 1995).

The tight interconnections among the different travel demand components are clear when examining the formal conditions for market equilibrium given a UO-S network equilibrium. As with a UO-S network equilibrium, we identify the minimum travel cost between an O-D pair for each mode (13-13) and only allow positive flow levels on routes that exhibit that minimal cost (13-12). We also require the summed route flows for each user class between an O-D pair to equal the total travel demand for that O-D pair (13-14). Similarly, route costs are also required to be the sum of the costs for the arcs that comprise each route (13-15). Finally, all route flows and minimum costs must be non-negative (13-16). However, unlike the UO-S conditions, the O-D travel demands are no longer fixed and exogenous but dependent on the minimum route costs between the O-D pair. The summed route flows between an O-D for a mode now must equal an aggregate travel demand level determined by the travel costs between that pair (13-14). Since these costs in turn depend on route flows, we have a "Gordian Knot" of intertwined influences that must be met simultaneously.

The functional dependencies among the different travel demand components in the market equilibrium conditions requires any travel demand model to link in a theoretically consistent manner the different travel demands, their influences on travel costs and the influence of these costs on demands. Without these explicit linkages, the model does not meet the market equilibrium requirements and is consequently misspecified (Aashtiani and Magnanti 1981; Fernandez and Friesz 1983). The traditional, four-step approach violates these market equilibrium conditions (or, more correctly, does not guarantee these conditions) since it does not contain theoretically consistent links among the components nor an explicit mechanism for satisfying the equilibrium conditions simultaneously across all components. In contrast, convergence is the very essence of the equilibrium approach and is central to the solutions generated by these models (Boyce, Zhang and Lupa 1994).

Several studies have demonstrated the weakness of the four-step approach. As far back as the mid-seventies, Florian, Nguyen and Ferland (1975) determined that sequential estimation with feedback loops of TD --> NA does not converge to a consistent solution. More recently, a study by COMSIS Corporation (COMSIS 1996) compared the four-step approach without feedback to the same approach with several different feedback mechanisms and a theoretically-consistent network-equilibrium approach, specifically, the Evans (1976) algorithm (referred to as the "method of optimal weighting" in the report). The "direct (feedback) method" did not consistently converge to an equilibrium solution. Feedback mechanisms based on the method of successive averages (MSA) compared favorably with Evans (1976) model with respect to convergence results, although the study recognizes that the MSA-based approach may not perform as well in large networks with high levels of congestion.

An extensive analysis by Boyce, Zhang and Lupa (1994) compared the four-step procedure, with and without feedback loops, with the Evans (1976) model. Specifically, the methods compared: i) one iteration through the TD --> MS --> NA with an "all-or-nothing" (AON) network assignment; ii) multiple iterations through TD --> MS --> NA with AON assignment; iii) multiple iterations through TD --> MS --> NA with AON assignment and MSA applied at each iteration; iv) multiple iterations through TD --> MS --> NA with UO-S assignment and MSA; and, v) the Evans (1976) algorithm. In many respects, the COMSIS (1996) report is similar to this study, although Boyce, Zhang and Lupa (1994) conclusions are more negative with respect to the four-step/feedback alternatives to the network equilibrium-based approach. The Evans (1976) algorithm was superior in reproducing known data, particularly key variables such as automobile link flows and total automobile trips, with only modest increases in computational effort compared with the four-step/feedback loop alternatives.

Boyce, Zhang and Lupa (1994) conclude their research paper with several recommendations that are relevant to the objectives of this current report. These recommendations are:

Progress in improving travel forecasts will not result from solving the four-step approach with feedback. Rather, progress will be achieved when professional practitioners begin to understand the requirements of the desired equilibrium solutions;
Practitioners should insist that software vendors correctly implement methods for achieving equilibrium solutions;
Federal agencies such as FHWA should conduct short courses to introduce practitioners to equilibrium-based approaches;
University instructors and textbook authors should update their courses and instructional material to produce a new generation of professionals who understand the principles of equilibrium travel models.

This research report attempts to meet some of the Boyce, Zhang and Lupa (1994) recommendations by providing an accessible review of transportation equilibrium theory and practical models within that theory. The next section of this report reviews some practical equilibrium-based travel demand models.