1- مقدمه

مدیریت زنجیرۀ تأمین[1](SCM) یکی از موضوعات بسیار مهمی است که  از نظر تئوری و از جنبۀ کاربردی سال‌ها مورد توجه پژوهشگران قرار گرفته است (مظاهری و همکاران، 1393). اما موضوع زمان‌بندی زنجیرۀ تأمین از موضوعات نسبتاً جدیدی است که اهم پژوهش‌ها آن مربوط به سال‌های بعد از 2000 میلادی است (راستی برزکی و همکاران، 1392). در سه دهۀ گذشته، پژوهش  زیادی بر مدل‌های یکپارچۀ تولید و توزیع صورت گرفته است و مقالات مروری زیادی نظیر سارمینتو و نقی[2] (1999)، ارنگوس و همکاران[3] (1999)، گوتسچالک و همکاران[4] (2002)، بیلگن و اوخاهان[5] (2004)، چن (2004) درخصوص چنین مدل‌هایی وجود دارد. به‌طور خاص موضوع زمان‌بندی یکپارچۀ تولید و توزیع نیز یکی از موضوعات مهمی است که پس از ارائۀ مقالۀ هال و پاتس[6] (2003) در سال 2003 پژوهش­های زیادی را به خود اختصاص داده است. چن[7] (2010) مطالعۀ مروری مناسبی را در این زمینه ارائه کرده است که بررسی آن  پژوهش، این موضوع را به‌خوبی نشان می‌دهد. تولید و توزیع دو جزء مهم یک زنجیرۀ تأمین را شامل می‌شوند؛ بنابراین هماهنگی برنامه‌ریزی تولید و ارسال، یکی از مسائل مهم زمان‌بندی زنجیرۀ تأمین است. در مسائل کلاسیک زمان‌بندی به هماهنگی با واحد حمل‌ونقل و درنظرگرفتن شرایط ارسال توجهی نشده است و تصمیمات مربوط به زمان‌بندی تولید و برنامه‌ریزی ارسال به‌طور جداگانه انجام می‌شود (راستی برزکی[8] و همکاران، 2013)؛ در حالی که، گرفتن تصمیمات یکپارچۀ تولید و توزیع که نگرش جامع‌تر این موضوع است، کاهش هزینه‌ها و افزایش سودآوری مرتبط با سیستم تولیدی و بهبود سطح سرویس و سطح رضایتمندی مشتری را به‌همراه دارد. یکی از مهم‌ترین شاخص‌ها جهت رضایت مشتری، عملکرد تحویل کالا یا خدمات ارائه‌داده شده است (محمد باقر فخرزاد و همکاران، 1391).

پژوهش و یافته‌های جدید نیز نشان می‌دهد که عملکرد تحویل یکی از مهم‌ترین دغدغه‌های مدیران در زنجیرۀ تأمین است (لاکامی و همکاران[9]، 2004). برآورده‌نشدن تحویل به‌موقع به‌عنوان تأخیر شناخته می شود؛ این مسئله زمانی مطرح می‌شود که تولیدکننده نتواند خدمت یا کالایی را در زمان (یا بازۀ زمانی) توافق‌شده با مشتری ارائه کند (لاکامی و همکاران، 2004). مدل‌های یکپارچۀ زمان‌بندی تولید و توزیع با توجه به هزینه‌های تأخیر و هزینه‌های زیاد لجستیک بسیار مهم هستند. چن و واراکتاراکیس (2005) و پاندور و چن (2005) نشان داده‌اند که در مدل‌هایی که آنها بررسی کرده‌اند، سود هنگفتی در گرفتن تصمیمات یکپارچه می‌تواند وجود داشته باشد. یکپارچگی تولید و توزیع، می‌تواند هزینه‌های کلی سیستم را بسته به هدف زمان‌بندی، 20درصد، 25درصد و حتی بیشتر کاهش دهد (هال و پاتس، 2005). اسلوتنیک و سوبل (2005) اشاره کرده‌اند که هزینه‌های مرتبط با تأخیر در صنعت هوا فضا می‌تواند تا نزدیک یک میلیون دلار در روز برای تأمین‌کنندگان قطعات هواپیماسازی باشد. همچنین بررسی توماس و گریفین (1996) نشان داده است که بیش از 11درصد تولید خالص ملی آمریکا صرف هزینه‌های حمل‌ونقل می‌شود و هزینه‌های لجستیک بیش از 30درصد هزینۀ کالاهای فروخته‌شده را تشکیل می‌دهد. به‌دلیل اهمیت تحویل سفارشات بدون تأخیر برای تولیدکننده، مسأله کمینه‌کردن مجموع وزنی تأخیر کارها یکی از مسائل مهم تئوری و کاربردی است که سال‌ها مورد توجه محققان قرار گرفته و تاکنون پژوهش بسیار زیادی در این زمینه انجام شده است (پاتس و همکاران، 2013). ایمون (1969) برای اولین بار با بررسی مسأله مجموع تأخیر سفارشات، اصول غلبه‌ای را ارائه داد که یکی از شاخص‌ترین توسعه‌ای است که تاکنون ارائه شده است. لاور (1977) و لنسترا و همکارانش (1977) در دو پژوهش مجزا NP-Hard بودن مسئله مجموع تأخیر کارها را از جنبۀ پیچیدگی زمانی نشان دادند. چارژه و بیکر (1978) یک الگوریتم برنامه‌ریزی پویای و پاتس و واسنهوز (1991)  با ارائۀ یک الگوریتم شاخه و کران توانستند اولین الگوریتم‌های دقیق را برای مسئله مجموع تأخیر کارها را ارائه دهند. فرنچ (1990) مسأله کمینه‌کردن مجموع وزنی تأخیر کارها (تعمیم‌یافتۀ مسأله ) را یکی از مشهورترین مسأله بهینه‌سازی ترکیبی در تئوری زمان‌بندی معرفی کرد و از عبارت اختصاری SMTWTP[10] برای بیان مسئله استفاده کرد؛‌ همچنین نمایش اختصاری مسأله گفته‌شده براساس علامت‌گذاری فرنچ به‌صورت  است.

