Algorithms for Efficient Real-time Traffic Assignment

by R. Jayakrishnan, Univ of California, Irvine, United States,
Wei K. Tsai, Univ of California, Irvine, United States,
Yossi Prashker, Univ of California, Irvine, United States,
Subodh Rajadhyaksha, Univ of California, Irvine, United States,

Abstract: Fast algorithms are essential to accomplish real-time traffic assignment for optimal routing or traffic prediction under ATMS/ATIS. User-equilibrium and system-optimal traffic assignment problems in urban networks under given origin-destination demand has conventionally been solved with the Frank-Wolfe optimization algorithm. Despite its slow convergence after the first few iterations, this algorithm has been very popular as it does not require network path enumeration and hence any extensive computer storage. It has severe limitations if path-based solutions are required, as in the case of use in ATMS/ATIS. In view of this, and also because computer RAM storage has become extremely cheap, a fresh examination of other algorithms is warranted. In this research we examine the feasibility of gradient projection algorithms. We attempt assignments in networks of varying sizes. We have also developed efficient data structures for storage of shortest path trees from successive iterations of gradient projection. Our results indicate that gradient projection does indeed perform much faster and that it should be considered as a candidate algorithm for fast path-flow based assignments on realistically large networks.

Subject Headings: Algorithms | Traffic assignment | Traffic models | Routing (transportation) | Computer networks | Data processing | Urban areas | Convergence (mathematics)

Services: Buy this book/Buy this article


Return to search