Traffic Analysis Toolbox Volume XIV: Guidebook on the Utilization of Dynamic Traffic Assignment in Modeling

2.0 DTA Fundamentals

Dynamic Traffic Assignment (DTA) is a modeling approach that captures the relationship between dynamic route choice behaviors (path and start time) and transportation network characteristics. DTA research in the last four decades consisted of a wide range of traveler behavior assumptions, model formulations, and solution algorithms. This guidebook discusses DTA models from the perspective of equilibrium-based and non-equilibrium-based models, related to the most common and practical transportation modeling and planning applications.

From a traveler behavior standpoint, DTA is a technique that allows for modeling of both long-term traveler adaptation to experienced congestion and modeling of traveler behavior in response to unexpected congestion that occurs within a single day.

A collection of link volume data over multiple days for a freeway location on I-25 outside of Denver, Colorado is presented in Figure 2.1 to illustrate traffic variability over a 24-hour period. DTA aims to identify and depict the time-varying traffic patterns inherently consistent with actual congestion dynamics, which are characterized by time dependence and variability of traffic data across multiple observations.

Figure 2.1 Traffic Variability

Source: University of Arizona.

2.1 DTA Primer Background

The Primer for Dynamic Traffic Assignment (Chiu, Bottom, Mahut, et al., 2011), published by Transportation Research Board (TRB), addresses the core concepts necessary for understanding DTA in relation to the static traffic assignment (STA) in terms of “equilibrium.” Equilibrium in DTA is typically based on the premise that the experienced travel time for all used routes is the same for travelers departing at the same time.

The DTA primer purposely left out other types of DTA models relevant to Wardrop’s principle (e.g., system optimal) or non-equilibrium-based DTA models (e.g., reactive models). Other definitions of DTA models found in the literature depict DTA from the following perspectives.

• Route choice from the traveler’s standpoint;
• Routing policy from the system’s standpoint;
• Different objectives, including user optimal, system optimal, or local optimal;
• Behavior assumptions, including repeated learning, reactive, or decisions based on limited information; and
• Information availability, including no information, pre-trip information, en route information, etc.

Because of the existence of such a diversified body of DTA models with different behavior assumptions and model formulations, the analysis team should avoid applying any models that claim to include DTA without a careful examination of the route choice behavior on which the model is based. It is important to select a DTA modeling approach based on route choice behavior that is most relevant to the problem of interest. The following are some cases that illustrate the types of DTA approaches consistent with the definition used in this guidebook.

Case 1. Long-Term Work Zone Impacts

If the problem is to evaluate the impact to highway capacity caused by a long-term work-zone condition, it is intuitive to assume that over time daily travelers of the highway would be motivated to try different routes. Eventually these daily travelers (after repeated learning) will settle down to a set of optimal routes that best satisfy their travel objectives. This decision process requires an equilibrium-based DTA to properly depict the final individual route choice.

Case 2. Emergency Evacuation

If the problem of interest is to understand what the best possible network performance could be for coordinating all travelers during an emergency evacuation situation, then the System-Optimal DTA model is more appropriate than the User-Optimal type of DTA modeling approach (Peeta 1994; Ziliaskopoulos 2000; Peeta and Ziliaskopoulos 2001; Zheng and Chiu 2010). System-Optimal-DTA is a widely discussed DTA modeling approach in which the goal of the model is to solve for the assignment policies that lead to optimal system performance as opposed to the optimal performance of an individual. More discussion of evacuation modeling is presented in Chapter 3.

Case 3. Traveler Information Systems

DTA can address the problem of understanding the impact of en route information that allows travelers to regularly receive updated traffic information and reroute as needed. This could include testing of both local and decentralized routing policies (Kuwahara and Akamatsu 1997; Chiu and Mahmassani 2001; Peeta and Ziliaskopoulos 2001; Gao and Chabini 2006).

Case 4. Short-Term Incident

If the problem is to test an unexpected event such as a freeway incident, it is reasonable to assume that travelers will react to increasing congestion and changing traffic dynamics based on their instantaneous judgment as well as information from various channels. To model this some form of a non-equilibrium-based DTA modeling approach would be more appropriate than an equilibrium-based modeling approach. The DTA approach for short-term traveler responses should include en route diversion and information capabilities.

Case 5. Short-Term and Long-Term Analysis Capabilities

