基于正则表达式的限制性路径规划

doi:10.3969/j.issn.1000-5641.2017.05.015

华东师范大学学报(自然科学版) ›› 2017, Vol. 2017 ›› Issue (5): 162-173,235.doi: 10.3969/j.issn.1000-5641.2017.05.015

基于正则表达式的限制性路径规划

王婧, 刘辉平, 金澈清

华东师范大学计算机科学与软件工程学院, 上海 200062

收稿日期:2017-06-20 出版日期:2017-09-25 发布日期:2017-09-25
通讯作者: 金澈清,男,博士生导师,研究方向为基于位置的服务.E-mail:cqjin@sei.ecnu.edu.cn E-mail:cqjin@sei.ecnu.edu.cn
作者简介:王婧,女,硕士研究生,研究方向为基于位置的服务.E-mail:jingwang@stu.ecnu.edu.cn
基金资助:
国家重点研发计划重点专项（973）（2016YFB1000905）；国家自然科学基金（61370101，61532021，U1501252，U1401256，61402180）

Constrained route planning based on the regular expression

WANG Jing, LIU Hui-ping, JIN Che-qing

School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China

Received:2017-06-20 Online:2017-09-25 Published:2017-09-25

摘要/Abstract

摘要： 传统的路径规划算法大多以长度、时间或代价等为度量标准搜索起止点间的最优路径，不适于解决有位置限制的路径规划需求，如搜索有序或无序地经过全部或部分用户指定的位置点或位置点类别的最短路径.本文主要针对这类应用场景，利用正则表达式表示复杂的限制性路径规划需求，形式化定义了基于正则表达式的限制性路径规划问题并设计了通用的解决框架，在此框架基础上提出了基本的限制性路径规划算法BCRP（Basic ConstrainedRoute Planning）以及加入剪枝策略的改进的限制性路径规划算法ICRP（Improved Constrained Route Planning），有效减少了搜索空间.最后通过在真实路网数据上的实验结果证明了方法的高效性.

关键词: 限制性路径规划, 正则表达式, 最短路径

Abstract: Traditional route planning algorithms, which mainly focus on metrics such as the distance, time, cost, etc. to find the optimal route from source to destination, are not suitable for solving route planning requirements with location constraints. For example, finding the shortest path passing the whole or a part of user-defined location categories in order or disorder. Mainly focusing on these scenarios, this paper formalizes the constrained route planning problem on the basis of the regular expression generated by user requirements and gives a general framework to solve this problem. Based on this, a basic constrained route planning algorithm (BCRP) and an improved constrained route planning algorithm (ICRP) are proposed while ICRP reduces the search space using pruning rules. Finally, extensive experiments on real road network datasets demonstrate the efficiency of our proposal.

Key words: constrained route planning, the regular expression, the shortest path

中图分类号:

TP391

王婧, 刘辉平, 金澈清. 基于正则表达式的限制性路径规划[J]. 华东师范大学学报(自然科学版), 2017, 2017(5): 162-173,235.

WANG Jing, LIU Hui-ping, JIN Che-qing. Constrained route planning based on the regular expression[J]. Journal of East China Normal University(Natural Sc, 2017, 2017(5): 162-173,235.

参考文献

[1] LIU H, JIN C, ZHOU A. Popular route planning with travel cost estimation[C]//Proceedings, Part Ⅱ, of the 21st International Conference on Database Systems for Advanced Applications. New York:Springer-Verlag, 2016, 9643:403-418.
[2] YUAN J, ZHENG Y, ZHANG C, et al. T-drive:Driving directions based on taxi trajectories[C]//Sigspatial International Conference on Advances in Geographic Information Systems. New York:ACM, 2010:99-108.
[3] ZHENG Y, CAPRA L, WOLFSON O, et al. Urban computing:Concepts, methodologies, and applications[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(3):38.
[4] ZHANG S, QIN L, ZHENG Y, et al. Effective and efficient:Large-scale dynamic city express[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(12):3203-3217.
[5] LU H C, LIN C Y, TSENG V S. Trip-Mine:An efficient trip planning approach with travel time constraints[C]//IEEE International Conference on Mobile Data Management.[S.l.]:IEEE, 2011:152-161.
[6] MALVIYA N, MADDEN S, BHATTACHARYA A. A continuous query system for dynamic route planning[C]//IEEE, International Conference on Data Engineering.[S.l.]:IEEE Computer Society, 2011:792-803.
[7] LI F, CHENG D, HADJIELEFTHERIOU M, et al. On trip planning queries in spatial databases[J]. Journal of Combinatorial Optimization, 2005, 31(1):1-16.
[8] SHARIFZADEH M, KOLAHDOUZAN M, SHAHABI C. The optimal sequenced route query[J]. The VLDB Journal, 2008, 17(4):765-787.
[9] SHARIFZADEH M, SHAHABI C. Additively weighted voronoi diagrams for optimal sequenced route queries[J]. Workshop on Spatio-Temporal Database Management, 2006.
[10] SHARIFZADEH M, SHAHABI C. Processing optimal sequenced route queries using voronoi diagrams[J]. Geoinformatica, 2008, 12(4):411-433.
[11] RICE M N, TSOTRAS V J. Engineering generalized shortest path queries[C]//IEEE International Conference on Data Engineering.[S.l.]:IEEE Computer Society, 2013:949-960.
[12] CHEN H, KU W S, SUN M T, et al. The multi-rule partial sequenced route query[C]//ACM Sigspatial International Symposium on Advances in Geographic Information Systems. USA:DBLP, 2008:1-10.
[13] LI J, YANG Y, MAMOULIS N. Optimal route queries with arbitrary order constraints[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5):1097-1110.
[14] YAO B, TANG M, LI F. Multi-approximate-keyword routing in GIS data[C]//ACM Sigspatial International Conference on Advances in Geographic Information Systems. New York:ACM, 2011:201-210.
[15] CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Proceedings of the VLDB Endowment, 2012, 5(11):1136-1147.
[16] CAO X, CHEN L, CONG G, et al. KORS:Keyword-aware optimal route search system[C]//IEEE, International Conference on Data Engineering.[S.l.]:IEEE, 2013:1340-1343.
[17] BARRETT C, JACOB R, MARATHE M. Formal language constrained path problems[J]. Computing, 1998, 30(3):234-245.

基于正则表达式的限制性路径规划

Constrained route planning based on the regular expression

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	CHENIKWI Kingsley Che, 王学锋. 将海上丝绸之路与撒哈拉以南非洲运输走廊整合在一起, 以促进经济发展[J]. 华东师范大学学报（自然科学版）, 2020, 2020(S1): 153-158.
[2]	郑燕飞;李响. 一种用于制定有组织撤离计划的算法[J]. 华东师范大学学报(自然科学版), 2009, 2009(5): 45-52.