بخشی از مقاله
چکیده
مساله مسیریابی وسایل نقلیه در دسته مسایل NP-Hard قرار میگیرد. با توجه به اینکه پیچیدگی زمانی این گونه مسایل درجهای بالاتر از چندجملهای دارند ، با افزایش ابعاد مساله زمان حل دقیق آنها با نرخ چشمگیری افزایش مییابد. به همین دلیل برای حل تقریبی این گونه مسایل راهحلهای ابتکاری و فرا ابتکاری پیشنهاد میشود. در این مقاله مساله مسیریابی وسایل نقلیه با ناوگان ناهمگن با در نظر گفتن هزینه ثابت بکارگیری وسیله نقلیه ، مورد بررسی قرار می گیرد. در مساله ارایه شده است. پس از ارایه مدل ریاضی مساله مذکور، با توجه به ماهیت NP-Hard بودن مساله ، الگوریتم فرا ابتکاری ژنتیک برای مسالهی ارایه شده ، توسعه داده شده است. سپس جهت تصدیق مدل چند مثال عددی عملکرد الگوریتم ژنتیک ،با مقایسه زمان حل و جواب الگوریتم با زمان حل و جواب حل دقیق - توسط نرمافزار لینگو - ، مورد بررسی قرار گرفته است وپس از آن یک مطالعه موردی که شامل یک دپوی مرکزی و24مشتری است حل شده است که نتایج بهدست آمده حاکی از این است که الگوریتم ژنتیک ارایه شده ، عملکرد قابل قبولی دارد و در زمان معقول جوابی با خطای ناچیز به دست میدهد.
کلمات کلیدی: مساله مسیریابی وسایل نقلیه ناهمگن، هزینه ثابت بکارگیری وسایل نقلیه ، الگوریتم ژنتیک،
-1مقدمه
از آنجا که توزیع کالا به طور متوسط حدود %20 از هزینه کل تولید را تشکیل می دهد، بهبود کارایی در حمل و نقل کالاها باعث صرفه جویی زیادی در قیمت تمام شده آنها و رقابت در اقتصاد منطقه ای میشود. بیشتر مسایل حوزه توزیع کالا می توانند به صورت مساله مسیریابی وسیله نقلیه - VRP - 1 درنظر گرفته شوند که تعمیم مساله فروشنده دوره گرد2 است و یکی از مسایل مهم در محدوده مسایل بهینه سازی ترکیبی است که روشهای مکاشفهای زیادی برای حل آن ایجاد شده است.مسیریابی کارآمد برای وسایل نقلیه به لحاظ اقتصادی هم برای بخشهای خصوصی و هم برای بخش های عمومی از اهمیت بالایی برخوردار است. مسئله ی مسیریابی وسایل نقلیه به عنوان یک زمینه ی گسترده ی مطالعاتی تعریف شده است [11].
این مقوله تنها به چند رشته دانشگاهی که این حوزه را تنها برای مدیریت ترافیک به کار می برند محدود نمی شود، مدل عمومی VRP شامل مجموعه ای از مشتریان است که تقاضای هر یک از آنها معلوم و هر مشتری تنها یکبار و به طور کامل خدمت میگیرد و فرض میشود که همه وسایل نقلیه همگن و شروع و پایان هر وسیله یک انبار مشخص است و هدف اصلی کمینه سازی کل مسافت طی شده توسط تمامی وسایل نقلیه است که در بر گیرنده همه حوزه ها می باشد [3]. با توجه به محدودیتهای موجود در دنیای واقعی، محدودیتهایی به مدل کلاسیک اضافه می شود . مروری بر ادبیات شامل مسائل ترکیب ناوگان و مسیریابی در حمل جاده ایی و دریایی توسط هاف و همکاران3 در سال 2010 ارائه شده است. این مطالعه در مجموع 120 مقاله که ترکیبی از تعیین ناوگان و مسیریابی هستند را بررسی و یک مدل ریاضی پایه برای این دسته از مسائل ارائه نموده است.[7]
سونپارچا و همکاران4 در سال 2014 مرور ادبیاتی در زمینههای اندازه ناوگان و مسیریابی وسائل حمل، مسیریابی وسائل حمل با ناوگان غیرمشابه و گسترشهای این مسائل ارائه و مطالعات جدید در این حوزه را بررسی نمودهاند.[13] در حالتی که ناوگان ناهمگن باشد ، ظرفیت وسایل نقلیه متفاوت از هم خواهد بود. در دهههای 1960 و 1970 میلادی عمده تحقیقات انجام گرفته برای حل VRPبر روی روشهای دقیق متمرکز بود که برخی از آنها عبارتند از برنامهریزی پویا و روش تبدیلVRP به TSP5 و فرمولبندی دو اندیسی.[12 ,4] برای مساله مذکور ، با توجه به NP-Hard بودن آن ، الگوریتم های ابتکاری نیز ارایه شده است. ازجمله الگوریتم صرفهجویی که در سال 1964 توسط کلارک و رایت برای حل مساله VRP با محدودیت ظرفیت ارایه شد.[2] این روش با ایجاد مسیرهایی که شامل مرکز و یک نقطه تقاضای دیگر است، شروع شده و در هر مرحله با توجه به بیشترین صرفه جویی ممکن دو مسیر با هم ترکیب میشود.[9 ,8] الگوریتم دیگر بنام الگوریتم مسیریابی کمانی توسط استرن و درور در مورد مسیر یابی ارائه شده است.[14]
الگوریتم طی دو فاز مسیرهای بهینه را محاسبه کرده و با توجه به محدودیتها مراکز تقاضا دسته بندی می-شوند. گدلن و وانگ الگوریتمی به نام الگوریتم صرفهجویی برای مسیریابی کمانی ابداع کردند. [5] در این الگوریتم همه مراکز تقاضا در مسیرهای جداگانه قرار گرفته و با توجه به محدودیتهای موجود ترکیب زوج مسیر های ممکن بررسی و دو مسیری که بیشترین صرفه جویی را ایجاد میکند، با یکدیگر ترکیب میشوند. همچین الگوریتم های فرا ابتکاری متعددی برای حل مساله VRP در ادبیات موضوع بکار گرفته شده است که از جمله میتوان به الگوریتم کلنی مورچگان[15] ، الگوریتم پرندگان و الگوریتم تبرید تدریجی و جستجوی ممنوع اشاره کرد.[10 ,1]
-2 تعریف مساله
در مسالهی VRP که در این مقاله مورد بررسی قرار میدهیم مفروضات بدین صورت است که n گره تقاضا - شهر - داریم. تمام تقاضاها باید برآورده شود.. انبار - دپو - در گره صفر مستقر شده است. از هر گره به گره دیگر یک مسیر مستقیم وجود دارد که این مسیر دارای هزینه سفر مخصوص به خود است. تعداد وسایط ناوگان محدود است و وسایط ناهمگن هستند بدین معنی که هر کدام دارای ظرفیت متفاوتی میباشند.تقاضای گرهها قطعی و از پیش مشخصشده میباشند کل تقاضاهایی که یک ماشین در طول مسیر خود تامین میکند نباید از ظرفیت آن ماشین تجاوز کند . پارامترها و متغیرهای تصمیم مدل به شرح زیر است: n :تعداد نقاط تقاضا - مشتری ها -
: q i مقدار تقاضای گره i ام.
: c ij هزینه سفر مستقیم از گره i به گرهj
: K تعداد کل ماشینهای در دسترس ناوگان : Q k ظرفیت وسیله نقلیه k ام.
: w k هزینه ثابت بکارگیری وسیله نقلیه k ام.
: x ijk متغیر صفر و یک ، اگر از گره i مستقیما به گره j توسط ماشین k ، طی مسیر شود، مقدار 1 میگیرد.
: y k متغیر صفر و یک که در صورتی که از ماشین k استفاده شود مقدار 1 و در غیر این صورت مقدار صفر میگیرد.
بخش اول تابع هدف ، کل هزینه سفر ، و بخش دوم مجموع هزینههای ثابت بکارگیری ماشینها میباشد.،محدودیت های 2 و 3 نشان میدهند که تمام تقاضاها باید برآورده شود و کل تقاضای هر مشتری فقط باید توسط یک ماشین تامین گردد. محدودیتهای 4 و 5 نشان میدهد که ماشینها از دپو شروع به حرکت میکنند و بعد از اتمام سرویسدهی به دپو برمیگردند. محدودیت 6 ، محدودیت موازنه جریان میباشد بدین معنی که کل جریان ورودی به یک گره با کل جریان خروجی از همان گره برابر است. محدودیت 7 نشان میدهد که تقاضاهایی که یک ماشین برآورده میکند نباید از ظرفیت آن ماشین تجاوز کند. محدودیت 8 زیرتورهایی را که شامل دپو نیستند ، حذف میکند. محدودیت 9 رابطه بین خروج ماشین از دپو و متغیر صفر و یک مربوط به هزینه بکارگیری را نشان میدهد. اگر ماشینی از دپو حرکت کند ، سمت راست رابطه 9 از صفر بیشتر میشود و درنتیجه سمت چپ باید مقدار 1 بگیرد و هزینه متناظر با آن در تابع هدف لحاظ شودو در نهایت رابطه10بیان کننده نوع متغییرهای تصمیم مساله است.
-4ارایه الگوریتم ژنتیک برای حل مساله ی ارایه شده
با توجه به ماهیت NP-Hard بودن مساله VRP ، در این بخش یک الگوریتم فرا ابتکاری بر پایه الگوریتم فرا ابتکاری ژنتیک برای مساله VRP توسعه داده شده است. الگوریتم ژنتیک یکی از معروفترین الگوریتمهای فرا ابتکاری است که اولین بار توسط جان هلند و دیگران در سال 1975 ابتداع شد.[5] الگوریتم ژنتیک، از دسته الگوریتمهای تکاملی و جمعیت محور است که در حل مسائل بهینهسازی ترکیبی زیادی موفقیت زیادی کسب کرده است. در این روش، جوابهایی تحت عنوان جمعیت اولیه تولید میشوند و برازندگی این جوابها محاسبه میشود . سپس با توجه به مقدار برازندگیها، از بین این جوابها والدینی برای تولید نسل بعدی انتخاب میشوند. تولید نسل بعدی با استفاده از عملگرهای تقاطع و جهش انجام مییابد و نسل جدید جایگزین نسل قبلی می-شود و این کار تا رسیدن شرط توقف - به طور نمونه تعداد معینی از تولید نسل - ادامه مییابد.
