روش‌های ابتکاری

 روش‌های ابتکاری با انجام جستجو نسبی و محدود در فضای جواب، جوابی با کیفیت خوب و در زمان حلی متوسط پیدا می‌نمایند. این الگوریتم‌ها در مسائل عملی بسیاری مورد استفاده قرار می‌گیرند. الگوریتم‌های ابتکاری برای حل مسائل به سه دسته کلی تقسیم می‌شوند:

1. الگوریتم‌های ابتکاری سازنده : این الگوریتم‌ها از قدیمی‌ترین این روش‌ها به شمار می‌روند. در قدم اول توجهی به هزینه جواب تولید نشده ندارند و به صورت تدریجی جواب موجه را ایجاد می‌کنند.

الگوریتم صرفه‌جویی مطرح شده توسط کلارک و رایت در سال 1964 یکی از الگوریتم‌های مشهور در زمینه VRPکه بر پایه مفهوم صرفه‌جویی عمل می‌کند. این الگوریتم به طور طبیعی در مسائلی کاربرد دارد که تعداد وسایل نقلیه در آنها متغیر بوده و برای هر دو نوع مسائل جهت‌دار و غیر‌جهت‌دار استفاده می‌شود (قصیری،2007).

2. الگوریتم‌های ابتکاری دومرحله‌ای :این الگوریتم‌ها خود به دو فاز مهم تقسیم می‌گردند:
3. اول دسته‌بندی رئوس، سپس مسیریابی
4. اول مسیریابی و سپس دسته‌بندی

در نوع اول ابتدا با رئوس (مشتریان) به دسته‌ ها یا گروه‌های موجه تقسیم می‌گردند سپس با تخصیص یک وسیله نقلیه به هر گروه مسیر بهینه برای آن ایجاد می‌کنیم. ژیلت و میلر در سال 1974 برای اولین بار این روش را ارئه نمودند. که به الگوریتم پیمایش نامیده می‌شود. منطق این الگوریتم بر پایه دسته‌بندی رئوس به گروه‌های موجه می‌باشد که توسط دوران یکنواخت یک شعاع چرخشی به مرکز دپو صورت می‌گیرد. سپس در هر دسته با حل یک مسأله TSP، مسیرهای وسایل نقلیه معین می‌گردند. روش بعدی در این فاز روشی است که توسط فیشر و جایکومار در سال 1981 ارائه شده است. در الگوریتم آنها به جای استفاده از روش‌های هندسی برای گروه‌بندی رئوس، از روش تخصیص یافته(GAP) استفاده می‌نمایند. روش تخصیص بدنبال کمینه کردن هزینه تخصیص هر مورد به دسته است. سپس هر دسته را می‌توان توسط روش ابتکاری یا دقیق حل نمود. در نوع دوم ابتدا یک تور بزرگ برای تمامی رئوس تعیین می‌گردد (مانند تور TSP ) سپس این تور به بخش‌های کوچکتر و موجهی تجزیه می‌شود که هر کدام به منزله یک مسیر برای یک وسیله نقلیه می‌باشد(قصیری،2007).

3. روش‌های بهبود : این روش‌ها در تلاش هستند تا جواب بهینه یافت شده را بهبود و ارتقا بخشند که این کار توسط تبادل پی در پی رئوس یا کناره‌ها در یک مسیر و یا بین دو مسیر وسیله به طور همزمان می‌گیرد.

بیشتر روش‌های بهبود برای مسأله TSP توسط لین در سال 1965 تحت عنوان مکانیزم  مطرح گردیده است. در این روش  کناره از تور حذف شده و سپس مجددا این  بخش را در تمامی حالت‌های ممکن به هم متصل می‌نماییم (قصیری،2007).

Generalized Assignment Problem