Efficient Algorithm for the Traffic Assignment Problem with Side Constraints

Liyang Feng, Jun Xie*, Yu Nie, Xiaobo Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The standard traffic assignment problem (TAP) is often augmented with additional constraints to address non-standard applications. These models are called TAP with side constraints (TAPSC). Despite the rising significance of TAPSC models, the ability to efficiently solve them to satisfactory precision remains limited in real-world applications. The purpose of this paper is to fill this gap by integrating a recently developed high performance TAP solver, known as the path-based Greedy algorithm, with the augmented Lagrangian multiplier (ALM) method. This paper examines how precisely the subproblems in the ALM method should be solved to optimize the overall convergence performance. It is found that insufficiently converged subproblem solutions sometimes lead to catastrophic failures, although pursuing extremely high precision could also be counterproductive. Accordingly, it is proposed to adjust the precision required to solve the subproblems based on an approximate gap measured by the augmented Lagrangian. Results of numerical experiments show that adaptively adjusting the subproblem precision limit produces a 25% speed-up compared with the algorithm with a fixed limit.

Original languageEnglish (US)
Pages (from-to)129-139
Number of pages11
JournalTransportation Research Record
Issue number4
StatePublished - Apr 2020

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Efficient Algorithm for the Traffic Assignment Problem with Side Constraints'. Together they form a unique fingerprint.

Cite this