基于城市兴趣点的连续路径诱导方法

doi:10.13229/j.cnki.jdxbgxb201403008

吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (3): 631-636.doi: 10.13229/j.cnki.jdxbgxb201403008

基于城市兴趣点的连续路径诱导方法

于尧¹,杨兆升^1,2,莫祥伦¹,林赐云^1,2

1.吉林大学交通学院长春 130022;
2.吉林大学汽车仿真与控制国家重点实验室长春 130022

收稿日期:2013-09-16 出版日期:2014-03-01 发布日期:2014-03-01
通讯作者: 杨兆升(1938),男,教授,博士生导师.研究方向:城市智能交通,交通控制与诱导.E-mail:yangzs@jlu.edu.cn E-mail:yuyao11@jlu.edu.cn
作者简介:于尧(1985),男,博士研究生.研究方向:城市智能交通,交通控制与诱导.E-mail:yuyao11@jlu.edu.cn
基金资助:
“863”国家高技术研究发展计划项目(2012AA112307).

Sequenced route search method based on urban point of interest data

YU Yao¹,YANG Zhao-sheng^1,2,MO Xiang-lun¹,LIN Ci-yun^1.2

1.College of Traffic, Jilin University, Changchun 130022, China;
2.State Key Laboratory of Automobile Simulation and Control, Jilin University, Changchun 130022, China

Received:2013-09-16 Online:2014-03-01 Published:2014-03-01

摘要/Abstract

摘要：

针对现有路径诱导算法无法实现多点连续搜索的不足,提出了一种可以满足出行者一次出行中访问多个兴趣点(Point of interest, POI)的ASSA算法(A^*-based sequenced search algorithm)。ASSA算法优化了路网搜索结构,大幅地减少了数据访问量,并通过兴趣点近邻区域的时空关联推理,得到最优出行路径。并基于城市POI兴趣点信息,对兴趣点数据进行了分类划分,设计了多规则下的兴趣点访问机制,并对其进行了试验验证。结果表明:相比于NS最近邻算法,提出的ASSA算法可以提高计算性能16%以上,并避免了非最优路径的出现,可以有效地满足出行者不同规则下的兴趣点访问需求。

关键词: 交通运输系统工程, 城市兴趣点信息, 路径诱导, 最短路径, 出行信息

Abstract:

To overcome the shortcoming that the existing route guidance algorithms can not execute sequenced route search, a new Artificial Searching Swarm Algorithm (ASSA) is developed that can query multi-Point of Interests (POIs) in travel processing. The ASSA can optimize search topological structure of the road-network, which greatly reduces the amount of data access. Thus the optimal path can be presented according to the spatial-time correlation reasoning. Further more, the POI data are categorized based on urban POIs and a method to go through the sequenced POIs under multi-rules is developed. Sensitive experiments were implemented to verify the proposed ASSA. Results show that, compared with NS algorithm, ASSA can improve the computing efficiency by at least 16%, and it can also avoid getting less-than-optimal path. It effectively meets the travelers' sequenced travel demand.

Key words: engineering of communication and transportation system, message of point of interest(POI), route guidance, shortest path, travel information

中图分类号:

U491.1

于尧,杨兆升,莫祥伦,林赐云. 基于城市兴趣点的连续路径诱导方法[J]. 吉林大学学报(工学版), 2014, 44(3): 631-636.

YU Yao,YANG Zhao-sheng,MO Xiang-lun,LIN Ci-yun. Sequenced route search method based on urban point of interest data[J]. 吉林大学学报(工学版), 2014, 44(3): 631-636.

参考文献

