A Shortest Network Distance Recommendation System In Mobile Terminal Based On GPS Trajectory

Urban roads will be badly damaged by natural disasters, such as earthquake or tsunami. At this case, existing electronic maps are invalid. Under these circumstances, it is of great value to recommend a shortest path to rescue sites by historical GPS trajectories.Existing shortest path algorithms between two positions are often computed by existing electronic maps and the Euclidean distance formula. However, the Euclidean distance cannot reflect the actual network topology, so the accuracy is low.In this paper, a novel shortest path algorithm is put forward under the condition of without electronic maps. Furthermore, a shortest network distance recommendation system based on GPS trajectories is devised and implemented in mobile terminal. Firstly, the road-network topology is automatically constructed in terms of historical GPS data. Secondly, the R-D shortest network-distance algorithm under the condition of without electronic maps is devised after analyzing existing shortest path algorithms. Last but not least, the shortest network-distance recommendation system prototype is explored based on Android. The main contents are as follows:(1)Under the condition of without electronic map, the R-D shortest network distance algorithm is researched. First of all, from a collection of GPS data that contains spatial temporal information automatically extracting road network topology, providing timely and accurate mapping services for the rescue work. Then combine the R-tree and the Dijkstra's algorithm, using the road topology data and other related data, achieved the shortest network distance recommendation. The experiment result shows that compared with the Dijkstra's algorithm, the method proposed in this paper can effectively reduce the calculation process amount of data processing, and reduce the redundancy. At the same time, the shortest path recommended by the R-D shortest network distance algorithm is accurate and reliable.(2) An Android system is explored to recommend the shortest network distance. The system includes three functional modules, routes recommended, POI recommended and map service. In the routes recommendation module, the R-D shortest network distance algorithm is implemented, and is used to calculate the shortest network distance between two points. The POI recommendation module provides POI information query and recommendation. The map service provides the map display and query functions.