Traffic Assignment Validation#

Similar to other complex algorithms that handle a large amount of data through complex computations, traffic assignment procedures can always be subject to at least one very reasonable question: Are the results right?

For this reason, we have used all equilibrium traffic assignment algorithms available in AequilibraE to solve standard instances used in academia for comparing algorithm results.

Instances can be downloaded here.

All tests were performed with the AequilibraE version 1.7.0.

As shown below, the results produced by AequilibraE are within expected, although some differences have been found, particularly for Anaheim. We suspect that there are issues with the reference results and welcome further investigations.

  • Links: 39,018

  • Nodes: 12,982

  • Zones: 1,790

Chicago Biconjugate Frank-Wolfe 1000 iterations
Chicago Conjugate Frank-Wolfe 1000 iterations
Chicago Frank-Wolfe 1000 iterations
Chicago MSA 1000 iterations

  • Links: 2,522

  • Nodes: 1,020

  • Zones: 110

Barcelona Biconjugate Frank-Wolfe 1000 iterations
Barcelona Conjugate Frank-Wolfe 1000 iterations
Barcelona Frank-Wolfe 1000 iterations
Barcelona MSA 1000 iterations

  • Links: 914

  • Nodes: 416

  • Zones: 38

Winnipeg Biconjugate Frank-Wolfe 1000 iterations
Winnipeg Conjugate Frank-Wolfe 1000 iterations
Winnipeg Frank-Wolfe 1000 iterations
Winnipeg MSA 1000 iterations

  • Links: 914

  • Nodes: 416

  • Zones: 38

Anaheim Biconjugate Frank-Wolfe 1000 iterations
Anaheim Conjugate Frank-Wolfe 1000 iterations
Anaheim Frank-Wolfe 1000 iterations
Anaheim MSA 1000 iterations

  • Links: 76

  • Nodes: 24

  • Zones: 24

Sioux Falls Biconjugate Frank-Wolfe 1000 iterations
Sioux Falls Conjugate Frank-Wolfe 1000 iterations
Sioux Falls Frank-Wolfe 1000 iterations
Sioux Falls MSA 1000 iterations

Convergence Study#

Besides validating the final results from the algorithms, we have also compared how well they converge for the largest instance we have tested (Chicago Regional), as that instance has a comparable size to real-world models.

Algorithm convergence comparison
Algorithm convergence comparison
Algorithm convergence comparison
Algorithm convergence comparison

Not surprisingly, one can see that Frank-Wolfe far outperforms the Method of Successive Averages for a number of iterations larger than 25 in the case of Chicago, and is capable of reaching 1.0e-04 just after 800 iterations, while MSA is still at 3.5e-4 even after 1,000 iterations for that same case.

The actual show, however, is left for the biconjugate Frank-Wolfe implementation, which delivers a relative gap of under 1.0e-04 in under 200 iterations, and a relative gap of under 1.0e-05 in just over 700 iterations.

This convergence capability, allied to its computational performance described below suggest that AequilibraE is ready to be used in large real-world applications.

Computational performance#

All tests were run on a desktop equipped with an Ryzen 9 6900HX (14 cores used only) running Windows 11 Pro.

On this machine, AequilibraE performed 1,000 iterations of biconjugate Frank-Wolfe assignment on the Chicago Network in around 442 seconds, or around 0.4422s per iteration (other algorithms are as low as 0.42 seconds per iteration).

This performance is substantially better than seen on previous versions and is on par with that of commercial software.

Note

The biggest opportunity for performance in AequilibraE right now it to apply network contraction hierarchies to the building of the graph, but that is still a long-term goal

Want to run your own convergence study?#

If you want to run the convergence study in your machine, with Chicago Regional instance or any other instance presented here, check out the code block below! Please make sure you have already imported TNTP files into your machine.

In the first part of the code, we’ll parse TNTP instances to a format AequilibraE can understand, and then we’ll perform the assignment.