حل مسایل کوتاه ترین مسیر گردشگری مقید با استفاده از الگوریتم ژنتیک

دراین پژوهش قصد بررسی ارایه روشی کارا جهت حل مسایل کوتاه ترین مسیر گردشگری مقید با استفاده از الگوریتم ژنتیک را داریم. این مسایل شامل مسایل کوتاه ترین مسیر بین یک مبدا یک مقصد در یک گراف جهت دار است، به طوری که یک سری شرایط برقرار گردد. در واقع علاوه بر محدودیت های اعمال شده به مسیله اصلی می خواهیم که مسیر مورد جستجو از دنباله ای از گره هایی که به ترتیب ثابت مشخص شده اند عبور کند ضمن اینکه این مسیر نباید از هیچ یال تکراری عبور کند. با توجه به اینکه مسیله اشاره شده یک مسیله NP-کامل می باشد الگوریتم فراابتکاری ژنتیک برای محاسبه جواب های نزدیک بهینه انتخاب شده است. این الگوریتم برروی سه نوع گراف کامل، شبکه ای تصادفی در نظر گرفته شده است. ارزیابی روش با در نظرگرفتن دو معیار عملکرد زمانی (سرعت) وکیفیت جواب انجام گرفته است. درنهایت نتایج به دست آمده با نتایج حاصل از بکارگیری الگوریتم تطبیقی تصادفی حریصانه (GRASP) که تاکنون تنها الگوریتم بکارگرفته شده برای حل این نوع مسایل می باشند مقایسه شده تا کارایی عملکرد روش پیشنهادی مشخص گردد.

Keywords:

مسایل کوتاه ترین مسیر , مسایل جریان شبکه ای , الگوریتم فراابتکاری ژنتیک