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

Abstract

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