An Efficient Algorithm for Continuous Bi-Criteria Traffic Assignment

• 成果类型: Article; Early Access
• 署名作者: Xie, Jun; Wang, Qianni; Li, Jiayang; Nie, Yu (Marco)
• 署名单位: Southwest Jiaotong University; Northwestern University; University of Hong Kong
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.0761
• 发表日期: 2026-06-15
• 关键词: continuous bi-criteria traffic assignment; single boundary adjustment; projected quasi-Newton method; NETWORK EQUILIBRIUM; USER HETEROGENEITY; MODEL; multiclass; IMPACT; cost

摘要

The continuous bi-criteria traffic assignment (C-BiTA) problem aims to find the distribution of agents with heterogeneous preferences in a network. The agents can be seen as playing a congestion game, and their payoff is a linear combination of time and toll accumulated over the selected path. We rediscover a formulation that enables the development of a novel and highly efficient algorithm. The novelty of the algorithm lies in a decomposition scheme and a special potential function. Together, they reduce a complex assignment problem into a series of single boundary adjustment (SBA) operations, which simply shift flows between adjacent efficient paths connecting an origin-destination (O-D) pair by using a projected quasi-Newton method. The SBA algorithm is capable of producing highly detailed path-based solutions that hitherto are not widely available to C-BiTA. Our numerical experiments, which are performed on networks with up to forty thousand links and millions of O-D pairs, confirmed the consistent and significant computational advantage of the SBA algorithm over the Frank-Wolfe algorithm, the widely used benchmark for C-BiTA. In most cases, SBA offers a speed-up of an order of magnitude. We also uncover evidence suggesting the discretization-based approach-or the standard multiclass formulation-is likely to produce far more used paths per O-D pair than C-BiTA, a potential computational disadvantage. Equipped with the proposed algorithm, C-BiTA, as well as its variants and extensions, could become a viable tool for researchers and practitioners seeking to apply multicriteria assignment models on large networks.