A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models

Muqing Du, Heqing Tan, Anthony Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)

Abstract

Step size determination (also known as line search) is an important component in effective algorithmic development for solving the traffic assignment problem. In this paper, we explore a novel step size determination scheme, the Barzilai-Borwein (BB) step size, and adapt it for solving the stochastic user equilibrium (SUE) problem. The BB step size is a special step size determination scheme incorporated into the gradient method to enhance its computational efficiency. It is motivated by the Newton-type methods, but it does not need to explicitly compute the second-order derivative. We apply the BB step size in a path-based traffic assignment algorithm to solve two well-known SUE models: the multinomial logit (MNL) and cross-nested logit (CNL) SUE models. Numerical experiments are conducted on two real transportation networks to demonstrate the computational efficiency and robustness of the BB step size. The results show that the BB step size outperforms the current step size strategies, i.e., the Armijo rule and the self-regulated averaging scheme.

Original languageEnglish
Pages (from-to)982-999
Number of pages18
JournalEuropean Journal of Operational Research
Volume290
Issue number3
DOIs
Publication statusPublished - 1 May 2021

Keywords

  • Barzilai-Borwein step size
  • Cross-nested logit
  • Path-based traffic assignment algorithm
  • Stochastic user equilibrium
  • Transportation

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models'. Together they form a unique fingerprint.

Cite this