مسیرگزینی وسایل با بارگیری متقابل در زنجیره عرضه کالا

مبتدی (مناسب برای درک مفهوم کلی مطلب)

F2135

 روش جستجوی بازدارنده
چون مساله موردنظر NP-hard است (Lee et al., 2006)، روش های ابتکاری برای جستجوی راه حل امکانپذیرتر استفاده شده است. با استفاده از رویکرد مشابه لی و همکاران (۲۰۰۶)، جستجوی بازدارنده (TS) به عنوان روش حل استفاده شده است زیرا یکی از بهترین روش های ابداعی دردسترس برای حل VRPهاست (Cordeau,Gendreau, Laporte, Potvin, & Semet, 2002; Wen et al., 2008). به طورکلی، TS شامل حداقل پنج عنصر است: یک حل اولیه، یک ساختار همسایگی، مقیاس توقف، لیست بازدارنده و مقیاس انتظار. با شروع از یک حل اولیه، TS از حل x به حل دیگر x’ در همسایگی x حرکت می کند تا زمانی که یک مقیاس توقف مشخص ارضا شود. لیست بازدارنده شامل حل هایی است که اخیرا مشاهده شده است. در حرکت TS ، از حل‌های مشاهدات اخیر صرف نظر می شود تا از بهینه محلی و جستجوی چرخه ای اجتناب شود. علاوه براین، مقیاس انتظار برای ابطال یک لیست بازدارنده حین حرکت بازدارنده فریبنده استفاده می شود.
در زیر طرحی را برای تولید یک حل اولیه برای مساله موردنظر پیشنهاد کرده ایم. در طرح حل اولیه، فقط کامیون با بار کامل به منظور بهره گیری کامل از ظرفیت وسایل نقلیه در نظر گرفته شده است.
همانطور که در بالا نشان داده شد، طرح حل اولیه شامل دو گام است. گام۱ عمده فروشان را به وسایل اختصاص داده و گام۲ خرده فروشان را به وسایل دردسترس اختصاص می دهد. در گام ۱٫ ۱، تعداد کمینه وسایل نقلیه با مقدار کلی برداشت کالا تقسیم بر ظرفیت وسیله محاسبه شده است. گام های ۱٫ ۲ – ۱٫ ۴ بدیهی هستند. زمان اتمام کار در گام ۱٫ ۵ زمانی را نشان می دهد که وسیله j از محل بارگیری متقابل شروع کرده و در همانجا ماموریتش را تمام می کند. گام ۱٫ ۵ برای تعیین نزدیکترین گره i به وسیل jام است. اگر تعیین شود، سپس وسیله jام در گره i متوقف خواهد شد؛ در غیراینصوت وسیله بعدی در گام ۱٫ ۶ در نظر گرفته می شود. اگر هیچ وسیله ای با موفقیت اختصاص نباید، سپس همانطور که در گام ۱٫ ۷ توضیح داده شده، یک وسیله خالی اضافه می شود. گام های ۱٫ ۲– ۱٫ ۷ تا زمانی تکرار می‌شوند که گره ها تخصیص یابند. پس از اتمام فرایند برداشت کالا، فرایند تحویل در گام ۲ ادامه می یابد، که محدودیت زمانی بروزرسانی می شود و رویه مشابه فرایند برداشت کالا برای اختصاص خرده فروشان به وسایل باقیمانده تکرار می‌شود.
پس از دستیابی به حل اولیه، الگوریتم TS برای تنظیم درست حل توسعه می یابد. ایده اساسی الگوریتم TS پیشنهادی، دستیابی به هزینه کلی حداقل با آرایش مداوم گره ها از وسیله ای به وسیله دیگر است. دو اختلاف اصلی بین الگوریتم TS پیشنهادی و الگوریتم لی و همکاران (۲۰۰۶) وجود دارد. اولا، ما هر دفعه یک گره واحد را به هر وسیله اختصاص می دهید، درحالی که لی و همکاران تلاش دارند تا گره ها بین دو وسیله مبادله کنند. دوما، امکان حذف وسیله خالی در الگوریتم TS پیشنهادی فراهم شده است، درحالی که این امکان در کار لی و همکاران وجود ندارد.
جزییات گام های الگوریتم TS پیشنهادی به صورت زیر است، که اندازه بازدارنده برابر با ۳ است.
۳٫ ۲٫ الگوریتم TS پیشنهادی
۱٫ حل اولیه را با استفاده از طرح حل اولیه گفته شده پیشین تولید نمایید.
فرض کنید r برابر با T منهای زمان اتمام کار ناوگان برداشت کالا باشد و z = 0.
۲٫ اگر z بیشتر از ۲۰۰ باشد، به گام ۱۰ بروید؛ در غیراینصورت ادامه دهید.
اگر ناوگان تحویل فقط شامل یک وسیله نقلیه باشد x = 0, y = 0 بگیرید و به گام۳ بروید؛ درغیراینصورت به گام۴ بروید.
۳٫ گام های زیر را تا جایی که y > 20 تکرار نمایید.
۳٫ ۱٫ اگر x > 20 باشد به گام ۳٫ ۳ بروید.
به صورت تصادفی دو موقعیت l1 و l2 را در ماموریت وسیله انتخاب کنید. گره ها را در l1 و l2 تعویض نمایید.
۳٫ ۲٫ اگر زمان تکمیل جدید بیشتر یا مساوی با r باشد، x = x + 1 انتخاب کنید و گام ۳٫ ۱ بروید.
هروقت که گره i به موقعیت j تخصیص یابد، هر ورودی fij در ماتریس فراوانی را به اندازه ۱ افزایش دهید.
اگر هزینه حمل و نقل جدید کمتر است، سپس حل لازم را بروزرسانی نمایید، l1 را به لیست بازدارنده اضافه نموده و x = x + 1 را انتخاب کنید. به گام ۳٫ ۱ بروید.
۳٫ ۳٫ fij بیشینه را از ماتریس فراوانی انتخاب کنید و گره i را به موقعیت j اختصاص دهید. سطر i و ستون j را حذف نموده و fij بیشینه باقیمانده را انتخاب کنید. رویه را تا جایی که تمام گره ها مشخص شوند ادامه دهید.
ماموریت جدید وسیله نقلیه را همانند گام ۳٫ ۱ انتخاب نمایید. x = 0 و y = y + 1 انتخاب کنید.
۴٫ اگر ناوگان تحویل کالا فقط شامل یک وسیله باشد، سپس z = z + 1 انتخاب نموده و به گام ۲ بروید.
به صورت تصادفی دو وسیله k1 و k2 را در ناوگان تحویل انتخاب نمایید. به صورت تصادفی یک گره i از k1 را انتخاب کنید.
۵٫ اگر فضای کافی در k2 وجود دارد، گره i را به موقعیت بعداز آخرین گره در k2 اختصاص داده و وسیله خالی را حذف نمایید؛ درغیراینصورت، z = z + 1 انتخاب کنید و ناوگان تحویل را احیا نموده و به گام ۲ بروید.
۶٫ _v را تعداد وسایل در ناوگان تحویل بگیرید.
Sj, j = 1; 2; . . . ; _v, را وسیله jام در ناوگان تحویل بگیرید.
گام های زیر را تا زمانی که تکرار نمایید.
۶٫ ۱٫ اگر زمان اتمام کار Sj کمتر یا برابر با r باشد، به گام ۶٫ ۴ بروید؛ درغیراینصورت x = 0 بگیرید و ادامه دهید.
۶٫ ۲٫ اگر x = 70 باشد، به گام ۶٫ ۴ بروید.
به طور تصادفی دو موقعیت l1 و l2 را در Sj انتخاب نمایید.
گره ها را در l1 و l2 تعویض نمایید.
۶٫ ۳٫ اگر زمان اتمام Sj بیشتر از r باشد، x = x + 1 انتخاب نمایید؛ درغیراینصورت حل لازم (Sj) را بروزرسانی نمایید، l1 را به لیست بازدارنده اضافه نموده و x = 0 بگیرید.
به گام ۶٫ ۳ بروید.
۶٫ ۴٫ j = j + 1 انتخاب کنید.
۷٫ اگر زمان اتمام کار یک وسیله در ناوگان تحویل بیشتر یا برابر با r باشد، ناوگان تحویل را همانند گام۴ احیا نموده، z = z + 1 انتخاب نمایید و به گام ۴ بروید.
۸٫ هزینه کلی ناوگان تحویل را با استفاده از رویه مشابه گام۳ کاهش دهید.
۹٫ اگر هزینه کلی ناوگان تحویل کمتر است، حل لازم را بروز نمایید. درغیراینصورت ناوگان تحویل را همانند گام۴ احیا نموده و z = z + 1 انتخاب کنید.
به گام۲ بروید.
۱۰٫ r را برابر با T منهای زمان اتمام کار ناوگان تحویل گرفته و z = 0 انتخاب نمایید.
هزینه کلی ناوگان برداشت کالا را با استفاده از رویه مشابه گام های ۲-۹ کاهش دهید.
الگوریتم TS پیشنهادی در پارگراف های زیر بیشتر تشریح شده است. اولا، z و x بترتیب نشان دهنده تعداد تکرارهای گره های تبادلی در یک ناوگان و در یک ماموریت انتقال کالا می باشد، درحالی که y تعداد تکرارهای تولیدکننده یک ماموریت جدید است. با بروزرسانی r و انتخاب z = 0 ، گام۱ باعث تولید یک حل امکانپذیر می شود. پارامتر r به عنوان محدودیت زمانی و z به عنوان تعداد تکرارها در TS استفاده می شود. سپس گام۳ برای کاهش هزینه حمل و نقل وسیله اجرا می شود. دو وظیفه در گام ۳٫ ۲ اجرا می شود: اولین وظیفه ثبت ماموریت یک وسیله در ماتریس فراوانی می باشد که یک ماتریس n × n برای یک ماموریت وسیله نقلیه با n گره است؛ وظیفه دوم تصمیم برای بروزسانی یا عدم بروزرسانی حل لازم و لیست بازدارنده است. گام ۳٫ ۳ تشریح می کند که چگونه می توان از ماتریس فراوانی یک ماموریت وسیله را تولید کرد (Ben-Daya & Al-Fawzan, 1998). گام های ۴و ۵ وظایف آرایش گره برای سایر وسایل را انجام می دهند. اگر آرایش جدید زمان تکمیل کار بیشتر از r را نشان دهد، در گام۶ آن را کوتاه می کنیم. در گام ۶٫ ۳ دو موقعیت در یک ماموریت وسیله نقلیه مشخص، به طور تصادفی انتخاب شده است و گره ها در دو موقعیت تعویض شده است. اگر زمان اتمام کار کمتر باشد، حل لازم و لیست بازدارنده بروز شده و x بازنشانی می شود. در گام۷، اگر زمان اتمام کار وسیله بیشتر از r باشد، ناوگان تحویل همانند گام۴ بازنشانی خواهد شد؛ درغیراینصورت، هزینه کلی در گام۸ کاهش خواهد یافت. گام۹ به دنبال آن تعیین می کند که آرایش جدید پذیرفته است یا خیر. گام های ۲-۹ تا زمانی که z بیشتر از ۲۰۰ باشد تکرار خواهند شد. پس از اتمام کار ناوگان تحویل، رویه مشابهی برای کاهش هزینه کلی ناوگان برداشت کالا در گام۱۱ اعمال می شود.
۴٫ آزمایشات محاسباتی
در این بخش، بازدهی الگوریتم TS پیشنهادی در مقایسه با TS مربوط به لی و همکاران (۲۰۰۶) ارزیابی شده است. برای داشتن مقایسه مناسب، هردو الگوریتم TS در جاوا کد زده شده و در یک پردازنده Pentium IV Intel at 3.2 GHz تحت Windows XP با ۵۱۲ MB RAM اجرا شده است.