Intelligence Routing Plan using K-d tree and Smart-A* with Google Map Data

Abstract

Road traffic congestion or jam is main problem in urban area of both developing and developed countries. In order to solve this problem, traffic congestion states of road networks are estimated so that congested road can be avoided and set the best optimal route. In this system, the real time traffic congestion states of users` desired between source and destination are estimated and presented the results in Google Map. GPS data from mobile phones on vehicles are used to get the real time data while using the system. The historical traffic condition data of each road network on each time using the collected data are utilized in this research. In this paper the system is to analyze and avoid traffic congestions and get optimal route with modified A* algorithm, also called Smart-A*. This includes the run-time traffic data from GPS enabled mobile and historical data in the database. In the system firstly, we take the GPS data (current location) and searching area and extracting geo-data between source and destination points of user by K-d tree. Second, search the traffic congestion data in that area by Google Traffic layer. Finally, calculate optimal route by Smart-A* and then show the result that best optimal route to the user.