Menu
French

Traffic assignment choices at Emme 4.1

With the new SOLA and PToll traffic assignment procedures in Emme 4.1, there is even more choice for Emme users to select the best traffic assignment for their model applications. Curious how to choose the right one? Here we summarize some criteria which may be helpful in picking the best traffic assignment for the job.

Meet the candidates. Traffic assignment algorithms at Emme 4.1:

  • Standard traffic assignment. Based on a multithreaded linear approximation method.
  • Path-based traffic assignment. Based on a projected-gradient method.
  • SOLA (Second Order Linear Approximation) traffic assignment. Based on a multithreaded conjugate/bi-conjugate variant of the linear approximation method.
  • PToll traffic assignment. Based on the SOLA traffic assignment but with special consideration for tolling applications.

A note to the reader that the discussion below refers specifically to the Emme design and implementation of these procedures. Conclusions may or may not be transferable to other implementations, despite any similarities in naming. Also, this discussion concerns static traffic assignment. For dynamic traffic assignment see Dynameq.

Computational performance

The following convergence chart compares SOLA traffic assignment (run with 2- , 8- and 32-threads), Standard traffic assignment (run with 2- , 8- , and 32-threads), and Path-based traffic assignment (cold start and warm start).convergences

Test runs are from a Seattle planning network, with approximately 1200 zones, 20000 links and 17000 turns, with 11 user classes and future-year demand resulting in highly congested conditions; courtesy Puget Sound Regional Council. As run on Intel Xeon ES-2690, 2.9 GHz (16 cores) with 64-bit Windows 7 Professional SP 1. Number of threads is a user-setting of the Standard and SOLA traffic assignments.

The chart illustrates some rules of thumb. First, the SOLA traffic assignment outperforms the Standard traffic assignment in all cases. Second, the SOLA traffic assignment is generally faster on a multithreaded system with 8 cores (including Intel hyper-threaded 'logical' cores) than is the Path-based traffic assignment (without warm start) for relative gaps up to 10-5. Given requirements of current practice, SOLA traffic assignment is the best starting point for most applications.

Furthermore, because the SOLA traffic assignment provides a convenient drop-in replacement for the Standard traffic assignment, with full path analysis and specification support, there is no longer any reason to continue to use the Standard traffic assignment. (Although some users may still require the latter to meet legacy requirements with older, more loosely converged models.)

From the curve labeled Path-based (cold start) one may be tempted to relegate application of the Path-based traffic assignment only to projects requiring highly-sensitive economic analysis, ie. tighter convergences of relative gaps 10-6 and beyond. But when we consider warm starts this generalization may not hold.

Warm starts and skims

During travel model equilibration traffic assignments are run multiple times with varying class demand at each iteration. At a given iteration, the demand normally resembles that from the previous iteration. Because similar demand results in similar network loading, re-using path information from the previous traffic assignment can be a substantial time savings. The Path-based traffic assignment offers such a "warm start" feature that can re-use class paths saved on disk from previous runs.

Now consider the curve labeled Path-based (warm start) above. To produce this curve we ran a Path-based traffic assignment using warm start in which each of the 11 class demand matrices was randomly perturbed by multiplying each matrix cell with a value drawn from a normal distribution with mean 1 and standard deviation 0.1. (Thus, most of the data will fall between +/-20% of the original values.) With warm start, the Path-based traffic assignment is much more competitive in terms of total model run time, even when used with conventional relative gap ranges of 10-3 to 10-5.

Another benefit of the Path-based traffic assignment is that subsequent, additional skim matrix computation, select-link, select-turn or other path analyses or cutoff analyses can be performed without re-running the assignment. This can also help save model run time.

Results and application

The SOLA traffic assignment, Path-based traffic assignment and Standard traffic assignment procedures all provide:

  • Compatibility with all user-defined volume-delay and turn-penalty functions (no modifications needed)
  • Multi-class support
  • Full implementations of user-defined Emme path analysis (including select-style analyses) and cutoff analysis

Thus, independent of the procedure selected, the modeller can expect general suitability for a wide-range of applications and to compute any ad hoc or model-automated analysis or metric.

But not all results are unique at convergence. And the characteristics of non-unique results tend to differ by traffic assignment procedure.

Proportionality and uniqueness

Thanks to the work of Hillel Bar-Gera, David Boyce and others, planners today are generally cautioned against the direct application of user equilibrium path- and class link-flows for decision-making unless additional conditions, including proportionality, are imposed.1 But since it was generally accepted that only bush-based methods with post-processing2, or more recently TAPAS3, were the only ways to meet these conditions, planners were unaware of a computationally attractive alternative for use on multi-class networks.

Research recently presented by INRO4 shows that a sufficiently well-converged SOLA traffic assignment exhibits path-flow and class link-flow uniqueness.

SOLA and uniqueness of path- and class link-flows

Proportionality asserts that the proportions of flow on alternative route segments with equal costs are the same for all drivers, regardless of their class, origin, or destination.

