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

来源：华东师范大学学报·哲学社会科学版杂志2017年第5期北京时间：

作者：王婧, 刘辉平, 金澈清

单位：王婧,女,硕士研究生,研究方向为基于位置的服务.E-mail:jingwang@stu.ecnu.edu.cn

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

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

基金资助：国家重点研发计划重点专项（973）（2016YFB1000905）；国家自然科学基金（61370101，61532021，U1501252，U1401256，61402180）