117
科学论坛
在智能交通领域，众所周知，智能交通系统在当今世界道路交通网络的管理中发挥着重要的作用，而车辆导航系统又是智能交通系统的重要组成部分。在车辆导航系统中，定位的精确性和实时性是导航系统的基本要求。但是，几乎所有的车辆导航系统都存在着定位误差问题，采用传统的硬件手段来改善定位误差是比较困难的，而地图匹配是一种软件修正技术，它把从ＧＰＳ接收机处获取的车辆轨迹数据（也叫浮动车数据）进行处理，并跟数字地图库中的地图数据（即道路网数据）进行匹配，从而达到修正车辆定位轨迹的目的。地图匹配算法的重点是路径分析，现阶段往往采用几何匹配、拓扑匹配和高级匹配三类算法来实现正确的路径分析。最短路径法作为常用的地图匹配算法，旨在解决从一个轨迹点到其他轨迹点的最短路径问题，但是，由于存在城市道路情况复杂以及建筑物或隧道遮挡信号等因素的影响，导致轨迹点之间缺失的信息较多，所以提出了很多改进的地图匹配算法，其中又属结合时空分析的最短路径匹配算法应用最为广泛，通过空间相对位置、时间、速度等特性来恢复路网信息。
由于道路网数据采集工作量大、精度要求高，需借助计算机应用软件来实现地图匹配具体流程，目前程序开发领域常用的开发语言有Ｊａｖａ、Ｃ／Ｃ＋＋、Ｃ＃等，但其入门成本较高，程序代码复杂，掌握难度相对较大。鉴于Ｐｙｔｈｏｎ语言在设计上坚持简洁明了的风格，以其学习难度低、操作简便、
具有大量优秀的库及框架等特征，在世界范围内广为应用。因而本文利用Ｐｙｔｈｏｎ强大的编程语言、高效的高级数据结构、面向对象的设计方法和高度可扩展等优点，来实现地图匹配最短路径法。
一、结合时空分析的最短路径算法
早期在运用Ｄｊｋｓｔｒａ算法选取道路路
段和轨迹点的过程中，往往只考虑道路的等级和属性，将每条道路当做单个个
基于Python的地图匹配最短路径法实现
刘佳瑜　陈明扬　杜佳慧　施桉棋　梁　丹  浙江农林大学
【摘　要】地图匹配算法是应用定位轨迹点的几何、拓扑等特性，将车辆在行驶过程中得到的轨迹点与数字地图中的实际位置进行配对，得到车辆在地图中的准确位置。而Python强大的脚本语言可应用于地图匹配的计算和建模。本文利用Python语言的简洁性、易读性和可扩展性来实现结合时空分析的最短路径算法，并重点介绍了Python用于地图匹配的关键模块和最短路径算法的实现流程。实验采用真实的出租车轨迹点定位数据和道路网数据进行验证，结果表明该最短路径法单点用时约为0.002s，匹配正确率可达到97.63%。【关键词】地图匹配；Python；Djkstra距离；时空分析
体，缺乏全局意识，因此综合空间几何和路网拓扑的效果较差。同时，获取道路网信息往往是瞬时状况下的，在处理时应充分考虑时间因素，以减小误差。所以，对候选路段、候选点以及需要匹配的轨迹进行时空分析，结合时空分析的地图匹配算法会在一定程度上降低了因算法局限性和现实性产生的误差，能够大大提高匹配精度和效率。
１．最短路径算法（Ｄｉｊｋｓｔｒａ算法）
Ｄｉｊｋｓｔｒａ是从一个顶点到其余各顶点的最短算法，解决的是有权图中最短路径问题。已知一个标记点Ｋ，寻与未标记点Ｊ之间的最短距离，遍历Ｋ与Ｊ之间的所有距离，到最短距离的路线为Ｋ→Ｃ→Ｊ，作为最终的输出结果。
                                        　图　１　最短路径算法示意图２．　空间分析