در سال‌های اخیر، به‌روش‌هایی که با الهام از طبیعت به‌عنوان یک ابزار کارا برای بهینه‌سازی مسائل پیچیده بهینه‌سازی ترکیبی استفاده می‌شود توجه زیادی شده است. بعد از سال 1990 به‌دلیل پیچیدگی حل SMTWTP حجم گسترده‌ای از پژوهش  بر الگوریتم‌های فرااِبتکاری فراوانی نظیر الگوریتم تبرید[11] ((ماتسو، 1989)، (پاتس و واسنهوز،1991)، (کراول، 1998))، الگوریتم ژنتیک[12] ((کراول، 1998)، (کلوگوز، 1998))، الگوریتم جستجوی ممنوعه[13] ((کراول، 1998)، (بیلژ، 2007))، الگوریتم بهینه‌سازی مورچگان[14] (باور، 1999)، الگوریتم بهینه‌سازی انبوه ذرات[15] (تاسگترین، 2006)، الگوریتم جستجوی متغیر همسایگی[16] (ونگ و تانگ،  2009) و الگوریتم ترکیبی ابتکاری و فرااِبتکاری (آندراس نراچو، 2013) تمرکز یافته است. الگوریتم بهینه‌سازی کلونی مورچگان یکی از روش‌های فرااِبتکاری است که با الهام از رفتار مورچه‌های طبیعی، به‌عنوان یکی از الگوریتم‌های فرااِبتکاری مبتنی بر هوش جمعی و جمعیت است که تاکنون بر مسائل گوناگون پژوهش عملیاتی از جمله استفاده شده است.

مرکل و میدندورف (2005) با استفاده از الگوریتم مورچگان توانستند یک جایگشت مناسبی را برای مسأله SMTWTP ارائه کنند. لیائو و جوان (2007) یک الگوریتم مورچگان را برای SMTWTP با درنظرگرفتن زمان‌های آماده‌سازی ارائه کردند. یاگماهان و ینیسی (2008) یک مسأله زمان‌بندی چندهدفه برپایۀ الگوریتم مورچگان را برای کاهش هزینه‌های زمان‌بندی ارائه دادند. آنگینولفی و پائولوسی یک رویکرد جدید  برای توالی وابسته به زمان‌های آماده‌سازی مسأله  ارائه کرد. مادور و همکاران (2012) یک الگوریتم  برای مسئله  برای مقیاس بزرگ ارائه کردند و نتایج الگوریتم را با داده‌های الگو OR-Library مقایسه کردند. با توجه به اهمیت موضوع، در مقالۀ حاضر تابع هدف SMTWTP به‌عنوان هدف زمان‌بندی تولید برای گرفتن تصمیم یکپارچۀ تولید و توزیع انتخاب شده است.

