Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem

Jun Xie, Yu Nie*, Xiaoguang Yang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

This paper first shows that LUCE (Gentile, 2012), a recent addition to the family of bush-based algorithms, is closely related to OBA (Bar-Gera, 2002). LUCE's promise comes mainly from its use of the greedy method for solving the quadratic approximation of node-based subproblems, which determines the search direction. While the greedy algorithm accelerates the solution of the subproblems and reduces the cost of line search, it unexpectedly disrupts the overall convergence performance in our experiments, which consistently show that LUCE failed to converge beyond certain threshold of relative gap. Our analysis suggests that the root cause to this interesting behavior is the inaccurate quadratic approximation constructed on faulty information of second-order derivatives. Because the quadratic approximations themselves are inaccurate, the search directions generated from them are sub-optimal. Unlike OBA, however, LUCE does not have a mechanism to correct these search directions through line search, which explains why its convergence performance suffers the observed breakdowns. We also attempt to improve LUCE using the ideas that have been experimented for the improvement of OBA. While these improvements do work, their effects are not enough to counteract the inability to adjust sub-optimal search directions. Importantly, the fact that the search direction has to be corrected in line search to ensure smooth convergence attests to the limitation of origin-based flow aggregation shared by both OBA and LUCE. These findings offer guidelines for the design of high performance traffic assignment algorithms.

Original languageEnglish (US)
Pages (from-to)15-30
Number of pages16
JournalTransportation Research Part B: Methodological
Volume56
DOIs
StatePublished - Oct 2013

Keywords

  • Bush-based algorithm
  • Greedy method
  • Line search
  • Quadratic approximation
  • Traffic assignment

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem'. Together they form a unique fingerprint.

Cite this