以路网的几何和拓扑信息为依据的空间分析用以下函数表示
()s i t 1i s c c F −−＝()
amor mios i t 1-i 0c c −P
＊(
)
s
i 1i t
t c c P −−            （１）其中()()θ
βπσ
α
σµ∆+=cos e 21
c 22
天使的翅膀徐誉滕2x 0P ，()()()
s
i t 1i i
1i s
i
1
-i t
t
W d c -c ，，→−→−=P ，j i x ＝ｄｉｓｔ（i
j c ，i P ）表示候选点i j c 和轨迹点i P 之间的距离，θ∆＝()j i i e -θθ表示车的前进方向和候选路段j i e 方向之间的夹角，α和β分别表示距离和方向之间的权重，
最终公式()j i 0c P 表示轨迹点i P 与候选点之间相匹配的可能性；给定的t
1-i c 和s
i c 分别代表相邻轨迹点1-i P 和i P 的任意候选点，ｄｉ－１→　ｉ表示相邻两个轨迹点1-i P 和i P 之间的欧
式距离，()()s i t 1-i ，，→W 表示t 1-i c 和s
i c 之间的Ｄｊｋｓｔｒａ距离，公式()s i 1-i t t c -c P 表示计算t 1-i c →s i c 为1-i P →i P 真实路径的可能性，两者相乘得到空间分析函数的表达式，从空间维度分每次都想呼唤你的名字
析了车辆t 1-i c 移动到s
i c 的可能性，综合考虑了几何和路网空间关系信息。
３．时间分析
以速度为依据的时间分析用以下函数来表示：
()
=
−s i c F t 1-i t c ∑
∑
∑=→−==→−k 1
u )
,(),1(2k 1
u 2u k
1
u ),(),1(u *
)
e )
*e s i t i s i t i v v v v ’’（（    　（２）
由公式（１）、（２）得到时空分析的函数表达式，以两式相乘得到的权重函数来分配空间与时间权重，得到同时考虑整体与时间信息的数据，完成时空分析。
二、 Python简介
Ｐｙｔｈｏｎ语言的定位是“优雅”、“简洁”、“明晰”，是一种面向对象的通用程序语言，其多样、强大的类库可应用于各种领域，是一门真正的全栈语言。
Ｐｙｔｈｏｎ的特点：Ｐｙｔｈｏｎ基于Ｃ语言设计的程序，易于学习，易于阅读，代码短
科学论坛
小，结构清晰，并可利用现有函数包简化设计工作，非常适合初学者，也特别适合专业人员；可移植；可嵌入，易于维护算法的安全性；功能齐全等。
三、基于Python的最短路径法地图匹配实例
本文实验数据采用某市道路网数据（包含６７２１１条路段）和出租车轨迹点数据（采样频率为１－３０ｓ）如下图２所示。下文首先介绍了本算法涉及到的Ｐｙｔｈｏｎ关键模块，给出了结合时空分析的最短路径算法实现流程图以及关键步骤的伪代码，最后给出了实验结果分析。
                                                      图　２　实验数据
