1、软件开发与应用Software Development&Application电子技术与软件工程Electronic Technology&Software Engineering37根据中共中央、国务院印发的国家新型城镇化规划（2014 2020 年），到 2050 年，中国城市化率需提高至 70%以上。城市化过程中，一个完善的交通运输体系成为城市良好发展的前提，国家新型城镇化规划指出我们要完善综合运输通道和区际交通骨干网络，强化城市群之间交通联系，加快城市群交通一体化规划建设，改善中小城市和小城镇对外交通，发挥综合交通运输网络对城镇化格局的支撑和引导作用。然而，我国部分地区交通发展水平低，
2、道路建设缓慢，路网结构不合理，导致严重的交通拥堵问题；同时，近年来中国经济的飞速发展带动了城市化进程的加速，而城市化进程带来的城市交通拥堵问题也日益严重。据中国交通运输部官网的数据，中国城市交通拥堵问题已经达到了前所未有的严重程度。总之，上述情况引发人们思考：（1）针对城市的拥堵现状，是否存在潜在的道路结构优化方式？（2）针对乡镇以及城市新区的开发建设，区域的道路该如何规划与建设？针对这两个问题，笔者设计了一个基于路网表征的城市交通仿真平台：MANTIS（Multi-layer Graph Attention Network for Transportation Simulation，多层图神
3、经网络交通仿真），旨在为交通管理部门合理有效地对道路进行管理和建设提供参考。2 MANTIS平台设计仿真平台的工作流程如图 1 所示，分为三个阶段。2.1 阶段1：收集交通信息 提取OD需求原始的汽车行驶轨迹信息是通过 GPS 获取的。GPS获取到的汽车行驶数据通常以经度和纬度的形式呈现。这些数据可以通过 GPS 设备捕捉并记录车辆位置的变化，形成一系列坐标点，从而形成行驶轨迹。在此将一一个基于路网表征的城市交通仿真平台王力超陈灿宇李京昊王永瑶（北京航空航天大学计算机学院 北京市 100191）摘要：本文通过基于图神经网络的路网表征模型来构建更加可信的仿真平台 MANTIS，针对目前交通仿真软
4、件交通要素数量人为指定、准确性和可信度不足的局限性进行了优化。关键词：交通仿真；路网表征；图神经网络；路径搜索图 1：MANTIS 流程图软件开发与应用Software Development&Application电子技术与软件工程Electronic Technology&Software Engineering38条车辆的轨迹规范表达为：(t1,long1,lat1),(tn,longn,latn).其中，longi,lati表示车辆的经纬度信息，ti表示时间戳，n 表示该轨迹的长度。2.1.1 路网匹配路网匹配（地图匹配）1，是指将 GPS 轨迹点匹配到路网中道路上的过程，是轨迹预处理
5、的一部分。由于GPS 误差，实际采集的 GPS 坐标点往往是在道路附近，通常车辆只能在路网内行驶，此时就需要通过路网匹配判断各个轨迹点实际在哪条路上，既将轨迹序列转化为路段序列，也起到修正误差的作用。匹配准确率会受到GPS 误差和轨迹低采样率影响，因此需要开发更优的匹配算法。地图匹配是一种将 GPS 轨迹数据与地图上的道路网络进行匹配的技术。它是许多基于位置的服务的基础预处理步骤，例如导航系统、交通管理和活动识别。最广泛使用的地图匹配算法之一是Fast Map Match（FMM）算法2。FMM 算法是一种基于概率的地图匹配方法。它假设 GPS 测量数据存在噪声和不确定性，并使用隐马尔可夫模型
6、（HMM）对轨迹和道路网络进行建模。HMM由一组状态和一组观测值组成。状态表示候选道路段，观测值表示 GPS 测量数据。FMM 算法使用维特比算法搜索最优状态序列以匹配观测值。FMM 算法包括两个主要步骤：初始化和迭代。在初始化步骤中，算法使用道路网络和 GPS 测量数据构建 HMM。它首先确定距离 GPS 测量点一定距离内的候选道路段。然后根据 GPS 测量误差和方向一致性估计每个候选段的可能性。最后，用候选段和它们的可能性初始化 HMM。在迭代步骤中，算法使用维特比算法找到最优状态序列以匹配观测值。它从初始状态开始，迭代地计算每个状态的可能性，基于前一个状态和观测值。然后选择可能性最高的状
7、态作为当前状态，并重复该过程直到所有观测值匹配。最优状态序列表示与 GPS 轨迹相对应的最可能道路段序列。通过路网匹配，得到了轨迹数据集。轨迹数据集中每一条轨迹数据为带有时间戳的路段 id 序列：(t1,geoid1),(tn,geoidn).2.1.2 收集交通信息从轨迹数据集中，统计时空交通信息。将时空交通信息这个概念定义为：各时段、各路段的车流量、平均车速等。例如，对于编号为 id 的路段，其对应的时空交通信息 did定义为：其中，n 表示将一天 24 小时划分成的时段个数，numi为一天中第 i 个时段内，在该路段通过的车辆数；vi表示一天内第 i 个时段内所有通过车辆在该路段的平均车
8、速。2.1.3 提取 OD 需求OD 需求指的是人们从某个起点（Origin）到达某个终点（Destination）的需求。这种需求在交通规划和运营中非常重要，因为它能帮助决策者了解人们的出行模式、出行时间、出行目的地等信息，以便更好地规划公共交通路线、调整交通流量、优化道路网络等。通过统计 OD 需求，交通决策者才能更好地了解公众出行需求，提高公共交通的效率和便利性。从轨迹数据集中，提取出行 OD 需求集。每一条OD 需求 dem 的形式如下：dem=(t,geoido,geoidd).其中，t 表示出发时间，geoide为起点路段的编号，geoidd为终点路段的编号。2.2 阶段2：模型预
9、测 轨迹生成2.2.1 基于图神经网络的路网表征模型 M-GAT在这一阶段，设计了多层图注意力网络模型M-GAT（Multi-layer Graph Attention Network）。2.2.1.1 模型结构模型结构图如图 2 所示。将路网定义为一个有向图 G：G=(V,E,FV).其中，V=v1,v|V|，每一个节点 vi表示一个路段；软件开发与应用Software Development&Application电子技术与软件工程Electronic Technology&Software Engineering39EVV 为边集数组，对任意 ei,j=(vi,vj)E，表示表示在路网中
10、，车辆能够从第 i 个路段到达第 j 个路段；FV是路段的特征，包括路段长度、车道数量、最大限速、路段种类。接下来，将建立图神经网络模型。这是一种针对图结构数据的神经网络模型，它的输入是一个图结构，输出是对节点或边的特征进行预测或分类的结果。对于没有明确训练任务的情况，其输出就是一种路网的表征。本文设计的模型是基于 GAT 网络3构成的。对于每一层 GAT，有.其中，ij表示节点 i 和节点 j 之间的注意力系数。权重矩阵 WFF。F 表示输入节点特征的维数，而 F表示该层输出节点的维数。其中的 和 表示，节点 i 和节点 j 的节点特征，如果这层 GAT 为输入层，那么节点特征直接就是图的原
11、节点特征 x。|符号代表表示张量的 concat。例 如，1,2,3,4|5,6,7,8=1,2,3,4,5,6,7,8。通过 concat，把两个 1F 的张量粘合成了 12F 的大张量。然后乘以一个 2F1 的 attention kernel：。得到的数值就是未加工的 attention 系数。接着通过激活函数 RELU 函数，并进行 softmax 归一化。GAT 在聚合邻居节点的表示向量时，使用注意力权重对其进行加权。这些权重是通过计算当前节点与邻居节点之间的相似度来确定的。注意力机制可以使模型专注于与当前节点相关的邻居节点，从而提高模型的效率和准确性。注意力机制还可以在学习节点表示
12、时选择性地强调不同节点之间的关系。接下来，就要导出这层 GAT 关于节点 i 的输出特征：.其中，Ni表示节点 i 的邻接节点，ij是刚刚得到的注意力系数。和卷积神经网络 CNN 的操作类似，CNN 中对于每一层特征图的卷积核，其实可以有多个，而且每个卷积核相互独立，从而使得输出特征图具有更多的 channel。在 GAT 中，可以有 K 个独立的 attention 系数，在训练过程中进行独立训练，并且有着独立的注意力系数矩阵。此时上式变为：.上式代表中间层的输出形式。最后输出层的输出形式为：.通过使用多头注意力机制，能够使模型：（1）关注图中更深度的子空间和位置信息；（2）让模型能够抽取到
13、更加丰富的特征信息；（3）增强模型的稳定性和泛化能力。2.2.1.2 模型准确性验证使用了真实世界的两个大规模数据集：北京和波尔图的路网数据以及出租车轨迹。如表 1 所示。表 1：数据集来源及信息数据集北京波尔图时间范围 2015/11/01-2015/11/30 2013/07/01-2014/07/01轨迹条数1018312695085路段条数1090338479图 2：M-GAT 模型图软件开发与应用Software Development&Application电子技术与软件工程Electronic Technology&Software Engineering40为了进行更有效的对比
14、，构建了与 M-GAT 模型类似但不蕴含图结构信息的多层感知机模型 modified multi-layer perception，记为M-MLP。与基线模型M-MLP的训练效果如图 3 所示。可见，M-GAT 能够更快、误差更小的完成任务。此外，仿真了北京三元桥道路施工案例中交通管制对车辆出行的影响。可以看到，仿真结果与实际情况相近。如图 4 所示。2.2.2 将 OD 需求转化为预测轨迹这一步的任务是将 OD 需求(t,geoido,geoidd)转化为预测轨迹(t1,id1),(tn,idn)。这涉及到路径规划问题。选用 A*算法。A*算法是一种常用于路径搜索的启发式搜索算法。它采用了最
15、优先搜索策略，结合了 BFS和贪心算法的思想，在减少搜索空间的同时能够保证找到最优解。这种算法的核心在于利用一个估价函数来预估到目标节点的代价，并根据此来决定搜索的方向。因此，A*算法在许多领域都得到了广泛应用，如游戏AI、路线规划、机器人路径规划等。A*算法的优点在于它具有高效性和准确性。通过合理地选择估价函数，A*算法可以在相对较短的时间内找到最优解，并且在大多数情况下能够减少搜索的节点数。如图 5 所示。A*路径搜索启发式算法的核心是构建估价函数 f(x)来计算每个节点的优先级：f(x)=g(x)+h(x).其中，x 表示当前所在的位置；g(x)表示历史代价，使用前述模型预测路段通行时间
16、 ti，ti作为有向图的 weights 送入 A*算法；h(x)表示未来代价，通过计算当前位置与目标位置的距离来得到。为保证 g(x)和 h(x)的影响相当，在实际操作中取 300。A*算法在运算过程中，每次从优先队列中选取 f(x)值最小（优先级最高）的节点作为下一个待遍历的节点。在轨迹搜索中，采用多种其它路径搜索算法进行了实验。如表 2 所示，相比 BFS、Dijkstra，选用的 A*算法在算法执行耗时，生成轨迹的通行用时两个指标的综合考量中表现最好。表 2：A*与其他路径搜索算法的对比算法执行平均耗时/s生成轨迹的平均通行用时/sPortoBFS0.009921585.8Dijkstra2.94817.2A*0.146892.9BeijingBFS0.04161066.5Dijkstra41.8421.8A*0.179792.52.3 阶段3：统计仿真 可视化基于前两个阶段的成果，开发了可交互的仿真平台名 为 MANTIS（Multi-layer Graph Attention Network for 图 5：M-GAT based A*结构图(左)正常情况下的情况(中)交通
