Research On Constrained Route Planning

As a basic and hotspot issue of location based services,intelligent transportation,GIS and spatio-temporal data management,route planning plays a vital role in people's lives as it is widely applied to GPS navigation,logistics delivery,unmanned aerial vehicle(uav)flight,communication etc.Because route planning requirements tend to be diverse,tra-ditional route planning,which mainly focuses on common metrics such as distance,time,cost,etc.to find the optimal route from source to destination,is not enough to solve route planning requirements with location and category constraints like sequence,alternative,avoidance,as well as the demand of personalized preference for the satisfaction of locations.Expressing such rich route planning requirements completely and accurately,as well as providing reasonable solutions,have become great challenges for route planning.Mainly focusing on these problems,we introduce regular expressions to design the constrained route query and propose CSRP,the Constrained Shortest Route Planning,and SCSRP,the Satisfaction based Constrained Shortest Route Planning problems as well as their solutions.Extensive experiments on real road network datasets demonstrate the efficiency of our proposal.The main contributions of this paper can be summarized as follows:· Constrained Route Queries Based on the Regular Expression By using regular expressions,we design the constrained route query which can not only express location constrained route planning requirements completely and accurately,but also assist in solving the problem efficiently.· Constrained Shortest Route Planning The constrained shortest route planning CSRP problem is proposed to find the shortest path from the source to the destination in the graph,which satisfies the constrained route query.By designing the state transition rules and constraints-based pruning rules while combining regular expres-sions,finite automata theory and shortest path algorithms,two solutions based on Dijkstra's algorithm and A*search algorithm respectively are proposed to solve the CSRP problem.Experiments on real road network datasets verify the effectiveness of these algorithms.· Satisfaction Based Constrained Shortest Route Planning For more personalized route planning,taking into account user preference for the satisfaction of locations,we extend the constrained shortest route planning problem to satisfaction-based constrained shortest route planning problem SCSRP,whose result is the shortest path both satisfying the constrained route query and the satisfaction threshold.By defin-ing the dominate relationship of constrained routes and satisfaction-based pruning rules,the SCSRP algorithm is proposed and then implemented by Dijkstra's algorithm and A*search algorithm.Finally,performance evaluation experiments carried out on the real road network datasets prove the effectiveness of algorithms.