ارائه مدلی دو هدفه برای مسئلۀ برنامه‌ریزی یکپارچه تولید- توزیع در یک زنجیره تامین چند سطحی با در نظر گرفتن سطح خدمت

مقدمه

با افزایش رقابت در دنیای کسب و کار و ظهور و توسعه فناوری‌های نوین، بسیاری از شرکت‌ها به سوی یکپارچگی روی آورده‌اند. نیاز به انعطاف‌پذیری، کاهش هزینه‎ها و برقراری ارتباطات نزدیک و گسترده بین تامین‎کنندگان، تولیدکنندگان و توزیع­کنندگان، شرکت‎ها را بر آن داشته است که برای بقا و فعالیت در محیط رقابتی و کاملاً متغیر امروز با یکپارچه‎سازی سیستم و سازمان خود، به کسب مزیت رقابتی بپردازند  (چوپرا و میندل[1]، 2004). شکل جدید کسب و کار در دنیای امروز نیز نشان دهنده این موضوع است. شرکت‎های بسیاری با برقراری شبکه‎های گسترده ارتباطی میان شرکا و تامین­کنندگان، به سمت یکپارچگی در زنجیره خود پیش رفته‎اند. در این زنجیره، تامین‎کنندگان با دسترسی به اطلاعات تولیدکنندگان، خود را برای تهیه به موقع نیازهای آنها آماده می‌کنند و توزیع کنندگان نیز با کسب آخرین اطلاعات مربوط به مشتریان و بازار، تولیدکنندگان را در جهت طراحی، تولید و توزیع به موقع محصولات یاری می‌کنند (لی و کیم[2]، 2002). در جهت یکپارچه‌سازی فرآیند‌های موجود در زنجیره تامین، مدل‌ها و ابزارهای گوناگونی وجود دارند که دو دسته عمده آن عبارتند از:

1- مدل‌های مفهومی شامل: مدل [3]SCOR، مدل دپارتمان نیروی دریایی آمریکا، مدل شرکت BGT، مدل دانشگاه تنسی و آژانس دفاعی لجستیک [4](DLA) (چن[5]، 2004).

2- مدل‌های برنامه‌ریزی ریاضی: مدل‌های ریاضی و تحلیلی بر مبنای علوم و تصمیم‌گیری ارائه می‌شوند. در این پژوهش به منظور یکپارچه‌سازی زنجیره تامین در بخش‌های تامین، تولید و توزیع از رویکرد برنامه‌ریزی ریاضی استفاده شده است.

یک زنجیره تامین شامل همه مراحلی (اعضای زنجیره) است که چه مستقیم و چه غیر مستقیم، در برآورده سازی تقاضای یک مشتری نقش دارند. در یک زنجیره تامین معمولی، مواد خام از تامین‌کنندگان به کارخانه‌ها ارسال می‌شوند، سپس محصولات تولید شده در کارخانه‌ها به انبارهای میانی و مراکز توزیع ارسال می‌شوند و از آنجا نیز به سمت خرده‌فروش‌ها و در نهایت به دست مشتری نهایی یا همان مصرف کننده می‌رسند. پس یک کالا مراحل مختلف زنجیره را طی می‌کند تا به دست مصرف­کننده برسد. در بعضی از این مراحل، کالا انبارش می‌شود و در بعضی دیگر حمل می‌شود، یعنی یک زنجیره تامین مجموعه‌ای از انبارش‌ها و حمل و نقل‌ها است (بالو^[6]، 2004). بیشتر مدل‌های یکپارچه ارائه شده در زنجیره­ تامین درپژوهش‌های گذشته را می‌توان به صورت زیر دسته‌بندی نمود:.

مدل‌های یکپارچه خریدار- فروشنده[7]، مدل‌های برنامه‌ریزی یکپارچه تولید– توزیع[8]، مدل‌های برنامه‌ریزی یکپارچه تولید- موجودی[9]، مدل‌های مکان‌یابی- تخصیص[10] (ریزک[11] و همکاران، 2006). هسته اصلی مسائل مدیریت زنجیره تامین مربوط به برنامه‌ریزی تولید و توزیع است. مسأله برنامه ریزی تولید در زنجیره تامین تصمیماتی است که سازنده جهت تولید کالای سفارش شده و زمان و تعداد آن به منظور برآورده کردن نیاز مشتری خواهد گرفت. مسأله برنامه‌ریزی توزیع در زنجیره تامین نیز در برگیرنده تصمیماتی برای پیدا کردن کانالی جهت تحویل کالا از یک سازنده به یک توزیع کننده یا به یک مشتری است. این مسائل وابستگی متقابلی به یکدیگر دارند از این رو بایستی آنها را به طور همزمان در یک روش یکپارچه بکار برد تا هزینه‌ها یا سود حاصل از آن در زنجیره مینیمم (ماکزیمم) شود (چن و لی[12]، 2004). در ادامهادبیات موضوع در حوزه مسأله برنامه‌ریزی یکپارچه تولید – توزیع بررسی می‌شود.

2- مروری بر ادبیات موضوع

