大规模微观交通仿真：基于层次图神经网络的并行加速机制

论文题目：Hierarchical graph neural network-based generalized graph partitioning for accelerated large-scale microscopic traffic parallel simulation

第一作者：马晨翔 东南大学硕士研究生，师从徐铖铖教授，研究方向：智能网联自动驾驶。

E-mai：220233337@seu.edu.cn

通讯作者：徐铖铖 东南大学青年首席教授，博士生导师，国家级青年人才，交通学院院长助理，研究聚焦于运筹学的数学与算法研究，涵盖组合优化、随机 / 鲁棒优化等领域，应用于智能交通包装等场景。

E-mail：xuchengcheng@seu.edu.cn

大规模微观交通仿真：基于层次图神经网络的并行加速机制

论文摘要

本文针对大规模微观交通仿真在计算效率和精度上的矛盾提出HGNN‑GP并行仿真框架，利用分层图神经网络实现道路网络的端到端划分并通过重叠状态与车辆组传输机制确保跨分区同步。研究背景源于当前微观交通仿真对网络规模敏感，传统图划分方法依赖启发式或谱聚类存在局部最优、运算成本高等问题。作者首先在道路图上建立基于Laplacian特征的图嵌入模型，通过层次化的池化、解池化和图卷积提取兼顾全局与局部的节点特征。随后构建HGNN图划分模型，利用跳跃连接与Softmax输出直接预测节点所属分区，训练中以归一化切割（Ncut）与分区体积平衡为损失函数。最后设计重叠状态和车辆组传输机制，预处理车辆路径并利用MPI在分区之间同步车辆群，避免仅单车传输导致宏观信息不同步。实验在河南省高速网络中进行，网络包含25,443个节点和25,740条边，三种交通需求（12k/24k/36k veh/h）下HGNN‑GP在16分区时加速比最高达13.23，且误差控制在1.5%以内。工程案例验证该框架在真实道路条件变化下仍能保持高准确度，显示其在大规模并行仿真中的应用潜力。

一、研究背景与问题

1.1 微观交通仿真与并行需求

• 微观交通仿真优势与局限：通过模拟车头追随、换道等行为，高精度地反映道路交通状态，但随着模拟实体增多，状态更新时间急剧增加。
• 并行仿真的必要性：并行计算通过将原路网划分为多个子任务并行运行，目标是最小化分区间通信并保持计算负载均衡。
• 当前划分方法问题：传统局部划分（如METIS）和遗传算法运算速度快但依赖固定流程，容易受初始状态影响而得到次优解；全局谱聚类利用拉普拉斯矩阵特征，但计算量大，对初始化敏感。
• 学习模型的局限：已有学习方法通常采用“两阶段”模式，先用图神经网络提取特征，再依赖传统聚类，不能端到端推断分区。
• 高速公路网络特点：高速公路连接简单、路网稀疏，节点度分布极不均匀，导致传统算法获取的特征相似，难以精准划分。
• 同步准确性的挑战：仅传输跨区车辆的微观状态会造成宏观交通信息延迟，尤其在边界车流密集时误差累积。

1.2 研究目标

• 提出端到端的图划分框架，通过学习模型直接从道路结构推断分区，避免迭代优化陷入局部最优。
• 增强道路节点特征表示，在稀疏图上引入Laplacian引导的嵌入，使特征更具判别性和稳定性。
• 设计高效的跨区同步机制，同时考虑车辆微观状态与宏观流量，保证并行仿真与单进程仿真高度一致。

下图展示传统图划分的示意流程：

二、总体框架与核心思想

2.1 HGNN‑GP并行仿真框架

作者提出的HGNN‑GP框架由三部分组成：

• Laplacian引导的图嵌入：在道路网络图上通过分层图卷积构建节点特征，为划分模型提供稳定输入。
• HGNN图划分模型：基于分层图神经网络的编码-解码结构，直接预测每个节点所属分区，并以归一化切割和体积平衡为目标训练。
• 重叠状态与车辆组同步：将车辆路径按分区预处理，并通过重叠区域和车辆组传输确保微观与宏观信息同步。

下图给出框架整体流程：

