Hyperbush Algorithm for Strategy-Based Equilibrium Traffic Assignment Problems

Zhandong Xu, Jun Xie*, Xiaobo Liu, Yu Nie

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en route at nodes, such as transit passengers’ transfer decisions, truckers’ bidding decisions, and taxi drivers’ reposition decisions. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within the same modeling framework, built on the concept of a hypergraph. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignments to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm that HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art hyperpath-based algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption.

Original languageEnglish (US)
Pages (from-to)877-903
Number of pages27
JournalTransportation Science
Issue number4
StatePublished - Jul 2022


  • hyperbush
  • hyperpath
  • strategy-based equilibrium
  • traffic assignment

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Hyperbush Algorithm for Strategy-Based Equilibrium Traffic Assignment Problems'. Together they form a unique fingerprint.

Cite this