توجه مدیران در برنامه‌ریزی زنجیره تامین از دیرباز بیشتر روی بخش تولید متمرکز بوده است که این موضوع امروزه تا حدودی تعدیل شده و مدیران دریافته‌اند که بدون برنامه‌ریزی دقیق در بخش تولید و توزیع در عرصه رقابت توان مقابله با رقبا را نخواهند داشت. بیشترین پژوهش‌های موجود در مدل‌های یکپارچه زنجیره تامین نیز به تصمیم‌گیری هم‌زمان در مورد تولید و توزیع پرداخته شده است که در برخی مقالات این مسائل تحت عنوان مسائل برنامه‌ریزی تولید– توزیع مطرح می‌شوند. کوهن و لی[13] (1988) سیستم‌های یکپارچه تولید- توزیع با تقاضاهای تصادفی را مطالعه کردند. آنها یک مدل تک هدفه زنجیره تامین که ترکیبی از مواد اولیه، محصولات نیمه ساخته و نهایی کارخانه­ها، مراکز توزیع، انبارها و مشتریان  را ارائه کردند. چاندرا و فیشر[14] (1994) مدلی ارائه کردند که جهت مقایسه کارایی، با استفاده از تعدادی شاخص و با مقادیر مختلف برای پارامترهای متعدد، تحلیل شدند. این پارامترها شامل طول پریود، تعداد محصولات، تعداد مشتری‌ها، هزینه‌های ثابت و هزینه‌های موجودی هستند. در این مدل تقاضا برای هر محصول در یک دوره برای هر خرده‌فروش مشخص است و تابع هدف این مدل به دنبال حداقل کردن هزینه کل زنجیره است. سیاریف[15] و همکاران (2002) شبکه زنجیره تامینی شامل تامین‌‌کنندگان، کارخانجات و مراکز توزیع را مورد بررسی قرار داده‌اند. تصمیماتی که باید در این شبکه اتخاذ شود شامل؛ راه‌اندازی کارخانجات و مراکز توزیع، میزان تولید و حمل محصولات است. تابع هدف بصورت کمینه‌کردن کل هزینه‌ها بیان می‌شود. برای حل این مدل از روش الگوریتم ژنتیک بر اساس درخت فراگیر[16] استفاده شده و اعتبار این روش با مقایسه آن با روش سنتی الگوریتم ژنتیک سنجیده شده است. چان[17] و همکاران (2005) شبکه‌ای را با تعدادی تولید کننده در نظر گرفته‌اند که باید تقاضای مشتریان را با ظرفیت تولیدی محدود به طور کامل تامین کنند و کمبود کالا مجاز نیست. در این سیستم باید در مورد میزان حمل کالا تصمیم‌‌گیری شود. توابع هدف چندگانه‌ای شامل کمینه کردن هزینه‌ها و تعادل در استفاده از ظرفیت تولید بین کارخانجات در نظر گرفته شده است. آنها از روش فرآیند تحلیل سلسله‌ مراتبی برای وزن دهی به اهداف و از الگوریتم ژنتیک برای حل مدل خطی استفاده می‌شود. کاظمی و همکاران (2009) از یک الگوریتم ژنتیک به منظور حل مسأله برنامه‌ریزی تولید- توزیع در یک سیستم چند سطحی زنجیره تامین استفاده کردند. آنها از دو سناریو برای حل [18]PDPD استفاده کردند، در ابتدا یک روش متمرکز برای حل آن اعمال کردند و سپس یک سیستم مبتنی بر عامل برای حل PDPD در نظر گرفتند. آنها برای هر سطح یک الگوریتم ژنتیک بکار گرفتند تا سیستم بتواند بهترین جواب را به منظور اثر متقابل بین سطح‌ها انتخاب کند. جولای[19] و همکاران (2011) یک مدل خطی برنامه‌ریزی تولید- توزیع یکپارچه چند هدفه .با چندین سطح، چندین محصول و در چندین دوره زمانی ارائه دادند.. آنها به­منظور انعکاس اثر مسائل برنامه‌ریزی یکپارچه بر روی مدل و فراهم آوردن ساختاری واقعی برای آن، سطوح تصمیم‌گیری غیر دقیق تصمیم‌گیرنده برای اهداف را با استفاده از رویکرد برنامه‌ریزی آرمانی فازی مدنظر قرار دادند. ساختار زنجیره تامین پیشنهادی آنها غیر متمرکز است و به یک مدل تک هدفه با محدودیت تبدیل می‌شود و سپس با استفاده از سه الگوریتم فرا ابتکاری مدل را حل کردند. یک الگوریتم ژنتیک برای حل مسئلۀ دارای محدودیت پیشنهاد شده و نتایج آن با دو الگوریتم ژنتیک و بهینه‌سازی اجتماع ذرات با استفاده از تابع جریمه مقایسه می‌شود. در ادامه برای بیان کاربرد مدل و کارایی روش‌های حل به اجرای یکسری آزمایشات محاسباتی بر روی یک مورد فرضی پرداختند و با مقایسه آنها با یکدیگر به کارا بودن روش پیشنهادی خود اشاره کردند. آشوکا وارتانان[20] و همکاران (2012) نیز با توسعه یک الگوریتم بهینه‌سازی اجتماع ذرات سلسله مراتبی مبتنی بر شبیه‌سازی به حل یک برنامه تولید- توزیع چند معیاره پرداختند. برنامه یکپارچه آنها در برگیرنده سه هدف کمینه‌سازی کل هزینه‌ها شامل هزینه‌های عادی کاری، اضافه کاری، برون‌سپاری شده، نگهداری موجودی، کمبود، استخدام، اخراج و هزینه­های توزیع، کاهش تغییرات در سطوح کاری و به حداقل رساندن بهره‌گیری پائین سطوح کاری است.. آنها الگوریتم پیشنهادی خود را با یک الگوریتم ژنتیک سلسله مراتبی صفر و یک اعتبارسنجی کردند. لیو و پاپاگئورگیو[21] (2013) یک مسئلۀ برنامه‌ریزی تولید – توزیع دو سطحی را با در نظر گرفتن همزمان هزینه، پاسخ‌دهی و خدمت به مشتری ارایه دادند. آن­ها به منظور حل مدل از دو روش ε- محدودیت و لکسیکوگراف[22] استفاده نموده و جواب‌ها را با یکدیگر مقایسه کردند. قابل ذکر است که در ادبیات مسائل برنامه‌ریزی تولید- توزیع، عمده پژوهش‌های مطالعه شده یا به صورت تک هدفه بوده و یا از رویکرد یکپارچه‌سازی و تبدیل اهداف به یک هدف برای حل مدل چند هدفه استفاده نموده‌اند. لذا ما در این پژوهش با ارائه مدلی در یک زنجیره تامین چند سطحی که علاوه بر کمینه‌کردن کل هزینه‌های زنجیره، سطح خدمت را با به حداقل رساندن زمان انتقال محصولات برای مشتریان افزایش می­دهد، از رویکرد پارتو[23] جهت حل مسأله یکپارچه تولید- توزیع استفاده می‌کنیم که در ادامه به بررسی مفاهیم آن خواهیم پرداخت.

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

