در این فصل ابتدا طراحی صورت مسأله و بعد فرمول VRPSD پیشنهادی ارائه می شود. سپس اجزای الگوریتم ژنتیک بر حسب روش پیشنهادی شرح داده میشوند.
طراحی صورت مسأله
در روش پیشنهادی ما، VRP به صورت پویا درنظر گرفته شده است بهاین صورت که تقاضاهای مشتریان از قبل شناخته شده نیست و هنگام رسیدنِ وسیلهنقلیه به محل مشتری، این تقاضاها تعیین میگردند. برای برآوردن تقاضاها، مسأله باید به گونه ای تعریف شده باشد که قدرت پاسخ دادن در برابرِ این تقاضاهای نامعلوم را داشته باشد؛ همین توانِ پاسخگویی سبب گردیده تا مسأله به یک مسأله پایدار تبدیل گردد.
هر چه مسأله در مقابل حالات مختلف تقاضا قابل انعطافتر باشد ضریب پایداری مسأله بیشتر خواهد بود.
تمامی زیربخشهای موجود در این قسمت، از Shanmugam et al. (2011) اقتباس شده است که با اندکی تغییر بر روی آن، برای روش پیشنهادی استفاده گردیده است.
متدولوژی حل
در سالهای اخیر نیاز به یک الگوریتم برای حل مسائل دنیای واقعی در انواع مسایل بهینهسازی بیشتر احساس می شود.
معلوم نبودن میزان تقاضای مشتریان در روش پیشنهادی ما نیز عدم قطعیت را در مسأله بارز کرده و آن را به مسائل کاربردی دنیای واقعی نزدیکتر کرده است. بخش اساسی کارِ ما این است که بتوانیم در شرایط عدم قطعیت به جوابهای پایداری در این شرایط برسیم و بهینهترین مسیرها را بدست آوریم. تقاضاهای مشتریان مشخص نیستند تا زمانیکه وسیلهنقلیه به محل مشتری برسد. وسیلهنقلیه بر اساس میزان تقاضای مشتری و بار موجود در وسیلهنقلیه تصمیم میگیرد؛ چنانچه تقاضای مشتری از بار کنونی کمتر باشد به مشتری سرویس داده خواهد شد و وسیلهنقلیه به سمت مشتری بعدی حرکت می کند تا اینکه تمامی مشتریان سرویس بگیرند؛ ولی چنانچه بار وسیلهنقلیه جوابگوی میزان تقاضای مشتری کنونی نباشد به همان مقدار هزینهای منفی (جریمه) درنظر گرفته می شود و وسیلهنقلیه برای بارگیری مجدد به انبار باز خواهد گشت و پس از بارگیری، به بقیهی مشتریان سرویس داده خواهد شد.
کاربرد روش پیشنهادی را میتوان با توجه به کاربردهای عملی که به طور مداوم اتفاق میافتد، پیدا کرد.
فرمول VRPSD پیشنهادی
در این بخش، مدل ریاضیِ مسأله با هدف حداقلکردن هزینه های متعارف VRP یعنی هزینه طی مسیر بههمراه هزینه بارگیریمجدد و هزینه تقاضاهای سرویس داده نشده، بیان شده است. جواب مدلِ مطرح شده، مسیر حرکت وسیله نقلیه به سمت مشتریانی که دارای تقاضای نامعلوم هستند را مشخص می کند. فرمول VRPSDروش پیشنهادی و تمامی زیربخشهای این قسمت، با اندکی تغییر و با اقتباس از Shanmugam et al. (2011) نوشته شده اند.
فرمول ریاضی
VRPSD بر روی گراف کامل تعریف شده است، که درآن مجموعه ای از گرهها (مشتریان) هستند که گره بیانگر انبار است.
مجموعـهای از کمانهای متصل به گرهها است.
هزینه سفر (فاصله) بین گرهها است.
از آنجایی که در Shanmugam et al. (2011) برای بدست آوردن فاصله بین گرهها از روش اقلیدسی استفاده کرده است، در روش پیشنهادی نیز فاصلهی بین گرهها از روش اقلیدسی به صورت رابطه (۴-۱) محاسبه گردیده است.
(۴-۱)
یک وسیلهنقلیه با حداکثر ظرفیت کالا را از انبار به مشتریان با توجه به تقاضاهایشان تحویل میدهد. حداکثر ظرفیت برای وسیلهنقلیه را برابر با ۱۵ واحد در نظر گرفتهایم.
تقاضاهای مشتریان متغیرهای تصادفی هستند. تقاضای هر مشتری شناخته شده نیست تا هنگامیکه وسیلهنقلیه به محل مشتری برسد. همچنین فرض می شود که از ظرفیت وسیلهنقلیه تجاوز نمیکند و از توزیع احتمال گسسته پیروی می کند؛ در روش پیشنهادی این مقدار از ۰ تا ۶ فرض شده است.
یک مسیر باید از انبار شروع و بعد از ملاقات تعدادی از مشتریان به انبار بازگردد. یک راه حل عملی برای VRPSD یک جایگشت از مشتریان است که با شروع و پایان در انبار به عنوان یک «مسیر پیش بینی شده» نامیده می شود. وسیلهنقلیه، مشتریان را به ترتیب مسیر پیش بینی شده ملاقات می کند و با توجه به تقاضای مشتری و بار کنونی وسیلهنقلیه تصمیم میگیرد که آیا برای ادامه به مشتری بعدی برود و یا اینکه برای «بارگیری مجدد»[۱۷۲] به انبار برگردد.
برآورد هزینه کل
در VRPSD هدف پیدا کردن یک مسیر است که فاصله سفر مورد انتظار را توسط یک وسیلهنقلیه مستقر در انبار با ظرفیت Q به حداقل برساند.
هزینه کل به موارد زیر بستگی دارد:
هزینه سفر از یک مشتری به مشتری دیگر
هزینه سفر از مشتری به انبار برای بارگیری مجدد، اگر تقاضای مشتری بیش از ظرفیت فعلی وسیلهنقلیه باشد.
هزینه سفر از انبار به مشتری بعد از مشتری کنونی
میزان جریمه ناشی از عدم سرویس به مشتریان
تابع هدف
فرض کنید که یک مسیر پیش بینی شده است. پس از توزیع، اجازه دهید بار باقیمانده از وسیلهنقلیه باشد و طول مسیر مورد انتظار وسیلهنقلیه پس از خدمت به مشتری است. هزینه مورد انتظار از یک مسیر پیش بینی شده به صورت بیان می شود.
هدف روش پیشنهادی کمینهسازی هزینه های متعارف VRP یعنی هزینه طی مسیر، هزینه ناوگان به همراه هزینه بارگیری مجدد و هزینه تقاضاهای سرویس داده نشده میباشد.
تعریف علائم و پارامترها
در Shanmugam et al. (2011) برای تعریف تابع هدف از یکسری پارامتر استفاده شده است که ما روش پیشنهادی را با آنها تطبیق دادهایم.
شرح علائم و پارامترهای مورد استفاده در تعریف تابع هدف به شرح زیر میباشند:
: مجموعه نقاط (گرهها) تقاضا یا تعداد مشتریان است به طوریکه و انبار در گره قرار گرفته است که همان محسوب می شود.
: مجموعه وسایل نقلیه در دسترس است به طوریکه است و تعداد کـل وسیله هاینقلیه در دسترس میباشد که در مطالعه ما درنظر گرفته شده است.
: ظرفیت وسیلهنقلیه
: بار فعلی وسیلهنقلیه
: حداکثر تقاضای مشتری
: تقاضای مشتری i اُم میباشد که میباشد و رابطه برقرار میباشد.
: مسافت بین انبار تا مشتری i
: مسافت بین مشتری i تا انبار
: مسافت بین انبار تا مشتری j
موضوعات: بدون موضوع
لینک ثابت
