发现拥堵的路线在公路网中使用车辆轨迹

文摘

流行的路线建议在公路网络和交通监控已经成为重要的基于位置的服务。方案找出拥挤的路线提出了通过考虑车辆在道路段的数量。然而,现有的方案不考虑每个路段的特点如宽度、长度和方向的道路网络。此外,现有的方案没有考虑车辆的平均移动速度。因此,他们可以检测到错误的密度路线。为了克服这些问题,我们提出一种新的发现拥堵的路线方案通过分析车辆轨迹的道路网络。该方案将每个道路分为段公路网络与不同的宽度和长度。然后,拥挤的道路段检测通过道路段的饱和程度和平均移动速度的车辆在路上。最后,我们计算最终的拥堵的路线通过使用集群方案。实验结果表明,该方案能够有效地发现拥堵的路线不同方向的道路。

1。介绍

最近,随着移动设备的使用,基于位置的服务越来越受欢迎。自从迅速增加卫星和GPS(全球定位系统)技术的发展,可以收集大量的移动对象轨迹数据,如车辆位置数据,飓风追踪数据,和动物运动数据(1- - - - - -4]。分析对这些轨迹数据越来越重要对于许多应用程序,如气象观测和预报,动物习惯观察道路交通情况分析,在运输和导航5- - - - - -9]。根据记录轨迹数据和公路网络,移动模式,交通状况和道路推荐服务可以支持1,2,10- - - - - -12]。

不断增加的车辆,最近的路线推荐服务是越来越重要1,4,7,8,13- - - - - -15]。基于道路网络的应用程序,车辆道路网络的移动性限制。大多数现有的计划试图监视和预测交通使用有记录的历史轨迹数据的车辆配备了GPS设备。基于指数的方案构建索引采用轨迹数据的车辆5,6]。然后根据路线推荐相关的车辆历史轨迹数据。基于集群的方案生成道路网的密度路线通过分析车辆的轨迹数据(9,13,16,17]。文献[1)提出了MPR方案发现流行的两个地点之间的路线通过观察许多之前用户的旅游行为。文献[18)研究的问题在公路网络找到合理的替代路线。在NETSCAN方案(13),道路网的密度路线评估通过考虑车辆的位置和时间。

根据轨迹数据,汽车的数量在一个特定的道路段和时间可以用来识别密度路线的道路。然而,现有的方案不适合真正的公路网络。现有的计划有三个主要问题:(1)道路方向的公路网络的不考虑;(2)道路的宽度和长度段不考虑;和(3)的平均移动速度车辆在道路段不被认为是。在真实道路网络环境中,每个路分为两个方向:积极的方向和消极的方向。车辆在路上向不同的方向相互不影响。因此,拥堵的路线是不准确的,如果不考虑道路的方向。每段道路的宽度和长度是不同的道路网络,这也将影响拥堵的路线的准确性。此外,车辆在道路段的平均移动速度可以识别道路的拥堵。

为了克服这些问题,我们提出一个拥堵的路线发现方案,方向,宽度和长度对道路拥堵的路线在实际道路网络环境中发现。该方案将道路分为段具有不同的宽度和长度。然后,拥挤的道路段提取通过考虑车辆的平均移动速度和饱和程度的公路网络中的每一段路。最后,我们执行聚类方案来计算最终在整个公路网络拥堵的路线。

本文的其余部分组织如下。我们将讨论相关工作2。部分3介绍了该方案的细节。部分4包含实验评价,证实了我们方案的优越性。最后,部分5本文总结道。

2。相关工作

发现热门线路或流行的路线是一个非常重要的技术在道路网络支持基于位置的服务。文献[1]研究发现方案最受欢迎的路线(MPR)两个地点之间通过观察许多之前用户的旅游行为。文献[1)提出了一个算法建立传输网络模型的历史轨迹和吸收马尔可夫链模型推导出利用转移概率转移节点。产品最大概率算法用于发现MPR从传输网络基于广度优先的流行指标方案。文献[16)定义了一个热路线一般路径在包含交通拥挤的道路网络和研究发现方案的热路线。文献[16)提出了一种新的叫做FlowScan density-based算法。它是一个健壮的算法,可以处理复杂的数据,并通过大量的实验验证。而不是集群移动物体、公路段集群是基于共同的密度交通他们分享。文献[15]研究了交通密度估计问题,利用信息提示出现在累积声学信号获得从roadside-installed单麦克风。

