文摘
找到一个路线最短旅行时间根据交通情况可以帮助游客更好的路径选择决策。本文基于FCD最短旅行时间(浮动车数据)用于评估整体交通状况提出了。更好地适应FCD和路线图,一个新的地图匹配算法,充分考虑距离因素,方向的因素,和可访问性因素是用来映射所有GPS(全球定位系统)指出道路。混合图结构构造和旅行时间最短路径分析算法考虑了动态边缘重量设计。通过比较与其他地图匹配算法,该方法具有更高的精度。比较结果表明,旅行时间最短路径长于路径最短的距离,但它成本更少的旅行时间。路径选择的实现基于最短旅行时间的方法可以用来指导人们的时空旅行通过选择最优路径的依赖。
1。介绍
目前迫切需要获得一个城市的交通动态交通指导。通过提供有效的交通信息,它可以帮助旅游者更好的路径选择决策。查询类型的“我们如何得到交通信息?”和“路径图中两个顶点之间最短的距离?“广泛讨论,而查询类型的“我们如何得到交通信息有效地和经济上?”和“路径是两个顶点之间的最短旅行时间图?“需要进一步分析。
虽然道路网络交通信息可以收集到感应圈或视觉系统,很难获得精确的估计瞬时旅行时间从当地交通速度和流量数据1]。交通拥挤演示了一个多核结构的时空分布在城市道路网络(2]。廉价的定位技术的可用性,可以使用历史导航数据模型的交通流在不同的时间在一个特定的一天。
近年来,越来越多的汽车已经配备了GPS(全球定位系统)。FCD(浮动车数据)收集交通信息包括实时位置,方向,速度,和其他信息。如果这个FCD系统实现超过1.5%的普及率(3),城市交通的服务质量将是足够好的。大规模的高速公路和动脉实验的结果凸显了FCD对交通管理的意义4]。到目前为止关于浮动车有丰富的研究及其应用,如检测热点[5- - - - - -7),公路网络更新(8,9)、交通预测(10,11),经验最优路径(12),和时空模式(13]。有大量的车辆收集数据对于一个城市,它将创建一个准确的交通条件在时间和空间的照片14]。如今,可以研究交通流的时空特征分析了FCD。
相比固定流量传感器,FCD能够提供一个健壮的概述当前道路交通状况以更少的成本(15]。一个新的操作系统基于信息从手机服务提供商进行流量测量速度和旅行时间(16]。主要的发现是,有一个很好的匹配FCD测量和双磁回路探测器。
Pfoser等人展示了一个促进FCD的收集系统,产生动态旅行时间信息,并提供增值服务,基于动态旅行时间(14]。然而,一个基本的问题是有限的汽车普及率和足够的数据覆盖。凯斯和Treiber认为一场基于车辆发动的方法收集交通数据和使用数据来估计交通堵塞的上游和下游领域17]。然而,这个估计不允许旅行时间预测成为相关当没有探测车辆通过路边单元。
由于GPS测量误差和道路几何数字地图中的错误,GPS的位置探测车辆可能不会出现在网络链接(18]。因此,它是必要的,不仅与GPS点的道路网络,而且还连续GPS点的路线。有许多作品提出了地图匹配的方法。增量算法匹配轨迹的连续部分的道路网络和两个全局算法相比,整个轨迹的候选路径提出了道路网(19]。由于限制跟踪数据和道路网络的全球算法,匹配的结果需要评估丢弃坏的部分匹配。自适应剪裁算法,考虑了跟踪误差估计被介绍给解决这张地图匹配任务(20.]。然而,这张地图匹配算法的质量评估。的程序和算法计算和地图匹配道路段速度数字提出了道路网(21]。因为很多相邻GPS分属于不同的道路,方向和距离因素的考虑只对地图匹配是不够的。
分析研究基于FCD的交通状况越来越突出。平均链接旅行时间根据交通流的分类,抵消控制和移动方向下游路口十字路口在城市交通网络进行了研究[22]。意思是出发地和目的地(OD)旅行时间被总结评估每个链接的平均旅行时间在交通网络。交通状态检测与FCD [23]。统计分析显示,高质量的重建网中的实际旅行时间只有1.5%配备FCD车辆。probe-car系统是用来预测交通堵塞在不远的将来[24]。一个基本的模型预测交通堵塞在不久的将来使用信息素。聚合和提供的交通质量评价FCD和常见的评价方案(25]。GPS交通监测和控制,提出了交通数据和交通信息的范围说明(26]。然而,这项研究是有限的在分析道路情况,不提供准确的旅行时间。
在这篇文章中,有两个重要的问题需要解决,以便更好地指导路线的选择。第一个是收购FCD的道路交通情况。第二个是找到最短的路径旅行时间通过设计最优路径分析算法。
本文的两个主要贡献如下。(1)一个新的地图匹配算法,充分考虑距离因素,方向的因素,提出了可访问性因素。该算法可用于获取道路交通情况。(2)最短旅行时间的算法设计。一种改进的迪杰斯特拉算法和旅行时间分配给边缘的动态重量。
本文组织如下。节2,提出了FCD和两个算法包括地图匹配算法和最短旅行时间的算法设计。节3,实现实验来验证该方法。节4、地图匹配算法和基于历史道路的平均行驶速度FCD进行了讨论。最后,部分5给出了结论和未来的工作。
2。材料和方法
2.1。数据描述
原FCD收集来自超过1.1万个出租车从武汉9月,2009年,定期(平均20秒)在六天的课程。武汉是湖北省的省会,中国。它位于江汉平原东部的十字路口的长江和汉江中游。它是一个主要的交通枢纽,与数十名铁路、道路和高速公路穿过这座城市。2009年人口91000000人(27]。在武汉的汽车数量约为55.6万(2008年28]。
FCD样品达到足够的普及率为1.9%来计算交通信息。总共有超过8500万条记录(每天超过1400万)与时间戳属性CarID,,、速度和角度。时间戳是一个字符序列通常给予准确的日期和时间。CarID出租车是一个独特的识别。和经度和纬度,分别记录出租车的位置。速度的即时速度出租车在给定的时间。角被定义为从北开始顺时针测量的一个水平角度基线。Brockfeld等人认为Taxi-FCD系统能够提供有价值的旅行时间信息移动服务和平均旅行时间能够可靠地检测并计算(29日]。表1显示了一些典型FCD记录。
2.2。方法
2.2.1。地图匹配算法
由于GPS误差或数字地图测量误差,FCD和地图之间的偏差的现象经常存在。本节的目标是开发一种地图匹配算法FCD评估交通条件。这张地图匹配算法的核心收益如下(图1)。最初的GPS点和道路是显示在图1(一)。然后,为每一个GPS点位置确定。GPS点地图道路图的匹配到相应的位置1 (b)。此外,邻点确定的路线。一个路由给描述点的路径图1 (c)。
(一)
(b)
(c)
在位置确定阶段,一个全面的模型(公式(1方向)),其中包括距离因素,因素,和可访问性因素是充分考虑。距离因子表示GPS点和道路之间的垂直距离。方向的因素是汽车行驶方向的角度和方位的必经之路。可访问性因素是相邻的GPS点的空间可访问性。此外, 在哪里是距离的综合结果,方向,和可访问性因素和地图匹配是缩写为。的参数,,是距离因素、方向的因素,分别和可访问性的因素。距离、方向和可访问性的,,,分别。,,是距离的重量因素,方向的因素,分别和可访问性的因素。的总和,,是1。Dis和Maxdis代表的距离公路和道路缓冲区的最大距离,分别。Dir表示行驶方向和道路之间的角度方位。Maxdir行驶方向和道路之间的最大角方位。Dispp Maxacc相邻点的距离,在一定时间内汽车的最大距离。根据公式(1),一个全面的最大值的道路选择。
最短路径算法是要找到一个路径图中两个顶点之间的权重之和构成边缘最小化。迪杰斯特拉算法(30.],Floyd-Warshall算法[31日),搜索算法(32)及其改进算法被广泛用于查找最短路径。迪杰斯特拉算法的一个优点是停止算法一旦目标节点的最短路径被确定。在路线确定阶段,迪杰斯特拉算法设计实现路线分析。由于大量的数据,最短路径算法耗时。介绍了四叉树索引的速度加快的最短路径算法。该算法的框架包括三个步骤:初始化、搜索和最短路径计算。
在步骤1中(初始化)、道路网络数据加载到内存中搜索最短路径。四叉树索引构建以促进道路网络的空间查询。每一段路都是构造成一个矩形插入到四叉树。
在步骤2中(搜索),搜索矩形构造索引相关的道路。两个相邻的GPS点介绍了构造边界框。有一个距离限制出租车在给定的时间范围内。在给定的时间内最大距离是应用扩展搜索区域。施工后的搜索区域,相关道路来计算最短路径可以选择。
在步骤3中(最短路径计算),迪杰斯特拉算法旨在解决最短路径问题。因为公路网络可以被视为一种稀疏图,表结构定义加速搜索的路线。通过连接所有的相邻点,可以获得出租车路线。
2.2.2。路径分析
最短路径问题是要找到一个路径图中两个顶点(或节点)之间,边的权值之和最小。最短路径选择的旅行时间也可以作为的最短路径问题。重量是旅行时间。区别传统的最短路径问题是边缘重量随时间动态变化。本节介绍了计算方法,时间最短的路径选择。
道路网络构造进行路线分析。创建节点信息和边缘信息首先从道路段进行进一步分析。节点信息包括三个部分:PointID,朗,纬度。PointID是识别的点。朗代表点的经度。纬度表示点的纬度。创建一个新的数据表命名节点信息存储上述信息。边缘信息记录开始和结束点识别的优势。与此同时,两列命名StartID和EndID被添加到属性表的公路段。StartID和EndID外键是一致的吗PointID节点的信息表。
根据节点信息和边缘信息,网络可以构造。因为有些道路段是单一的方式,共享一个共同的节点并不意味着两个部分可以互相访问。在下一节中,单一的方式和双向道路部分进一步讨论。
道路网络是一个典型的混合图(图2)。一些道路段是单向的,和其他人是双向的。每一个无向公路段two-directed边缘相反的方向设置在图2。
三个类包括节点,边缘,图设计的路线分析。这三个类的层次关系图中描述3。可以作为一个稀疏的道路网络图,所以相邻表结构是用于存储的关系节点和边缘。图类包含的节点集合。节点类包括节点识别和边缘从这个节点集合。边缘类包含边缘识别、边缘的长度,bSingleWay,StartID,EndID,重量,htTimeRate,在那里bSingleWay代表是否边缘是单向的htTimeRate是一个哈希表,记录在不同道路的驾驶速度吗时间片。
基于图3,设计了路线最短旅行时间的分析。传统上,公路段重量是一个静态变量。在这项研究中,边缘体重变化随着时间的推移来解决动态边缘的体重问题。图4作为一个案例来解释的过程最短旅行时间和每一步的结果列在表吗2。选择最低成本优势和相应的点是放在一组命名每一步都在表2。首先,原始点,目标点,起飞时间设置。在图4,,,8点原始点,目标点,分别与起飞时间。其次,边缘的最小时间成本(边缘的最小时间成本,因为它需要10分钟的来和8:10分小于到达时间从原始点(其他点)在图4)被选中。以下步骤显示为每个边旅行时间的计算过程。
(一)CurRate这是平均行驶速度CurrentTime在路上被收购htTimeRate。CurrentTime车辆的驾驶时间。
(b)Remainingtime这是休息的时间时间片计算公式(5)。时间片是时间的最小单位的统计信息高速公路的行车速度。INT意味着浮点数的整数部分。
如果(c)Remainingtime这时间片这个速度可以完成这条路,然后边权重计算公式(6)。e.Length和e.Weight路的长度和重量段,分别。
(d),如果Remainingtime这时间片这个速度,汽车不能通过这条路,然后使用时间片及其速率计算长度,直到开车能完成公路段时间片。如果这条路部分已经过,那么分配这条边的重量:
第三,与其他边缘点的最低重量命名在图4是显著的。这意味着该节点一直在搜索和将不考虑以下步骤。第四,如果路径通过循环更新边缘重量和接近原始点。第五,继续选择next最低重量优势和添加点直到找到目标点。最后,旅行时间最短的路径从源点到目的点。的道路是短暂的旅行时间的来在图4。
因为路长度不等于路重量动态改变随着时间的推移,边缘不能按长度。这个算法运行在(是顶点的数量)。
3所示。结果
3.1。地图匹配的结果
出租车的连续轨迹可以通过提出了地图匹配方法。首先,预计将公路GPS点。然后,最短路径算法获得相邻点的路径。最后,出租车的时空位置是获得(图5)。图5显示了FCD的地图匹配的结果。图5(一个)FCD数据库中随机5个出租车在24小时。主要的GPS空间中的点是离散点构成。图5 (b)显示五个出租车的轨迹的结果。提出了地图匹配的连续轨迹的出租车了。
(一)
(b)
3.2。时空的道路
周末和工作日有不同的交通模式(7]。因此,工作日和周末分离研究道路交通情况。研究区域的出租车不断推动更多的皮卡最大利润。所有的出租车速度可以获得24小时。道路的行驶速度是在每一个计算时间片。时间片不能太长或短。太短的时间将导致记录不充分,太长时间会导致低精度。各种研究表明,最小信息率应该在10分钟和3分钟33,34]。考虑各种因素后,时间片计算公式表示如下: 在哪里TaxiNeed最小的出租车数量计算的平均速度,TaxiNum在研究领域表示出租车的总数,RoadSegNum道路段的总数,代表了出租车的平均数量每一瞬时的时刻,RoadLenAvg代表路段的平均长度,SpeedAvg表示所有的出租车的平均速度,意味着汽车的平均行驶时间在路上段。在这项研究中,的结果时间片是238.04秒。为了计算方便,整数的时间片240秒。GPS点选择计算的平均速度每片的必经之路。大部分的出租车都集中在市中心,附近。如果路上没有GPS点,极限速度的道路被认为是这条路的平均速度。
三个道路选择随机计算每个工作日的平均行驶速度从FCD:也就是说,Dingziqiao路(右下角的图6(一)),武汉长江大桥(在图的中间6(一)),新华社路(左上角的图6(一))。Dingziqiao道路的平均速度,武汉长江大桥和新华社道路提出了数字6 (b),6 (c),6 (d),分别。
(一)
(b)
(c)
(d)
四个工作日在同一个道路数据呈现出类似的模式6 (b)- - - - - -6 (d)。一般来说,所有的三个道路有两个高峰,高峰出现在8点和18:00。一个明显的下降0:00至4点,一个明显的上升周期从4点到8点。
因为道路的平均速度可以反映道路的交通信息,道路的时空分布速度每片是调查。图7显示道路的平均速度大约四个工作日在两个典型的瞬间。
(一)
(b)
结论可以从图7。一般来说,所有道路的行车速度会随着时间而改变。具体地说,高峰时段的道路的驾驶速度(喂饲)低于在其他时间(06:00时)。道路的平均行驶速度在附近城市的中心或低于郊区,而改变行驶速度的道路在城市的中心或附近的比在郊区。
3.3。旅行时间最短路径的实验
根据改进的迪杰斯特拉算法,路径选择原型开发。路径最短的距离和最短路径旅行时间函数实现。因为他们可能产生不同的结果,相同的起点和终点选择路线分析以下三个实验。实验结果显示出不同的特征(图8)。图8(一个)显示路径最短的距离。在图8 (b),出发的时间设置为6:00:00和旅行时间最短路径。在图8 (c),出发的时间设置为8:00:00和旅行时间最短路径。
(一)
(b)
(c)
4所示。讨论
4.1。地图匹配算法的分析
地图匹配算法的准确性有很大的影响取得道路情况。因此,实验的精度是一个重要因素。在一天内所有FCD(超过1400万个记录)被选中来验证该算法。
七集的值分配给公式中的参数(1)来评估提出了地图匹配算法的准确性。在实验1中,的值,,被分配到1 0分别和0。上述值意味着只有距离因素被认为是,准确率是81.7%。在实验2中,的值,,被分配到0 1和0。上述值意味着只有方向因子被认为是,准确率是76.3%。在实验3中,的值,,被分配到0,0,1,分别。上述值意味着只有被认为是可访问性因素,准确率是70.8%。实验4的值,,被分配到1/2,1/2,分别和0。上述值意味着距离因子和方向因子被认为是,准确率是89.9%。在实验5,的值,,被分配到1/2,0,分别又1/2。上述值意味着距离因素和可访问性因素被认为是,准确率是87.6%。实验6的值,,被分配到0,1/2,分别又1/2。上述值意味着方向因素和可访问性因素被认为是,准确率是85.1%。在实验7中,的值,,被分配到1/3,1/3,分别和1/3。上述值意味着距离因素、方向的因素,和可访问性的因素是,准确率为94.9%。该方法的准确性,包括距离,方向,和可访问性因素,比传统的地图匹配算法,包括距离和方向的因素。
因此,的值,,被分配到1/3,1/3,1/3在这个研究。大部分的GPS点已经匹配到正确的道路图5。基于地图匹配算法,提出道路的驾驶速度可以获得。
4.2。基于历史FCD平均行车速度的道路
历史FCD在一定时间内的平均速度可能反映了道路交通条件在一个特定的时刻。简历(变异系数)介绍表达道路的驾驶速度的离散程度: 在哪里工作日的每日平均速度和吗代表四个工作日的平均速度。
简历的行驶速度大约三路(图6(一))如图9。三个道路的简历平均值0.099244701,0.079581216和0.110617283。根据统计分析,Dingziqiao路的履历的百分比小于0.1,0.15,和0.2是55.12%,83.93%,和97.23%,分别。同样,武汉长江大桥公路的百分比的简历小于0.1,0.15,和0.2是73.96%,82.55%,和92.24%,分别。新华社道路的履历的百分比小于0.1,0.15,和0.2是49.03%,76.73%,和93.63%,分别。显然,0.2百分比小于阈值的绝对多数三公路。我们可以得出结论,历史FCD可以近似的平均速度道路的平均速度在一个特定的时刻。
(一)
(b)
(c)
4.3。旅行时间最短路径分析
距离因素和时间因素是用来评估拟议的最短旅行时间的算法。的距离和时间成本规划路径数据8(一个),8 (b),8 (c)表中列出3。距离和时间成本的单位分别以米和秒。
如果交通条件好,规划路径(路径最短的距离和最短旅行时间路径)可能会关闭在空间性和部分重叠(数字8(一个)和8 (b))。距离的差异数据的路径8(一个)和8 (b)小(表3)。然而,旅行时间最短路径(图8 (b))通常包含更多的主要道路。相反,路径最短的距离(图8(一个))通常包含更多的二级公路。
如果交通堵塞发生在市中心的一些道路,通常有一个很大的区别旅行时间最短路径和路径最短的距离,由于高速公路的交通状况通常比其他更好的道路。例如,旅行时间最短路径图8 (c)包含更多的公路。虽然距离图的规划路径8 (c)长于规划路径距离图8(一个)旅游,花费更少的时间。
规划路径在不同的时间也是不同的,虽然它们使用相同的算法。道路交通状况会随着时间发生变化,所以旅行时间最短路径在不同的起飞时间(数据完全不同8 (b)和8 (c))。
5。结论
在这项研究中,一个有效的地图匹配算法,结果表明,该方法具有更高的精度。结果的基础上三路的简历,我们得出这样的结论:为每个道路交通分布在四个工作日也有类似的模式。通过比较与路线最短旅行时间和最短的距离,结果表明,旅行时间最短路径旅行时间成本小于路径最短的距离。
尽管有超过8500万条记录收集和分析,交通状况可能会受到其他因素的影响,比如天气和节日。然而,我们没有考虑这些因素对流量的影响。提出了地图匹配算法,因为有些地图匹配算法不是开源的,我们没有计算这些算法的准确性。
显然,本文的研究可以被视为一个应用程序的初始步骤FCD。因为FCD大数据的特点,未来的研究计划应用分布式计算技术加快分析速度的大规模GPS记录。此外,多源数据将被用来分析未来的交通状况的工作。
相互竞争的利益
作者宣称没有利益冲突有关的出版。
确认
这项工作是由中国国家自然科学基金(没有。41301417),国家资助的奖学金项目,重庆市自然科学基金(没有。cstc2014jcyjA20017),中央大学基础研究基金(没有。XDJK2015B022),开放研究基金由四川工程研究中心应急与减灾(没有映射。K2015B015)。