ارزیابی آلگوریتم های دایسترا و ژنتیک جهت یافتن کوتاه ترین مسیر در GIS

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشکده مهندسی ژئودزی و ژئوماتیک

2 دانشگاه صنعتی خواجه نصیرالدین طوسی

چکیده

با توسعه روزافزون GIS، توابع تجزیه و تحلیل قابل اجرا توسط آن نیز به طور قابل توجهی گسترش یافته ­اند، که از جمله آنها می­ توان به آنالیز شبکه اشاره نمود. یافتن کوتاه ترین مسیر از آنالیزهای مهم شبکه می باشد که به عنوان یکی از کاربردهای مهم در مسائل حمل و نقل مطرح می­ گردد. با توجه به کاربردهای فراوان آنالیز مسیریابی، تنوع در نوع و حجم اطلاعات ورودی و پارامترهای گوناگون اثرگذار بر کارائی یک الگوریتم مسیریابی در یک سیستم اطلاعات جغرافیایی از سوی محققین راه حل­ های مختلفی برای حل مسئله مسیریابی ارائه شده است که از جمله آنها به الگوریتم دایسترا و ژنتیک می­ توان اشاره نمود.
الگوریتم دایسترا یکی از معروف ترین روش­های یافتن کوتاه ترین مسیر می­ باشد که قادر است در یک شبکه مشخص کوتاه ترین مسیر را با استفاده از محاسبات ماتریسی بیاید. اما در کاربردهای آنی، با توجه به حجم بالای اطلاعات ورودی، قید و شرط ­های پیچیده و نیاز به عملکرد سریع، این الگوریتم کارائی خود را از دست خواهد داد. بدین ترتیب که، با افزایش حجم محاسباتی در ماتریس شبکه، پیچیدگی زمانی آن نیز افزایش می­ یابد. برای رفع این مشکل از الگوریتم ژنتیک می­ توان استفاده نمود. الگوریتم ژنتیک یک تکنیک بهینه ­سازی است که با کوچک نمودن محدوده جستجو قادر است میزان محاسبات و تعداد مقایسه­ ها را کاهش دهد.
در این مقاله با بررسی اجمالی تئوری گراف­ها، نحوه عملکرد الگوریتم ­های مسیریابی دایسترا و ژنتیک مورد بررسی قرار گرفته و نتایج چند کار عملی ارائه می­ گردد. در نهایت با مقایسه و بررسی نتایج، نقاط قوت و ضعف هر یک از آنها مشخص خواهد شد.

عنوان مقاله [English]

Evaluation of Dijkstra and Genetic Algorithms in Order to Find the Shortest Route in GIS

نویسندگان [English]

  • Hamid Ebadi 1
  • Ruzbeh Shad 2
1 Faculty of Geodesy and Geomatics
2 K.N. Toosi University of Technology
چکیده [English]

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.

1- Arounof.S.(1995). Geographic Information System, AManagement persoective, P.P. 189-192.
2- Cherkassky, B.V., Goldberg, A.v., and Radzik, T.(1993) Shortest Paths Algorithms: Theory and Experimental Evaluation. Technical Report. P.P.93-1480.
3- Diaz A.(1996), Optimization IIueristic Algorithms. Madrid, P.P.29-46.
4- Gen M.(1997), Genetic Algorithms and Engineering Design, John Wiley, New York, P.P.5-63.
5- Laurini. R. and Thompson.D.(1992). Fundamentals of Spatial Information System, P.P.546-548.
6- Worboys. M.F.(1995). GIS,A Computing Perspective, P.P.232-238.
7- Zhan.F.Benjamin. (1996). Three Fastest Shortest Path Algorithms, P.P.69-82.
8- مؤسسه فرهنگی هنری دیباگران تهران- نظریه گرافها و کاربردهای آن-1379- چاپ اول.