Research And Implementation Of Multi Site High Efficiency Navigation Algorithm

In recent years,with rapid development of the Internet technology,especially the popularity of the O2 O,the logistics industry is booming.Courier are facing with two problems: the first problem is that it's difficult for couriers to plan the path when path contains a large number of nodes.Common sense and experience can no longer help them to find a good sulotion,so they usually have no choice but to take a bad path.It not only reduce the efficiency,but also increase the energy consumption.The second problem is that couriers are facing more real-time requests than ever,many O2 O services request timely response,path planing must be finished in a short time,otherwise it will reduce the efficiency of service.This thesis combines the TSP algorithm with the online electronic map to plan the optimal path and visualize the result.In order to solve the problems above,this thesis puts forward the multi-site high efficiency navigation algorithm and multi-site high efficiency navigation system.The algorithm consists of two parts:planning algorithm and navigation algorithm.The planning algorithm is based on K-OPT algorithm.It firstly analyzes the advantages and disadvantages of several kinds of path generation algorithm and selects the most appropriate algorithm.Secondly,it discusses about the parameter K.Through the actual test,this thesis compares the quality of solution and time cost of each situation and finally shows that when K=4,the algorithm has highest performance-cost ratio.Finally,this thesis propose a measure to reduce the running time of generating the distance matrix.And the experiment shows that the improvement is effective.For the navigation algorithm,this thesis puts forward a A* algorithm which considers the real-time traffic conditions.By modifying the evaluation function,the algorithm can search the path which avoids congestion sections.Based on the above algorithm,we designed the multi-site high efficiency navigation system.The system uses MVC architecture,combined with BaiDuMap API,provides users path plan service and visual navigation service.Then the thesis introduces the detail implementation of basic module,planning module,additional functional module and the analysis module.Finally,this thesis tests the system and algorithm by real-life data,it verifies the reliability of system and the good performance of algorithm.