دسته‌بندی به‌منظور کاهش هزینه‌های ارسال به مشتری صورت می‌گیرد؛ بدین ترتیب که یک دسته شامل کارهایی است که یک‌دفعه و با یکدیگر توسط یک وسیله ارسال می‌شوند. گسترش این نوع از مسائل موضوع مهمی است که اخیراً مورد توجه محققان زنجیرۀ تأمین واقع شده است. این دسته از مسائل در ادبیات موضوع به ارسال دسته‌ای[17]معروف شده است. اولین مقاله با درنظرگرفتن هزینۀ حمل‌ونقل برای ارسال دسته‌ها توسط چنگ و کالباچر (2008) ارائه شد؛ آنها مسأله  را بررسی کردند؛ در این مورد نیز اغلب مقالات مرتبط با روش ارسال مستقیم ارجاعی به این مقاله دارند. از سال 1993 تا سال 2012 بیش از 45 مقاله در این زمینه منتشر شده است که بیانگر گسترش و اهمیت این دسته از مسائل است که اخیراً مورد توجه محققان در بحث زنجیرۀ تأمین واقع شده است (راستی، 1391). در این مطالعه ارسال مستقیم سفارشات به هر مشتری بررسی می‌شود. تابع هزینۀ ارسال به‌صورت یک رابطۀ خطی بین تعداد دفعات ارسال و هزینۀ هر بار ارسال تعریف می‌شود. به نظر می‌رسد اولین مقاله در زمینۀ مسائل تولید و توزیع یکپارچۀ مسأله  باشد که در سال 1980 ارائه شد (پاتس، 1980). این پژوهش  با درنظرگرفتن زمان حمل‌ونقل اما بدون ظرفیت یا هزینۀ ارسال است. اغلب مقالات IPODS با روش ارسال تکی و فوری به مقالۀ پاتس اشاره دارند. در سال 1993 اولین مقاله با درنظرگرفتن هزینۀ حمل‌ونقل برای ارسال دسته‌ها توسط چنگ و کالباچر (2008) ارائه شد؛ آنها مسأله  را بررسی کردند. تنها مطالعۀ موجود در زمینۀ یکپارچگی تولید و توزیع با محوریت تأخیر مربوط به پاتس (2005) است که برای اولین بار در زمینۀ مسائل IPODS تابع هدف مجموع تأخیر کارها را محور بخش زمان‌بندی تولید قرار داد و آن را با مفهوم زمان‌بندی ارسال دسته‌ای ترکیب کرد و برای مسأله  یک الگوریتم برنامه‌ریزی پویا ([18]DP) شبه‌چندجمله‌ای ارائه داد. حالت تعمیم‌یافتۀ مسأله پاتس یعنی  است که ترکیب مسأله SMTWTP و ارسال دسته‌ای است در مقالۀ حاضر بررسی می‌شود (جمع‌بندی ادبیات موضوع را در جدول 1 ببینید).

جدول 1- بررسی ادبیات موضوع برحسب سال انتشار

ساختار این مقاله بدین صورت است که در بخش اول مسأله موردنظر تعریف می‌شود و پیچیدگی و کاربردهای آن بررسی می‌شود، در بخش دوم مدل خطی مختلط[19] آورده شده است. در بخش چهارم، الگوریتم بهینه‌سازی کلونی مورچگان[20] و الگوریتم سیستم مورچه‌ای نخبه‌گرا ارائه می‌شود. انجام تست‌های محاسباتی به‌منظور مقایسۀ دو رویکرد در بخش پنجم آورده شده است. جمع‌بندی به‌همراه ارائۀ پیشنهاداتی جهت کارهای آتی نیز در بخش پایانی مقاله است.

2- تعریف مسئله

یک مسأله زمان‌بندی تک‌ماشینه زنجیرۀ تأمین را در نظر بگیرید که در آن  کار توسط یک مشتری سفارش داده می‌شود. زمان پردازش کار ام  و موعد تحویل آن  است. به‌منظور کاهش هزینه‌های ارسال می‌توان کارهای پردازش‌شده را دسته‌بندی کرد و تمام کارهای یک دسته را با یک وسیله و با هزینۀ  (مستقل از حجم و تعداد کارها) ارسال کرد. فرض می‌شود به تعداد کافی وسیله وجود دارد و تحویل دسته به مشتری در زمان ارسال صورت می‌گیرد.‌ به عبارت دیگر زمان تحویل هر سفارش به مشتری، برابر زمان تکمیل دسته‌ای است که آن سفارش با آن دسته فرستاده می‌شود. هدف کمینه‌سازی مجموع وزنی تأخیر کارها و هزینه‌های ارسال است. به‌منظور تطابق بیشتر با دنیای واقعی، برای هر دسته یک زمان آماده‌سازی در نظر گرفته می‌شود. استینر و ژانگ در پژوهش­های خود اشاره کرده‌اند که استفاده از این نوع زمان آماده‌سازی بسیار واقعی‌تر و عملی‌تر است و پژوهش­ها کاربردی‌تر می‌شوند (استینر و ژانگ، 2009). نمونه‌هایی از کاربرد زمان آماده‌سازی برای هر دسته که موضوع ارسال هم در آن وجود دارد در مطالعات هاچمن و لاندی (1991) و نیز لینگ و چنگ (2005) ارائه شده است. به‌عنوان مثال می‌توان به زمان‌های موردنیاز جهت بسته‌بندی سفارشات اشاره کرد که در آن به جز زمان پردازش سفارشات زمانی هم برای آماده‌سازی پالت یا انتقال بسته باید منظور کرد. همچنین نمونه‌های دیگری از کاربرد آن در سیستم‌های بارگیری است که زمانی صرف انتقال بسته‌ها می‌شود. گفتنی است جهت محاسبۀ زمان تکمیل هر دسته باید زمان تکمیل پردازش کارهای موجود در آن دسته را با یک زمان آماده‌سازی جمع کرد (تفاوتی در اینکه زمان آماده‌سازی در کجای دسته در نظر گرفته شود وجود ندارد؛ زیرا زمان تکمیل دسته برابر مجموع زمان‌های گفته‌شده است و زمان تکمیل هر کار برابر زمان تکمیل دسته مربوطه است) (راستی برزکی و همکاران، 1391). براساس نمایش اختصاری پیشنهادشده توسط چن (2010) نمایش اختصاری این مسئله به‌صورت  است که در آن  مجموع وزنی تأخیر کارها و  کل هزینۀ ارسال است.

