Research And Implementation Of Route Planning Algorithm For Multiple Requests

In the urban road network,there are many points of interest.These points Of Interest(POI)can provide residents with one or more different types of services,such as a large shopping mall with fruit store,drug store,convenience store,eyeglasses store,KFC store and so on.A gas station not only provides refueling service,but also has convenience stores and KFC stores.Given a starting point,end point,and a list of service requests,the multi-request Route Planning(MRRP)problem is to find a path that satisfies all the requests in the list and minimizes the cost of the path(distance cost,travel time cost,or cost).For example,on the way home from work after work,the user wants to buy gas,dinner at KFC and buy glasses.The MRRP Problem can be reduced to the classic Traveling Salesman Problem(TSP).Since TSP is a NP-hard problem,the exact solution of MRRP problem cannot be found in polynomial time.The existing method to solve the MRRP problem needs to call A*algorithm to calculate the shortest path from a large number of current nodes to the end point,which is inefficient and unable to handle large-scale road network.In addition,when expanding the subnet,the algorithm simply takes the number of satisfying services as the basis for selection,without considering whether these services are difficult to satisfy(corresponding POI distribution is sparse),and the overall cost of the path selected is relatively high.Based on the above observation,we propose a new framework to solve the MRRP problem,which takes the overall distribution of the POIs who provide the required services into account.Furthermore,we design two algorithms GOD and SPGOD using the framework with the help of a grid index.They can identify the POIs that will definitely be visited earlier,and guide the expansion towards such POIs which can further improve the effectiveness and efficiency.On the basis of SPGOD algorithm,we propose a method based on detour distance and shortest path.After determining the POIs that must pass through,this method gives priority to the nodes that provide services on the shortest path between them,and then queries the nodes nearest to the shortest path that provide the remaining services based on the detour distance algorithm.Because this method gives priority to the shortest path,the path cost of this method is greatly reduced.This paper designs and implements a multi-request path planning system based on three proposed algorithms,and in different real road networks,we verify the proposed algorithms.The experimental results show that under different parameters,the query efficiency of the proposed SPGOD algorithm is 4-7 times higher than that of the existing algorithm.The cost of SPDD algorithm is 1-2 times shorter than that of existing algorithms.The parking times of the GOD algorithm are reduced by 2-3 times compared with the existing algorithm.