3- بیان مسأله.

در این بخش، ابتدا مسأله یکپارچه تولید- توزیع پیشنهادی تشریح شده، سپس فرضیات، پارامترها و متغیرهای تصمیم تعریف می‌شوند و در ادامه مدل دو هدفه تولید- توزیع در یک زنجیره تامین چهار سطحی ارائه می‌شود..

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

3-1- مفروضات مدل

در این بخش، مفروضات مدل پیشنهادی ذکر شده که به قرار ذیل گزارش می‌شود:

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

3-2- نمادها و پارامترها

s: تعداد تامین‌‌کنندگان (s=1,2,…,S)

p: تعداد تولیدن‌کنندگان (p=1,2,…,P)

d: تعداد توزیعن‌کنندگان (d=1,2,…D)

c: تعداد مشتریان (c=1,2,…,C)

t: تعداد دوره‌های زمانی (t=1,2,…,T)

i: تعداد محصولات (i=1,2,…I)

m: تعداد مواد اولیه (m=1, 2,…, M)

: تقاضای محصول i از مشتری c در دوره t

: هزینه آماده‌سازی تولید محصول i توسط تولید کننده p در دوره t

: هزینه تولید محصول i توسط تولیدکننده p در دوره t

: هزینه خرید محصول i از تولیدکننده p توسط توزیع کننده d در دوره t

: هزینه نگهداری موجودی هر واحد محصولi توسط تولیدکننده p در دوره t

: هزینه نگهداری موجودی هر واحد ماده اولیهm توسط تولیدکننده p در دورهt

: هزینه حمل هر واحد ماده اولیه m از تامین کننده s به تولید کننده p در دوره t

: هزینه حمل هر واحد محصول i از تولید کننده p به توزیع کننده d در دوره t

: هزینه حمل هر واحد محصول i از توزیع کننده d به مشتری c در دوره t

: هزینه تامین هر واحد ماده اولیه نوع m از تامین کننده s به تولیدکننده p در دوره t

: هزینه نگهداری موجودی هر واحد محصول i توسط توزیع کننده d در دوره t

: مدت زمان تامین مواد اولیه نوع mاز تامین کننده sبرای تولید کننده p در دوره t

: مدت زمان پردازش محصول iتوسط تولید کننده p در دوره t

: مدت زمان حمل محصول i از تولید کننده p به توزیع کننده d در دوره t

: مدت زمان حمل محصول i از توزیع کننده d به مشتری c در دوره­ی t

: ظرفیت حمل و نقل مواد اولیه از تامین کننده s به تولید کننده p در دوره­ t

: ظرفیت حمل و نقل محصولات از تولید کننده p به توزیع کننده d در دوره t

: ظرفیت حمل و نقل محصولات از توزیع کننده d به مشتری c در دوره t

: ظرفیت تولید محصول iتوسط تولید کننده p در دوره t

: ظرفیت کارخانه p برای موجودی ماده اولیه mدر دوره t

: ظرفیت کارخانه p برای موجودی محصول i در دوره t