[1] 李威武,王慧,钱积新. 智能交通系统中路径诱导算法研究进展[J]. 浙江大学学报:工学版,2005,39(6):819-825.
Li Wei-wu,Wang Hui,Qian Ji-xin. New trends in route guidance algorithm research of intelligent transportation system[J]. Journal of Zhejiang University (Engineering Science), 2005,39(6):819-825.
[2] Li Y F,Le J,Danny M,et al. Mapping oversized and overweight truck routes with procedure based on geographic information systems[J]. Transportation Research Record,2012,12(2219):8-16.
[3] 杨兆升. 城市交通流诱导系统理论与模型[M]. 北京:人民交通出版社,2000.
[4] Xing S H,Shahabi C. Scalable shortest paths browsing on land surface[C]∥GIS:Proceedings of the ACM International Symposium on Advances in Geographic Information Systems,2010:89-98.
[5] Alba Martínez M A,Cordeau J F,Dell'Amico M, et al. A branch-and-cut algorithm for the double traveling salesman problem with multiple stacks[J]. Informs Journal on Computing,2013,25(1):41-55.
[6] Sharifzadeh M, Kolahdouzan M, Shahabi C. The optimal sequenced route query[J]. The VLDB Journal,2008,17(4): 765-787.
[7] Lee K C K, Lee W C, Leong H V. Nearest surrounder queries[C]∥IEEE Transactions on Knowledge and Data Engineering,2010,22(10): 1444-1458.
[8] Terrovitis M, Bakiras S, Papadias D, et al. Constrained shortest path computation[C]∥Proceeding of the 9th International Symposium on Spatial and Temporal Databases,2005: 181-199.
[9] Chen H Q,Ku W S,Sun M T,et al. The multi-rule partial sequenced route query[C]∥GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems,2008:65-74.
[10] Taniar D,Safar M,Tran Q T,et al. Spatial network RNN queries in GIS[J]. Computer Journal,2011,54(4):617-627.
[11] Montalto F A,Bartrand T A, Waldman A M,et al. Decentralised green infrastructure: The importance of stakeholder behaviour in determining spatial and temporal outcomes[J]. Structure and Infrastructure Engineering,2013,9(12):1187-1205.
[12] Zhao W,Li Q,Li B. Extracting hierarchical landmarks from urban POI data[J]. Journal of Remote Sensing,2011,15(5): 973-988.
[13] Raubal M,Winter S. Enriching wayfinding instructions with local landmarks[J]. Geographic Information Science Lecture Notes in Computer Science,2002,2478:243-259.
[14] 范志起. 半结构化数据索引技术的研究[D]. 长春:吉林大学:计算机科学与技术学院,2011.
Fan Zhi-qi. Research on the index technology of semi-structured data[D]. Changchun: College of Computer Science and Technology,Jilin University,2011.
[15] Engebretsen L,Karpinski M. TSP with bounded metrics[J]. Journal of Computer and System Sciences,2006,72(4):509-546.
[16] 于德新,杨兆升,高鹏. 动态限制搜索区域的带约束K则最优路径算法[J]. 吉林大学学报:工学版, 2009,39(增刊2):172-176.
Yu De-xin,Yang Zhao-sheng,Gao Peng. Constrained K-shortest paths algorithm within dynamic restricted searching area[J]. Journal of Jilin University (Engineering and Technology Edition),2009,39(Sup.2):172-176.
[17] 郑四发,曹剑东,连小珉. 复杂路网下多客户间最短路径的扇面Dijkstra算法[J]. 清华大学学报:自然科学版,2009,49(11):1834-1837.
Zheng Si-fa,Cao Jian-dong,Lian Xiao-min. Sector Dijkstra algorithm for shortest routes between customers in complex road networks[J]. Journal of Tsinghua University, 2009,49(11):1834-1837.

相关文章 15

[1]	陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[2]	常山,宋瑞,何世伟,黎浩东,殷玮川. 共享单车故障车辆回收模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1677-1684.
[3]	曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[4]	宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[5]	刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[6]	钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[7]	刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[8]	宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.
[9]	栾鑫, 邓卫, 程琳, 陈新元. 特大城市居民出行方式选择行为的混合Logit模型[J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
[10]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[11]	陈永恒, 刘鑫山, 熊帅, 汪昆维, 谌垚, 杨少辉. 冰雪条件下快速路汇流区可变限速控制[J]. 吉林大学学报(工学版), 2018, 48(3): 677-687.
[12]	王占中, 卢月, 刘晓峰, 赵利英. 基于改进和声搜索算法的越库车辆排序[J]. 吉林大学学报(工学版), 2018, 48(3): 688-693.
[13]	李志慧, 胡永利, 赵永华, 马佳磊, 李海涛, 钟涛, 杨少辉. 基于车载的运动行人区域估计方法[J]. 吉林大学学报(工学版), 2018, 48(3): 694-703.
[14]	陈松, 李显生, 任园园. 公交车钩形转弯交叉口自适应信号控制方法[J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[15]	苏书杰, 何露. 步行交通规划交叉路口行人瞬时动态拥塞疏散模型[J]. 吉林大学学报(工学版), 2018, 48(2): 440-447.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于城市兴趣点的连续路径诱导方法

Sequenced route search method based on urban point of interest data

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10