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

Constrained route planning based on the regular expression

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

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.