Faster Frank-Wolfe Traffic Assignment with New Flow Update Scheme

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.