2.2 创新亮点

• 端到端划分：突破传统两阶段方法，实现结构信息到分区标签的直接映射，避免依赖后续聚类。
• 稀疏图鲁棒性：Laplacian引导的特征学习在稀疏高速公路网络上仍能保持判别力。
• 同步机制优化：通过重叠状态与车辆组传输，相比只传输单车信息，可同步传递局部交通流特性，显著提高并行仿真准确性。

三、Laplacian引导的图嵌入模型

3.1 道路图建模与特征构建

• 图模型：采用原始图表示，节点代表交叉口，边代表路段，交通量作为边权构成加权邻接矩阵 。
• 特征需求：仅用节点度难以捕捉全局信息；作者采用分层嵌入提取全局与局部特征。
• 嵌入结构：包括池化（将节点聚合为“超级节点”以提取高层特征）、解池化（将超级节点映射回原图）及图卷积。算法采用Graclus聚类进行池化，直到图中仅剩2个节点。

3.2 图卷积与GraphSAGE

为适应不同规模图，作者采用可拓展的GraphSAGE卷积。对于第  层，节点  的隐藏表示  由邻居特征聚合并与自身特征拼接后经线性变换与非线性激活得到，其公式如下：

其中  为邻接节点集合， 可为平均或池化聚合， 为可学习权重， 为激活函数。通过层叠  层卷积并共享权重，获得稳定的节点嵌入。

3.3 输出与损失

• 特征正交化：解池化恢复到原图后，使用QR分解保证嵌入矩阵  的列正交性，使其逼近Laplacian特征向量。
• 损失函数：设计如下损失以使嵌入靠近随机游走拉普拉斯矩阵的特征向量，同时抑制特征的冗余：

其中  为随机游走拉普拉斯矩阵， 包含目标特征值 ，损失第一项约束嵌入符合谱信息，第二项通过最小化特征值之和保证平滑性。

下图给出三次池化情况下的嵌入架构示意：

四、分层图神经网络划分模型

4.1 模型结构与输出

• 输入：原图  及嵌入特征矩阵 （去除与最小特征值对应的常数列）。
• 层次结构：与嵌入相似，划分模型也包含池化、解池化与图卷积，并且在解码阶段使用跳跃连接将高层恢复图的特征与同层编码图的特征平均融合，防止信息丢失。
• 参数共享：同一层的GraphSAGE参数在各个池化阶段共享，降低模型参数并提升泛化能力。
• 输出：最后通过  个图卷积和  个线性层得到 ，并通过Softmax得到每个节点属于各分区的概率向量 。

4.2 划分目标与损失

• 归一化切割（Ncut）目标：模型训练以期望Ncut为主目标，Ncut度量跨分区边权与分区内部体积的比值，避免分区过小或割过大。
• 概率化计算：通过概率矩阵  计算每个分区的切割期望和体积期望，并用 Ncut 表示总体损失。
• 平衡约束：仅使用Ncut易导致分区不均衡。作者加入显式的分区体积平衡项，约束每个分区的节点总度数接近全网平均水平。
• 最终损失：综合Ncut与平衡约束，得到完整的训练目标：

其中  为第  个分区的期望体积， 为节点度，第一项是期望Ncut，第二项是分区体积平衡约束。

下图展示HGNN划分模型结构示意：

4.3 划分算法实现与递归策略

• 二分递归：模型训练采用二分策略，即先训练一个  的分类模型进行图二分，然后递归应用直到达到目标分区数。这种方法避免一次训练多分类模型难以收敛。
• 重要参数：设置 ，使用Graclus聚类实现池化，各层通道数统一为32，训练采用Adam优化器。

五、并行同步与通信机制

5.1 车辆路径划分与进程管理

• 路径预处理：根据划分结果，将车辆完整路径拆分为跨分区的子路径序列，保证每个子路径只在一台进程内仿真。
• MPI通信：每个分区对应一个MPI进程，车辆迁移时，将车辆状态（位置、速度、加速度、当前子路径ID等）包装发送到目标进程，实现严格同步。

5.2 重叠状态与车辆组传输