: ظرفیت مرکز توزیع d برای موجودی محصول i در دوره t

: مقدار ماده اولیه نوع  mمصرف شده در محصول i در دوره t

: هزینه کمبود پس افت برای محصول i از مشتری c در دورهt

3-3- متغیرهای تصمیم

: مقدار تولید برای محصول i توسط تولید کننده p در دوره t

: مقدار تامین برای محصول i از تولید کننده p به توزیع کننده d در دوره t

: موجودی ماده اولیه m برای تولید کننده p در دوره t

: موجودی محصول i برای تولید کننده p در دوره t

: موجودی محصول i برای توزیع کننده d در دوره t

: مقدار تامین مواد اولیه نوع m از تامین کننده s به تولید کننده p در دوره t

: سطح پس افت محصول i برای مشتری c در دوره t

: برابر است با یک اگر محصول i توسط تولید کننده p در دوره tتولید می‌شود در غیر این­صورت صفر

:  برابر است با یک اگر انتقالی از تامین­کننده s به تولیدکننده p در دوره t صورت گیرد در غیر این­صورت صفر.

:  برابر است با یک اگر انتقالی از تولید کننده p به مرکز توزیع d در دوره t صورت گیرد در غیر این صورت صفر

:  برابر است با یک اگر انتقالی از مرکز توزیع d به مشتری c در دوره t صورت گیرد در غیر این صورت صفر

3-4- توابع هدف و محدودیت‌ها

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

محدودیت‌های (3)، (4) و (5) نشان‌دهنده مقدار ماده اولیه m و محصول i ارسال شده در دوره‌های مختلف با توجه به ظرفیت حمل و نقل و در صورت انتقال از آنها به سطوح دیگر می‌باشد. محدودیت (6) اطمینان می‌دهد که مقدار تولید محصول i در صورت تولید در کارخانه p و در دوره t حداکثر به اندازه ظرفیت تولید می‌باشد.محدودیت (7) و (8) نشان دهنده ظرفیت کارخانه p برای نگهداری موجودی مواد اولیه و محصول نهایی در دوره t است. محدودیت (9) بیان کننده ظرفیت مرکز توزیع برای نگهداری موجودی هر محصول i است. محدودیت (10) اطمینان می‌دهد که محصولات ارسالی از یک تولید کننده به تمامی مراکز توزیع، حداکثر به اندازه مقدار تولید محصولات در کارخانه p در دوره t است. محدودیت (11) بیانگر رابطه تعادلی موجودی مواد اولیه در کارخانه p است که برابر با مجموع موجودی ماده اولیه دوره قبل و مواد اولیه ارسالی از تمامی تامین‌کنندگان به تولید کننده p در دوره t منهای مقدار تولید تمامی محصولات در ضریب ماده اولیه استفاده شده برای تولید آن محصول می‌باشد. محدودیت‌های (12) و (13) نیز بیانگر محدودیت‌های تعادلی نگهداری موجودی در سطوح تولید کننده و توزیع کننده است. رابطه (14) محدودیت مربوط به کمبود پس افت برای مشتری c در هر دوره زمانی می‌باشد. محدودیت (15) تصدیق می‌کند که سطح پس افت در دوره آخر بایستی به­منظور تکمیل تقاضای مشتریان برابر صفر شود. روابط (16) و (17) غیر منفی و صفر و یک بودن متغیرهای تصمیم را نشان می‌دهد. رابطه (18) نیز بیان می‌کند که مقادیر موجودی مواد اولیه و محصولات و همچنین سطح پس­افت محصولات در شروع دوره صفر است.

پس از ارائه مدل پیشنهادی، روش‌های مورد استفاده جهت حل مدل از جمله مباحث مهم در ادبیات مسائل بهینه‌سازی است. از آنجاکه این نوع مسائل از رسته مسائل NP-Hard هستند و به دلیل پیچیده‌بودن مدل، زمان محاسباتی روش‌های حل دقیق به شدت بالا بوده و در اغلب موارد ناتوان در حل این نوع مسائل هستند (کاظمی و همکاران، 2009؛ جولای و همکاران، 2011). از فاکتورهایی که باعث پیچیدگی مدل شده، تعداد زیاد محدودیت‌ها و متغیرهای تصمیم و همچنین صفر و یک بودن بعضی از متغیرها می‌باشد. همچنین چند هدفه بودن مدل و تضاد بین جنس اهداف بر پیچیدگی مسأله افزوده است. بدین منظور به عنوان یکی از پرکاربردترین ابزارهای حل این مدل‌ها، از الگوریتم‌های فرا ابتکاری چندهدفه برای حل این نوع مسائل استفاده شده است.

4- روش‌شناسی حل

