بنابراین ملاحظه می­کنید که حتی مسائل جایگشتی نیز برای GA مسائل غیرقابل حلی نیستند (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱؛ Wikipedia, 2013).

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

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

مقدمه
همان­طور که در فصل دوم گفته شد، عدم قطعیت یکی از مهم­ترین پدیده­هایی است که در حل مسائل مهندسی وجود دارد. شبکه ­های حمل­ونقل به دلیل وجود اثر متقابل انسان-­سیستم، وضعیت جغرافیایی و محیطی، پارامترهای ورودی، الگوی فعالیت کاربران و تقاضای سفرها، رفتار رانندگان و تغییر در کاربری زمین دچار عدم قطعیت هستند و مطالعات در زمینه­ این عدم قطعیت­ها، نزدیک به دو دهه است که در حال انجام است (افندی­زاده، غفاری و کلانتری، ۱۳۹۰د).
انواع بسیاری از عدم قطعیت­ها وجود دارند. برخی از این عدم قطعیت­ها عبارتند از: عدم قطعیت در زمان توزیع، عدم قطعیت در تقاضاهای آنلاین و زمان سفر نامعلوم ، عدم قطعیت در تقاضای سفر و عرضه، عدم قطعیت در تقاضای متغیر و عدم قطعیت در تقاضای تصادفی.
ما در این فصل، مروری بر کارهای انجام شده در زمینه­ VRP در شرایط عدم قطعیت­های مختلف می­کنیم.

عدم قطعیت در زمان توزیع
عدم قطعیت در زمان توزیع، در بسیاری از تحقیقات قبلی متخصصان و دانشمندان مورد مطالعه قرار گرفته است (Zheng, 2012). ری^[۱۴۷] و همکاران (۲۰۰۵) زمان تحویل قطعی را در طـراحی تصمیم ­گیری زنجیره تأمین در نظر گرفتند، ولی اتفاقا زمان توزیع عملا نادیده گرفته شد. همچنین برای هنگامی که رویدادهای جدید رخ می­دهد، برنامه بهینه­سازی مجدد پیشنهاد شد (Xiang et al., 2008).
مسأله فروشنده دوره­گرد (TSP) با زمان­های سفر مختلف (اما نه احتمالی) مورد بررسی قرار گرفت (Alfa, 1987). لاپورت^[۱۴۸] و همکاران (a1992) زمان سفر تصادفی را مورد بررسی قرار دادند و تحلیل سناریو از زمان سفر متفاوت(Huisman et al., 2004)، به­کار برده شد.

عدم قطعیت در تقاضاهای آنلاین و زمان سفر نامعلوم
با توجه بهVRP پویا، تقاضاهای آنلاین و زمان سفر نامعلوم با بهره گرفتن از روش دقیق (Chen & Xu, 2006; Yang et al., 2004; )؛ با بهره گرفتن از روش اکتشافی (Fleischmann et al., 2004; Regan et al., 1996) و با بهره گرفتن از روش فراابتکاری (Gendreau et al., 1994; Haghani & Jung, 2005) حل شد.

عدم قطعیت در تقاضای سفر و عرضه
عدم قطعیت­های موجود در شبکه ­های حمل­ونقل را به دو دسته کلی زیر تقسیم می نمایند: «تغییرات تقاضای سفر» و «تغییرات عرضه» (Sumalee et al., 2006). در مطالعاتی از فرض توزیع پواسن برای تقاضا به منظور ارائه روشی تحلیلی برای برآورد میانگین و واریانس زمان سفر مسیر استفاده شد (Sumalee et al., 2006; Watling et al., 2005). اکسوری^[۱۴۹] (۲۰۰۵) نیز با فرض توزیع نرمال برای تقاضا، رابطه­ای تحلیلی برای برآورد میانگین و واریانس، تابع هدف تعادل استفاده کننده را ارائه نموده است.
فرض مهم دیگر در این زمینه، در نظر گرفتن توزیع نرمال برای جریان در مسیرها و کمان­ها است. مجموعه مطالعات فوق در چارچوب برآورد شاخص­ های مختلفِ قابلیت اطمینان شبکه، تعریف شده ­اند (افندی­زاده، غفاری و کلانتری، ۱۳۹۰الف).
چن و همکاران نیز در سال ۲۰۰۸ دو شاخص قابلیت اطمینان کاهش تقاضا^[۱۵۰] و قابلیت اطمینان پاسخ گویی به تقاضا^[۱۵۱] را از مطالعاتی (Du & Nicholson, 1997; Heydecker & Lam & Zhang, 2007) به­عنوان شاخص­ های قابلیت اطمینان مرتبط با تقاضا معرفی کردند. شاخص اول نشان­دهنده احتمال آن است که شبکه بتواند نسبتی از تقاضا را در سطح سرویس مشخص تحمل کند. شاخص دوم نشان دهنده احتمال آن است که نرخ کاهش جریان به دلیل تخریب شبکه، کمتر از مقدار غیر قابل تحمل در شبکه کاهش یافته باشد (افندی­زاده، غفاری و کلانتری، ۱۳۹۰الف).

