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

摘要：

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

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

分类号：TP391(计算技术、计算机技术)

资助基金：国家重点研发计划重点专项9732016YFB1000905;国家自然科学基金61370101,61532021,U1501252,U1401256,61402180

在线出版日期：2017-12-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：162-173,235