Reduced gradient algorithm for user equilibrium traffic assignment problem

ABSTRACT

A path-based algorithm is developed for the static traffic assignment problem (TAP). In each iteration, it decomposes the problem into origin-destination (OD) pairs and solves each subproblem separately using the Wolfe reduced gradient (RG) method. This method reduces the dimensions of each single-OD subproblem by selecting a basic path between the OD pair and reformulating the subproblem in terms of the nonbasic paths. A column generation technique is included to avoid path enumeration in large scale networks. Also, some speed-up techniques are designed to improve the computational efficiency. The algorithm shifts flows from costlier paths to cheaper paths; however, the amount of flow shifted from a costlier path is proportional to not only the travel time but also the flow on the path. It is applied to the Philadelphia and Chicago test problems, while different strategies for choosing the basic paths are examined. The RG algorithm shows an excellent convergence to relative gaps of the order of 1.0E-14 when compared against several reference TAP algorithms.

KEYWORDS:

• Traffic assignment problem
• reduced gradient method
• path-based algorithm
• large scale network

Acknowledgement

The authors greatly appreciate the thoughtful comments and constructive suggestions of the editor and four anonymous reviewers.

Disclosure statement

No potential conflict of interest was reported by the author(s).

ORCID

Abbas Babazadeh http://orcid.org/0000-0002-3838-5220

Guido Gentile http://orcid.org/0000-0002-1523-1640

Notes

1 We run SOLA with 8 threads available to us on our PC. Using more threads (e.g. 20 threads) may speed up the algorithm but will use more memory.

2 If a smaller value is specified in Emme's SOLA and path-based traffic assignment modules, it will be converted automatically to 1.0E-7.

3 GAMS only prints up to 8 decimals on the output file.