امروزه بسیاری از مسائل کاربردی در جهان واقعی را مسائل بهینه‌سازی ترکیباتی چند هدفه تشکیل می­دهند که اهداف در تضاد با یکدیگر بوده و بهبود در یک هدف باعث بهتر شدن هدف دیگر نمی‌شود. اکثر مطالعات در زمینه مسائل تولید- توزیع در زنجیره تامین به صورت تک معیاره و یا تک هدفه بررسی شده است در حالی‌که یک هدف یا معیار در مسائل کاربردی، واقعی و عملی کافی نمی‌باشد. در مسائل بهینه‌سازی تک هدفه، با بهینه ساختن تابع هدف الگوریتم به پایان می‌رسد اما در مسائل چند هدفه بهینه­سازی همزمان چند تابع هدف کار سخت و زمان­بری است و در بیشتر این مسائل تعدادی جواب قابل قبول بر اساس معیارهای نامغلوبی بدست می‌آید. بنابراین جواب نهایی به شکل دسته‌ای از جواب­ها است که نماینده موازنه‌ای از توابع هدف مختلف مسأله است. در نهایت یکی از جواب‌ها به عنوان جواب مرجح توسط تصمیم‌گیرنده انتخاب می‌شود. در این مقاله جهت حل مدل پیشنهادی به ارائه دو الگوریتم چند هدفه مبتنی بر پارتو به نام‌های الگوریتم ژنتیک مرتب سازی نامغلوب‌ها[24] و الگوریتم ژنتیک رتبه‌بندی نامغلوب‌ها[25] می­پردازیم که نتایج حاصل از این دو الگوریتم با یکدیگر مقایسه می­شوند.

4-1- الگوریتم ژنتیک مرتب‌سازی نامغلوب‌ها

الگوریتم ژنتیک مرتب‌سازی نامغلوب (NSGA-II) یکی از کارآمدترین و مشهورترین الگوریتم­های بهینه‌سازی چند هدفه می‌باشد که توسط دب[26] و همکاران در سال 2000 ارائه شد. همان‌طور که اشاره شد، الگوریتم‌های بهینه‌سازی تک هدفه، حل بهینه را با توجه به یک هدف می‌یابند و این در حالی است که در مسائل چند هدفه یک حل بهینه مجزا را نمی‌توان یافت. پس طبیعی است که با یک مجموعه­ای از حل‌ها به نام حل‌های مغلوب نشده موثر سروکار داشته باشیم. از بین این مجموعه حل‌های متناهی حل مناسب جواب‌هایی خواهد بود که عملکرد قابل قبولی را نسبت به همه اهداف داشته باشد. برای انجام مقایسات مناسب در بهینه‌سازی چند هدفه از مفهوم غلبه استفاده می‌شود. مفهوم غلبه به این صورت است که فرض کنید F کل فضای موجه مسأله باشد و  دو جواب از این مسأله باشد، گفته می‌شود  بر  غالب است (یا  مغلوب  است) اگر و فقط  نسبت به  در هیچ کدام از اهداف بدتر نباشد  و  نسبت به  حداقل در یکی از اهداف اکیداً بهتر باشد  (دب، 2000). بدین منظور با توجه به این تعریف دو اپراتور به‌منظور رتبه­بندی جواب‌ها به الگوریتم ژنتیک اضافه شده و در ادبیات به الگوریتم NSGA-II شهرت یافته است. آن دو اپراتور مرتب‌سازی سریع نامغلوب‌ها[27] و فاصله ازدحامی[28] می‌باشند. در ادامه قدم‌های پیاده‌سازی الگوریتم NSGA-II تشریح می‌شود.

4-1-1- مقداردهی اولیه

اطلاعات اولیه برای شروع کار الگوریتم NSGA-II پیشنهادی شامل اندازه جمعیت اولیه (nPop)، احتمال عملگر تقاطع (P_c)، احتمال عملگر جهش (P_m) و تعداد تکرار الگوریتم (nIt) است. لازم به ذکر است که مقادیر تنظیم شده این پارامترها را با استفاده از روش تاگوچی بدست می‌آوریم.

4-1-2- ساختار کروموزوم

در این قسمت به‌منظور طراحی کروموزوم، از متغیرهای ساختاری استفاده شده‌است. بدین صورت که هریک از ساختارهای موجود در جواب‌های ایجاد شده، مشخص کننده یکی از ویژگی‌‌های جواب نیز می‌باشد. ساختار مربوط به متغیرهای مسأله به قرار ذیل در شکل 1 هستند.

به عنوان نمونه در مورد ساختار جواب مربوط به ، در صورتی‌که تامین‌کننده s به تولیدکننده p در دوره t اختصاص یابد ماده اولیه نوع m از تامین‌کننده s به تولیدکننده p در دوره t (6=t فرض شده است) با توجه به ظرفیت حمل آن انتقال می‌یابد. نمونه ساختار تشریح شده در شکل 2 نشان داده شده است.

 شکل 1- ساختار جواب‌های مسأله

