بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه ي الگوریتم شبیه سازي تبرید ترکیبی براي حل مسئله ي مسیریابی وسایل نقلیه چند انباره
چکیده: مسئلهي مسیریابی وسایل نقلیه به عنوان یک زمینهي گستردهي مطالعاتی همواره مورد توجه محققین بوده است. با مروري بر ادبیات این حوزه دیده شد که تا به حال محدودیتهاي مربوط به ظرفیت انبار، ظرفیت وسایل نقلیه و طول مسیر بطور همزمان در نظر گرفته نشده است. با توجه به اینکه در نظر گرفتن همزمان این سه محدودیت با یکدیگر مسئله را به واقعیت نزدیکتر میکند، در این مقاله براي اولین بار این سه محدودیت با هم در نظر گرفته شده است. در این مقاله براي حل مسئله در نظر گرفته شده، دو الگوریتم شبیه سازي تبرید که یکی از آنها با روش ابتکاري حریصانه ترکیب شده، پیشنهاد می-شود. الگوریتم اول جوابی تولید میکند که در سه محدودیت صدق میکند ولی الگوریتم دوم به گونهاي است که اگر جواب در محدودیت ظرفیت انبار صدق نکرد مقداري را به عنوان جریمه به تابع هدف اضافه میکند. پارامترهاي بکار رفته در الگوریتمهاي پیشنهادي به کمک آزمایشات انجام گرفته تنظیم شده است. به منظور اعتبار سنجی الگوریتمهاي پیشنهادي، ابتدا جواب حاصل از این دو الگوریتم در نمونه مسائل با اندازه کوچک با جواب بهینه مورد ارزیابی قرار گرفته است. همچنین کارایی دو الگوریتم در ابعاد بزرگ با یکدیگر مقایسه شده است. نتایج نشان دهنده کارایی الگوریتمهاي پیشنهادي و برتري الگوریتم ترکیبی پیشنهادي میباشد.
کلمات کلیدي: مسئله مسیریابی وسایل نقلیه، الگوریتم شبیه سازي تبرید، روش ابتکاري حریصانه.
١- مقدمه
مسیریابی کارآمد براي وسایل نقلیه به لحاظ اقتصادي هم براي بخشهاي خصوصی و هم براي بخشهـاي عمـومی از اهمیـت بالایی برخوردار است .[1] مسئلهي مسیریابی وسایل نقلیه 1(VRP) به عنوان یک زمینهي گستردهي مطالعاتی تعریف شـده است. این مقوله تنها به چند رشته دانشگاهی که این حوزه را تنها براي مدیریت ترافیک به کار میبرند محدود نمیشود، بلکـه در بر گیرنده همه حوزهها میباشد .[2] مدل عمومی VRP شامل مجموعهاي از مشتریان است که تقاضـاي هـر یـک از آنهـا معلوم و هر مشتري تنها یکبار و به طور کامل خدمت میگیرد و فرض میشود که همه وسایل نقلیه همگن و شروع و پایان هر وسیله یک انبار مشخص است و هدف اصلی کمینه سازي کل مسافت طی شده توسط تمامی وسایل نقلیه است .[1]
با توجه به محدودیتهاي موجود در دنیاي واقعی، محدودیتهایی به مدل کلاسیک اضافه میشود براي مثال در صـنعت گاز چند انبار را به جاي یک انبار در نظر گرفته میشود .[3] ما در این مقاله به مطالعهي مسئله مسیریابی وسایل نقلیه چنـد انباره 2(MDVRP) میپردازیم. تفاوت مسئله MDVRP با VRP کلاسیک در این است که در MDVRP دیگر تنها یک انبار به همهي مشتريها خدمت نمیدهد، بلکه مشتريها کالاهاي خود را از چندین انبار دریافت میکنند .[1] مسـئله MDVRP خود به دو دسته تقسیم میشود: دسته اول مسائلی هستند که شروع و مقصد هر وسیله نقلیه یک انبار است 6]،5،[4 و دسـته دیگر مسائلی هستند که هر وسیله نقلیه میتواند به انباري برگردد که شروع حرکتش از آنجا نبوده اسـت 9]،8،.[1 مسـأله در نظر گرفته شده در این مقاله از نوع اول می باشد و هر خودرو از هر انباري که شروع به حرکت کرد به همان انبـار هـم برمـی گردد. در ادبیات، MDVRP جز مسائل کلاسیک NP-hard به شمار میآید و یافتن جواب بهینه در این حوزه حتی در ابعـاد نسبتا کوچک نیز دشوار است .[10] بنابراین کاربرد روشهاي ابتکاري و فراابتکاري در این حوزه رشد چشمگیري داشته است.
تیلمن یکی از اولین کسانی بود که از الگوریتم ابتکاري در حوزه MDVRP استفاده کرد .[11] ریناد و همکاران گزارشی از سایرالگوریتم هاي ابتکاري را که اخیراً در این حوزه بکار رفته است را در مقاله خود گردآوري کـردهانـد. همچنـین در ایـن مقاله الگوریتم جستجوي ممنوع در این زمینه ارائه شده است .[12] تانگیاه الگوریتم ژنتیک را براي حل مسـألهي MDVRP بکار برد [8] و در سال 2008 نیز هو و همکاران از الگوریتم ژنتیک ترکیبی در این حوزه استفاده کردند .[9]
با مطالعهي ادبیات در حوزه مسیریابی وسایلنقلیه چند انباره دیده شد که تا به حال محدودیتهـایی ماننـد ظرفیـت وسـایل نقلیه، ظرفیت انبار و یا محدودیت طول مسیر طی شده براي هر وسیله در نظر گرفته شدهاست 9] ،8 ،[1، اما تا به حال این سه محدودیت با هم در نظر گرفته نشده است و با توجه به اینکه در نظر گرفتن این سه با هم مسئله را به واقعیت نزدیکتر مـی-کند، در این مقاله براي اولین بار این سه محدودیت به طور همزمان در نظر گرفته شده است.
روش شبیهسازي تبرید 3(SA) براي نخستین بار توسط کیرك پارتیک و همکارانش در سـال 1983 مطـرح شـد و از آن زمان تا کنون، براي حل بسیاري از مسائل با پیچیدگی محاسبتی بالا مورد استفاده قرارگرفته است .[13] مـروري بـر ادبیـات مسئله MDVRP نشان می دهد که تا کنون براي حل این مسئله با وجود محدودیتهاي ذکر شده از الگـوریتم SA اسـتفاده نشده است . بنابراین هدف این تحقیق بکارگیري الگوریتم شبیه سازي در تبرید در حل مسئله MDVRP بـا در نظـر گـرفتن محدودیت هاي موجود در دنیاي واقعی و بصورت یکپارچه میباشد. بر این اساس، در این مقاله الگوریتم شـبیه سـازي تبریـد ترکیبی 4(HSA) براي حل مسئله مورد نظر توسعه داده شده است. در این الگوریتم به منظور افزایش کارایی الگـوریتم، بـراي یافتن جواب اولیه یک روش ابتکاري حریصانه ارائه شده است.
ادامه مقاله به صورت زیر سازماندهی شده است. در بخش 2 فرضیات مسئله در نظر گرفته شده ارائه شده است. جزئیـات مربوط به الگوریتم پیشنهادي در بخش 3 تشریح شده است. تنظیم پارامترهاي بکاررفته در الگـوریتم و نتـایج محاسـباتی بـه ترتیب در بخشهاي 4 و 5 ارائه شده است. در بخش پایانی مقاله نتیجه گیري تحقیق و پیشنهاداتی جهت تحقیقات آتی بیان شده است.
٢- مسئله مسیریابی وسایل نقلیه چند انباره
در MDVRP فرض میشود که تعداد و مکان هر دپو و مشتري از ابتدا معلوم است و تقاضاي هر مشـتري و تعـداد و نـوع هـر وسیله نقلیه مشخص است. در این مقاله از مدل پذیرفته شدهي ریناد و همکاران استفاده میکنیم .[12] با ایـن تغییـر کـه در این مقاله هزینه سوخت به صورت جزیی از هزینه مسیر در نظر گرفته نشده است بلکه به صورت مجزا و بـر حسـب تـابعی از مسافت طی شده عنوان شده است.
G=(V,A) یک گراف است که V مجموعه راس هاست که تعداد مشتريها و انبارها را نشان میدهد و A نشـان دهنـده مجموعه یال هاست و مسیرها را نشان میدهد . ماتریس Fij ماتریس فاصله بین راسها است و هدف در اینجا تعیین مشتري-هایی است که به هر دپو تخصیص میدهیم به نحوي که تعداد وسایل نقلیـه کـاهش یابـد و مصـرف سـوخت حـداقل شـود و محدودیتهایی مانند: (1 هر مشتري تنها توسط یک انبار خدمت دریافت کند، (2 شروع و پایان مسیر هر وسـیله نقلیـه یـک انبار باشد، (3 کل تقاضاي هر مسیر کمتر یا مساوي ظرفیت وسیله نقلیه باشد، (4 مسافت طی شده در هر مسـیر کمتـر و یـا مساوي مسافتی باشد که هر وسیله نقلیه مجاز است طیکند و (5 کل تقاضاي مشتري هایی که به هر انبار تخصیص داده مـی شود کمتر و یا مساوي ظرفیت انبار باشد، ارضا شود.
براي مدل کردن مسئله، متغیرهاي صفر و یک fij و xijk را داریم که اگر fij مقدار یک را بگیرد به ایـن معناسـت کـه مشتري j ام به انبار i ام تخصیص داده شده است و در غیر این صورت مقدار صفر را میگیرد و اگر متغیر xijk مقدار یـک را بگیرد به این معناست که وسیله نقلیه k ام از گره iام تا گره j ام را طی کرده است که در غیر این صورت مقدار صفر را می-گیرد.
مسئله به صورت برنامه عدد صحیح صفر و یک به صورت زیر فرموله می شود:
در مدل بالا cij مسافت طی شده از مشتري i ام به مشتري j ام، k تعداد وسایل نقلیه، Q ظرفیت وسایل نقلیـه، d j نشان دهنده تقاضاي هر مشتري، W ظرفیت انبار، L حداکثر مسافتی که هر وسیله نقلیه میتواند طی میکند، میباشد. تابع هدف (1) تعداد وسایل نقلیه و هزینه مصرف سوخت را مینیمم می کند.محدودیت (2) بیام میکند که هـر مشـتري دقیقاً به یک مسیر تعلق دارد و به هر مشتري تنهـا یـک مسـیر وارد مـیشـود.محـدودیتهـاي (3)، (4) و (5) در ارتبـاط بـا محدودیت هاي ظرفیت وسایل نقلیه، ظرفیت انبار و طول مسیر میباشند. محدودیت هاي (6) و (7) تداوم و پیوستگی سـیر
را تضمین می کنند و اینکه پایان هر مسیر از انباري است که مسیر از آنجا شروع شده است.( شروع و پایان هر مسـیر بـه یـک انبار است). محدودیت (8) محدودیت حذف زیر تور می باشد.محدودیت (9) تضمین می کند که هر مشتري بایسـتی بـه یـک انبار تخصیص داده شود.در نهایت محدودیت هاي((10 و (11) متغیرهاي صفر و یک که در مدل مورد استفاده قرار گرفتهاند را مشخص میکنند.
٣- الگوریتم آنیل شبیهسازي پیشنهادي براي مسئله MDVRP
ایده اصلی الگوریتم حل مسائل بهینه سازي شبیه سازي تبریدشده از متروپلیسگرفته شده است .[14] آنها در ایـن الگـوریتم ماده را به عنوان سیستمی از اجزاء شبیهسازي کردند. این الگوریتم پروسه سرد شدن مواد را با کاهش تدریجی دما تا رسـیدن به یک نقطه تعادل دمایی شبیهسازي میکند. بعدها کیركپاتریک و همکارانش این ایده را براي سایر مسائل بهینـهسـازي بـه کار گرفتند .[13] مزیت اصلی الگوریتم SA توانایی آن براي رفع گرفتاري در نقطه بهینه محلی در حرکـت بـه سـمت نقطـه بهینه میباشد. این الگوریتم یک جستوجوي تصادفی را به کار میگیرد که نه تنها تغییراتی را که در تابع هدف بهبـود ایجـاد میکند میپذیرد بلکه برخی حرکتهایی که در تابع هدف بهبود ایجـاد نمـیکننـد در طـول اجـراي الگـوریتم انجـام پـذیرد. الگوریتم SA از یک جواب اولیه شروع کرده، یک جواب همسایگی براي جواب حاضر پیدا میکند و در صورت بهبود تابع هدف به آن همسایگی می رود. با یک احتمال حتی در صورت عدم بهبود تابع هدف نیز بـه آن همسـایگی مـیرود. ایـن کـار منجـر می شود تا از گرفتار شدن در نقطه بهینه محلی اجتناب شود. قانون ترمودینامیک بیان میکند که در دماي t احتمال افـزایش سطح انرژي ماده به صورت زیر بیان میشود:
که در آن k ثابت بولتزمان و e میزان افزایش سطح انرژي است.
200
معیار پذیرش جواب در الگوریتم SA (معیار (Metropolis نیز به صورت زیر میباشد:
فرض کنید میزان تغییر تابع هدف در صورت رفتن به نقطه همسایه به مقدار c باشـد، در مسـائل کمینـهسـازي همـواره یـک حرکت نزولی پذیرفته میشود یعنی c < 0 و جواب صعودي نیز به شرط احتمالی زیر پذیرفته میشود:
که در آن c میزان تغییر تابع هدف، t دماي حال حاضر و r یک عدد تصادفی بین صفر و یک است.
الگوریتم از دوحلقه تشکیل می شود که یک حلقه دما را از دماي اولیه تا دماي نهایی کاهش میدهـد و حلقـه دوم تعـداد تکرار را در هر دما مشخص میکند. عوامل موثر بر زمانبندي کاهش دما شامل موارد دماي اولیه، دماي نهـایی، نحـوه کـاهش دما و تعداد تکرار در هر دما میباشد. در این مقاله دو الگوریتم شبیهسازي تبرید ترکیبی جدید براي حل مسئله ارائه می شود. استفاده از الگوریتم ابتکاري حریصانه در روش اول به گونهاي که جواب درمحدودیت ظرفیت انبار صـدق کنـد و همچنـین در نظر گرفتن جریمه براي الگوریتم دوم در صورتی که جواب در محدودیت ظرفیت انبار صدق نکند، از نوعآوريهاي موجود در نوشته شود.
-1 -3 الگوریتم پیشنهادي اول
در روش اول ما در تمامی مراحل جوابی داریم که در هر سه محدودیت صدق میکند. در این روش ابتدا با استفاده از الگوریتم حریصانه یک جواب اولیه که در همه محدودیتها صدق کند را براي مسئله پیدا میکنیم. سپس الگوریتم شبیه سازي تبرید را براي حل مسئله به کار میگیریم. جواب در این الگوریتم به صورت یک رشته میباشد. در شـکل (1) یـک جـواب بـراي یـک مساله با سه انبار و هفت مشتري آورده شده است. در شکل زیر انبار 10 به هیچ مشتري خدمت نمیدهـد و صـفرها در رشـته نشان دهنده آن هستند که وسیله نقلیه باید به دپو برگردد. براي هر یک از انبارهاي 8 و 9 دو وسیله نقلیه نیاز است.
-1-1-3 الگوریتم ابتکاري حریصانه
با توجه به اینکه یکی از اهداف اصلی مسأله کاهش سوخت مصرفی است و این امر در سایهي کاهش طول مسیر محقـق مـی-شود بنابراین سعی میشود که مشتريها نزدیک ترین فاصله را به انبارها داشـته باشـند و در عـین حـال محـدودیت ظرفیـت انبارها نقض نشود.
مراحل این روش بصورت زیر است:
مرحله -1 فاصلهي ( اقلیدسی) هر یک از مشتريها را تا هر یک از انبارها بدست آورید. در انبار مجموعهاي مانند U دارد و هـر مشتري در مجوعهي نزدیکترین انبار به خودش قرار میگیرد.
مرحله-2 شلوغ ترین انبار را مشخص کنید.
مرحله-3 از شلوغ ترین انبار شروع کنید و مشتریی را که نسبت یه سایر مشتري هـاي موجـود در مجموعـهي U، نزدیکتـرین فاصله را تا انبار دارد انتخاب و به انبار تخصیص و از مجموعه U حذف کنید.
مرحله-4 مرحله 3 را تا زمانی که محدودیت انبار نقض نشده ادامه دهید تا اینکه مجموعهي U مربوط به انبار، تهی شود.
