Research And Application On The Algorithm Of Optimal Route Navigation Based On LBS

Motion Location Service is called Location Based Service (LBS) too. Ituses the network of telecom mobile operators (like GSM,CDMA) to accessthe location information of the motion end-user. With the help of Electronicmapping platform, it provides the services of value-added business. Now inChina, there are a few companies who provide LBS with moderncommunications technology,computer technology,control technology,location technology,gis technology and etc. They can achieve real-timetracking, location, navigation and etc.; and provide users more travellinginformation to meet the rapid development of modern city traffic.This paper based on LBS is about the route people choose when they areon their trip, the fastest, the least cost, or the most comfortable. In this way,we study on city road optimal path search and navigation. It is intended toprovide the necessary traffic information and point out the optimal route, fortrip. Optimal remote search is the core of the motion location servicesequipment, and it plays a decision-making role in the city traffic.This text can be mainly divided into three parts, they are the analyse ofthe structure and function of the system,the function of road which based onthe decision of users,the optimal remote based on city road net.The system's goal is to realize a platform based on LBS on the J2EEplatform. The platform uses map mapping algorithm, optimal remotealgorithm and provides services for users with location,navigation and theoptimal remote. We used free API to develop the lightweight HTTP serverFGI. And we didn't use too much the third parties API and complex frame. Inorder to enhance the system concurrency and the overload, it removed someredundant functions which in the HTTP servers which this system does notneed. We used Mapinfo Corporation's mapxtreme for java API to process map essential factor, and build the map data to the FGI server, analysis andwithdraws the path node information for the services of twice localizations,optimal remote search,navigation and etc. The picture image's productionuses the phantom pre-production mechanism which likes the service stationsGoogle Map, Baidu Map, Virtual Earth use, with the high speed of mapresponse. The picture retrieval's way selects four fork tree methods, which isfast and convenient. From the view of the overall system, we use the currentframework of the more advanced open source, with mapxtreme for javatechnology, and less use of the other company's products, we developed thelightweight picture servers, map elements server, and high security userserver.This study focused on the Optimal Route search problems, the OptimalRoute search algorithm is the core function of mobile location-based servicesplatform, also offers selected cities Route, and it is an effective way to travel.The Optimal Route choice should be attributed to the transport networkin the shortest path problem. The shortest path problem is a lot of academicresearch hot spots, large number of domestic and foreign scholars havecarried out in-depth research, and made a large number of research results.The shortest path is the algorithm and the value of the path weight. So thecrux of the problem is how the two ruling. In this paper, about the shortestpath algorithm, the author has been selected based on the Dijkstra algorithm,the hierarchical search algorithm and the dynamic regional restrictions searchalgorithm for associate, to reduce the time and space complexity of thealgorithm; with the value of the path weight, the author used method of userdecision-making to determine the road weight.After analyzes of several shortest path algorithms, Floyd,Dijkstra,heuristic algorithms,two-way search algorithms, commonly used innavigation like the hierarchical algorithm, and the restricted area searchalgorithm. After contrast, abandoned Floyd which is not suitable for the calculation of large amounts of data, the heuristic which is difficult to findthe optimal path from the overall, and the two-way search algorithm whichwould allow the two met become complex and expensive, but use Dijkstraalgorithm as the based algorithm. According to the format of mapinfo map,hierarchical search algorithm can reduce the layers we do not care about,targeted analysis of the relevant layers, reduce system response time.Maptreme for java provide a limit search area searching function graphicelement. So here mainly uses the regional rectangular search, on this basis,the establishment of a dynamic regional restrictions search algorithm. WithDijkstra algorithm,hierarchical algorithm and restricted area searchalgorithm, it forms a part of the shortest path algorithm; Another part of thealgorithm, the road weighted value is gained decision-making theory.In many kinds of the shortest path analysis and path navigationmechanism, trip to decision-making based on the optimal path search isthought to be the ideal solution. In the choice of the optimal path it followedthe wishes of users; the system is also suitable for the shortest path algorithmprocessing requirements. This paper analyzes the impact of the decisionmakingtravel many factors, and uses shortest period of time,the shortest,the most comfortable three decision-making. Inside, sections of the shortestperiod of time are the main consideration in the decision-making journeytimes, the method is road section average travel time is road section coursedivided by road section traveling schedule average vehicle speed; the fuel isthe main consideration of road costs, charges of road projects such as fees arenot taken into account; for comfortable and safety guidelines are the mainlyconsideration in the traffic load,road conditions (traffic quality,brokensituation),safty,road level factors. According to the indicators, it gains theweight from dealing with comfortable and safty.Finally, the final algorithm model which adopts this article insynthesizes together has formed a comprehensive system core model: the classical Dijkstra algorithm is the based shortest path algorithm; Hierarchicalsearch algorithms and Dynamic regional restrictions search algorithms on theDijkstra algorithm amendment, to reduce the complexity of time and space;the theory of decision-making to determine the weight of path road, to makethe Optimal Route be consistent with the actual users'travel will. Itssuperiority lays in unified present existence some fine shortest pathalgorithms together, uses in this motion position service system.