Document Type : Research Paper

Authors

• Hamid Ebadi ¹
• Ruzbeh Shad ²

¹ Faculty of Geodesy and Geomatics

² K.N. Toosi University of Technology

Abstract

With increasing development of GIS, the analysis functions applicable by it have also been significantly expanded, including network analysis. Finding the shortest path is among the important network analyses that is considered as one of the important applications in transportation issues. Considering the many applications of routing analysis, the variation in the type and volume of input information and various parameters affecting the efficiency of a routing algorithm in a geographic information system, various solutions have been proposed to solve the routing problem, including the Dijkstra and Genetic Algorithms.
Dijkstra's algorithm is one of the most famous methods for finding the shortest route that can be used to find the shortest path in a given network using matrix computations. However, in instant applications, due to large volume of input information, complex constraints and the need for fast performance, this algorithm will lose its effectiveness. As computational volume increases in the network matrix, its time complexity increases as well. Genetic algorithm can be used to solve this problem. Genetic algorithm is an optimization technique that can reduce the amount of computations and number of comparisons by minimizing the search range.
In this paper, with a brief overview of the Theory of Graphs, the operation of Dijkstra and genetics routing algorithms are reviewed and results of several practical works are presented. Finally, by comparing and verifying the results, the strengths and weaknesses of each of them will be determined.

20.1001.1.25883860.1383.13.49.10.2