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

Jun Xie, Nie, Yu (Marco) and Xiaoguang Yang

Transportation Research Part B: Methodological, 2013, vol. 56, issue C, 15-30

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.

Keywords: Bush-based algorithm; Traffic assignment; Quadratic approximation; Greedy method; Line search (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261513001148
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:56:y:2013:i:c:p:15-30

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2013.06.015

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().