2-1- مفروضات مسئله

• سیستم تولیدی تک‌ماشین است؛
• یک مشتری وجود دارد؛
• نحوة ارسال مستقیم و دسته‌ای است؛
• برای هر دسته یک زمان آماده‌سازی منظور می‌شود؛
• برای هر دسته یک هزینة ارسال مستقل از حجم و تعداد کارهای آن دسته منظور می‌شود؛
• موعد تحویل کارها مختلف و مشخص است (برای هر کار یک موعد تحویل)؛
• زمان‌های پردازش برای هر کار مشخص است؛
• انقطاع کارها مجاز نیست؛
• کلیة کارها در زمان صفر دردسترس هستند؛
• کار تکمیل‌شده در یک دسته، تا زمان تکمیل تمام کارهای متعلق به آن دسته برای ارسال منتظر می‌ماند.

2-2- پیچیدگی مسئله

واضح است مسائلی که علاوه بر اهداف معمول زمان‌بندی و توالی، هزینه‌های ارسال را نیز در نظر می‌گیرند پیچیده‌تر از مسائل کلاسیک هستند. مسئلة ، به‌طور قوی[21]NP-hard است (چنگ، 2004). بنابراین، مسئلة  نیز به‌طور قوی NP-hard است.

2-3- علائم اصلی

علائم مورداستفاده در برنامه‌ریزی عدد صحیح مسئله موردبررسی در جدول 2 آمده است.

جدول 2- تعریف علائم مورداستفاده در مدل

3- برنامه‌ریزی عدد صحیح مختلط

در این بخش، برنامه‌ریزی عدد صحیح مختلط برای مسئلة گفته‌شده ارائه می‌شود (رضایی و همکاران، 1392)..

تابع هدف شامل کمینه‌کردن مجموع هزینه‌های تأخیر و ارسال است که در رابطۀ (1) نشان داده شده است. رابطۀ (2) مقدار تأخیر هر کار را محاسبه می‌کند. رابطۀ (3) نشان می‌دهد که هر کار باید فقط به یک دسته اختصاص یابد. رابطۀ (4)، زمان تکمیل پردازش یک دسته را با درنظرگرفتن زمان آماده‌سازی محاسبه می‌کند. مقدار اولیه متغیر زمان تکمیل دسته ( ) در رابطۀ (5) آورده شده است. رابطۀ (6) زمان ارسال هر کار را با استفاده از زمان تکمیل دسته‌ای که آن کار متعلق به آن دسته است، محاسبه می‌کند. رابطۀ (8) و (9) تعداد دسته‌های بهینۀ مسئله را با استفاده از متغیر  مشخص می‌کند. روابط (10) تا (13) نیز وضعیت متغیرهای مدل را نشان می‌دهند.

4- معرفی الگوریتم مورچگان.

در این بخش، یکی از الگوریتم‌های فرااِبتکاری مبتنی بر هوش جمعی و جمعیت، به نام بهینه‌سازی کلونی مورچگان معرفی می‌شود. بهینه‌سازی کلونی مورچگان، شامل مجموعه‌ای از روش‌هاست که از رفتار کلونی مورچه‌ها، برای جستجوی غذا الهام گرفته شده است. مورچه‌ها برای یافتن غذا، همواره مسیر یکسانی را دنبال می‌کنند و این مسیر، کوتاه‌ترین مسیر ممکن است. هر مورچه در طول مسیر از خود یک ماده شیمیایی به نام فرومون ترشح می‌کند. تمامی اعضای کلونی، این ماده را حس می‌کنند و حرکت خود را به سمت مسیری جهت می‌دهند که دارای فرومون بیشتری است. به عبارت دیگر، مسیری که دارای فرومون بیشتری باشد، جذابیت بیشتری برای انتخاب توسط یک مورچه خواهد داشت (دوریگو و همکاران، 2002). الگوریتم ACS یکی از کاراترین نسخه‌های الگوریتم مورچگان است که تاکنون در مسائل گوناگون پژوهش عملیاتی استفاده شده است. ساختار الگوریتم ACS بدین صورت است که تعدادی مورچه در یک گراف که متناظر با مسأله بهینه‌یابی است قرار می‌گیرد. هر چه مورچه به‌صورت احتمالی در این گراف حرکت می‌کند و براساس مقدار فرومون و اطلاعات ابتکاری اقدام به تولید جواب می‌کند. سپس مقدار فرومون مسیر را براساس کیفیت جواب تولیدشده به‌هنگام می‌کند و به این وسیله بین مورچه‌ها ارتباط برقرار می‌شود. هر مورچۀ مصنوعی علاوه بر ویژگی‌های مورچه‌های طبیعی، از اطلاعات ابتکاری و حافظه‌ای برای ثبت حرکت‌های قبلی خود بهره می‌برد. اطلاعات ابتکاری براساس تابع هدف مسئله تعریف می‌شود، به این صورت که معرف میزان بهبود در مقدار این تابع، در اثر حرکت یک مورچه از یک گره به گره دیگری است. همچنین هر حرکتی که یک مورچۀ مصنوعی انجام می‌دهد در حافظه‌ای ذخیره می‌شود، تا برگشت به عقب و اصلاح مقادیر فرومون به‌سادگی قابل انجام باشد. همچنین به‌علت ساختار پیچیده‌ای که مسئله دارد تاکنون تعداد کمی از کاربرد الگوریتم مورچگان برای حل مسأله  استفاده شده است. در این مقاله یک روش ACS و یک روشEAS  برای حل مسأله تحت مطالعه ارائه می‌شود که در بخش‌های بعدی با جزئیات کافی به آن پرداخته می‌شود..