بدین ترتیب‌که اگر ارتباطی از تامین‌کننده s با تولیدکننده p در دوره t صورت پذیرد، مقدار ماده اولیه‌ای که از هر تامین‌کننده برای هر تولیدکننده در دوره t تامین می‌گردد حداکثر به اندازه ظرفیت حمل آن از تامین­کننده به تولیدکننده در دوره مربوطه می‌باشد. حال تا جایی‌که مجموع مقدار مواد اولیه ارسالی بیشتر از ظرفیت حمل باشد، یک تامین‌کننده به ترتیب به صورت تصادفی انتخاب شده و به اندازه ماکزیمم مجموع این اختلاف از مقدار ارسالی ماده اولیه برای تولیدکننده در آن دوره و مقدار صفر، ماده اولیه برای تولید کننده تامین می‌شود. در واقع مقدار صفر به این خاطر است که حداقل مقدار تامین شده از یک تامین‌کننده خاص منفی نشده و جواب­ها به صورت موجه تولید شوند.

4-1-3- مرتب‌سازی سریع نامغلوب‌ها و فاصله ازدحامی

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

شکل 3- نحوه مرتب‌سازی جواب‌های نامغلوب یک جمعیت

برای تخمین تراکم جواب اطراف یک جواب خاص در جمعیت، متوسط فاصله این جواب از هر دو جواب مجاور براساس مقادیر اهداف محاسبه می‌شود و این مقدار، فاصله ازدحام نامیده می‌شود. به منظور محاسبه فاصله ازدحامی یک جواب خاص موجود در یک مرز، بزرگترین مستطیلی که آن جواب خاص درون مستطیل  و دو جواب مجاور در دو سمت آن جواب (راس‌های آن مستطیل) در نظر گرفته می‌شود و مجموع طول و عرض آن به عنوان فاصله ازدحامی برای آن جواب خاص بدست می‌آید. شکل 4 نحوه نمایش محاسبات مربوط به فاصله ازدحامی  برای عضو دلخواه i از یک مرز غیر مغلوب را نشان می‌دهد (دب، 2000).

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

 شکل 4- محاسبه فاصله ازدحام (دب، 2000)

4-1-4- والدین

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

4-1-5- استراتژی انتخاب

انتخاب جمعیت والد برای بکارگیری عملگرهای تقاطع و جهش بر روی آنها با استفاده از عملگر مسابقه‌ای ازدحام[29] صورت می‌گیرد. این عملگر دو جواب i را مقایسه کرده و پیروز مسابقه را مشخص می‌نماید که در این راستا جواب iام از جمعیت دو ویژگی زیر را دارا می‌باشد: (1) دارای یک رتبه یا درجه نامغلوب بودن است که آن را با  نشان می­دهیم و (2) دارای یک فاصله ازدحامی محلی است که آن را با  نشان می‌دهیم.

بر پایه دو ویژگی بیان شده عملگر مسابقه­ای ازدحام بدین صورت تعریف می‌شود که جواب i در مسابقه با جواب j پیروز می‌شود اگر و فقط اگر یکی از دو شرط: (1) جواب i رتبه بهتری داشته باشد  که این اطمینان را بوجود می‌آورد که جواب پیروز از درجه نامغلوب بودن بهتری نسبت به حریف خود برخوردار است و شرط (2) که در هنگام هم­رتبه بودن جواب‌ها پیش می‌آید بیانگر این است که جواب‌های i و جواب‌های j هم‌رتبه باشند و جواب i از فاصله ازدحامی بیشتری نسبت به جواب j برخوردار باشد ( و )، این اطمینان را بوجود می‌آورد که جواب پیروز از ناحیه ازدحامی کوچکتری ( بزرگتر) نسبت به حریف برخوردار است (دب، 2000).

4-1-6- عملگر تقاطع

جهت تولید فرزند جدید در هر تکرار از الگوریتم، عملگر تقاطع یکنواخت[30] پیاده‌سازی شده است. از این عملگر تقاطع جهت انتقال خصوصیات مناسب بعضی از ژن‌ها که در طول کروموزوم پراکنده شده‌اند، استفاده می‌شود. در شرایطی که ژن‌ها با خصوصیات مناسب در طول رشته پراکنده شده باشند، استفاده از تقاطع یکنواخت می تواند مفیدتر از سایر روش های تقاطع باشد. عملگر تقاطع یکنواخت، به صورت تصادفی بعضی از بیت‌ها را در طول رشته‌های والدین به منظور تولید فرزندان جابجا می‌نماید (بیت و جونز[31]، 2007). شکل (5) نحوه اجرایی عملگر تقاطع یکنواخت مورد استفاده را برای نمونه یک جواب نشان می‌دهد.

شکل 5- نحوه اجرای عملگر تقاطع یکنواخت برای یک نمونه جواب

4-1-7- عملگر جهش

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

4-1-8- ارزیابی فرزندان و ترکیب‌کردن با والدین

در این بخش مجموعه فرزندانی که از طریق. عملگرهای تقاطع و جهش به‌وجود آمده‌اند مورد ارزیابی قرار می‌گیرد و به هریک از فرزندان میزانی از برازندگی اختصاص می‌یابد. در این بخش از الگوریتم جمعیت فرزندان و والدین را با هم ترکیب شده و جمعیتی برابر دو برابر جمعیت سایز اولیه ایجاد می‌شود (دب، 2000). بعد از انجام عمل ترکیب، حال مرتب‌سازی سریع نامغلوب‌ها و فاصله ازدحامی مطرح شده به اجرا گذاشته می‌شود. بدین صورت که ابتدا اعضای جمعیت هر مرز بر اساس فاصله ازدحامی و سپس بر پایه نامغلوب‌ها رتبه‌بندی می شود. این عمل باعث می‌شود جمعیت بر اساس مرز نامغلوب و فاصله ازدحامی رتبه‌بندی شود (رحمتی و همکاران، 2013).

