Optimum Path Finding Based on Time Criterion under Traffic Variation

Facilitation of transportation is one of the most important applications of Geographic Information System (GIS). In this area the network capabilities of GIS such as shortest path computation,could be very useful. Different criteria have ever considered for shortest path analysis in GIS such as: Distance, travel time, path comfort, path beauty. Travel time criterion has some random continues variations, due to its relation to traffic. Therefore, path finding based on these criterions by current algorithms such as Dijkstra is not suitable. In this field a development of algorithms that can be used on dynamic networks is necessary. In this paper we have developed an algorithm for this purpose that used statistical information of travel time in previous days for prediction of travel time in future. Also for modeling of the randomness of traffic, we have used a risk parameter for each edge in network. We have used the model of space-time partitioning for consideration of observed travel time, predicted travel time and risk parameters together. Finally for testing the developed algorithm, a case study has been explained in this paper. The implemented case study showed the usefulness of represented method in finding shortest path beside current static methods where the total travel time between two points in tested network was reduced from 35.71 minutes by static methods to 29.43 minutes. Certainly, the usefulness of our represented method could be more apparent by increased distance between origin and destination in the network.