Multi-source Shortest Path Algorithm With Rendezvous

With the rapid development of urban logistics business,logistics distribution business puts forward higher requirements for path planning algorithm.The shortest distance query of multi-source shortest path is a basic and common problem in the road network,and it plays a basic supporting role in determining the location of assembly point and transportation route planning and calculation.This paper considers to shorten the total transportation distance and save the transportation cost by aggregating the transportation goods from multiple source points to the assembly point,and then distributing them uniformly from the assembly point,and proves that the problem is NP hard.In this problem,the location of the assembly point is unknown.This paper needs to calculate the shortest path while determining the location of the assembly point.The two objectives of determining the location of the assembly point and calculating the shortest path are constrained by each other as conditions.This paper mainly proposes branch-and-bound method,basic dynamic programming algorithm and advanced dynamic programming algorithm to solve the problem.First of all,assuming that the location of the assembly points are known,this paper transforms this problem into a search problem.After the location of the assembly points are determined,this paper applies the greedy algorithm to calculate the shortest distance from the source points to the assembly points which are set.By brute force enumerating the locations of all possible assembly points and calculating their corresponding shortest distance,this paper can finally determine the optimal set of assembly points.In order to reduce the search space of enumeration,this paper proposes a branch and bound method based on search tree on distance graph.By pruning,the impossible assembly points are excluded in advance,and the location of the most likely optimal set nodes is determined one by one.However,the combination of assembly points on the whole map is exponential,and the amount of calculation after pruning still can not give a solution in an acceptable time.Therefore,by observing the properties of the solution itself,this paper proposes two other algorithms.Secondly,by analyzing the tree structure of the path,this paper transforms the search problem into an optimization problem.By analyzing the structure of the path on the distance graph,the paths have the property of tree.That is,the problem can be decomposed into smaller independent sub-problems,and the sub-problems have optimal sub-structure.After solving the sub-problems one by one,the solution of the problem can be obtained by merging the sub-problems.By defining the state and state transition equation of sub-trees,this paper proposes a basic dynamic programming algorithm to calculate the distance and sum of all sub-trees.Experiments show that the algorithm is 1000 times faster than the branch-and-bound method.However,the distance graph ignores the local information of the graph itself.All nodes in graph are constrained by its neighbors.Thirdly,considering the local constraints of the graph,this paper proposes the advanced dynamic programming algorithm.Compared with the basic dynamic programming algorithm,this algorithm introduces a new dimension,and considers the neighbor information of each vertex more finely,so that the algorithm reduces unnecessary out-of-range neighbor search and increases approximately linearly with the size of the graph.Through comparative experiments,this paper proves the superiority of the proposed advanced dynamic programming algorithm over basic dynamic programming and branch-and-bound algorithm,and the algorithm has a good performance on the map of real world cities.