4-1-9- معیار توقف

آخرین قدم در الگوریتم‌های ژنتیک بررسی شرایط توقف می‌باشد. در این راستا تکنیک استانداردی برای برای شرایط توقف الگوریتم‌های بهینه‌سازی چند هدفه وجود ندارد. در نتیجه الگوریتم زمانی متوقف می‌شود که به ماکزیمم مقدار از پیش تعریف شده برسد.

4-2- الگوریتم ژنتیک رتبه‌بندی نامغلوب‌‌ها (NRGA).

در سال 2008 یک الگوریتم تکاملی چند هدفه جدید مبتنی بر جمعیت با نام الگوریتم ژنتیک مبتنی بر رتبه‌بندی نامغلوب‌ها به طور موفقیت‌آمیزی توسط عمرالجدان[32] و همکارانش برای بهینه‌سازی غیر محدب، غیرخطی و گسسته توسعه داده شده است (عمرالجدان و همکاران، 2008). براساس رویکردهای موجود در مسائل قبلی، آن ها رویکرد جدیدی را با ترکیب الگوریتم انتخاب چرخه‌رولت مبتنی بر رتبه‌بندی و الگوریتم رتبه‌بندی جمعیت براساس پارتو توسعه دادند که الگوریتم ژنتیک رتبه­بندی نامغلوب‌ها (NRGA) نام‌گذاری شد. تفاوت الگوریتم NRGA با  INSGA-I در دو بخش استراتژی انتخاب و بخش مرتب کردن جمعیت و انتخاب برای نسل بعد می‌باشد. در استراتژی انتخاب از عملگر چرخه رولت مبتنی بر رتبه‌بندی[33] (RRWS) به‌جای استفاده از عملگر مسابقه‌ای ازدحام استفاده می‌شود (رحمتی و همکاران، 2012). این عملگر به گونه‌ای طراحی می‌شود که اعضای بهتر (با برازش بهتر)، احتمال انتخاب بیشتری برای تولید مثل و تشکیل نسل بعدی پیدا می‌کنند. در اینجا هر عضو جمعیت دارای دو مشخصه رتبه مرز غیر مغلوبی که در آن قرار دارد و رتبه خودش درون مرز بر اساس فاصله ازدحامی می‌باشد. بنابراین برای انتخاب یک جواب، ابتدا باید یک مرز غیرمغلوب انتخاب شود سپس درون آن مرز یک جواب انتخاب شود (عمرالجدان و همکاران، 2008). شکل (7) روند پیاده‌سازی هر دو الگوریتم INSGA-I و NRGA را نشان می‌ دهد.

5- تجزیه و تحلیل نتایج

به‌منظور حل مدل پیشنهادی، دو الگوریتم فرا ابتکاری حل مسائل چند هدفه بر مبنای رویکرد پارتو شامل الگوریتم ژنتیک مرتب‌سازی نامغلوب (NSGA-II) و الگوریتم ژنتیک رتبه‌بندی نامغلوب (NRGA) ارائه شده است. در این بخش نتایج بدست آمده از پیاده­سازی روش‌های حل پیشنهادی بر روی مسائل آزمایشی تولید شده مورد تجزیه و تحلیل قرار گرفته است. در ابتدا پارامترهای الگوریتم‌های مورد استفاده در این مقاله پس از اجراهای متوالی بر روی مقادیر مطابق جدول (1) دسته‌بندی شده و سپس توسط روش تاگوچی تنظیم شده‌اند که سطوح تنظیم شده در شکل (8) نشان داده شده است. سپس آزمایشات بر روی 15 مسأله آزمایشی تولید شده در سه دسته سایز کوچک، متوسط و بزرگ با (2=I، 4=M، 4=D، 2=P، 3=S) و از 4 الی 8 منطقه مشتری در سایز کوچک، (4=I، 7=M، 6=D، 4=P، 5=S) و از 9 الی 13 منطقه مشتری در سایز متوسط، (5=I، 10=M، 9=D، 6=P، 8=S) و از 14 الی 18 منطقه مشتری در سایز بزرگ و همگی در 6 دوره زمانی اجرا شده است. به­منظور پیاده‌سازی مسائل، پارامترهای ورودی در جدول (2) نشان داده شده است. کلیه الگوریتم‌های پیشنهاد شده با نرم افزار MATLAB (Version 10.0, R2010a) برنامه‌نویسی شده و بر روی یک نوت بوک با چهار گیگا بایت حافظه و پردازندهIntel® Core ™ i5  اجرا شده است.

5-1- روش تاگوچی