１．　Ｐｙｔｈｏｎ关键模块应用
（１）Ｎｅｔｗｏｒｋｘ
Ｎｅｔｗｏｒｋｘ可以以规范化和非规范化的数据格式存储网络、生成多种随机网络和经典网络、分析网络结构、建立网络模型、设计新的网络算法、进行网络绘制等。其中用到的Ｇｒａｐｈ函数是用几何对象中的点和线来联系离散要素间相关程度的数据模型。其作为Ｎｅｔｗｏｒｋｘ中的一种函数，包含了Ｇｒａｐｈ：无向图（ｕｎｄｉｒｅｃｔｅｄ　Ｇｒａｐｈ），即忽略了两节点间边的方向；ＤｉＧｒａｐｈ：有向图（ｄｉｒｅｃｔｅｄ　Ｇｒａｐｈ），即考虑了边的有向性。引入Ｎｅｔｗｏｒｋｘ模块对于分析道路网生成最后的连通道路有很大的帮助。
（２）Ｆｉｏｎａ
Ｆｉｏｎａ采用Ｐｙｔｈｏｎ中内置的数据结构表示矢量数据，一个要素以ＧｅｏＪＳＯＮ（Ｇｅｏ
ＪＳＯＮ是一种对各种地理数据结构进行编码的格式）使用Ｐｙｔｈｏｎ内置的字典（ｄｉｃｔ）结构组织；一个图层包含在一个集合中（Ｃｏｌｌｅｃｔｉｏｎ）。可以对该集合进行迭代遍历，得到其中的要素。对于读取Ｓｈａｐｅｆｉｌｅ数据，Ｆｉｏｎａ有着更为简洁的处理过程。
（３）Ｓｃｉｐｙ
Ｓｃｉｐｙ是一个用于数学、科学、工程领域的常用模块，可以处理积分、插值、图像处理、优化、常微分方程数值的求解、信号处理等问题。其中用到了ｓｐａｔｉａｌ函数与ｓｔａｔｓ函数，对于处理空间数据结构和算法以及对数据的统计有很大的帮助。
还珠格格第一部歌曲（４）Ｃｏｌｌｅｃｔｉｏｎ
Ｃｏｌｌｅｃｔｉｏｎ作为Ｐｙｔｈｏｎ中一个较强大的模块，可以处理并维护一个有序的ｄｉｃｔ（字典），也可以提高运算效率，对地图匹配中的轨迹点的检索效率有很大的提高。
（５）Ｓｈａｐｅｌｙ
Ｓｈａｐｅｌｙ是用于操作和分析笛卡尔坐标中的几何对象。其中用到的ｓｈａｐｅｌｙ．ｇｅｏｍｅｔｒｙ．ｓｈａｐｅ函数，可以方便地构造一个新的独立几何图形，对弈地图匹配中形成新的路网有极大的实用性。
（６）Ｐｓｙｃｏｐｇ２
Ｐｓｙｃｏｐｇ２是Ｐｙｔｈｏｎ语言的ＰｏｓｔｇｒｅＳＱＬ数据库接口，适用于实时创建、删除大量的数据缓冲区和产生大量并发插入、更新操作的多线程数据库应用，对地图匹配过程中候选点暂时的储存以及后续过程中的读取有很大的帮助。
２．结合时空分析的最短路径地图匹配流程
地图匹配算法是将定位系统产生的轨迹数据匹配到正确的道路网里，结合时空分析的最短路径地图匹配算法考虑了轨迹点的位置信息和候选路段的拓扑信息，还结合了整体路段的时空分析，把单条道路放在了全局道路网中，其算法流程如图３所示。
主要的步骤如下：
在进行地图匹配之前，首先要对实验数据进行匹配。处理过程包括建立有向道路网图、建立网格索引、以及最短路径求解。
①建立有向道路网图
已知的道路网数据为Ｓｈａｐｅｆｉｌｅ格式，通过Ｐｙｔｈｏｎ中的Ｆｉｏｎａ模块，读取Ｓｈａｐｅｆｉｌｅ文
件，通过获取道路节点的ＩＤ、起点（ｓｏｕｒｃｅ）、终点（ｔａｒｇｅｔ）等信息，并利用Ｐｙｔｈｏｎ中Ｎｅｔｗｏｒｋｘ模块中的ＤｉＧｒａｐｈ函数生成有向图，考虑了边的有向性。
②建立网格索引
在整个地图匹配过程中，需要处理的道路网中共有６７２１１条路段，如果利用传统的遍历的方式进行候选路段的查询，其算法复杂度是Ｏ（ＭＮ），其中Ｍ和Ｎ分别代表的是路段的总和与轨迹点的数目，运算的复杂度将上升到平方量级。利用Ｐｙｔｈｏｎ中ｓｈａｐｅｌｙ模块的ｓｈａｐｅｌｙ．ｓｔｒｔｒｅｅ函数，可以方便地建立网格索引，将地图划分为Ｋ×Ｌ个网格，得到候选区域后，只需要遍历候选方格网中的路段，使其算法复杂度降低，最终得到候选路段。
③最短路径求解
在进行匹配的道路网中，选取的轨迹点是深圳市出租车的数据。状态转移概率代表了轨迹点从一个候选路段移动到另外一个候选路段的过程。基于一个假设，出租车司机一般选择最近的线路行驶，所以前后路段间的路网距离越小，其状态转移概率越大，越有可能是需要匹配到的路段。本文采用Ｄｉｊｋｓｔｒａ算法，与其他最短路径算法，比如Ａ＊算法相比，当目标点较多时，Ａ＊算法会带来大量重复数据和复杂的估算节点重要性的过程。为了提高匹配的效率，采用Ｄｉｊｋｓｔｒａ算法。计算整个道路网中路段起点与终点的最短距离。
（２）对候选区域内的轨迹点进行空间分析与时间分析，获取两者乘积的最大值
①候选区域的确定
由于定位系统存在的系统误差，显示在道路网中的轨迹点会有一定的误差，因此出租车在某个时刻的定位信息可以描述为：出租车在当前时刻以概率Ｐ落在以ｑ为圆心，ｒ为半径的区域内，该区域为候选域。候选域的确定，可以将地图匹配问题简化为轨迹点匹配到候选区域内最合适的路段问题。
②空间分析与时间分析
空间分析部分主要考虑了轨迹点与候选点之间的距离。利用Ｐｙｔｈｏｎ中Ｓｃｉｐｙ模块的ｄｉｓ
火花dj
ｔａｎｃｅ．ｅｕｃｌｉｄｅａｎ函数，可以方便地计算两点之间的欧氏距离。根据两点之间的欧式距离，可以认为距离越近的点，越有可能作为匹配度最高的点。空间分析给出的空间匹配度，在大多数情况下都能够得到比较好的匹配结果，但是在一些特殊路段上匹配效果不理想，因此，为考虑出租车的轨迹信息和路网的空间位置可引入时空分析模块，得到两者权重，从而大大提高了匹配的正确率。
118
119
牛莉主演的电视剧
科学论坛
算法                  匹配正确率（％）              算法用时（ｓ）
Ｄｊｋｓｔｒａ算法                            ９６．７                        ０．２３结合时空分析Ｄｊｋｓｔｒａ算法      ９７．６３                      ０．００２
③选择权重最大点
根据之前候选域内进行空间分析与时间分析得到权重最大的点，用于后面的地图匹配过程。
（３）匹配并输出。根据得到权重值最大的点，将点投影到之前生成的有向道路网中，然后利用Ｐｙｔｈｏｎ中Ｎｅｔｗｏｒｋｘ模块的ＤｉＧｒａｐｈ函数生成有权重图，从权重图中，到最长的路径，获得匹配轨迹，并作为结果输出；如果返回的轨迹不连通，则尝试删除断裂处的点，重新进行匹配。
图　３　地图匹配算法流程图
３．关键步骤伪代码。地图匹配主要包括数据预处理和特征分析以及匹配输出三个部分，算法的伪代码如表１所示。
表１　地图匹配算法流程伪代码
１  ｉｎｐｕｔ（ｔｒａｃｋ．ｓｈｐ　ｃｏｎｎｅｃｔｅｄ＿ｒａｏｄ）２  ｆｏｒ（ｉ＝１，Ｎ－１，ｉ＋＋）  ／／总路段为Ｎ３  获取道路网路段ｌ１　与ｌ２对应的候选集Ｌｉ与Ｌｉ＋１
４　ｆｏｒ　ｅａｃｈ　ｌ１　ｉｎ　Ｌｉ５　ｆｏｒ　ｅａｃｈ　ｌ２　ｉｎ　Ｌｉ＋１６　计算ｌ１　与ｌ２最短路径７　ｄｏ（时空与时间分析）
８Ｆｕｎｃ［Ｐｍａｘ］  ／／Ｐｍａｘ为权重最大的点
９Ｏｕｔ＝ａｒｇｍａｘ｛ｆｕｎｃ［Ｐ］｝  ／／获取全局最优路径中权重最大点集合
１０  Ｓ．ａｐｐｅｎｄ（Ｏｕｔ）  　／／将所有权重最大点添加至Ｓ中
１１  Ｓ．ｒｅｖｅｒｓｅ（）  ／／反向生成最优路径
图
１２  ｒｅｔｕｒｎ　Ｓ  ／／输出最优路径图４．　匹配实验结果分析
实验中计算了深圳市３７９个有效定位数据，单点用时约为０．００２ｓ，其中有３７０个定位数据正确匹配，正确率９７．６３％，分析表３数据可以发现综合考虑了空间几何信息和时间因素后的算法较单独的道路匹配算法和Ｄｊｋｓｔｒａ　在匹配正确率和算法时间上都有所改善，图４显示了截取路段的正确道路和点。
                                                  表２　实验结果
                                        表３　匹配结果对比统计
                            图　４　正确匹配后局部道路与轨迹点图