4-1- الگوریتم جمعیت مورچگان^[22] (ACS).

.تاکنون نسخه‌های مختلفی برای الگوریتم ACO ارائه شده است. از جملۀ این الگوریتم‌ها می‌توان به الگوریتم سیستم مورچگان[23] (AS)، سیستم مورچگان ماکس مین[24] (MMAS) و سیستم اجتماع مورچگان(ACS) اشاره کرد (لیائو و جوان، 2007). البته عمده تفاوت نسخه‌های مختلف الگوریتم ACO در نحوۀ به‌روزرسانی فرومون‌های آنها است. الگوریتم ACS، یکی از موفق‌ترین نسخه‌های الگوریتم ACO است که آن را دوریگو و گامباردلا (2005) ارائه کرده‌اند.

شکل 1 شبه‌کدهای این الگوریتم را نشان می‌دهد.

شکل 1- شبه‌کدهای الگوریتم ACS

4-2- معرفی پارامترهای روش ACS

: مقدار فرومون روی یالی است که گره‌های  و  را به هم متصل می‌کند.

: احتمال حرکت از گره  به گره ملاقات‌نشدۀ  و به‌وسیلۀ مورچۀ k است.

: اطلاعات ابتکاری برای اندازه‌گیری میدان دید مورچه است.

  : پارامترهایی کنترلی هستند که نسبت اهمیت مقدار میدان دید مورچه را در برابر مقدار فرومون روی یالی که گره  و  را متصل کرده است تعیین می‌کند.

: یک پارامتر تصادفی است که به‌طور یکنواخت در  توزیع شده است.

: یک پارامتر آستانه‌ثابت در  است که نسبت اهمیت استخراج به اکتشاف را تعیین می‌کند. توجه کنید که انتخاب  روش ACS را به‌روش AS تبدیل می‌کند. بنابراین موقعی که q کمتر یا مساوی  باشد مورچه‌ها اکتشاف را به کار می‌گیرند تا کار j را به‌عنوان کار بعدی در زمان‌بندی انتخاب کنند؛ در حالی که اگر q بزرگ‌تر از  باشد مورچه‌ها از استخراج برپایۀ احتمال، برای انتخاب کار بعدی استفاده می‌کند.

4-3- مقداردهی اولیه[25]

در این گام، تعداد  مورچه هر کدام به‌صورت تصادفی به یکی از کارهای مسئله اختصاص داده می‌شوند. این کارها، نقطۀ شروع هر مورچه برای ساخت جوابش است. همچنین میزان  را به‌عنوان مقدار اولیۀ فرومون به تمام کمان‌های مسئله اختصاص می‌دهیم )که در اینجا  میزان فرومون کمان  است. معمولاً مقدار اولیۀ فرومون را  در نظر می‌گیرند که در آن، مقدار هزینه‌ای است که توسط الگوریتم ابتکاری به دست می‌آید.

4-4- ساخت جواب[26]

در مرحلۀ ساخت جواب، هر مورچه یک توالی شدنی را در  گام می‌سازد. در هر گام، مورچۀ   که در کار ام قرار دارد، با احتمال  کار بعدی‌اش، j را طبق رابطۀ (14) حساب می‌کند:

همچنین با احتمال  کار بعدی‌اش را به‌صورت احتمالی طبق رابطۀ (15) حساب می‌کند:

که در این روابط  طول کمان ،  یک مقدار ابتکاری و  میزان تأثیر این مقدار ابتکاری را نشان می‌دهد. همچنین  مجموعۀ کارهای کاندید مورچۀ  برای حرکت بعدی‌اش است.