Agencies may also be concerned with both the short-term and long-term impacts of a project. For instance, multiple modeling approaches may be needed to model a multi-year freeway construction project. The approach to identifying the correct application is to set clear parameters that highlight the need for both equilibrium and non-equilibrium DTA modeling methods. Ideally these two modeling methods are part of the same modeling software and the user does not have to create different models. The analysis team should also examine the objectives of the project and determine the modeling approach with the route choice behavior that is consistent with the application of interest.

Case 6. Capacity Improvement Studies

DTA can be used to test the effects of capacity improvements such as new lanes. For instance, DTA can be useful in assessing the impacts of a new freeway lane (or lack thereof) to adjacent roadways.

2.2 Equilibrium-Based DTA Approach

Wardrop’s User-Equilibrium principle (Wardrop 1952) as stated below defines the equilibrium condition that many transportation models and algorithms are developed to satisfy.

Many models and algorithms were developed in the realm of equilibrium-based DTA since the 1970s (Yager 1971; Merchant and Nemhauser 1978; Merchant and Nemhauser 1978; Ghali and Smith 1992; Mahmassani, Hu, Peeta, et al. 1993; Ben-Akiva 1996; Boyce, Lee and Ran 2001; Florian, Mahut, and Tremblay 2001). Peeta and Ziliaskopoulos (2001) provide a comprehensive review of DTA’s history and future perspectives. The following is the commonly agreed-upon dynamic (time-dependent) user equilibrium (TDUE or DUE) condition that is directly related to and extended from the original user equilibrium (UE) condition.

In DTA the DUE condition applies to each O-D pair and departure time and is relevant to those travelers who travel at the same time period between the same O-D pair. In STA, path travel time is simply the summation of link travel times evaluated using some form of link travel time function. However in the DTA context, link/node travel times are time-varying due to the onset and dissipation of congestion. What travelers care about is the time they would actually experience traversing the chosen path. As such, the experienced travel time for a chosen path needs to consider the time instance at which travelers arrives at each link. Recognizing this time dependence would lead to a path choice that is consistent with the route choice behavior in a congested network (Chiu, Bottom et al. 2011).

Equilibrium-Based DTA Algorithmic Procedures

The algorithmic procedures of STA and DTA share comparable structures. At their core they include an evaluation of the following:

• Shortest paths. The purpose of a shortest path algorithm is to search for a new solution in the current iteration using the network traffic data produced by the network loading step. The shortest path in STA is the same across the entire time horizon, and therefore only one shortest path exists per O-D pair. In DTA, travel times vary in time increments and therefore a time-dependent shortest path (TDSP) is calculated for each origin-destination-departure time increment (O-D-T) combination. The distinct feature of TDSP from the traditional SP is that the shortest path search considers the experience travel time of the next searched link based on the arrival time at the previous link (Gallo and Pallotino 1988; Ziliaskopoulos and Mahmassani 1993; Chabini 1998; Daganzo 2001).
• Assignment of trips to paths. In STA, the purpose of this step is to determine, for a given amount of trips travelling between an O-D pair, the assignment of trips to a set of routes such that the resulting travel times for the possible routes are equal. In equilibrium-based DTA this step applies to the O-D-T. Aside from the classic Frank-Wolfe algorithm, some of the modern methods include gradient projection (A common step of non-linear optimization solution algorithm)(Florian and Nguyen 1974; Wie, Friesz, and Tobin 1987) and origin-based or bush-based algorithms ((Bar-Gera and Boyce 2003; Dial 2006). The commonly used assignment algorithm for earlier DTA models is the method of successive average (MSA) (Sheffi 1984), but most of the modern methods apply gradient projection-based methods explicitly, aiming to reduce the relative gap.
• Loading of trips on the assigned paths and evaluation of the resultant traffic conditions. The purpose of loading trips to the network is to evaluate whether the latest assignment leads to satisfactory convergence or not.

Figures 2.2 and 2.3 show algorithm structures for Static and Dynamic Traffic Assignments, respectively.

Figure 2.2 Static Traffic Assignment Algorithmic Structure

Source: DTA Primer, with permission from UA.

Figure 2.3 Dynamic Traffic Assignment Solution Algorithm Framework

Source: DTA Primer, with permission from UA.

The STA problem is typically formulated as a mathematical programming/variation inequality problem. Due to its convexity in objective function and constraint sets, this problem has one unique optimal assignment solution. When a good assignment algorithm (one that is proven to reach the optimal assignment solution) approaches to UE, the link flow changes diminish; therefore, link flow change is the proxy measure of the UE condition and is often used as the stopping criterion because link flows are easy to measure. One should note, however, that diminishing link flow change is the necessary condition of UE but not the sufficient condition. In other words, an algorithm that is approaching the UE condition will also produce diminishing link flow change, but an algorithm that diminishes the link flow change does not necessarily guarantee to lead to the UE condition.

In DTA, using algorithms that use constantly changing travel times not only means calculating route travel times many times during the modeling period but also anticipating the future travel times of links along a driver’s path. In turn, these new travel times are used to determine a vehicle’s path. This process is depicted in Figure 2.4. Because travel times may change between the time the vehicle departs and the time the vehicle actually traverses a section of road, it is the “future” travel time that drivers use to assess their path choices. Most sophisticated DTA models operate in this fashion; whereby, route travel times are developed using not a snapshot of link travel times at the beginning of the trip, but instead a string of travel times equal to the sum of the travel times of each link in the route based on the time the vehicle will reach this link.

Figure 2.4 General DTA Algorithmic Procedure^a

Source: DTA Primer, with permission from UA.

^a Chiu, Bottom et al. 2011.

Relative Gap

The goal of DUE models is to achieve a satisfactory level of convergence around the equilibrium condition. The measure of convergence used is often the Relative Gap, which compares the current assignment solution to the ideal shortest-route time for all O-D pairs and all departure intervals.

The relative gap is a rather common stopping criterion also used by static traffic assignment models. The typical definition of the total relative gap is as follows:

Where

 = set of all departure time intervals

 = departure time interval,  ∈ 

 = set of all origin-destination trip pairs

 = origin-destination trip pair,  ∈ 

 = set of all used routes for origin-destination pair

 = used route for origin-destination pair ,  ∈ 

 = flow from used route at departure time interval

 = experienced travel time on used route at departure time interval

 = total flow from origin-destination pair at departure time interval

 = shortest route travel time from origin-destination pair at departure time interval

The numerator is the total gap, which measures how far the current assignment solution is from the ideal shortest route time. Since the travel-time on all used routes will always be greater than or equal to the shortest route, the value of relative gap will never be negative. In most DTA applications, the solution is assumed to have converged to an equilibrium solution when the relative gap is less than a pre-specified tolerance level. Tolerance levels should be specified based on variability observed in field data. For more detailed information on the subject see Chapter 6 of the Guidance on the Level of Effort Required to Conduct Traffic Analysis Using Microsimulation.

Convergence occurs through an iterative process consisting of three sequential steps: Network Loading, Path Set Updating, and Path Assignment Adjusting. At each iteration, vehicles are dynamically loaded onto the network based on the path assignment, and new travel times are recorded. These new travel times are used to calculate the new shortest paths for each O-D pair and departure interval. Then, depending on the algorithm, a percentage of trips between each O-D pair and departure interval is assigned to different paths from those they used on the previous iteration, generally moving from higher cost paths to lower cost paths. The process repeats until the convergence criterion such as Relative Gap is met. Figure 2.4 depicts the general DTA algorithmic procedure.

Other Stopping Criteria

In addition to Relative Gap as a measure of model convergence, other measures of a model’s stability include waiting vehicles at entry locations, gridlock, and stable link flows and travel times. These different criteria are discussed below.

Waiting Vehicles

In a DTA model, vehicles can wait at their loading points if they cannot begin their trip in their assigned departure time. Waiting problems often indicate heavy congestion in the vicinity of the entry links, a network coding error (poor connectivity), or a demand error (surge of demand). Typically, a model run with a high number of waiting vehicles is not a valid one. Such a situation should be avoided because it can significantly complicate the modeling of alternative scenarios.

Gridlock

Gridlock in a DTA model can occur when one or more vehicles cannot move forward because another vehicle is blocking their movement. No useful simulation statistics can be obtained from a gridlocked network because the flow is zero and the travel time is infinity for one or more links. Gridlock can continue indefinitely unless it is possible for one or more drivers to change course and arrive to their destinations though another route. The analysis team should review the simulation software manual for potential causes of gridlock and potential remedies.

Stable Link Flows and Travel Times

A Relative Gap of zero is probably not achievable in a DTA model due to the stochastic nature of the traffic simulation. The analysis team should be aware of the range in link flow and travel time variations, and adjust the target Relative Gap accordingly. More model convergence iterations are required when link flows or travel times are not stable. Section 7.3 provides more discussion on model convergence.

2.3 Non-Equilibrium DTA Approach

DTA-related terms have been used to describe rather different procedures and concepts that involve assigning a route to a vehicle. One concept is the one-shot simulation approach that regularly updates and assigns routes to newly-generated or en-route vehicles. The route choice mechanism in the non-equilibrium DTA approach reflects the situation in which drivers are reacting to information (including that gained by direct observation) about unexpected traffic conditions or environmental conditions and using this information in conjunction with the knowledge gained by adaptation (day-to-day learning) to experienced traffic conditions.

The non-equilibrium DTA approach is a desirable capability when evaluating unexpected events such as incidents, evacuations, or even the presence of pre-trip or en route real-time information. In the case of an incident, travelers need to assess and react to this particular event that was not considered when the traveler chose his/her initial route. A decision may need to be made as to where, when, and how to choose a different route to mitigate the impact of the event. For example, assigning a driver with an instantaneous shortest path at the time of departure would imply that the driver is accessing real-time information (e.g., TV, web, or smartphone) and chooses the route that is the best at time of departure. With the increasing use adoption of navigation devices and software, a higher percent of the traveling public may be developing this sort of route choice behavior as part of their commute in the future.

In the non-equilibrium DTA modeling approach, each vehicle is assigned an initial route when starting the trip. Different types of routes may be assigned to vehicles and each type corresponds to distinct behavior and information assumptions. These types of routes may include habitual routes, instantaneous shortest paths, and analyst-defined routes. The habitual routes can be supplied from a previously completed DUE model run. Doing so would assume that vehicles select a route based on prior knowledge and experience of the network condition. Instantaneous shortest paths are typically calculated regularly during simulation by using snapshots of the network’s traffic state. Such sets of routes are made available for all newly generated vehicles until the next time instance at which a new set of shortest path times is calculated. This type of routing can be regarded as the outcome of pre-trip traveler information, where vehicles departing at different times access the best routes known at the departure time. The last type of routing is manually specified by the analyst based on certain objectives and needs.

In non-equilibrium DTA, it also possible to divert vehicles en route in response to endogenous and/or exogenous stimuli. The endogenous stimuli could be the assessment of the level of deviation of the present route in contrast to the habitual routes. If the perceived delay exceeds a certain threshold, the vehicle may choose to divert to a different route. The exogenous stimuli could be triggered by travel information systems, such as DMS or in-vehicle device (e.g., radio or smartphone), equipped to receive real-time updates. Travelers utilize this information to access travel time for the remaining length of their journey.

Algorithmic Structure for Non-Equilibrium DTA Approaches

Some documents refer to an approach in which the route set and flows are predefined and remain unchanged throughout the simulation (see Figure 2.5) as static assignment, but the use of “assignment” is different from the concept of the equilibrium-based DTA.

Figure 2.5 Static Assignment in a One-shot Simulation

Source: DTA Primer, with permission from UA.

A basic approach to one-shot assignment has shortest routes regularly updated based on prevailing traffic conditions (i.e., instantaneous link travel times) and has these routes “assigned” to newly generated vehicles at the start of the trip. This is sometimes referred to as dynamic assignment (see Figure 2.6), yet it should be recognized as a different notion of assignment from the equilibrium-based DTA methods.

Figure 2.6 Dynamic Assignment (with Feedback) in a One-shot Simulation

Source: DTA Primer, with permission from UA.

In a more flexible one-shot method, in addition to applying the above assignment approach for newly generated vehicles, each traveler (or a subset of travelers, called “informed travelers”) reevaluates the current route at each decision node, based on current (instantaneous) link travel times. A decision node is one at which there is at least one feasible route to the destination on two or more of the outgoing links of the node. This approach allows the traveler to divert away from the current route for a better one for the remaining trip, as a result of changes in link travel times since the last route choice was made (at an earlier decision node, or at the origin node). This method is sometimes referred to as one-shot dynamic assignment with feedback, but again, one must distinguish between this method and the notion of assignment defined for the equilibrium-based DTA.

2.4 Multiple Traveler Classes (MTC)

The multiple traveler class DTA model implementation allows stratification of the traveler mix to follow different route choice behavior. In the MTC framework, a certain percent of travelers may choose to follow the DUE route choice principles, whereas others may choose to follow pre-trip or en route information, rendering their route choice “memoryless” and more responsive to unfolding traffic. With the increasing use of smartphones and in-vehicle telematics capabilities, a larger number of tripmakers may be following the routes recommended by navigation systems. In this case, the MTC modeling capability becomes relevant and advantageous as it improves modeling realism, granularity, and flexibility.