عدم قطعیت در تقاضای متغیر
عدم قطعیت در تقاضا نیز یکی از مهم­ترین منابع وجود عدم قطعیت در شبکه ­های حمل­ونقل است. از سوی دیگر مدل­ها و ابزارهای پیش ­بینی تقاضای آینده، خود دارای دقت­های مختلفی هستند. بر این اساس، در مطالعات مختلف برای ارزیابی اثر تقاضای متغیر در برآوردهای شبکه، از فرضیاتی مانند درنظر گرفتن توزیع­های احتمالاتی، بازه­ها و مجموعه­های عدم قطعیت استفاده شده است (افندی­زاده، غفاری و کلانتری، ۱۳۹۰ب).
در طراحی شبکه­هـای حمل­ونقل، با یک مسأله دو سطحی روبرو هستیـم که مسـأله­ی سطح بالای آن، سـعی در مینیمم­کردن تابع هدف طراحی در شرایط محدودیت بودجه دارد و سطح پایین آن، تخصیص تعادلی است (Yang & Bell, 1998). تابع هدف طراحی توسط برنامه­ریزِ سیستم مشخص می­ شود، و می ­تواند شاخصی از تراکم، قابلیت اطمینان، آلودگی و … باشد (Yang & Bell, 1998). الگوریتم« فرانک ولف» برای انجام تخصیص تعادلی اسـتفاده می­ شود (Leblanc, 1975). به­ دلیل این­که مسأله تخصیص تعادلی یک مسأله­ غیرخطی و غیرمحدب می­باشد، حل آن با بهره گرفتن از روش­های یافتن بهینه­ معمول دشوار است (Ukkusuri, 2005). یکی از اولین روش­ها برای حل آن، روش شاخه و کران است که برای طراحی شبکه، برای حل یک مدل برنامه­ ریزی غیرخطی ترکیبی عدد صحیح ارائه شد(Leblanc,1975). بر همین اساس برای حل مسأله طراحی شبکه، الگوریتم­های فراابتکاری از قبیل: الگوریتم ژنتیک، الگوریتم کلونی­مورچگان^[۱۵۲] (ACA)، جستجوی ممنوعه^[۱۵۳] (TS)، شبیه­سازی تبربد^[۱۵۴] (SA) (Magnanti, & Wong, 1984; Xiong & Schneider, 1995; Solanki, 1998; Poorzahedy & Abulghasemi; 2005 ) بــه­کار گرفته شدند. هم­چنین پورزاهدی^[۱۵۵] و روحانی^[۱۵۶] در سال ۲۰۰۷ الگوریتم کلونی­مورچگان را با الگوریتم­های ژنتیک، شبیه­سازی تبرید و جستجوی ممنوعه به صورت ترکیبی^[۱۵۷] استفاده کردند و موثر بودن عمل ترکیب، برای حل این مسأله مورد تایید قرار گرفت (افندی­زاده، غفاری و کلانتری، ۱۳۹۰ب).
بخش دیگری از مطالعات تقاضای متغیر نیز در چارچوب بهینه سازی استوار (RO)^[158] انجام شده است. این روش نیز یکی از روش­های نوین حل مسائل برنامه­ ریزی در شرایط عدم قطعیت است که کنترل میزان عدم قطعیت وارد شده به مسـأله را در نظر می­گیرد. تفـاوت عمده این روش با روش برنامه­ ریزی احتمالاتی (SP)^[159] در کاربرد آن­ها است. SP میانگین تابع هدف را در شرایط عدم قطعیت بهینه می­نماید در حالی که RO ممان­های بالاتری را برای این منظور در نظر می­گیرد (افندی­زاده، غفاری و کلانتری، ۱۳۹۰الف).
در بهینه­سازی استوار، اغلب از مجموعه­های عدم قطعیت مانند عدم قطعیت جعبه ای^[۱۶۰]، عدم قطعیت بیضوی^[۱۶۱]، عدم قطعیت سناریو مبنا و غیره استفاده شده است. در برنامه­ ریزی احتمالاتی روش­هایی برای تبدیل مسأله برنامه­ ریزی با این عدم قطعیت­ها به مسأله قطعی معادل به نام« مسأله متقابل استوار»^[۱۶۲] ارائه شده که بن تال^[۱۶۳] و همکاران (۲۰۰۶) آن­ها را ارائه نموده ­اند (افندی­زاده، غفاری و کلانتری، ۱۳۹۰الف).
با فرض عدم قطعیت بیضوی برای مدل­سازی نواسانات تقاضای روزانه، به منظور طراحی شبکه پیوسته از روشی مبتنی بر شبیه­سازی به نام الگوریتم تولید تقاضا^[۱۶۴] استفاده شد (Yin & Lawphongpanich , 2007). این الگوریتم در هر گامِ مسأله، یافتن بدترین تقاضا و همچنین طراحی شبکه را تا رسیدن به همگرایی انجام می­دهد.
همچنین در مطالعه­ ای، با فرض وقوع سناریوهای مختلف تقاضا، که نسبت به یکدیگر اولویتی ندارند، مسأله طراحی شبکه گسسته نیز با استفاده الگوریتم تولید تقاضا حل شده است (Yin, Lou & Lawphongpanich, 2009). این مطالعه برای حل مسأله بهبود شبکه در شرایط تقاضای متغیر با بهره گرفتن از تخصیص تعادلی احتمالاتی، سه روش بهینه­سازی «آنالیز حساسیت»، «سناریو مبنا» و «مدل حداکثر -حداقل» را ارائه نمود. روش اول برای استفاده در شرایط وجود تغییرات تقاضای اندک مانند تغییرات روزانه مناسب است. روش دوم برای برنامه­ ریزی بر اساس سناریوهای مختلف با احتمال وقوع معلوم و روش آخر برای طراحی برای بدترین حالت مناسب است (افندی­زاده، غفاری و کلانتری، ۱۳۹۰الف).
به­ طور کلی، عمده مطالعات انجام شده در زمینه­ عدم قطعیت در شبکه ­های حمل­ونقل، در چارچوب ارزیابی قابلیت اطمینان انجام شده است. ال دیک^[۱۶۵] و همکاران در سال ۲۰۰۶، آنالیز قابلیت اطمینان شبکه را به صورت اندازه ­گیری قابلیت شبکه در انجام نقش­های استاندارد یا حدود مجاز آن (که توسط کاربر مشخص شده) تعریف می­ کنند که به دلایل بازگشت­پذیر یا بازگشت­ناپذیر بسته به شدت و تناوب آن دچار تغییر می­ شود (افندی­زاده، غفاری و کلانتری، ۱۳۹۰ب).
در مطالعات مختلف، با درنظر گرفتن فرض­هایی در زمینه تغییرات مورد نظر بر عرضه و یا تقاضا، شاخص­ های ارزیابی قابلیت اطمینان شبکه برآورد می­ شود. این شاخص ­ها که نشان دهنده ­کیفیت شبکه در شرایط وقوع عدم قطعیت­ها هستند، می­توانند در مسائل مختلف از جمله مسأله طراحی شبکه مورد استفاده قرار گیرند (چن و همکاران،۲۰۰۲).
روش حل رایج برای در نظر گرفتن اثر تقاضای متغیر، استفاده از شبیه­سازی است (Asakura et al., 1991; Chen et al., 2002 ). هم­چنین در مطالعاتی، اثر تغییرات تقاضا با بهره گرفتن از روشی تحلیلی و با تعیین تابع چگالی، احتمال کل زمان سفر مدل­سازی شده است (Watling et al., 2005; Lo et al., 2008). به عنوان مثال از فرض توزیع پواسن و از فرض توزیع نرمال برای تقاضا استفاده شد (Watling et al., 2005; Ukkusuri, 2005). در مطالعاتی (Lo et al., 2008)، فرض کردند که کل تقاضای سفر شامل دو بخش مسافران دائمی و غیردائمی است. تقاضای مسافران غیردائمی به صورت احتمالاتی و بر اساس نسبت انتخاب مسیر ثابت بر شبکه وارد می­ شود. در حالی که تقاضای مسافران دائمی به صورت قطعی بوده و انتخـاب مسیـر آن­ها در شبـکه، به طور تعـادلی و بر اسـاس شناخت آن­ها از شبـکه صورت می­گیرد (افندی­زاده، غفاری و کلانتری، ۱۳۹۰ب).

