Equilibrium Solver

An origin-based algorithm for the Traffic Assignment Problem.

The code approximates expected steady-state traffic levels on road networks given demand specifications, road congestion functions and an assumption of "greedy" driver behaviour.

Features:

Gives the right answers
Convergence testing (so it can tell you the answers are right)
Rather quick
Arbitrary volume delay funtions

Possible future extensions:

Turn delays
Input routines for EMME/TransCAD data
Explicit numerical stability fixes
Parallel assignment
Documentation :)

Build reqs:

Source (on Github)
C++ compiler (works on Linux/g++ and Windows/MSVC++)

Notes:

This project provides fast route assignment procedures for networks in the format specified on Hillel Bar-Gera's page of test problems. It's reasonably efficient on Linux, though it seems to run rather slowly on Windows.

Line-endings on Windows must be CR+LF. The test problems linked above may need to be converted.

This package implements something of a cross between Hillel Bar-Gera's Origin Based Assignment and Robert Dial's Algorithm B.

Benchmarks:

Convergence data for the Chicago Regional network (1790 zones, 12982 nodes and 39018 arcs) from Hillel Bar-Gera's page of test problems are shown in the graph below. The benchmark system has a Core 2 Duo T5750 (2GHz) and 3GiB of RAM (of which the benchmark used about 2.) No use of the CPU's second core was made.

Chicago regional convergence: 1E-5 in 500s.

Looking at the recent literature, it's quite likely that the algorithm used here is not the fastest that has been developed - I wouldn't mind coding up Hillel Bar Gera's "TAPAS" and Guido Gentile's "LUCE" algorithms, but this is low priority stuff already. That said, I've had fun optimising this code to reduce memory use and runtime by getting the data into more cache-friendly layouts and more compact data structures. Lots of plans to make it quite a bit faster and more memory-efficient still, but I'm not sure anyone is ever going to actually use this...

Many thanks to Dr. Stuart Mitchell for motivating this project, and Drs. Hillel Bar-Gera and Robert Dial for their correspondence regarding the traffic assignment problem and its solution.