四、 结束语
本文阐述了结合时空分析的最短路径法地图匹配的数据预处理、特征分析、权重匹配等流程，以Ｐｙｔｈｏｎ为开发语言，以某市道路网和出租车轨迹点数据为实验数据，实现了结合时空分析的Ｄｊｋｓｔｒａ最短路径地图匹配算法。该算法的匹配正确率为９７．６３％。通过实例阐明了利用Ｐｙｔｈｏｎ语言和Ｄｊｋｓｔｒａ算法对路网中道路点与实际路段匹配的优化性，展示了Ｐｙｔｈｏｎ在处理离散点与匹配路段的高度智能化和流程性。
参考文献：
[1] 李清泉，黄练.基于GPS轨迹数据的地图匹配算法[J].测绘学报，2010(39):207-212.
[2] Furtado, A.S.L.O.C.Alvares,N.Pelekis,Y.Theodoridis and V.Bogorny. Unveiling movement uncertainty for
robust trajectory similarity analysis[J]. International Journal of Geographical Information Science,2017, 32(1): 140-168.
[3] Yang, C. and G. Gidófalvi. Fast map matching, an algorithm integrating hidden Markov model with precomputation[J]. International Journal of Geographical Information Science, 2017,32(3): 547-570.
[4] Mohammed Quddus,Simon Washington.Shortest path and vehicle trajectory aided map-matching for low frequency GPS data[J].Transportation Research Part C，2015(55): 328-339.
[5] 刘卫宁，汪杰宇，郑林江.基于时空分析的地图匹配算法研究[J].计算机应用研究，2016，33(8):2266-2269[6] 李洋.地图信息识别和地图匹配算法的研究[D].北京交通大学.
[7]沈殊璇，薄亚明.适合于科学计算的脚本语言Python[J].微计算机应用,2002(5):189-291.