عدم قطعیت در تقاضای تصادفی
الگوریتم «اکتشاف دوره­ای» در سال۱۹۹۱ برای حلِ مسأله مسیریابی وسایل نقلیه با تقاضای تصادفی (VRPSD)^[166]، معرفی شد (Bertsimas, 1991). اجرای نمونه­ها، نشان داده است که الگوریتم اکتشاف دوره­ای بهتر از الگوریتم «اکتشاف بهینه­سازی مجدد» انجام می­ شود. در سال۲۰۰۰ نام VRPSD را مسأله مسیریابی وسایل نقلیه­ی تصادفی (SVRP)^[167] گذاشتند و دو الگوریتم ابتکاری ارائه دادند (Yang et al., 2000).
در مقاله­ای (Bianchi, 2004) در سال ۲۰۰۴، الگوریتم­های فراابتکاری­ نشان دادند که عملکردی فراتر از عملکردِ الگوریتم اکتشاف دوره­ای دارند. چون تقاضا نامشخص است، ممکن است ظرفیت وسیله­­نقلیه ناکافی باشد، به­همین دلیل استراتژی «ذخیره­سازی مجدد»^[۱۶۸] امیدوارکننده به­نظر می­رسد (Bertsimas et al., 1991; Yang et al., 2000). استراتژی ذخیره­سازی مجدد، به وسایل­نقلیه اجازه می­دهد تا به انبار بازگردند و سپس به بازدید از بقیه­ی مشتریان ادامه دهند؛ هنگامی که بازگشت صورت می­گیرد یک متغیر تصمیم ­گیری افزوده می­ شود (Zheng, 2012).
هم­چنین الگوریتم ژنتیک تولیدکننده (BGA)^[169] برای حل VRPSD پیشنهاد شده است (Irhamah & Ismail, 2009).BGA در جستجوی سراسری از GA قدرتمندتر و قابل اعتمادتر است (Shanmugam et al., 2011).
مقاله­ای در سال ۲۰۱۱ با عنوان « الگوریتم فرا اکتشافی برای مساله مسیریابی وسایل­نقلیه با تقاضاهای تصادفی»، توسط چند الگوریتم فراابتکاری از قبیل الگوریتم ژنتیک، الگوریتم بهینه­سازی ازدحام ذرات و الگوریتم بهینه­سازی ازدحام ذرات ترکیبی ارائه شد؛ در این مقاله مسأله مسیریابی وسایل نقلیه با تقاضاهای تصادفی مورد بررسی قرار گرفته است (Shanmugam et al., 2011)؛ در فصل روش پیشنهادیِ این پایان نامه، از این مقاله استفاده خواهیم نمود.

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