车辆都位于人口稠密区试着搬到一个noncongested区域。文献[10)提出了一种路由发现的方法缓解交通拥挤提供行驶路线的旅行时间变短。该方法不需要全球交通信息但区域每个车辆的交通信息。车辆计算路线的目的地,评估值的总和的道路段路线变得最小。给定一个空间范围和用户偏好由用户指定的深度和广度,(11)处理pattern-aware轨迹搜索(拍)检索前K轨迹通过流行的roi。拍支持旅行计划不需要先验知识的roi指定的空间范围。拍一个用户使用运动图捕捉旅游模式隐藏在轨迹和开发一个算法来确定roi的吸引力评分和BTS提出了一个算法来有效地检索K轨迹。

文献[19)提出了一种快速路径找到最好的最短路径的算法解决路径规划问题的道路网路线导航系统的精度和速度。文献[20.)提出了一种自适应最快路径算法能够有效地占重要的驾驶和速度数据开采大量的交通模式。文献[20.)提出了一种路由算法使用的道路等级和预先计算的区域限制搜索空间。这提高了旅行时间通过升级道路只要有益和发现路线,考虑速度和驾驶模式。

文献[13)提出了一个方案发现密集的路线通过聚类相似的道路部分根据每个时间段的交通和位置。文献[13]介绍NETSCAN进行了密集的部分和包含它们的集群形成密集的航线。NETSCAN集群道路部分基于网络密度统计数据。这个集群考虑轨迹的方向。此外,这种方法利用网络拓扑创建相关的集群。提出一个模型来评估密集的进化路线对在两个连续的时间间隔,DENSITYLINK算法。DENSITYLINK允许表征密集的道路网络的进化。文献[17)提出了一个基于时间的聚类算法称为Tk-means适应轨迹数据的k - means算法。Tk-means集群对象的时间间隔不同的轨迹运动。如果一个对象跨越不同的时间间隔,它最终将属于不同的集群。Tk-means使用两种方法,一个精确的方法和一种近似方法。确切的方法计算实际的集群访问对象在其生命时间和近似方法准确地计算一些实际访问集群和基于这些计算集群以及集群产生的剩余的数据集,它预测未来查询对象的运动模式。

3所示。该方案

3.1。数据模型

我们假设道路网络是由一个图形表示,在那里表示节点的不同路段之间的十字路口用于连接两个表示边缘道路网络中相邻节点。车辆的轨迹是由Tr。每个节点在道路网是由一个点表示。表示一段公路网络。“+”和“−”用来表示不同方向的车辆在道路网络中。此外,由于每个道路的长度和车道的数量是不同的,每个道路段的长度和宽度。因此,每一段路都是由=,}、长度、宽度,长度是道路段的长度和宽度是车道的数量。如图1,和邻居的吗在道路网。

在道路网路,每一段商店的信息直接连接道路段。此信息用于以下聚类评价。自车辆可以连续移动或者呆在一个位置,有必要每辆车的位置知识根据时间戳。假设轨道每辆车的如下: 在哪里表示部分和是时间戳。根据,每辆车的位置很容易被检索。

3.2。拥挤的路段

最初的道路信息和轨迹数据可用于确定车辆的存在在每一个公路段不同的方向。每一段路都是评估的复杂性值。道路段被认为是拥挤的地区如果复杂性评估值高于预定义的阈值。执行聚类算法在拥挤的路段。道路段移动速度和较低的高数量的确定车辆拥堵的路段。图2显示了程序计算拥挤的路线。

摘要拥挤的道路段计算根据不同方向的道路。每辆车的位置和方向可以从记录轨迹中检索数据。每一段路都是计算的复杂度值通过考虑车辆在路上段的平均速度和道路段的饱和程度。快速移动的速度表明,道路的拥堵段很低。相比之下,移动速度较低表明,道路的拥堵段高。饱和程度计算基于车辆的数量在一个道路段和道路段的长度和宽度,显示在图3。我们定义的道路拥堵的道路在道路网段段高复杂度值。

平均移动速度车辆的道路段根据以下方程计算不同方向(2),表示车辆的移动速度。饱和根据宽度和长度公路段计算(3),表示车辆在道路段的数量。因此,公路段计算的复杂度值(4)相结合(2)和(3);表示之间的权重值平均移动速度的车辆和道路段的饱和度。考虑

3.3。拥挤的路线检测

在本节中,我们提出的算法检测拥挤的路线。该算法在两个阶段。在第一阶段,每个路段的复杂性值根据不同的方向计算公路网络。在第二个阶段,道路网络的拥堵的路线是由聚类评估与每个时间间隔段拥挤的道路。当道路段的复杂度值大于预定义的阈值,道路段段被认为是一个拥挤的道路。最后,同一方向的拥堵的路段都聚集在一起。算法1显示了拥堵的路线检测算法。

