Hyperbush Algorithm for Strategy-based Equilibrium Traffic Assignment Problems

This recent paper extends the concept of bush to hyperbush and uses it devise a new class of algorithms for strategy-based traffic equilibrium assignment problem, of which frequency-based transit assignment is an archetype.  One of the longest papers that I’ve ever written (nearly 50 pages), the paper just appeared online in Transportation Science.    Here is a preprint  Hyperbush.

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 decision, truckers’ bidding decision and taxi drivers’ re-position decision. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within a same modeling framework, built on the concept of hypergragh. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignment 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 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.