بعد از اینکه کار j برای حرکت بعدی مورچۀ انتخاب شد، این کار را از  حذف می‌کنیم. به عبارت دیگر تا انتهای فرایند ساخت جواب، مورچۀ دیگر حق ندارد کار j  را انتخاب کند. همچنین گفتنی است که در ابتدای فرایند ساخت جواب، ،  که مجموعۀ تمام کارهای مسئله است.

4-5- به‌روزرسانی محلی فرومون‌ها

در طول فرایند ساخت جواب، به محض اینکه یک مورچه یک کمان  را طی کند، میزان فرومون روی آن کمان نیز طبق رابطۀ (16)  به‌روز می‌شود.

که در این رابطه  ،  یک پارامتر است. به این فرایند، به‌روزرسانی محلی فرومون‌ها می‌گویند.

4-6- به‌روزرسانی سراسری فرومون‌ها

وقتی فرایند ساخت جواب برای تمام مورچه‌ها کامل شود و فرایند جستجوی محلی بر همۀ این جواب‌ها صورت گیرد، فرایند به‌روزرسانی سراسری فرومون‌ها صورت می‌پذیرد. در به‌روزرسانی سراسری فرومون‌ها، فقط میزان فرومون روی کمان‌های بهترین جواب به‌دست‌آمده در هر تکرار، یعنی ، طبق رابطۀ (18)به‌روز می‌شود:

که ، نرخ تبخیر،  و  نیز مقدار  است. البته همین عمل سبب تشویق مورچه‌های دیگر به تکرار این تور می‌شود (الابیب و همکاران، 2007).

4-7- شرط خاتمه

الگوریتم ACS در صورتی خاتمه می‌یابد که تعداد تکرارهای الگوریتم به بیشترین مقدار خود برسد (این مقدار در تنظیم پارامترها تعیین می‌شود).

5- الگوریتم سیستم مورچۀ نخبه‌گرا[27] (EAS)

اولین بهبودی که بر AS اتفاق افتاد، استفاده از استراتژی نخبه بود که توسط دوریگو و همکارانش در سال 1996 ارائه شد. این الگوریتم به‌دلیل معرفی مکانیسم‌هایی جدید ازلحاظ کارایی نسبت به AS به بهبودهایی دست یافته بود. باید توجه کرد که روند استراتژی نخبه بدین صورت است که یکی از مورچه‌ها، بهترین مورچه‌ای که تاکنون توانسته است بهترین جواب را به دست آورد، می‌تواند در هر تکرار مسیر خود را دوباره فرمون‌ریزی کند. این کار باعث می‌شود کارایی الگوریتم بهتر شود؛ زیرا در روش   ASتمام مورچه‌ها بعد از مدتی توالی‌های یکسانی تولید می‌کردند و این کار باعث می‌شد که اگر این تور مطلوب نباشد عملاً الگوریتم توانایی خود را برای یافتن جواب بهتر از دست داده و روند جستجو و استخراج جواب متوقف شود. درنتیجه الگوریتم برای مسائل نسبتاً بزرگ، کارایی خود را از دست می‌دهد. تفاوت عمده‌ای که EAS نسبت به الگوریتم AS دارد عبارت‌اند از:

فرض کنید  بهترین جوابی است که تاکنون در اجرای کامل الگوریتم به دست آمده است؛ بنابراین در هنگام به‌روزرسانی فرومون، مسیر طی‌شده به‌وسیلۀ مورچه‌ای که مسیر  را تولید کرده است یک مقدار اضافی از فرومون با مقدار  را جذب می‌کند. بنابراین معادلۀ به‌روزرسانی فرومون به‌صورت رابطۀ (19) اصلاح می‌شود.

که در آن:

e: وزن تور  است و دارای یک مقدار ثابت است که توسط کاربر تعیین می­شود.

: هزینۀ توری است که مورچۀ kام پیموده است.

: نرخ تبخیر ثابت در دامنه  است که کاربر بدین وسیله کاهش فرومون روی یال‌ها را تنظیم می‌کند.

: مجموعه یال‌هایی که توسط مورچۀ kام مورد ملاقات قرار گرفته است.

: مقدار فرومون‌ریزی محلی است که در آن مورچه‌ها در حین حرکت ما بین هر گره i و j ، مقداری فرومون، به‌اندازۀ عکس اندازه‌ای که هر کدام تاکنون پیموده‌اند، روی یال مربوطه می‌ریزند (رابطۀ (20)) .

: مقدار فرومون سراسری است که روی یال‌های متعلق به بهترین تور تاکنون شناخته‌شده ریخته می‌شود و برابر  است که در آن  مقدار طول بهترین مسیر به دست آمده است.

