مسیریابی بهینه در شبکه ی حمل و نقل درون شهری با ادغام الگوریتم های فرا ابتکاری ژنتیک (GA) و جستجوی ممنوع (TS)

با توجه به گسترش شهرها و پیچیده تر شدن شبکه ی راه های درون شهری به ویژه در شهرهای بزرگ، مسئله ی مسیریابی و در واقع یافتن کوتاه ترین مسیر تبدیل به یکی از دغدغه های افراد در هنگام تصمیم گیری برای انتخاب مسیر در جابجایی از مبدا حرکت به یک مقصد مشخص، شده است. روشی که در این پژوهش برای حل مسئله ی کوتاه ترین مسیر پیشنهاد می شود، استفاده از ترکیب الگوریتم های فراابتکاری ژنتیک (GA) و جستجوی ممنوع (TS) می باشد. بدین منظور پس از اعمال یک سری پیش پردازش هندسی بر روی شبکه ی مورد نظر برای سرعت بخشیدن به روند جستجوی الگوریتم از یک محدوده ی جستجو حول نود مبدا و مقصد استفاده می شود. در الگوریتم پیشنهادی، تابع هزینه به صورت یک عدد مختلط تعریف می شود که قسمت حقیقی آن نشان دهنده ی مجموع وزن یال های واقعی و قسمت موهومی آن نشان دهنده ی تعداد یال های مجازی و در واقع تعداد عدم اتصالات بین نود ها در کروموزوم های الگوریتم ژنتیک می باشد.  همچنین در بحث اعمال جهش بر روی کروموزوم های الگوریتم ژنتیک، از الگوریتم جستجوی ممنوع استفاده می گردد. علت پیشنهاد این روش، جدید بودن و نیز زمان بر بودن روش های قطعی مثل الگوریتم دایجسترا و نیز جواب نامناسب الگوریتم ژنتیک خالص(غیر ترکیبی) از لحاظ وزن نهایی مسیر در حل مسئله ی مسیریابی در شبکه های واقعی بخصوص شبکه های بزرگ می باشد. به منظور ارزیابی کارایی الگوریتم پیشنهادی، الگوریتم بر روی یک شبکه ی واقعی جهت دار شامل 739 نود و 1160 یال که بخشی از شبکه ی راه های شهر تهران می باشد، پیاده سازی شد. نتایج نشان می دهد که در الگوریتم پیشنهادی، طول مسیر تا حد ممکن به جواب حاصل از الگوریتم قطعی دایجسترا نزدیک است. این الگوریتم طول نهایی مسیر را 5 درصد بیشتر پیش بینی می کند. اما از لحاظ سرعت اجرا به طور متوسط 12/5 برابر نسبت به الگوریتم دایجسترا سریع تر است. در مقایسه با الگوریتم ژنتیک خالص نیز الگوریتم پیشنهادی از نظر طول مسیر به طور متوسط 9 درصد کوتاه تر می باشد و از نظر زمان اجرا سرعت الگوریتم پیشنهادی با الگوریتم ژنتیک خالص تقریبا برابر است. همچنین به لحاظ قابلیت تکرارپذیری نیز الگوریتم پیشنهادی 36/25 درصد، تکرارپذیری را نشان می دهد.