论文标题
静态交通分配问题的计算效率分解启发式
Computationally-Efficient Decomposition Heuristic for the Static Traffic Assignment Problem
论文作者
论文摘要
大型区域计划等应用程序需要有效的方法来解决大型网络上的交通分配问题（TAP）。我们提出了一种分解启发式，该启发式措施通过将完整的网络分配到并行求解并使用迭代式重新算法来改进网络分区来生成近似的TAP解决方案。还提出了一种新型的网络变换和三阶段算法来解决约束的最短路径问题作为启发式的子问题。各种网络上的实验表明，启发式方法可以生成15.1-67.8％的计算节省，以查找初始相对差距为0.02的解决方案。当热门标准的TAP算法被证明时，提出的启发式启发式的性能优势，平均计算节省为10-35％，而不是Tap求解器而无需加热的求解器。
Applications such as megaregional planning require efficient methods for solving traffic assignment problems (TAPs) on large-scale networks. We propose a decomposition heuristic that generates approximate TAP solutions by partitioning the complete network into subnetworks which are solved in parallel and use an iterative-refinement algorithm for improving the network partitions. A novel network transformation and three-stage algorithm are also proposed to solve a constrained shortest path problem as a subproblem of the heuristic. Experiments on various networks show that the heuristic can generate 15.1-67.8% computational savings in finding solutions with initial relative gap of 0.02. The performance benefits of the proposed heuristic when warmstarting standard TAP algorithms are demonstrated with an average computational savings of 10-35% over a TAP solver without warmstarting.
