Faster Frank-Wolfe traffic assignment with new flow update scheme

Anthony Chen, R. Jayakrishnan, Wei K. Tsai

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)

Abstract

The most widely used algorithm for solving traffic assignment problems is the Frank-Wolfe (FW) algorithm. Its popularity is attributed to its modest memory requirements and simplicity. However, it is also known that FW converges very slowly. This paper describes a method to accelerate the performance of the FW algorithm. It utilizes path information to speed the convergence of the algorithm by updating the flow pattern one origin-destination (OD) at a time. The results indicate that a FW implementation with an OD-based flow update takes less iteration to reach convergence but requires more computational times per iteration. This computational burden is due to the fact that the flow update of each OD pair requires a separate line search, which demands a significant amount of computational times, making it only competitive to the standard FW algorithm in some extreme cases. However, since the OD-based Frank-Wolfe algorithm takes fewer iterations to reach convergence, it requires much less computer storage and thus, is a better alternative to the standard FW if path-flow solutions are to be derived from a link-flow based FW algorithm.
Original languageEnglish
Pages (from-to)31-39
Number of pages9
JournalJournal of Transportation Engineering
Volume128
Issue number1
DOIs
Publication statusPublished - 1 Jan 2002
Externally publishedYes

Keywords

  • Algorithm
  • Traffic assignment
  • Transportation planning

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this