از طرف دیگر گفتنی است که ساختار الگوریتم EAS به‌نحوی است که دقت جواب‌ها در ابتدا بسیار پایین است؛ اما به‌تدریج با افزایش تکرارها و ریختن فرومون توسط مورچه‌ها دقت جواب‌ها افزایش پیدا می‌کند. بنابراین ضریب ثابت e نمی‌تواند ضریب مناسبی برای تشویق بهترین مسیر تاکنون به دست آمده باشد؛ زیرا تفاوتی در اینکه بهترین جواب در چه تکراری و با چه دقتی به دست آمده، نمی‌گذارد. در روند بهبود EAS مشخص شد که استفاده از رابطۀ (21) در ابتدا دارای مقدار 1 است و هر زمانی که الگوریتم جواب بهتر را به دست آورد یک واحد افزایش پیدا می‌کند، سبب می‌شود که نتایج بهتری برای به دست آید که در بخش بعدی به تفصیل شرح داده می‌شود.

علاوه بر این، این تابع چندجمله‌ای از آن جهت انتخاب نسبتاً مناسبی به نظر می‌آید که اولاً یک تابع صعودی است و ثانیاً دارای یک شیب متغیر است، به عبارت دیگر با افزایش تکرارها و به‌دست‌آمدن جواب‌های بهتر، تابع مربوطه رشد کرده و بهترین مسیر به‌دست‌آمده با قدرت بیشتری نسبت به جواب‌های قبلی تشویق می‌شود.

توجه به این نکته ضروری است که مقدار کم تابع در ابتدای الگوریتم باعث می شود که فرمون ریخته شده بر  بهترین مسیر تأثیر کمتری بر انتخاب مسیرها در تکرارهای بعدی الگوریتم داشته باشد و مورچه ها نوعی از فراموشی را به اجرا بگذارند؛ به عبارت دیگر این کار باعث می‌شود که اگر مورچه‌ها جواب‌های ضعیفی را در ابتدای الگوریتم به دست آوردند، این جواب‌ها را به فراموشی بسپارند؛ اما با گذشت زمان که الگوریتم به جلو می‌رود و جواب‌ها با دقت بیشتری به دست می‌آیند این مقدار چندجمله‌ای نیز به‌سرعت افزایش پیدا می‌کنند و یال‌های متعلق به بهترین جواب، فرمون بیشتری را جذب می‌کنند.

6- تنظیم پارامترها

قبل از اجرای ACS و EAS برای حل مسائل، ابتدا باید پارامترهای الگوریتم تنظیم شوند بدین منظور مهم‌ترین پارامترهای الگوریتم پیشنهادی که تأثیر بسزایی در همگرایی الگوریتم دارند، تجزیه و تحلیل می‌شوند. برای این منظور برای هر پارامتر موردنظر مقادیر مختلفی آزمایش می‌شود تا بهترین مقادیر برای پارامترهای موردبررسی در بازۀ انتخاب‌شده یافت شود. برای انتخاب این مقادیری، آزمایشی مطابق جدول طراحی شد و برای هر تعداد کار در هر گروه، 3 مسئله به‌صورت تصادفی تولید شدند؛ بنابراین، تعداد کل مسائل تولیدشده برای 27 گروه و 108 (27 4) تیمار، 324 (3 108) مسئله است. هر مسأله تولیدشده توسط روش ACS  به‌ازای تمام پارامترهای موجود در جدول یعنی 486 (3 3 3 2 3 3) مرتبه حل شد از طرف دیگر در هنگامی که یک پارامتر بررسی می‌شود، بقیۀ پارامترها ثابت در نظر گرفته می‌شوند تا به این ترتیب بتوان با دقت بیشتری پارامتر موردآزمایش را بررسی کرد. نتایجی که در جدول نشان داده شده است، بهترین مقادیری است که الگوریتم توانسته است در حل 157464 (324 486) مسئله به دست آورد.

7- نتایج محاسباتی

در این بخش به‌منظور ارزیابی عملکرد روش‌های ارائه‌شده، نتایج محاسباتی ارائه می‌شود. داده‌های معیاری برای مسأله مطرح‌شده یافت نشد. در این تست عملکرد ACS در مقایسه با CPLEX ارزیابی می‌شود. روش‌ها ACS در محیط MATLAB 2011 (a) و مدل MIP در محیط GAMS23.7 کدنویسی شدند. CPLEX یکی از مشهورترین و بهترین محصولات تجاری برای حل MIP در نرم‌افزار GAMS است (براکر و همکاران، 2008). رایانۀ مورداستفاده دارای مشخصات CPU 2.30GHz, RAM 2GB, OS Windows 7 (64-bit) است. با توجه به پیچیدگی بالای مسئله (SNP) و محدودیت پردازشگرها، CPLEX و ACS جهت استفاده مسائلی با تعداد محدودی از کارها مورد توجه قرار می‌گیرند. از آنجایی که مقادیر پارامترهای مسئله بر زمان حل آن تأثیر می‌گذارند در این تست بازه‌های مختلفی برای تعدادی از پارامترهای مهم مسئله در نظر گرفته شده است. این تست نشان می‌دهد که مقادیر پارامترها چگونه بر زمان حل مسائل تأثیر می‌گذارد. پارامترهای مسائل به‌طور تصادفی از توزیع یکنواخت در بازه‌هایی به‌شرح زیر تولید شدند:

زمان‌های پردازش ( )‌ در بازۀ ،

