Constrained route planning based on the regular expression
-
摘要: 传统的路径规划算法大多以长度、时间或代价等为度量标准搜索起止点间的最优路径，不适于解决有位置限制的路径规划需求，如搜索有序或无序地经过全部或部分用户指定的位置点或位置点类别的最短路径.本文主要针对这类应用场景，利用正则表达式表示复杂的限制性路径规划需求，形式化定义了基于正则表达式的限制性路径规划问题并设计了通用的解决框架，在此框架基础上提出了基本的限制性路径规划算法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
-
图 7 采用不同num, j, k时的平均扩展节点数目
Fig. 7 Average number of expanded nodes when varying num, jand k
算法1BCRP($G,T)$ 输入:图$G$, 状态转移表$T$ 输出:图$G$中满足正则表达式的最短路径及其长度 1:获取$T$的开始状态$startState$和终结状态$endState$; 2:创建$item_{s}(s, path.add(s),0$, $T(startState, s.c)$, $startState$)并插入优先级队列$h$; 3: while $h$不为空do 4: 取出$h$的队首元素$item_{i}$; 5: if $item_{i}.nowstate=endState$ then 6: return $item_{i}$; 7: else 8: BCRPGetLinks($G, T, h, item_{i})$; 9: end if 10:end while 
下载: 导出CSV
算法 2 BCRPGetLinks($G, T, h, item_{i})$ 输入:图$G$, 状态转移表$T$, 优先级队列$h$, 待扩展的队首元素$item_{i}$ 1: for $item_{i}.vnode$的所有直接可达连接点$u$ do 2: 创建$item_{k}(u, item_{i}.path.add(u), item_{i}.mindist+w(item_{i}.vnode, u), nowstate, paststate)$; 3: SetItemState($T,u, item_{i},item_{k})$; 4: 将$item_{k}$插入$h$; 5: end for
下载: 导出CSV
算法3 SetItemState($T, linknode, item_{i},item_k$) 输入:状态转移表$T$, 当前点$linknode$, 待扩展的队首元素$item_{i}$, 新的扩展元素$item_{k}$ 1: if $item_{i}.nowstate=arb$ then 2: $item_{k}.paststate \leftarrow item_{i}$.$paststate$; 3: if $T$中存在转移($item_{i}.paststate, linknode.c$) then 4: $item_{k}.nowstate \leftarrow T (item_{i}.paststate, linknode.c)$; 5: else 6: $item_{k}.nowstate \leftarrow arb$; 7: end if 8: else 9: 与上述过程相同, 区别在于根据$item_{i}.nowstate$的转移情况判断; 10:end if
下载: 导出CSV
算法4 ICRP($G,T )$ 输入:图$G$, 状态转移表$T$ 输出:图$G$中满足正则表达式的最短路径及其长度 1:获取$T$的开始状态startState和终结状态endState; 2:将item$_{s}(item_{s}.path.add(s), 0, T(startState, s.c), startState)$插入s.ownheap, 将$s$插入$h$; 3: while $h$不为空do 4: 取出$h$的队首节点node$_{i}$的队首元素item$_{i}$; 5: if item$_{i}$.nowstate=endState then 6: return item$_{i}$; 7: else 8: if node$_{i}$.ownheap不为空then 9: 将node$_{i}$插入$h$; 10: end if 11: ICRPGetLinks($G, T, h, node_{i}$, item$_{i})$; 12:end if 13: end while
下载: 导出CSV
算法5 ICRPGetLinks($G, T, h, node_i, item_i)$ 输入:图$G$, 状态转移表$T$, 全局优先级队列$h$, 当前点node$_{i}$, 待扩展的队首元素item$_{i}$ 1: for node$_{i}$的所有直接可达连接点$u$ do 2: 创建item$_{k}$ (item$_{i}.path.add(u)$, item$_{i}.mindist + w(item_{i}.vnode_{i}, u)$, nowstate, paststate); 3: SetItemState$(T, u, item_{i},item_{k})$; 4: if $u$不在$h$中then 5: 将item$_{k}$插入$u$的ownheap, 将$u$插入$h$; 6: else if在$u$的ownheap中存在一项item$_{j}$使得item$_{j}$.nowstate = item$_{k}$.nowstate then 7: if item$_{j}$和item$_{k}$的nowstate均为arb then 8: if item$_{j}$.paststate =item}$_{k}$.paststatethen 9: 将拥有更短mindist的项保留在$u$的ownheap中; 10: else 11: 将item$_{k}$插入$u$的ownheap; 12: end if 13: else 14: 将拥有更短mindist的项保留在$u$的ownheap中; 15: end if 16: else 17: 将item$_{k}$插入$u$的ownheap; 18: end if 19: end for
下载: 导出CSV
表 1 实验设置
Tab. 1 Settings of experiments
参数 取值范围 默认值 $num$ 5 k, 10 k, 15 k, 20 k 10 k $j$ 2, 3, 4 3 $k$ 1, 2, 3 2
下载: 导出CSV
-
[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. http://www.wenkuxiazai.com/doc/3a69c21dad51f01dc281f1d1.html [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. https://users.wpi.edu/~yli15/courses/DS595CS525Spring17/slides/ST-4-Team5.pptx [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. doi: 10.1007/s00778-006-0038-6 [9] SHARIFZADEH M, SHAHABI C. Additively weighted voronoi diagrams for optimal sequenced route queries[J]. Workshop on Spatio-Temporal Database Management, 2006. doi: 10.1007/s10707-007-0034-z [10] SHARIFZADEH M, SHAHABI C. Processing optimal sequenced route queries using voronoi diagrams[J]. Geoinformatica, 2008, 12(4):411-433. doi: 10.1007/s10707-007-0034-z [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. doi: 10.1109/TKDE.2012.36 [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. doi: 10.14778/2350229 [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. doi: 10.1007/BFb0054371 -
点击查看大图
图(7) / 表(6)
计量
- 文章访问数: 190
- HTML全文浏览量: 87
- PDF下载量: 470
- 被引次数: 0