A conjugate gradient projection algorithm for the traffic assignment problem

Der Horng Lee*, Yu Nie, Anthony Chen

*Corresponding author for this work

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

In recent years, researchers have shown interests in adopting path-based algorithms to the traffic assignment problem (TAP). The gradient projection (GP) algorithm demonstrates promising computational efficiency and convergence performance over state-of-the-practice link-based algorithms such as the widely accepted and used Frank-Wolfe (FW) algorithm. Note that GP still retains a linear convergence rate. GP thus could be slow as it is approaching the optimal solution. As a remedy, the Newton type approach becomes an intuitive candidate to improve GP's performance. In this paper, we introduce an additional projection along the conjugate gradient direction besides the ordinary gradient projection in every iteration, by which the Hessian matrix is approximated more accurately. According to our computational results, the conjugate gradient projection (CGP) improves the convergence performance greatly. The results indicate that CGP can deliver better and more reliable convergence than GP and remains its computational tractability even when large-scale networks are being considered.

Original languageEnglish (US)
Pages (from-to)863-878
Number of pages16
JournalMathematical and Computer Modelling
Volume37
Issue number7-8
DOIs
StatePublished - May 23 2003

Keywords

  • Conjugate gradient projection
  • Gradient projection
  • Path-based algorithm
  • Traffic assigment

ASJC Scopus subject areas

  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A conjugate gradient projection algorithm for the traffic assignment problem'. Together they form a unique fingerprint.

  • Cite this