华东师范大学学报（自然科学版）Issue(5)：162-173,235,13.DOI:10.3969/j.issn.1000-5641.2017.05.015
基于正则表达式的限制性路径规划
Constrained route planning based on the regular expression
摘要
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分类
信息技术与安全科学引用本文复制引用
王婧,刘辉平,金澈清..基于正则表达式的限制性路径规划[J].华东师范大学学报（自然科学版）,2017,(5):162-173,235,13.基金项目
国家重点研发计划重点专项(973) (2016YFB1000905) （973）
国家自然科学基金(61370101,61532021,U1501252,U1401256,61402180) （61370101,61532021,U1501252,U1401256,61402180）
