The Management System Of Business Services Based On LBS And The Research Of Shortest Path Algorithm

With the popularity of computer science and the development of geographic information, GIS are increasingly extensive and in-depth application because of their powerful features. Network of GIS analysis problem is hot and difficult, and the shortest path is the most basic and pivotal item in the analysis of GIS network in which it is with a direct application. People are never interrupted in the study of algorithms on the shortest path issue. With continuously improvement of computer data structure and algorithm it makes the effective integration of the new shortest path algorithm emerging continuously. Dijkstra algorithm is the theoretical basis to resolve the shortest path issue in the majority systems. Dijkstra algorithm has the advantage of the simple design process and high universality. In this paper, the purpose of the study is the combination realization of two above.Motion Location Service is also called Location Based Service (LBS) . It uses the network of telecom mobile operators (like GSM,CDMA) to access the location information of the motion end-user. With the help of Electronic mapping platform, it provides the services of value-added business. Now in China, there are only several companies who can provide LBS with modern communications technology,computer technology,control technology,location technology,gis technology and etc. They can achieve real-time tracking, location, navigation and etc.; and provide users more traveling information to meet the rapid development of modern city traffic.This article is based on the LBS platform for mobile location-based services provide users with a variety of location-based services information, as well as the study to shortest path algorithm. Purpose of the research is to meet the demand of the mobile company -added services for mobile positioning and of the problem of growing demand for GPS navigation services.This article is included two parts. The first part is the management of business services. First of all, it is the introduction to the web portal for mobile positioning technology- WebGIS and the study to key technologies., has given several options for the implementation of programs. The overall system is based on the J2EE platform, and based on distributed storage server architecture, which provides the user a safe, stable, fast location of services.Secondly, the location-based services is classified on the type of business and refinement for the actual demand, the LBS services is classified according to the application characteristics, the request business side, the access to the LBS business that based on the analysis of existing business. For various users with their own different types of services required for business. Personal information of the user with the security measures in the system when user identification, distinguish different user to denial of service authority according to illegal use of service function effectively, and protected the legitimate rights and interests of users.The second part of the thesis is the study of the shortest path. First, it is the analysis of some algorithm about the study of shortest path, and compared with Floyd algorithm, Dijkstra algorithm, heuristic algorithms, two-way search algorithms. Because of the amount of data in the face of big time algorithm, time complexity of Floyd algorithm is O (n3), it does not fit the positioning system that the algorithm requirements in the response time. The heuristic which is difficult to find the optimal path from the overall, and the two-way search algorithm which would allow the two met become complex and expensive. After analyzes of several shortest path algorithms, the system chose the Dijkstra algorithm as the based algorithm.Although the use of Dijkstra algorithm will be the optimal solution, but because it includes a lot of computing nodes, the efficiency is lower. For improving the computation speed of the system to optimize, that to make it adapted to digital maps Web GIS better which has the characteristics of a large quantity computing. When we completely use the Dijkstra algorithm, there are a lot of useless calculation, there has been a lot of the infinite value. The same as the Dijkstra algorithm and optimize Dijkstra algorithm of the process, and that will be omitted the infinite value for the calculation, so this will greatly reduces the space complexity of algorithm to improve the computational efficiency.Through the optimization of the algorithm can improve the speed of algorithm for computing in some extent. But when face to the actual city road, substantial amount of data computing time is still not high. On the basis of that, this paper use the hierarchical search algorithm, which can reduce the layer that is not concerned, and the targeted analysis of relevant layers will reduce the system response time. As well as using the regional restriction can reduce the search area in order to reduce computation algorithm and improve response time. The best path selection algorithm of users to travel, according to the different needs of users on the road re-assigns the right value.In this thesis, we analyzed and compared the restricted area of the oval, the rectangular, the fan, and the combination of round and rectangular,. And they all have their own advantages and disadvantages. For example, the oval restricted area can get the shortest path under normal circumstances, but when the starting point is far away from the end point, the efficiency is sometimes even worse than the whole region search algorithm without restrictions. In the rectangular and fan restricted area, the starting point and end point is the corresponding vertex of the region, and the shortest path in the actual traffic may be reverse from the starting point, in which situation the searched shortest path is not the real shortest path. In the combination of round and rectangular restricted area, the issue of reverse has been taken into account, but the consideration about the ring roads is not enough.Through the general analysis and comparison of the existing algorithms with various restricted area, we propose the restrictions search algorithm on the use of diamond-shaped region to amend and optimize restrictions Dijkstra algorithm to improve response time and to reduce the computing organizing time. Although this method is more than combination of round and rectangular or rectangular area alone in the search area limits, but is less than the oval. And it considers of the road environment in the real existence of the reverse, loop and so on. As a whole it is relatively better than the other regions of the search algorithm.Finally, this article draw the shortest path algorithm of the system model above the serval algorithm as follows: after optimized Dijkstra algorithm for the based algorithm, as its foundation on the use of user optimal travel path selection algorithm, hierarchical path search algorithm, as well as diamond regional restrictions search algorithm. The system enabled the maximum extent possible to meet the needs of users, and on implementation at mapxtreme there is a full advantage of the existing library to the application in the positioning system.