由于道路段的复杂度值根据不同的时间戳,改变他们必须定期计算。道路的拥挤的航线网络根据复杂性计算值。图4显示了拥堵的路线(虚线区域)的公路网络在不同的时间戳。根据车辆的轨迹数据记录时间的拥堵的路线产生不同方向的道路网络,等和在图4(一)。如图4 (b),当时间,,,评估是拥堵的路段。自和邻居道路段,同一方向的道路网络,它们聚集在一起。

4所示。绩效评估

在本节中,我们介绍了绩效评估通过比较该方案与现有方案NETSCAN [13]。基于网络的发电机(生成的车辆21]。生成的复杂度值和集群根据车辆的数量在每个时间间隔。所有的实验都是用Java编写的,实验是在英特尔i3 3.0 GHz CPU和4 G内存。表1总结了绩效评估的参数。

在第一个实验中,我们将展示奥尔登堡城市的拥堵的路线公路网络通过使用我们的方案。在这个实验中,车辆在道路网络的总数量设置为50000,饱和度的道路设置为30%。如图5,结果表明,道路网络的拥堵的路线是不同的根据不同方向的道路网络。蓝色和红色区域代表道路的拥挤的航线网络正方向和消极的方向,分别。

在图6,我们比较NETSCAN计划和方案。NETSCAN拥堵的路线的数量和该方案的评估是根据车辆的数量。方案,拥堵的路线是评估在不同的方向(正方向和反方向)和同一方向,分别。提出(正面)和建议(消极的)的数量意味着每个方向路段的拥堵的路线,并提出(整体)意味着拥挤的路线的双向的数量根据车辆的数量。结果表明,拥堵的路线的数量增加时,车辆数量的增加。的数量的拥堵的路线方案时类似车辆的数量在20000年和30000年之间。这是因为每个路段的饱和度被认为是在该方案。当一段道路的宽度和长度大,20000和30000辆大型的道路。因此,大部分的道路段不确定为拥堵的路线。NETSCAN方案,拥堵的路线的数量比例增加汽车的数量的增加。

图7显示了拥堵的路线的数量根据不同时间戳时时间间隔设置为1小时。拥挤的航线是评估在不同的方向(正方向和反方向)和同一方向,分别。集群(正面)和集群的数量(消极的)意味着拥挤的路线的每个方向根据不同的时间戳。我们可以看到,正方向的拥堵的路线的数量大于消极的方向。和拥挤的路线的方案没有考虑道路的方向线段比的大拥堵的路线的方案考虑道路段的方向。

5。结论

在本文中,我们提出了一个拥挤的路线发现方案在实际道路网络。该方案将道路划分为段具有不同的宽度和长度。它提取拥挤的路段平均速度的基础上的车辆和道路段的饱和程度。最后一个拥堵的路线计算通过执行聚类方案。实验结果表明,该方案可以发现不同方向的拥堵的路线在现有的方案。在未来,我们将展示我们的方法的优越性通过使用车辆的真实轨迹数据。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究得到了MSIP(科技部、ICT和未来规划),韩国,在期(信息技术研究中心)支持程序(NIPA - 2014 - h0301 - 14 - 1022)监督的海椰子(国家信息产业促进机构)和C-ITRC(融合信息技术研究中心)支持程序(NIPA - 2014 - h0401 - 14 - 1007)监督的海椰子(国家信息产业促进机构),信息通信技术研发项目的大规模实时数据分析,发现平台MSIP / IITP(14-824-09-001,开发高性能视觉发现大数据平台的大规模实时数据分析),和韩国国家研究基金会(NRF)授予由韩国政府(MSIP)(没有。2013 r1a2a2a01015710)。

引用

