城市交通网络求解：基于动态块缩减的OpenMP并行块坐标下降算法

一、研究背景与问题提出

1.1 交通赋值与用户均衡问题

• 交通赋值（Traffic Assignment）是交通工程中预测交通流在网络中分布的核心问题。用户均衡理论假定每个旅行者都会选择最短路径，当所有路径的旅行时间达到均衡即为用户均衡（UE）。
• 随着城市网络规模不断扩大，求解大规模网络的 UE 问题需要高效且稳定的算法。传统的 Frank–Wolfe 方法以及均匀加权平均法在可行性和收敛速度上存在局限。
• 文献中提出的基于块坐标下降（Block Coordinate Descent, BCD）算法，通过将原问题拆分为若干出行需求（OD pair）块并逐个更新，可加速收敛。然而 BCD 是顺序算法，仅利用单线程计算，面对大规模网络效率有限。

1.2 研究问题

该论文关注如何在共享内存平台上重构 PBCD 算法 , 以充分利用多核处理器的并行能力。主要问题包括：

• 如何利用 OpenMP 框架对 PBCD 进行并行化，实现从串行到并行的结构转换。
• 并行过程中如何避免数据竞争（data race），保持算法正确性。
• 如何通过动态调整块大小提高并行效率并保持算法稳定性，克服传统固定块大小导致的负载不均和收敛慢的问题。
• 最终算法在不同规模网络上的表现如何，是否能在保证精度前提下显著减少计算时间。

二、算法框架与关键概念

2.1 OpenMP 与 fork–join 并行模型

论文在共享内存环境下采用了 OpenMP 作为并行框架。OpenMP 基于 fork–join 模型 ：主线程在并行区域前“fork”出多个子线程并行执行，完成后再“join”回单线程。其高效的线程管理与较低内存开销，使其适合在多核 CPU 上重构 PBCD 算法。

下图展示了 OpenMP 的 fork–join 并行模型，在并行区域内可以利用多线程同时处理多个 OD 块：

2.2 PBCD 算法核心

PBCD 算法的基本思想是：

• 分块思想：将 OD 对集合分成若干块，每次仅对一个块内的路径流量进行调整，其他块保持不变。
• 路径基梯度投影（Gradient Projection, GP）求解器：针对每个 OD 块，使用 GP 方法求解子问题，得到改进的路径流并计算相应的相对间隙（relative gap）。
• 受限 OD 对：利用各 OD 对的相对间隙判断是否需要再次调整；当某 OD 对的相对间隙大于设定阈值时列为受限对，否则跳过。
• 迭代停止条件：整个网络的相对间隙满足预设精度或达到最大迭代次数。

整个网络的相对间隙为：

其中：

•  为 OD 对  的最短路径旅行时间；
•  为 OD 对  的需求量；
•  表示链路  的旅行时间函数；
•  为链路流量。

当  小于给定阈值（如 ）时，算法终止，认为网络达到了用户均衡状态。

2.3 数据竞争与线程私有数据结构

2.3.1 数据竞争问题

在并行化过程中，多线程可能同时读写同一变量，导致数据竞争。例如，在更新链路流量  时，多条线程可能同时修改该链路的增量，产生不可预期的错误。

2.3.1 线程私有数据结构

为避免数据竞争，论文提出了线程私有数据结构：

• 将 OD 块分配给不同线程，每个线程维护独立的局部数据结构，包括私有的路径集、链路流量和相对间隙。
• 在线程内执行 GP 求解器计算局部增量，不直接写入全局链路流。
• 并行区域结束后通过归约将各线程私有结果累积到全局变量。

下图展示了线程私有数据结构的流程示意：

图中左侧为一个 OD 块，右侧为多个线程，各线程分别调用 GP 求解器，计算路径流与相对间隙并存储于私有内存，随后在同步阶段将私有链路流累加至共享内存。

2.4 动态块缩减（Dynamic Block Reduction, DBR）

2.4.1 原因与思路

固定的块大小可能导致负载不均衡：迭代初期许多 OD 对需要调整，块应较大以提高并行度；随着收敛，受限 OD 对数量减少，继续维持大块会浪费计算资源。因此引入动态块缩减策略：根据并行效率动态调整块大小，从而减少空闲线程时间并提高整体效率。

2.4.2 并行比与块大小更新

设  为单线程执行 GP 所需时间， 为  条线程并行执行所需时间，定义第  轮迭代的并行比  为：

根据  更新下一轮的块数量 ：

当  时，表示并行效率下降，减少块数量；当  时，保持原块数。这样可在各阶段平衡线程利用率和收敛速度。

2.4.3 块内步长调节：预设与 Armijo 规则

PBCD 中更新路径流量的步长由参数  控制。论文提出两种策略：

（1） 固定缩减参数：设定初始步长 ，在每轮缩减中乘以固定系数 ，即

作者根据相对间隙与路径数的经验关系绘制了初始步长的建议值（见下图）。

（2） Armijo 自适应规则：以目标函数下降量为判据：

其中 、 为固定参数。该策略依据 Armijo 条件自适应调整 以保证充分下降并加快收敛。

三、数值实验与结果分析

3.1 实验设计

作者在四个不同规模的网络（California Statewide CS、Birmingham Birm、Chicago Regional CR、Philadelphia Phi）上验证算法性能。网络参数如节点、链路、OD 对数量见表2（原论文）。实验设置如下：