زمان راه‌اندازی دسته برای مشتری ( ) در بازۀ ،

وزن کارها ( ) در بازه‌های ،  و ،

موعد تحویل هر کار ( ) در بازه‌های ، ، و ،

جدول 3 عوامل انتخاب‌شده و سطوح موردنظر را نشان می‌دهد.

برای هر تعداد کار در هر گروه، 10 مسئله به‌صورت تصادفی تولید و حل شدند؛ بنابراین، تعداد کل مسائل تولیدشده برای 27 گروه و 108 (27 4) تیمار، 1080 (10 108) مسئله است. همچنین، یک محدودیت زمانی 3600 ثانیه‌ای برای حل هر مسئله در نظر گرفته شد؛ به‌طوری که اگر الگوریتم در محدودیت گفته‌شده به پایان نرسد بالاجبار متوقف می‌شود. نتایج تست محاسباتی برای 27 گروه و 108 تیمار گفته‌شده در جدول 5 آورده شده است.

جدول 3- عوامل و سطوح انتخاب‌شده برای پارامترها

جدول 4- نتایج تنظیم پارامتر برای روشACS

جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

ادامه جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

ادامه جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

برخلاف الگوریتم‌های دقیق که زمان معیار اصلی موفقیت آنها محسوب می‌شود، دو موضوع مهم در ارزیابی الگوریتم‌های فرااِبتکاری مورد توجه است: اول سرعت الگوریتم و دوم دقت جواب. براساس مشاهدات تست‌های انجام‌شده، کمترین، متوسط و بیشترین متوسط انحراف ACS از جواب بهینه برای همۀ تیمارها به‌ترتیب 00/0درصد، 11/5درصد و 59/33درصد است. ACS ، 28/62درصد از مسائل تولیدشده را صورت بهینه حل کرده است؛ این در حالی است که روشMIP با توجه به ساختار مسئله 89درصد مسائل تولیدشده را حل کرده است؛ همچنین کمترین، متوسط و بیشترین زمان اجرای ACS برای همۀ تیمارها به‌ترتیب 3/3، 83/. و 92/1 ثانیه است البته همان‌طور که از شکل 2 مشهود است با افزایش تعداد کارها، زمان حل مسائل روش MIP به‌صورت کاملاً نمایی افزایش یافته است؛ این در حالی است که روش ACS توانسته است مسائل را در زمان بسیار اندکی حل کند. این موضوع نشان می‌دهد که الگوریتم فرااِبتکاری طراحی‌شده در معیار زمان بسیار بهتر از روش دقیق است و می‌تواند عدم‌کارایی روش MIP را برای اندازه‌های بزرگ جبران کند. بنابراین می‌توان نتیجه گرفت با درنظرگرفتن هم‌زمان دو معیار سرعت و دقت الگوریتم و توجه به پیچیدگی بالای مسأله  ، این نتایج برای روش فرااِبتکاری بسیار مناسب هستند. نتایج حاصل از آنالیز واریانس برای تست گفته‌شده در

 آورده شده است. براساس p-value مدل، مدل برای همۀ روش‌ها معنادار است؛ بنابراین، حداقل یکی از عوامل انتخاب‌شده دارای اثر اصلی یا حداقل دو مورد از عوامل انتخاب‌شده دارای آثار متقابل بر روش مورداستفاده هستند. گفتنی است آثار از درجۀ دو به بالا به‌عنوان باقیمانده در مدل در نظر گرفته شده است. مطابق جدول 6، علاوه بر وجود آثار اصلی معنادار یکی از آثار متقابل عوامل نیز معنادار هستند؛ بنابراین، در تحلیل نتایج لازم است به آثار متقابل عوامل دقت شود. همچنین در سطح معناداری 5درصد، سختی مسئله برای هر سه رویکرد متأثر از عوامل تعداد کارها، وزن کارها و موعد تحویل است. بنابراین، عملکرد ACS و CPLEX نه تنها به اندازۀ مسئله بلکه به مقادیر پارامترها نیز بستگی دارد.

برای ارزیابی کارایی ACS و EAS برای ابعاد متوسط و بزرگ (30،15، 45، ...، 105) شاخص‌های متعدد و متنوعی وجود دارد که پس از انجام مطالعات مرتبط، سه شاخص زمان حل، کیفیت و پراکندگی جواب‌های به‌دست‌آمده انتخاب شده است که در ادامه بحث خواهد شد.

شکل 2- زمان اجرای روش‌های ACS و MIP برحسب n به‌صورت تجمعی

شکل 3- نمودار آثار اصلی، متغیر پاسخ: درصد جواب‌های بهینة به‌دست‌آمده توسط ACS

جدول 6- تحلیل ANOVA برای CPLEXو ACS

* مجموع مربعات           ** درجه آزادی

جدول 7- نتایج تست‌های محاسباتی برای روش‌های ACS و EAS

ادامه جدول 7- نتایج تست‌های محاسباتی برای روش‌های ACS و EAS