(۳-۱۸)

(۳-۱۹)

محدودیت­های (۳-۱۶) تا (۳-۱۹) نیز دامنه متغیرهای مساله را تعریف می­ کنند. محدودیت­های دیگر:

(L)

(۳-۲۰)

s.t

(۳-۲۱)

(۳-۲۲)

(۳-۲۳)

مدل سطح پایین Lمساله تخصیص سفر بر اساس رویه تعادل کاربر قطعی است که جریان­های تعادلی در کمان­ها x_ij را برای هر ترکیب معین از متغیرهای سطح بالا محاسبه می­ کند. توضیحات لازم در رابطه با مدل ریاضی و ویژگی­های آن در پیوست (الف) آمده­اند.

روش‏ حل توسعه داده شده

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

کلیات الگوریتم ژنتیک

از سال ۱۹۶۰ تقلید از موجودات زنده برای استفاده در الگوریتم­های قدرتمند درحل مسایل بهینه سازی مورد توجه قرار گرفتند، که ” تکنیک­های محاسبه­ی تکاملی” نام گرفتند. الگوریتم ژنتیک اولین بار توسط جان هالند]۴۶[ و همکاران در دانشگاه میشیگان مطرح شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم­های طبیعی توجه کردند و برای مدل­سازی آن در سیستم­های مصنوعی، که باید دارای توانایی­های سیستم طبیعی باشند، تلاش کردند. نتیجه تلاش آنها پیدایش الگوریتم ژنتیک بود.

مزایای الگوریتم ژنتیک

می توان قابلیت های روش ژنتیک را نتیجه­ امتیازات ویژه این روش دانست. برخی از این امتیازات به صورت زیر هستند.

• جستجوی چند جانبه و کار همزمان بر روی جمعیتی از متغیرها. الگوریتم ژنتیک در یک جمعیت از جواب ها و با مجموعه ­ای از آن­ها شروع به جستجو می­ کند، نه با یک جواب واحد. بدین ترتیب، به جای یافتن نقطه­ی مناسب، محدوده­های مناسب در فضای متغیر­ها شناسایی می شوند.

• استفاده از مقدار تابع هدف برای جستجو. بنابراین، نیازی به اطلاعات جانبی دیگر مانند مشتق تابع ندارد. به همین دلیل، به راحتی می­توان از این روش در بهینه سازی توابع ناپیوسته یا دارای تغییرات ناگهانی و چندین نقطه بهینه­ موضعی استفاده کرد.

• کلی بودن الگوریتم و مستقل بودن اجزای آن. الگوریتم ژنتیک به خاطر طبیعت تکاملی، جواب ها را بدون توجه به طرز کار ویژه­ی مساله جستجو می­ کند و می­توان با هر نوع تابع هدف و محدودیت (خطی و غیر خطی) در هر فضای جستجو (گسسته، پیوسته یا مرکب) به کار گرفت. به عبارت دیگر، این الگوریتم انعطاف پذیری بالایی دارد.

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