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

• 作者: 刘辉平 王婧 金澈清
• 来源期刊: 华东师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 限制性路径规划 正则表达式 最短路径
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 位置服务
• 页码范围: 162-173,235
• 页数: 13页
• 分类号: TP391
• 字数: 8012字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5641.2017.05.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	金澈清	华东师范大学计算机科学与软件工程学院	39	1646	13.0	39.0
2	刘辉平	华东师范大学计算机科学与软件工程学院	5	28	2.0	5.0
3	王婧	华东师范大学计算机科学与软件工程学院	5	9	2.0	3.0