1. z陈、h·t·沈和x周,“发现受欢迎的路线轨迹,”IEEE学报》27日数据工程国际会议(ICDE 11),页900 - 911,汉诺威,德国,2011年4月。视图:出版商的网站|谷歌学术搜索
2. p . Cudre-Mauroux大肠吴,s·马登,“TrajStore:一个非常大的轨迹数据集自适应存储系统,”第26届IEEE国际会议数据工程学报》(ICDE 10)长滩,页109 - 120年,加州,美国,2010年3月。视图:出版商的网站|谷歌学术搜索
3. e . Kanoulas y Du, t·夏,d,“找到最快路径与速度模式、道路网”22日国际会议数据工程的程序2006年4月,p。。视图:出版商的网站|谷歌学术搜索
4. g . Gidofalvi c . Borgelt m·科尔,t·b·皮德森”频繁路线连续移动物体的位置和密度预测基于道路网络,”19 ACM SIGSPATIAL诉讼进展国际会议在地理信息系统(GIS 11)2011年11月,页381 - 384。视图:出版商的网站|谷歌学术搜索
5. J.-W。Chang M.-S。歌,黄永发。嗯,“TMN-tree:新轨迹移动对象索引结构的空间网络,”《IEEE 10计算机和信息技术国际会议(CIT 10)布拉德福德,页1633 - 1638年,英国6 - 2010。视图:出版商的网站|谷歌学术搜索
6. 胡黄m p, l .夏”网格轨迹移动对象索引方法基于固定网络,”《18 Geoinformatics国际会议,2010年6月。视图:出版商的网站|谷歌学术搜索
7. 我。赢了,S.-W。金,黄永发。门敏,j·李,“轨迹聚类在道路网络环境中,”《IEEE研讨会上计算智能和数据挖掘(CIDM ' 09)2009年4月,页299 - 305。视图:出版商的网站|谷歌学术搜索
8. G.-P。卢武铉,J.-W。卢武铉,S.-W。黄,B.-K。咦,“支持模式匹配道路网络,查询轨迹”IEEE工程知识和数据,23卷,不。11日,第1758 - 1753页,2011年。视图:出版商的网站|谷歌学术搜索
9. n . Pelekis Kopanakis, e·e·Kotsifakos e . Frentzos和y Theodoridis”集群移动对象的轨迹在一个不确定的世界,”《IEEE国际会议数据挖掘(ICDM ' 09)2009年12月,页417 - 427。视图:出版商的网站|谷歌学术搜索
10. m .木村,井上,y Kakuda, t . Dohi”路线发现方法基于VANETs缓解交通堵塞在城市运输考虑车辆密度和平均速度之间的关系,”学报》国际研讨会上10日国际研讨会上自动分散系统(ISADS 11)2011年3月,页299 - 302。视图:出版商的网站|谷歌学术搜索
11. L.-Y。魏,观测。彭和观测。李,“探索pattern-aware旅游路线轨迹搜索,”ACM智能交易系统和技术,4卷,不。3、第四十八条,2013年。视图:出版商的网站|谷歌学术搜索
12. y徐和j .王”最优路径解决城市交通道路,”第七届国际会议上自然计算学报》(ICNC 11)2011年7月,页799 - 802。视图:出版商的网站|谷歌学术搜索
13. a . Kharrat k . Zeitouni Sandu-Popa,和美国的费,”描述交通密度及其移动对象轨迹,演化”学报》第五届国际会议上信号图像技术和基于互联网的系统(斯' 09)2009年12月,页257 - 263。视图:出版商的网站|谷歌学术搜索
14. k . w . Min, j·w·金和j . h .公园,“最优路线的决心技术基于轨迹查询移动对象数据库”学报》国际会议数据库和专家系统的应用程序,第675 - 666页,2006年。视图:谷歌学术搜索
15. 诉Tyagi、美国Kalyanaraman和r . Krishnapuram”交通密度状态估计基于累积路声学,”IEEE智能交通系统,13卷,不。3、1156 - 1166年,2012页。视图:出版商的网站|谷歌学术搜索
16. x, j·汉、j·李和h·冈萨雷斯,“交通density-based发现热路线的道路网络,”暹罗学报》国际会议数据挖掘,第459 - 441页,2007年。视图:谷歌学术搜索
17. h . m . o . Mokhtar o . Ossama, m . e . Sharkawi”集群移动物体轨迹的参数化技术,”《数据挖掘和知识管理过程,1卷,不。1,14-30,2011页。视图:谷歌学术搜索
18. 亚伯拉罕,d·德尔·a . v . Goldberg和r·f·Werneck“替代路线在公路网,”《实验算法第1.3条,卷。18日,2013年。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. A . Selamat m . Zolfpour-Arokhlo s . z . Hashim和m . h . Selamat”路径诱导系统的快速路径规划算法,”《IEEE国际会议系统,人,控制论(SMC的11)安克雷奇,页2773 - 2778年,阿拉斯加,美国,2011年10月。视图:出版商的网站|谷歌学术搜索
20. h·冈萨雷斯,j .汉李x m . Myslinska j.p. Sondag,“自适应最快路径计算道路网:交通采矿方法,”学报》国际会议上非常大的数据基础,第805 - 794页,2007年。视图:谷歌学术搜索
21. t . Brinkhoff”生成基于网络的移动对象的框架。”GeoInformatica》第六卷,没有。2、153 - 180年,2002页。视图:出版商的网站|谷歌学术搜索

版权

版权©2015 Kyoung博克等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。