An Empirical Comparison of Alternative User Equilibrium Traffic Assignment Methods
Howard Slavin, Jonathan Brandon, Andres Rabinowicz, Caliper Corporation, US
This paper describes research on link-based, origin-based, and path-based algorithms for computing equilibrium assignment on large networks. An origin-based approach developed by the authors is shown to converge more rapidly than other methods.
This paper presents an empirical comparison of alternative methods for computing user equilibrium on large regional transportation networks. Specifically, it examines the solution characteristics, convergence behavior and associated computing times of link-based, origin-based, and path-based methods. The latter two methods use more memory and are computationally more demanding, but have been touted in the literature as converging more rapidly than the link-based Frank-Wolfe method or variants thereof that are commonly employed in planning software.
The principal motivation in searching for improved methods is achieving more rapid and/or tighter convergence in the computation of equilibrium. Greater convergence is needed for accurate forecasting the impacts associated with road and public transport projects and affects nearly all aspects and components of transportation models as well as being a major determinant of their internal consistency. Congested travel speeds are typically used to compute trip distribution and mode choice and these speeds will be incorrect if a satisfactory traffic assignment is not achieved. Due to long computational times, many models are insufficiently calibrated and converged for forecasting purposes. This problem is partly the result of and is compounded by the slow convergence of the Frank-Wolfe algorithm.
In order to perform this research, origin-based and path-based algorithms were coded following the existing literature as closely as possible and tested on networks of various sizes. An origin-based traffic assignment code written by its major proponent and made freely available for research was also tested. The initial tests revealed that the origin and path-based methods described in the literature needed improvements before they could be competitive with existing link-based codes. The path-based method did not converge on medium to large size networks. The origin-based method converged tightly but only after very long computational times rendering it impractical for project use. Once improvements were made in search procedures and in software implementation, both were found to offer some advantages with the origin user equilibrium method that we developed probably being the most promising in terms of tight convergence with a modest amount of computation time.
Association for European Transport