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.
WANG Jing
,
LIU Hui-ping
,
JIN Che-qing
. Constrained route planning based on the regular expression[J]. Journal of East China Normal University(Natural Science), 2017
, 2017(5)
: 162
-173,235
.
DOI: 10.3969/j.issn.1000-5641.2017.05.015
[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.
中国综合性科技类核心期刊(北大核心)