Use of GPS to provide real-time road traffic information and routing based on Dijkstra's and Yen's algorithms

A dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Mobile Telecommunications and Innovation.Traffic experienced in many parts of the world leads to a reduced productivity and a lot of time wasted. In Nairobi the tools available for providing accurate, real-time traffic information are limited. The major sources of information are reports from radio stations and a few camera views from some companies. These offer fragmentary and intermittent information, without useful features such as Travel Time Estimation and Optimal Route Selection. This research experiments on the use of mobile probes employing GPS and GSM technologies to collect information. It entails the development of an Android-based mobile application, called Tazama, to illustrate the feasibility of GPS positioning techniques to collect and disseminate traffic information in Nairobi. Key aspects of the system include Map-Matching, Travel Time Estimation and Optimal Route Selection. Map-Matching helps identify the specific road segment a GPS is on. Optimal Route Selection helps determine the best route among a number of possibilities given a start and destination point based on real-time traffic conditions. It is based on an implementation of Dijkstra's algorithm and Yen's algorithms. The geo-information for the roads and routes is derived from Google Maps. Based on tests done on a number of roads in Nairobi it was found that the combination of Dijkstra's and Yen's algorithms could give the optimal routes for a given pair of start and destination points. Results for Time Travel Estimation suggested that GPS positioning is a viable source for traffic information. Keywords: Real-Time Traffic Information, Optimal Route Selection, Map-Matching, GPS-Positioning, Dijkstra's Algorithm, Yen's Algorith