Research Article
Constrained Route Planning Based on the Regular Expression
@INPROCEEDINGS{10.1007/978-3-030-00916-8_10, author={Jing Wang and Huiping Liu and Zhao Zhang}, title={Constrained Route Planning Based on the Regular Expression}, proceedings={Collaborative Computing: Networking, Applications and Worksharing. 13th International Conference, CollaborateCom 2017, Edinburgh, UK, December 11--13, 2017, Proceedings}, proceedings_a={COLLABORATECOM}, year={2018}, month={10}, keywords={Constrained route planning The regular expression The shortest path Dijkstra’s algorithm A* search algorithm}, doi={10.1007/978-3-030-00916-8_10} }- Jing Wang
Huiping Liu
Zhao Zhang
Year: 2018
Constrained Route Planning Based on the Regular Expression
COLLABORATECOM
Springer
DOI: 10.1007/978-3-030-00916-8_10
Abstract
Traditional route planning algorithms, which mainly focus on common metrics to find the optimal route from source to destination, are not enough to solve route planning requirements with location constraints like sequence, alternative and avoidance. For example, finding the shortest path passing the whole or a part of user-defined locations or location categories in order or disorder, or not passing some specified locations or categories. Mainly focusing on these scenarios, this paper formalizes the constrained route planning problem based on the regular expression generated by user requirements and gives a general framework for the exact solution. By using different shortest path algorithms, we show how the framework works efficiently with shortest path algorithms. Finally, extensive experiments on real road network datasets demonstrate the efficiency of our proposal.