• 采用 Linux 服务器，2.40 GHz Intel Xeon Silver 4314 CPU（128 线程），251 GB 内存；算法以 C++ 实现并采用 OpenMP 4.5 并行
• 与以下算法比较：基于 Link 的 Frank–Wolfe (FW)、改进的梯度投影 (IGP)、原始的顺序 PBCD，以及本文提出的 OpenMP 并行 PBCD、带固定 DBR 的 PBCD 和带 Armijo DBR 的 PBCD。
• 评价指标：相对间隙随 CPU 时间变化。

3.2 私有数据结构的效果

下图比较了使用 OpenMP 临界指令（critical） 与 线程私有数据结构的并行 PBCD。在中等规模 CS 和 Birm 网络上，两种并行实现的相对间隙收敛趋势类似，但私有数据结构能显著减少同步开销，平均提升近 35% 的速度。

3.3 并行 PBCD 与其他算法比较

图5 和图6 展示了在中等规模和大型网络中，不同算法的收敛曲线。可以看到：

• IGP 的初期收敛较快，但当相对间隙降至  以下时，收敛速度迅速减慢。
• 顺序 PBCD 的优势在于利用了块坐标思想，但单线程导致 CPU 时间长。
• OpenMP PBCD 在中等网络上整体优于顺序 PBCD 和 IGP，当相对间隙约为  时，大约比顺序 PBCD 快 1.3~1.6 倍。

大型网络 (CR、Phi) 中，OpenMP PBCD 相比 IGP 的优势更明显，原因在于多线程能同时处理大量 OD 对，减少瓶颈。当需求量加大时，IGP 可能陷入震荡，而 PBCD 仍能稳定下降。

3.4 动态块缩减的效果

3.4.1 固定 DBR 参数

图7 展示了作者根据不同相对间隙范围预设的初始步长  值。随着网络逐渐接近均衡，相对间隙减小，预设  随之减少，以避免过大步长导致震荡。

使用固定 DBR 参数的 PBCD 在大规模网络上取得良好效果，如图8 所示。动态减少块数量可进一步提高并行效率，使 CPU 时间约降低 40%。

3.4.2 自适应 DBR (Armijo 规则)

作者进一步引入 Armijo 规则，根据目标函数下降量自适应调整步长参数。图9 对比了固定和自适应两种 DBR。

• 在中等网络上，自适应 DBR 略慢于固定 DBR，但收敛更稳健。
• 在大型网络上，自适应 DBR 能显著避免震荡，实现更平滑的下降曲线。

3.4.3 初始全块数量敏感性

图10 研究了不同初始全块数量对算法性能的影响。结果显示，当初始块数设置过多或过少都会影响效率，而适中的块数（约略为 OD 对数量的 30%）能取得最佳性能。

3.4.4 需求水平分析

图11 对比了不同交通需求水平（需求乘数 =0.5、1、2）下的收敛性能。需求越大，网络越拥堵，各算法收敛更慢。Dynamic PBCD 在高需求场景下仍保持较高的效率，而 IGP 在高需求下震荡明显。

四、研究贡献与启示

4.1 主要贡献

• 共享内存并行化：通过 OpenMP 重构 PBCD 算法，实现了与顺序版本一致的解，并在实验中获得约 1.3~1.6 倍速度提升。
• 线程私有数据结构：解决了并行过程中的数据竞争问题，显著降低同步开销。
• 动态块缩减策略：根据并行效率动态调整块数量，结合固定或自适应步长，有效平衡并行速度与收敛稳定性，在大型网络上将 CPU 时间进一步降低 30%~49%。
• 丰富的实验验证：在不同规模和需求水平的网络上比较多种算法，全面展示了提出方法的优势与适用范围。

4.2 管理与研究启示

• 高并行性算法的设计需兼顾效率与稳定性。仅追求并行度可能导致收敛震荡，需要通过步长调节与动态块管理平衡两者。
• 私有数据结构是共享内存并行的核心。避免数据竞争不仅保证结果正确性，还能减少锁带来的性能损失。
• 动态调整策略适用于多种优化算法。本文提出的并行比指标和动态缩减思想也可推广到其他分块优化问题。
• 交通需求与网络规模对算法性能影响显著。在规划大型网络时，应根据需求水平选择合适的算法和并行策略。

4.3 局限与未来方向

• 算法仍依赖准确的旅行时间函数，在高拥堵情况下可能出现路径流震荡；未来可考虑采用更稳定的边延迟模型。
• 块划分与参数设置仍需经验调整。深度学习方法可用于预测最优块大小和步长。
• GPU 与异构计算平台：未来可尝试在 GPU 端实现路径基梯度投影，并与 CPU 协同，实现更大规模的实时交通赋值。

五、结论

论文针对大规模交通赋值问题，提出了基于 OpenMP 的并行块坐标下降算法，并通过线程私有数据结构和动态块缩减策略解决了并行过程中的数据竞争与负载不均问题。实验表明，在多种网络规模和需求水平下，该算法相较于传统算法具有显著的速度优势，并保持良好的收敛性和稳定性。研究为交通网络用户均衡求解提供了高效的并行化方案，为未来大规模交通管理与动态流量预测提供理论与方法支持。

文章须知 

推文编辑：单子叶 

责任编辑：弓仪长

原文链接：https://doi.org/10.1016/j.tre.2025.104377