Office of Planning, Environment, & Realty (HEP)
The following is a synopsis of the contributions and responses regarding feedback loops for travel demand models. Approaches noted by contributors as well as potential considerations and criteria for measuring convergence are also reviewed. This synthesis represents contributions made to the e-mail list that were initially made in 2005, briefly revisited in 2006 and addressed again in February, 2009 when the subject of convergence criteria for large urban area models was discussed. Additional contributions were augmented by the discussion of determining Braess' paradox.
Traditional four-step models apply trip generation, trip distribution, mode choice, and trip assignment model components in a sequential, linear and independent fashion. In general, outputs from an individual model component are used as input to the next model component without any further adjustment or refinement. The individual treatment of model components isolates decisions regarding origin-destination, mode and route. Immediately evident with this approach is the discrepancy between the input travel times used for trip distribution and mode choice, with the resulting congested weighted inter-zonal travel times from trip assignment.
In contrast by creating a nexus between the different model components in the TDM hierarchy through an iterative process, the outputs from one level of the model hierarchy become consistent with the inputs to a proceeding step in the model structure rather than exist as autonomous activities in the model chain. This sequential iterative approach to travel demand modeling is called a feedback loop process where the demand or representation of regional travel patterns by trip purpose is no longer estimated independently and irrespective of network supply as a result of having link costs (e.g. time/speed) updated for each iteration of the feedback process. As a result, the travel times used to determine trip patterns during the trip distribution process and the resulting congested travel times from assignment become increasingly consistent with each iteration of the feedback loop process. The most common feedback structure is to link trip distribution, mode choice and traffic assignment.
There are a number of approaches associated with implementing a heuristic model structure. The two most common approaches discussed are the naíve feedback and the method of successive averages (MSA). Three other approaches were also mentioned in the listserv but did not receive as much attention. The basic descriptions of the approaches follow:
Naíve: The naíve or direct feedback approach uses the demand from an initial model cycle to update travel times for the next successive iteration of the model chain. New estimates of demand are determined by updating travel times during each iteration. The resulting travel times are used directly and are not altered between iterations based on previous results. As one contributor noted, "the demand normally oscillates from one cycle to the next cycle" and convergence may be difficult. A pre-determined optimization function or fixed number of iterations is used to determine the converged solution set.
MSA: The MSA approach uses the weighted link flows or travel times from the current and previously weighted trip assignment results to compute updated links costs (e.g. time) that are reintroduced to the next iteration. Convergence is tested prior to the next iteration to determine if the difference in values being tested have diminished enough to achieve a pre-specified threshold level between iterations (e.g. travel time, link flow, or trip table stability). If convergence is not achieved, another loop is performed; otherwise, the pre-determined optimization function is satisfied or a fixed number of iterations is encountered (typically to limit computation times).
Fictive Costs (2.5 Cycles): A third approach briefly mentioned is the fictive costs approach. The initial congested weighted travel times are fed back directly for the second iteration. The results of the second iteration are averaged with the resulting times of the first iteration to obtain the final travel times.
Constant Weights: An alternative approach to the MSA application briefly mentioned in the discussion is the use of constant weights (sometimes referred to as fixed weights). Proponents of this approach feel that a predetermined weighting scheme can be identified to reduce potential oscillations between iterations and to arrive at consistent travel times. Within the general discussion, various weighting schemes (sometimes referred to as step sizes) were discussed, such as applying equal weighting or determining an optimal weighting scheme between the current and previous iteration (e.g. 70% new/30% old). Several contributors noted success with fixed Lambda values while another contributor noted success with decaying the Lambda variable with each iteration.
A fifth less discussed approach is the Evans MSA approach. Some contributors find the combined model scheme more compelling than others.
The MSA approach appears to be the most widely adopted feedback methodology implemented in the United States.
According to some contributors, determining the appropriate metric of convergence can be elusive given the array of options available to measure system-level and link level performance. It was noted by one contributor that a single parameter may not be adequate to, "sufficiently define the solution" while others emphasized that measures of system-wide convergence may be achieved without actually arriving at acceptable link level performance criteria (e.g. volumes v. count comparisons). Methods of achieving feedback convergence and the measure used to achieve convergence include:
Additional convergence measures include the GEH statistic and relative gap (traffic assignment).
The Atlanta MPO provided the following convergence criteria:
Portland Metro provided the following guidance:
Based on contributions to the e-mail list, there does not appear to be consensus regarding any one parameter or set of parameters that should be used in the averaging process to determine closure for the MSA approach. As noted above, three different approaches (i.e. travel time, trip tables, and link volumes) have been used individually or in combination (e.g. measuring convergence using trip matrices as well as link flows). Some contributors indicated experience with trip matrices converging faster than link flows. Several others felt using time was not adequate because this variable may not be stable in terms of oscillation from one iteration to the next and the resulting travel times may not be consistent with the resulting link flows.
Because the feedback process represents a holistic approach to modeling, the interaction and specifications within each individual model step may influence model results from one application to another (i.e. comparing different network alternatives). Within each loop, the traffic assignment model must be applied, which in and of itself is an iterative feedback process. Some contributors noted that the stability associated with the equilibrium assignment model may improve overall convergence (and reduce computation time) for the iterative process. Several contributors indicated that a traffic assignment stopping criteria of 0.001 or tighter (i.e. relative gap) is necessary to improve overall model convergence in a feedback mechanism.
Another variable associated with uniqueness is the input data itself. As noted, quite different solutions may be achieved, if a different set of initial conditions are utilized (e.g. input travel times – free flow times versus congested weighted times). A specific contribution concluded that no matter how beneficial feedback mechanisms may be in resolving input and output data in the sequential modeling process, the implementation of a feedback approach does not correct or overcome short-comings with model input data (e.g. demographics).
As evident in the discussion, the type and sophistication of feedback process is highly dependent on urban area size and level of congestion. As noted by some contributors, models for smaller study areas (e.g. urban areas with 50,000 in population) probably don't merit a feedback mechanism given the level of congestion typically associated with these urban areas. Conversely, the implementation of a robust feedback process was considered critical for large, heavily congested urbanized areas. Achieving tightly controlled feedback convergence also comes at an expense though. Each individual loop may take several hours, depending on the complexity of the models. It is for this reason, that some contributors noted applying a fixed number of loops. MPOs need to weigh the practical benefits of achieving improved solutions sets against the computational time and effort required to apply the models.
A few contributors posed strategic questions regarding the validity of the results. As noted by one contributor, "are the sensitivities implied in the feedback observed in the real world?" Stated another way, the optimized results may not actually reflect real-world travel behavior associated with a congested system. Several contributors noted that sensitivity tests should be implemented when comparing model results between different alternatives.
Based on the variety of e-mails on the topic, wide-spread adoption beyond very large metropolitan areas has probably been limited by the rigorous knowledge base it requires to implement a feedback mechanism. It is evident in the discussion that some contributors have significant breadth and understanding regarding the mathematics and theory behind feedback loops. As such, a number of approaches have been adopted in the modeling community. The approaches probably reflect the level of understanding of the problem, available software and the desired solution set. Conversely, some MPO staff may not have the same level of familiarity with these concepts to implement a successful feedback mechanism. As one contributor noted, "there are a lot of very poor implementations of feedback sitting on MPO computers".
Because of the array of approaches and practices associated with measuring convergence, formulating meaningfully conclusions based on the e-mail list regarding approaches, convergence parameters and measures of convergence is difficult. This does not suggest that ambiguity exists. A number of erudite contributions for each methodology and approach were made in the discussion. Clearly, each approach yielded a solution set but as one contributor noted, there are also multiple solution sets to the same problem.
The objective of the series is to provide technical syntheses of current discussion topics generating significant interest on the TMIP e-mail list. Each synthesis is drawn from e-mails posted to the TMIP e-mail list regarding a specific topic. The syntheses are intended to capture and organize worthwhile thoughts and discussions into one concise document. They do not represent the opinions of FHWA and do not constitute an endorsement, recommendation or specification by FHWA. These syntheses do not determine or advocate a policy decision/directive or make specific recommendations regarding future research initiatives. The syntheses are based solely on comments posted to the e-mail list.