| As the information technology is developing rapidly, the navigation softwares play a very important role in people’s daily trip, such as the Baidu map, AMAP, Sogou maps, Navigation dogs,Google Map, Tencent SOSO maps, Careland Navigation and so on. Nevertheless, all of them only give the suggestive route between two points, without taking the needs of multiple destinations into consideration, therefore, this thesis proposes an multiple places navigation algorithm.With this algorithm,the minimum time length path of total travel among multiple places can be reached.In addition, the application of the algorithm is also given on the basis of Baidu Maps API.Currently, the APP is developed mainly in three manners: the Android application development based on Java, the IOS application development based on Object C, and the Web App development based on Ionic framework and HTML/CSS/JavaScript. Compared to the previous two methods,there are two advantages in Web App development: cross-platform characteristics and low burden in coding. Therefore, this thesis adopts Web App to develop the source programming, and then compile it into the application through the Android SDK.Among all the shortest path algorithms, the most widely used is dijkstra algorithm. But its application is only limited to navigating between two points,and it can’t solve multi-destination navigation problems.As a result, this paper proposes to combine ant colony algorithm and dijkstra algorithm to obtain the minimum time length path of the total travel. Firstly, it is needed to obtain the predicted time of each path by calling Baidu map interface. Secondly,the shortest time paths between each two places can be achieved by applying dijkstra algorithm. Finally, the minimum time length path covering all points can be reached by using ant colony algorithm. Besides, the thesis also makes an improvement based on the analysis of the traditional ant colony algorithm on two sides:the pheromone update and the next city selection. |
PDF Full Text Request