• 问题：传统只复制单车状态的做法忽视整体车流特性，边界附近车群会拉伸，导致宏观误差。
• 解决方案：定义通信响应区域：以边界边为中心，两侧延伸至相邻边形成重叠区域。边界及邻接边均在两个分区中存在副本。
• 车辆组同步：在通信响应区域内，车辆在两个分区同时存在为“重叠状态”，直到整个车辆组完全通过区域才删除旧副本，这样可以保持车距与队列结构一致。
• 效果：该机制可以传递完整的微观和宏观信息，解决车辆高速穿越边界边导致的遗漏问题，显著提升并行仿真的准确性。

通信过程示意如图所示：

六、实验设计与结果分析

6.1 试验设置

• 道路网络：选取河南省高速公路网，面积约16.7万km²，总长度约17,101km。构建的图包含 25,443 个节点和 25,740 条边，平均每个节点仅1条边，属于稀疏图。
• 交通需求：生成低（12k veh/h）、中（24k veh/h）、高（36k veh/h）三种交通流，各通过17个城市的OD矩阵产生。
• 数据增广：利用边级增广随机删除部分完整车辆路径重新计算边权，以及图级增广随机采样节点生成多样子图，共构建1,000个训练子网。
• 训练平台与参数：采用四颗Intel Xeon Gold 6346处理器和NVIDIA L20 GPU。嵌入模型设置 ，批量大小8，学习率0.0001；划分模型以相同层数和通道数训练100轮。

6.2 分区结果与效率分析

• 分区形态：HGNN‑GP产生的分区在地理上相对连续，每个子网主要集中在特定区域，而不是离散散布。
• 加速效果：在16分区的高流量场景下，HGNN‑GP实现13.23倍加速，将近6小时原始仿真缩短至不到1小时；在分区数较少时各方法相近，但分区增加时HGNN‑GP优势明显。
• 负载均衡：HGNN‑GP通过图学习捕捉结构模式，保持较低的时间均值和标准差，即使在分区数增加时仍较稳定；SP法标准差较低但平均时间高，表明通信成本大。
• 通信成本：在高流量下，与METIS、iMETIS和SP相比，HGNN‑GP通信成本明显降低；但随着分区数增至16，通信成本提高到43.39%，主要因车辆迁移频繁，此时加速收益开始减小。
• 准确性：表3列出的平均误差显示，在2、4、8、16分区下车辆数误差分别为0.261%、0.286%、0.473%、0.724%，行程时间误差和线路长度误差均在1.5%以内。提高分区会累积少量误差，但通过扩展边界边和限制车速，可进一步降低差异。

6.3 工程案例分析

在工程场景中，作者随机选取50%的边在两个时间段内关闭或降低限速，并在中等流量、8分区下进行仿真。结果显示，两种仿真中车辆数和行程时间分布右移，说明车辆按原路径行驶但速度降低，仿真与真实情况吻合。效率指标仍然达到6.68倍加速，且宏观误差控制在0.2%以内，验证了HGNN‑GP框架在复杂道路条件下的实用价值。

七、结论与展望

本文面向大规模微观交通模拟提出了一个端到端并行仿真框架HGNN‑GP，通过Laplacian引导的图嵌入、分层图神经网络划分以及重叠状态车辆组同步机制解决了传统图划分效率低、稀疏网络难以处理、跨区同步误差大等问题。实验表明在河南省高速公路网中，HGNN‑GP在16分区下实现13.23倍加速，负载均衡优于传统方法，通信成本和仿真误差显著降低。工程案例进一步证明该框架在实际道路条件变化下能够快速且准确地再现交通状态。

未来研究方向包括：

• 动态分区与实时适应：针对交通需求和路况实时变化，研发动态划分策略，以提升仿真适应性。
• 更丰富的交通特征融合：引入实时交通量、速度等多源数据，构建更全面的节点特征。
• 异构路网扩展：将框架推广至城市交叉路口和混合路网，探索复杂拓扑下的划分与同步机制。

综上，HGNN‑GP框架为大规模高速公路并行仿真提供了高效准确的新思路，并为智能交通领域的仿真技术奠定了基础。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。