بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه ي الگوریتم آنیل شبیه سازي براي حل مسئله ي مسیر یابی باز وسایل نقلیه
چکیده - مسئله مسیریابی باز وسایل نقلیه یکی از مهم ترین مسائل پایهاي در حوزه حمل و نقل و لجستیک میباشد. این مسئله با مسئله-ي پایهاي آن، مسئله مسیریابی وسایل نقلیه، متفاوت است چرا که وسایل نقلیه لازم نیست به دپو برگردند. در این مقاله براي اولین بار الگوریتم کاراي آنیل شبیه سازي براي حل مسئلهي مسیریابی باز وسایل نقلیه ارائه شده است. به منظور اعتبارسنجی الگوریتم پیشنهادي از نمونه مسائل موجود در ادبیات استفاده میشود. نتایج بدست آمده از نمونه مسائل، کارایی این الگوریتم را نشان میدهد.
کلید واژه- زنجیره تامین، الگوریتم آنیل شبیه سازي، مسئله مسیریابی باز وسایل نقلیه.
-1 مقدمه
یکی از مهم ترین مسائل مدیریت زنجیره تامین توزیع محصولات بین مشتریان میباشد که در ادبیات تحت عنوان مسئله مسیریابی وسایل نقلیه شناخته میشود و اولین بار توسط رامستر و دانتزینگ در سال 1959 مطرح شد .[1] مدل عمومی مسئله مسیریابی وسایل نقلیه شامل مجموعهاي از مشتریان است که تقاضاي هر یک از آنها معلوم و هر مشتري تنها یکبار و به طور کامل خدمت میگیرد و فرض میشود که همه وسایل نقلیه همگن و شروع و پایان هر وسیله یک انبار مشخص است و هدف اصلی کمینه سازي کل مسافت طی شده توسط تمامی وسایل نقلیه است .[2] مسئله مسیریابی باز وسایل نقلیه نیز یکی از مسائل مدیریت توزیع است و با مسئله کلاسیک مسیر یابی وسایل نقلیه متفاوت میباشد چرا که دیگر نیازي نیست وسایل نقلیه به انبار باز گردند. شرکتهایی که ناوگان وسیله نقلیه ندارند و یا تعداد وسایل نقلیه آنها براي برآورده کردن تقاضاي مشتریانشان کافی نیست با این مسئله مواجه هستند. این شرکتها وسایل نقلیه مورد نیاز خود را کرایه میکنند بنابراین این وسایل نقلیه بعد از خدمت رسانی به آخرین مشتري دیگر نیازي ندارند که به انبار برگردند .[3] تفاوت اصلی بین مسئله مسیریابی باز وسایل نقلیه و مسئله کلاسیک مسیر یابی وسایل نقلیه در این است که مسئله مسیریابی باز وسایل نقلیه داراي الگوي همیلتونی است در حالی که مسئله کلاسیک مسیر یابی وسایل نقلیه داراي یک سیکل همیلتونی میباشد، بنابراین جواب بهینه براي مسئله کلاسیک مسیر یابی وسایل نقلیه با جواب بهینه حاصل از مسئله مسیریابی باز وسایل نقلیه بسیار متفاوت است .[4] براي حل مسئله مسیر یابی باز وسایل نقلیه این سوال مطرح میشود که چرا الگوریتمهاي موجود در مسئله مسیر یابی وسایل نقلیه را به کار نبریم و در آخر، مسافت طی شده از آخرین مشتري را به انبار حذف نکنیم؟ به دو دلیل نمیتوان از این روش استفاده کرد: (1 زمان حل افزایش مییابد، (2 جواب بهینه در مسئله مسیر یابی وسایل نقلیه میتواند یک جواب بد در مسئله مسیر یابی باز وسایل نقلیه باشد .[5] مسئله پیدا کردن بهترین الگوي همیلتونی براي مجموعه مشتریانی که به یک وسیله نقلیه تخصیص مییابند NP-hard است و چون این مسئله زیر مسئله مسیریابی باز وسایل نقلیه میباشد، بنابر این مسئله مسیریابی باز وسایل نقلیه نیز NP-hard میباشد .[6] این مقاله براي اولین بار الگوریتم کاراي آنیل شبیه سازي را براي حل مسئلهي مسیریابی باز وسایل نقلیه به کار برده است.
ادامه مقاله به صورت زیر سازماندهی شده است. در بخش 2 مرور ادبیاتی بر مسئله مسیریابی باز وسایل نقلیه انجام شده در بخش 3 فرضیات مسئله و مدل ریاضی این مسئله ارائه شده است. جزئیات مربوط به الگوریتم حل در بخش 4 تشریح شده است. نتایج محاسباتی در بخش 5 و در بخش پایانی مقاله، نتیجه گیري تحقیق و پیشنهاداتی جهت تحقیقات آتی بیان شده است.
-2 مرور ادبیات
مسئلهي مسیریابی باز وسایل نقلیه اولین بار توسط ساریکلیس و پاول در سال 2000 مطرح شد که در این مقاله یک روش ابتکاري دو مرحلهاي را براي حل مسئله مسیریابی باز وسایل نقلیه ارائه کردند .[3] بعد از آن تارانتیلیس و کراندویس در سال 2002 مسئله مسیریابی باز وسایل نقلیه را براي حالت چند انبار مدلسازي نمودند، آنها براي حل این مسئله از الگوریتم فراابتکاري (LBTA) List-based threshold accepting استفاده کردند .[7] برانداو در سال 2004 اولین الگوریتم جستجوي ممنوع را براي حل مسئله مسیریابی باز وسایل نقلیه به کار برد .[5] فودر سال 2005 براي حل مسئله مسیریابی باز وسایل نقلیه از ترکیب الگوریتم جستجوي ممنوع و الگوریتم ابتکاري Farthest First استفاده کرد .[8] تارانتیلیس و همکارانش در سال 2005 مسئله مسیریابی باز وسایل نقلیه را با استفاده از الگوریتم LBTA حل نمودند .[9] لچفورد و همکارانش در سال 2007 الگوریتم شاخه و حد را براي حل مسئله مسیریابی باز وسایل نقلیه ارائه نمودند، این نویسندگان از این الگوریتم براي حل نمونه مسائلی در اندازه هاي کوچک و متوسط استفاده کردند . [10] ریپوسیس در سال 2007 از الگوریتم فرا ابتکاري براي حل مسئله مسیریابی باز نقلیه با در نظر گرفتن پنجره زمانی استفاده نمود.[6] لی و همکاران در سال 2009 براي حل مسئله مسیریابی باز وسایل نقلیه از ترکیب دو الگوریتم مورچگان و جستجوي ممنوع استفاده کرد . [11] اربائو و مینگ یانگ نیز در سال 2010 مدل مسئله وسایل مسیریابی باز وسایل نقلیه را در حالتی که تقاضاي مشتریان غیر قطعی، فازي، میباشد ارائه نمودند. آنها در مسئله خود از الگوریتم ترکیبی هوشمندانه براي حل مسئله مسیریابی باز وسایل نقلیه استفاده نمودند .[12] زاچاریادیس و کراندویس در همان سال الگوریتم فرا ابتکاري که بر پایه ساختار همسایگی است را براي حل مسئله مسیریابی باز وسایل نقلیه ارائه نمودند. آنها در این ساختار همسایگی بجاي تعویض یک مشتري با مشتري دیگر، مجموعه اي از مشتریان را جا به جا میکردند .[13] یو و همکارانش در سال 2011 از الگوریتم ترکیبی ژنتیک و جستجوي ممنوع براي حل مسئله مسیریابی باز وسایل نقلیه استفاده نمودند. آنها از مدل مسیریابی باز وسایل نقلیه براي حل مسئله مسیریابی وسایل نقلیه در معدن زغال سنگ استفاده کردند .[14] میرحسنی و ابوالقاسمی در سال 2011 از الگوریتم بهینه سازي انبوه ذرات براي حل مسئله مسیریابی باز وسایل نقلیه استفاده نمودند و به منظور اعتبارسنجی الگوریتم خود از نمونه مسائل موجود در ادبیات استفاده کردند .[4] لی و همکارانش در سال 2012 مدل مسئله باز وسایل نقلیه را در حالتی که ناوگان وسایل نقلیه ناهمگن میباشد ارائه نمودند. آنها براي حل این مسئله از الگوریتم جستجوي ممنوع استفاده کردند.[15]
-3 فرضیات مسئله و مدل ریاضی:
مسئله مسیریابی باز وسایل نقلیه شامل یک انبار و تعدادي مشتري است که تقاضاي هر یک از آنها مشخص میباشد. در انبار ناوگانی از وسایل نقلیه قرار گرفته است که این ناوگان همگن هستند و ظرفیت هر یک از آنها مشخص میباشد، هزینه سفر بین انبار و مشتريها و همچنین بین هر دو جفت از مشتريها مشخص میباشد. مسئله در پی پیدا کردن کمترین تعداد مسیر و هزینه سفر است به شکلی که هر مسیر از انبار شروع شود و به یکی از مشتريها ختم شود، تقاضاي هر مشتري تنها توسط یک وسیله نقلیه و تنها یک بار و به طور کامل برآورده شود و مجموع تقاضاي مشتریانی که در یک مسیر قرار میگیرند کمتر و یا مساوي ظرفیت وسیله نقلیه باشد . [3] پارامترها در جدول (1) تعریف شده اند.
به منظور مدلسازي مسئله، متغیرهاي صفر و یک و Zk را داریم. مقدار یک گرفتن متغیر به این معناست که وسیله نقلیه k ام از مشتري i به مشتري j برود و در غیر اینصورت مقدار صفر را میگیرد، و اگر متغیر Zk مقدار یک بگیرد بیانگر این است که از وسیله نقلیه k ام استفاده شده، در غیر این صورت مقدار صفر را میگیرد.
فرمول بندي مسئله به صورت زیر میباشد:
تابع هدف فاز اول (1) بیان میکند که تعداد وسایل نقلیه و مجموع هزینه هاي سفر کمینه شود. محدودیت (2) بیان می-کند که به هر مشتري تنها یک وسیله نقلیه وارد میشود. محدودیت (3) بیان میکند که از هر مشتري تنها یک وسیله نقلیه خارج می شود. محدودیت (4) پیویستگی مسیر را براي هر وسیله نقلیه تضمین میکند. محدودیت (5) محدودیت حذف زیر تور میباشد. محدودیت (6) بیان میکند که مجموع تقاضاي مشتریانی که توسط یک وسیله نقلیه خدمت رسانی میشوند نباید از ظرفیت وسیله نقلیه بیشتر شود. محدودیت (7) بیان میکند هیچ وسیله نقلیه اي به انبار بر نمیگردد. محدودیت (8) بیان میکند که از انبار به هر مشتري حداکثر یک وسیله نقلیه براي خدمت رسانی خارج میشود. محدودیت (9) بیان میکند که تمام مشتريها باید توسط وسایل نقلیهي فعال خدمت رسانی شوند. محدودیت (10) و (11) متغیرهاي سیستم را معرفی می-کنند .[4]
-4 الگوریتم حل
ایده اصلی الگوریتم حل مسائل بهینه سازي آنیل شبیه سازي از متروپلیس گرفته شده است .[16] آنها در این الگوریتم ماده را به عنوان سیستمی از اجزاء شبیهسازي کردند. این الگوریتم پروسه سرد شدن مواد را با کاهش تدریجی دما تا رسیدن به یک نقطه تعادل دمایی شبیهسازي میکند. بعدها کیركپاتریک و همکارانش این ایده را براي سایر مسائل بهینهسازي به کار گرفتند .[17] مزیت اصلی الگوریتم آنیل شبیه سازي توانایی آن براي رفع گرفتاري در نقطه بهینه محلی میباشد. این الگوریتم یک جستجوي تصادفی را به کار میگیرد که نه تنها تغییراتی را که در تابع هدف بهبود ایجاد میکند می-پذیرد بلکه برخی حرکتهایی که در تابع هدف بهبود ایجاد نمیکنند در طول اجراي الگوریتم انجام پذیرد. الگوریتم SA از یک جواب اولیه شروع کرده، یک جواب همسایگی براي جواب حاضر پیدا میکند و در صورت بهبود تابع هدف به آن همسایگی میرود. با یک احتمال حتی در صورت عدم بهبود تابع هدف نیز به آن همسایگی میرود. این کار منجر میشود تا از گرفتار شدن در نقطه بهینه محلی اجتناب شود . قانون ترمودینامیک بیان میکند که در دماي t احتمال افزایش سطح انرژي ماده به صورت زیر بیان میشود:
که در آن k ثابت بولتزمان و میزان افزایش سطح انرژي است.
معیار پذیرش جواب در الگوریتم SA نیز به صورت زیر میباشد:
فرض کنید میزان تغییر تابع هدف در صورت رفتن به نقطه همسایه به مقدار c باشد، در مسائل کمینه سازي همواره یک حرکت نزولی پذیرفته میشود یعنی c < 0 و جواب صعودي نیز به شرط احتمالی زیر پذیرفته میشود:
که در آن c میزان تغییر تابع هدف، t دماي حال حاضر و r یک عدد تصادفی بین صفر و یک است.. در این مقاله براي حل مسئله از الگوریتم آنیل شبیه سازي استفاده میکنیم.
-1-4 نحوه نمایش جواب
اولین قدم در الگوریتم آنیل شبیه سازي در نظر گرفتن ساختاري براي نمایش جوابهاي موجه میباشد.
در شکل (1) یک جواب براي یک مساله با هفت مشتري و یک انبار آورده شده است. در شکل زیر، صفرها نشان دهنده خاتمه مسیر و 8 نشان دهندهي انبار میباشند. وسیله نقلیه مربوط به مسیر اول، از انبار به مشتري هاي اول، پنجم و دوم، وسیله نقلیه دوم از انبار به مشتري هاي چهارم و هفتم و وسیله نقلیه سوم از انبار به مشتري هاي ششم و سوم میرود.
-2-4 تولید جواب اولیه
براي تولید جواب اولیه به صورت تصادفی ابتدا به تعداد صفر تولید میکنیم، سپس به صورت تصادفی یک جایگشت به تعداد مجموع n و تعداد صفرها تولید میکنیم و در آخر محدودیت ظرفیت وسایل نقلیه را بررسی می کنیم اگر این محدودیت نقض شده بود صفر ها را حذف کرده و از ابتدا تا زمانی که محدودیت ظرفیت وسایل نقلیه نقض شود تقاضاي مشتریان را با هم جمع میکنیم ، سپس قبل از مشتري نقض کننده محدودیت صفر را تخصیص میدهیم.
-3-4 تولید همسایگی
در این مقاله براي تولید همسایگی ابتدا انبار و صفرها را حذف کرده و سپس به صورت تصادفی از سه رویهي Swap، Reversion و Insertion استفاده میکنیم که در زیر به تشریح هر یک می پردازیم، اگر جواب بدست آمده موجه نبود صفرها را حذف کرده و از ابتدا تا زمانی که محدودیت ظرفیت وسایل نقلیه نقض شود تقاضاي مشتریان را با هم جمع میکنیم، سپس قبل از مشتري نقض کننده محدودیت صفر را تخصیص میدهیم.
:Swap دو مشتري را به تصادف انتخاب و مکان آنها را با هم تعویض می کنیم.
:Reversion دو مشتري را به تصادف انتخاب کرده سپس مکانهاي بین این دو مشتري را حذف و به صورت معکوس دوباره می نویسیم.
:Insertion دو مشتري را به تصادف انتخاب و مشتري انتخاب شده اول را بعد از مشتري انتخاب شده دوم قرار می دهیم.
شبه کد الگوریتم حل پیشنهادي اول در حل مسئله بصورت زیر می باشد:
-1 تولید جواب اولیه w به صورت تصادفی و بدست آوردن مقدار تابع هدف . f(w)
-2 یک دمابه عنوان دماي اولیه t0 که t0 >0 و دمایی به عنوان دماي نهایی e > 0 و یک ضریب کاهش دما به نام a و عددي را به عنوان تعداد تکرار در هر دما m را انتخاب کنید.
-3 تکرار.
. m 0-4
-5 تکرار.
-6 به صورت تصادفی یکی از سه رویهي Swap، Reversion و Insertion را انتخاب و بر روي جواب اعمال کنید وw´ را بدست آورید.
-7 اگر موجه نبود صفر ها را حذف کنید.
-8 از ابتدا تا زمانی که محدودیت ظرفیت وسایل نقلیه نقض شود تقاضاي مشتریان را با هم جمع کنید سپس قبل از مشتري نقض کننده محدودیت، صفر را تخصیص دهید وw´ را بدست آورید.
-10 اگر و یا عدد تصادفی تولید شده بین
m m 1-11