مقدمه
یکی از مسائلی که امروزه در زنجیره تامین بسیار مطرح است و مطالعات گسترده­ای در زمینه­ آن انجام شده، مسأله مسیریابی وسایل­نقلیه (VRP)^[170] می­باشد. در مسأله VRP، مجموعه ­ای از وسایل­نقلیه وجود دارند که موظف هستند برای برآورده کردن تقاضاهای مشتریان، از انبار^[۱۷۱] به سمت آن­ها حرکت نمایند و پس از خدمت به تمـامی مشتریـان دوباره به انبار بازگـردند. هدف این مسأله این است که با بهینه­سازی تابع هدف، یکسری از پارامترهای مورد نظر مسأله از قبیل مسافت طی­شده، زمان سفر و تعداد وسایل­نقلیه کمینه شود و تابع هدف حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. به دلیل این­که مسائل VRP و TSP جزء مسائل Np- hard یا Np- complete می­باشند و با افزایش اندازه مسأله حجم محاسباتی روش­های شناخته شده برای حل بهینه آن­ها دارای رشد نمایی است، بنابراین حل بهینه مسائل واقعی با اندازه بزرگ تقریبـا غیرعملی است و به ناچـار باید از روش­های ابتکاری و فراابتکاری برای محاسبه­ی جواب قابل قبول و تقریبا بهینه استفاده شود. در دنیای واقعی، وجود یکسری از عوامل باعث می­ شود که مسأله VRP یک مسأله غیرقطعی و متغیر باشد. الگوریتم­های فراابتکاریِ بسیاری درحل مسأله مسیریابی وسایل­نقلیه استفاده شده است که از آن جمله می­توان به الگوریتم ژنتیک اشاره نمود. تحقیقات بسیاری درVRP با بهره گرفتن از GA انجام شده است.
بدیهی است، VRP با تقاضاهای تصادفی (SVRP) چالش برانگیزتر و پیچیده­تر از VRP است. تمرکز ما بر روی «مسیریابی وسایل­نقلیه با تقاضای تصادفی (VRPSD)» می­باشد که در بخش ۱-۶-۴-۴ فصل اول معرفی شد، GA برای حل VRPSD توسعه داده شده است.
در پژوهش ما، روشی بر اساس الگوریتم ژنتیک مقاوم برای حل مسأله VRP غیرقطعی ارائه شده است که در آن سعی می­ شود جواب­های مقاومی برای این مسأله یافت شوند که در مواجه شدن با تغییرات، بهینگی خود را حفظ کنند.