Survey on Certain and Heuristic Route Finding Algorithms in GIS

Traffic condition is one of the most important issues in urban transportation system of large cities, because it affects other important areas directly and indirectly. For example, water and air pollution as an environmental issue and physical or mental health of citizens as a health issue. Suggesting best routes based on different criteria such as traffic condition is one of the ways to reduce urban traffic, implicitly. In GIS, best routes can be suggested to users based on different algorithms that have been developed so far, to move in urban road network, and consider different costs, travel time, traffic, distance and other factors. Aim of this paper is reviewing route finding algorithms in GIS. For this purpose, algorithms are investigated in two categories, deterministic and heuristic algorithms. Advanced route finding problems which are closer to the real world problems are also described. Finally, a comparison between algorithms are done based on different parameters so that researchers can find the best suited algorithm based on their requirement.