To verify proportionality with the SOLA traffic assignment (relative gap 10-6), we first compute the ratio of travelers by O-D pair traversing the lower (red) vs upper (blue) paired-alternative route segments, as illustrated below, on one of the paired-alternative segments identified by Bar-Gera, Boyce and Nie (2012). The resulting slopes, both for the car and truck class, are 200/233=0.8584 : the same as the ratio of the class (and total) link flows on the paired-alternative segments.6 pas

Next, we compare class link-flows from the SOLA traffic assignment at relative gap 10-6 against TAPAS results at relative gap 10-12. Note that they produce almost identical results. The log scale is also included to illustrate the very small differences in some class link-flows. At the bottom of this page we have included additional class link-flow comparisons between SOLA at 10-3, 10-5, and 10-7 relative gaps and TAPAS at 10-12. TAPAS results at 10-12 relative gap and the two-class Chicago test network were graciously provided by Professor David Boyce.6 cars and trucks

As a general rule of thumb, for any reasonably well-converged SOLA traffic assignment, the uniqueness of path- and class link-flows in most travel demand forecasting applications need not be a practical concern.

Note that proportionality does not hold for the Path-based traffic assignment, which typically produces a smaller path set (at equilibrium). Unlike SOLA, Path-based class link- and path-flow results are not unique at equilibrium. Also, related analyses using paths may require care in interpretation. For instance, subarea demand at gates may appear 'lumpy' after a traversal analysis, even though subarea demand correctly reproduces total link flows. This is one reason we do not encourage traversal analysis with the Path-based traffic assignment.

Toll modelling

Emme users who need results from specific tolling schemes like ramp-to-ramp or distance-based tolls with caps5 can now use the PToll traffic assignment. PToll includes the performance benefits and proportionality properties of SOLA, but manages internally the network construction details necessary for toll modelling applications and provides a convenient way to specify and skim for multi-class tolling applications.ptoll ramps

Multithreading and results stability

The performance achieved by the SOLA traffic assignment and the Standard traffic assignment is due in large part to multithreading for parallel processing. One question we have been asked repeatedly concerns the stability of multithreaded assignment results across number of threads used. Although floating point arithmetic is notoriously variable across CPU architectures and instruction sets as well as compiler and optimization settings, steps can be taken to mitigate these effects. In Emme, traffic assignment results are stable regardless of the number of threads used, especially when run on computers with the same CPU architecture (eg. Intel vs AMD). The number of threads is a user setting of the assignment, and can be set to keep one or more threads free for other work, for instance, while running assignments locally.

PSRC 12 classes scenario XY chart SOLA 4 vs 8 threads

A comment on bush-based algorithms

Several bush-based algorithms for computing equilibrium assignments with very finely converged flows exist, see Bar-Gera (2002), Dial (2006) and Gentile (2012). INRO has experimented with bush-based algorithms for traffic assignment and found that they do not perform as well as other alternatives. While the performance on single-class networks is exciting, we have not yet seen them scale as well for the (most common) case of multiple traffic classes. That's why none of our bush-based traffic assignment prototypes have yet been generally released in Emme.

Distributed computing vs multiprocessing

It is very well known that the traffic assignment problem is most efficiently parallelized on shared memory multiprocessing systems, not distributed computing systems. This is certainly true, at least, for the methods described here.


Summary

  • The SOLA traffic assignment on 8 cores (physical or logical) is an excellent choice for applications requiring relative gaps 10-4 to 10-5
  • The Path-based traffic assignment is also an excellent choice for multi-class travel demand forecasting applications when warm starts are used during equilibration
  • For a reasonably well-converged SOLA traffic assignment, the uniqueness of path- and class link-flows should not be a practical concern
  • For travel demand forecasting applications using the Path-based traffic assignment, proportionality can still be achieved for analysis by using the SOLA traffic assignment in the last feedback loop
  • If you are using the Standard traffic assignment or parallelized Standard traffic assignment (or Emme Prompt Module 5.21 or 5.22), you can upgrade seamlessly to the new SOLA traffic assignment at Emme 4.1
  • The PToll traffic assignment provides all the benefits of SOLA with additional toll modeling features

Hopefully these collected notes from our team help to illustrate some of the tradeoffs in choosing the best traffic assignment for the job. Should you have any applications to discuss, or any questions or comments, please do not hesitate to contact us, or follow us on Twitter for updates.


References

  1. Bar-Gera, H., Boyce, D., Nie, Y. (2012) Consistent route flows and the condition of proportionality. Transportation Research, Part B, 46(3), 440-462.
  2. Boyce, D. and Xie J. (2013) Assigning user class link flows uniquely. Transportation Research, Part A, 53, 22-35.
  3. Bar-Gera, H. (2010) Traffic assignment by paired alternative segments. Transportation Research, Part B, 44(8–9), 1022-1046.
  4. Florian, M. and Morosan, C.D. (2014, April) On uniqueness and proportionality in multi-class equilibrium assignment. Proceedings of Transportation Research Board Innovations in Travel Modeling, April 2014
  5. Morosan, C.D. and Florian, M. (2014, April) A network model for capped distance-based tolls. Proceedings of Transportation Research Board Innovations in Travel Modeling, April 2014