از آنجایی‌که خروجی مسائل به شدت به پارامترهای الگوریتم‌های پیشنهادی وابسته هستند، لذا از روش تاگوچی به‌منظور تنظیم پارامترهای آن­ها استفاده می­کنیم. مزیت روش تاگوچی نسبت به دیگر روش­های طراحی آزمایشات علاوه بر هزینه، بدست آوردن سطوح بهینه پارامترها در زمان کمتر است (فرالی[34] و همکاران، 2006). یکی از مهم‌ترین قدم‌های این روش انتخاب یک آرایه متعامد[35] است که اثرات عوامل در میانگین پاسخ و تغییرات را تخمین می‌زند. در این پژوهش، مناسب‌ترین طرح، آزمایش‌های سه سطحی تشخیص داده شده‌اند و با توجه به آرایه‌های متعامد استاندارد تاگوچی، آرایه‌ی L₉ به عنوان طرح مناسب آزمایشی برای تنظیم پارامتر الگوریتم‌های پیشنهادی انتخاب شده است. تاگوچی به‌منظور تنظیم پارامترهای بهینه، یک اندازه آماری عملکرد تحت عنوان نسبت S/N[36] را در نظر می‌گیرد که این نسبت در برگیرنده میانگین و تغییرات است و در هر سطحی بیشتر باشد مطلوب‌تر است (تاگوچی[37]، 1986). متغیر پاسخ در نظر گرفته شده، نسبت دو شاخص استاندارد MID[38] به Diversity برای الگوریتم‌های چند هدفه است. از آن‌جا که این متغیر پاسخ از نوع "هرچه کمتر بهتر" است، نسبت S/N متناظر آن به صورت رابطه (19) در نظر گرفته می‌شود. الگوریتم‌های فراابتکاری پیشنهادی برای هر آزمایش تاگوچی اجرا می‌شوند و سپس نسبت‌های S/N توسط نرم‌افزار 14.1 Minitab محاسبه می‌گردند.جدول 1- سطوح و دامنه ارائه شده برای پارامترهای الگوریتم‌های پیشنهادی

شکل 8- نمودار S/N پارامترهای الگوریتم‌های پیشنهادی

5-2- معیارهای اندازه‌گیری برای مقایسه نتایج

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

5-2-1- بیشترین گسترش[39]

این معیار که توسط زیتلر[40] (1999) ارایه شده است، طول قطر مکعب فضایی که توسط مقادیر انتهایی اهداف برای مجموعه جواب‌های نامغلوب بکار می‌رود را اندازه‌گیری می‌کند. رابطه (20) رویه محاسباتی این شاخص را نشان می‌دهد.

در مدل دو هدفه ما، این معیار برابر با فاصله اقلیدسی بین دو جواب مرزی در فضای هدف می‌باشد. هرچه این معیار بزرگتر باشد، بهتر است.

5-2-2- فاصله‌گذاری[41]

این معیار که توسط اسکات[42] (1995) ارایه شد، میزان فاصله نسبی جواب‌های متوالی را با استفاده از رابطه (21) محاسبه می‌‌کند.

که  و  می‌باشد. فاصله اندازه‌گیری شده برابر با کمترین مقدار مجموع قدرمطلق تفاضل در مقادیر توابع هدف بین iامین جواب و جواب‌های واقع در مجموعه نامغلوب نهایی است. قابل ذکر است که این معیار فاصله با معیار کمترین فاصله اقلیدسی بین جواب‌ها متفاوت است (رحمتی و همکاران، 2012).

5-2-3- تعداد جواب‌های پارتو[43]

مقدار معیار NOS نشان‌دهنده تعداد جواب‌های بهینه پارتو هستند که در هر الگوریتم می‌توان یافت.

5-2-4- فاصله از جواب ایده‌آل[44]

از آنجایی‌که در مباحث چند هدفه مبتنی بر رویکرد پارتو، یکی از اهداف، فرونت‌های هرچه نزدیکتر به مبدأ مختصات است لذا این معیار فاصله فرونت‌ها را از بهترین مقدار جمعیت محاسبه می‌کند (زیتلر و تیله[45]، 1998).

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

جدول 3- نتایج محاسباتی معیارهای اندازه‌گیری مقایسه الگوریتم‌های NSGA-II و NRGA

شکل 9- نمودار گرافیکی مقایسه الگوریتم‌های NSGA-II و NRGA بر اساس معیارهای استاندارد

همان‌طور که در ردیف انتهایی جدول محاسباتی (3) نشان داده شده است مجموع مقادیر معیارهای MID، Diversity و NOS در الگوریتم NSGA-II و معیار Spacing برای الگوریتم NRGA از مطلوبیت بالاتری برخوردارند. به‌منظور بررسی و مقایسه دقیق‌تر از تحلیل‌های آماری استفاده کرده‌ایم. همان‌طور که اشاره شد، در این حیطه از تحلیل واریانس و آزمون t بهره جسته‌ایم که نتایج آن در جدول 4 و شکل 10 نشان داده شده است.

جدول 4- نتایج تحلیل واریانس مقایسه معیارها

شکل 10- نمودار جعبه‌ای مقایسه فاصله اطمینان بر اساس معیارهای استاندارد الگوریتم‌های چندهدفه