Scholarlink

<p>Efficiently solving the traffic assignment problem (TAP) is important in urban transportation planning. Until now, most algorithms for solving TAP are serial and confined to a single-computer operation, which inherently limits their computational efficiency. There are several pressing challenges faced by algorithms for solving TAP: i) the growing scale of traffic networks and increased travel demands often render traditional serial algorithms inadequate for real-time applications; ii) despite the potential benefits of parallel processing, there is a scarcity of research on effective model decomposition and parallel algorithm development; and iii) existing algorithms rarely leverage iterative information from multiple previous steps, which could enhance computational performance. To address these challenges, this study introduces a randomized partially symmetric algorithm based on the alternating direction method of multipliers (ADMM), referred to as the rpsADMM, and presents its momentum-accelerated variant. Both algorithms utilize a parallel computing framework tailored to solve the TAP. The proposed rpsADMM employs a novel approach by updating Lagrange multiplier randomly twice per iteration, thereby optimizing update efficiency. The rpsADMM also updates its subproblems using a Gauss-Seidel scheme and internal variables using a Jacobi scheme, which significantly improves computational performance in large-scale traffic networks. Furthermore, to improve convergence efficiency without sacrificing parallelism, this study develops a momentum-acceleration variant of the rpsADMM, termed the ma-rpsADMM, which integrates a momentum-acceleration strategy that combines the iterative patterns of both the Polyak heavy ball and successive over-relaxation methods after each block iteration. Extensive testing on three real-world traffic networks shows that both algorithms considerably reduce computation times while maintaining robust parallel capabilities and improving convergence. Specifically, the test results demonstrate that the computation times of the proposed ma-rpsADMM are 72.7%, 25.1%, and 75.7% less than those of the original ADMM on three different traffic networks, respectively. These findings provide valuable insights and reliable tools for TAP-solving, supporting efficient decision-making in traffic planning and management.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Randomized partially-symmetric ADMM-based algorithm and its momentum-accelerated variant for traffic assignment problem

  • 期刊论文

  • 发表日期：

    2025年6月14日

查看全文
  • Pengjie Liu,
  • Feng Shao,
  • Hu Shao,
  • Chunkai Tang,
  • Haoning Xi,
  • Shengbei Xu

摘要

Efficiently solving the traffic assignment problem (TAP) is important in urban transportation planning. Until now, most algorithms for solving TAP are serial and confined to a single-computer operation, which inherently limits their computational efficiency. There are several pressing challenges faced by algorithms for solving TAP: i) the growing scale of traffic networks and increased travel demands often render traditional serial algorithms inadequate for real-time applications; ii) despite the potential benefits of parallel processing, there is a scarcity of research on effective model decomposition and parallel algorithm development; and iii) existing algorithms rarely leverage iterative information from multiple previous steps, which could enhance computational performance. To address these challenges, this study introduces a randomized partially symmetric algorithm based on the alternating direction method of multipliers (ADMM), referred to as the rpsADMM, and presents its momentum-accelerated variant. Both algorithms utilize a parallel computing framework tailored to solve the TAP. The proposed rpsADMM employs a novel approach by updating Lagrange multiplier randomly twice per iteration, thereby optimizing update efficiency. The rpsADMM also updates its subproblems using a Gauss-Seidel scheme and internal variables using a Jacobi scheme, which significantly improves computational performance in large-scale traffic networks. Furthermore, to improve convergence efficiency without sacrificing parallelism, this study develops a momentum-acceleration variant of the rpsADMM, termed the ma-rpsADMM, which integrates a momentum-acceleration strategy that combines the iterative patterns of both the Polyak heavy ball and successive over-relaxation methods after each block iteration. Extensive testing on three real-world traffic networks shows that both algorithms considerably reduce computation times while maintaining robust parallel capabilities and improving convergence. Specifically, the test results demonstrate that the computation times of the proposed ma-rpsADMM are 72.7%, 25.1%, and 75.7% less than those of the original ADMM on three different traffic networks, respectively. These findings provide valuable insights and reliable tools for TAP-solving, supporting efficient decision-making in traffic planning and management.