Accelerating the gradient projection algorithm for solving the non-additive traffic equilibrium problem with the Barzilai-Borwein step size

Heqing Tan, Muqing Du, Anthony Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

The non-additive traffic equilibrium problem (NaTEP) overcomes the inadequacies of the additivity assumption in traditional traffic equilibrium models by relaxing the cost incurred on each path that is not a simple sum of the link costs on that path. The computation of the NaTEP heavily depends on the efficiency of the step size determination. This paper aims to accelerate the path-based gradient projection (GP) algorithm for solving the NaTEP using the Barzilai-Borwein (BB) step size scheme. The GP algorithm with the BB step size scheme uses the solution information of the last two iterations to determine a suitable step size and avoids extra evaluations of the mapping value. The proposed algorithm only needs to perform one-time projection onto the nonnegative orthant at each iteration. Two approaches with and without column generation are considered in the GP algorithm implementation. A non-additive shortest path algorithm is adopted for the column generation approach. Numerical results on four transportation networks demonstrate the superior efficiency and robustness of the GP algorithm with the BB step size scheme over the self-adaptive GP method.

Original languageEnglish
Article number105723
JournalComputers and Operations Research
Volume141
DOIs
Publication statusPublished - May 2022

Keywords

  • Barzilai-Borwein step size
  • Column generation
  • Non-additive path cost
  • Projection method
  • Traffic equilibrium

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this