مقاله توسعه مدل مسیریابی چندسفره با درنظر گرفتن تحویل چند بخشی و پنجره زمانی

بخشی از مقاله

چکیده

مسأله مسیریابی، از جمله مسائل پیچیده در مهندسی حمل و نقل و مهندسی صنایع در حوزه فرآیندهاي پخش یا جمع آوري کالا است. موضوع این مسأله بهینه سازي، تصمیم گیري درباره مسیریابی براي هر یک از عوامل جابه جا کننده کالاها - ناوگان و نیروي انسانی ویزیتور یا فروشنده - است. مدل کلاسیک این مساله شامل یک یا چند دپو دردسترس براي تخصیص مشتریان به این دپو - ها - می باشد. ایجاد مسیرهایی براي خدمت رسانی به مشتریان به نحوي که هزینه هاي سفر کمینه شود، هدف این مساله است. در این تحقیق سعی شده است تا با توسعه حالت کلاسیک مساله VRP ،مدلی براي استفاده در شرایط واقعی فراهم شود. مدل حاضر، براساس سناریوهاي چند سفره بودن وسیله نقلیه و همچنین تحویل سفارشات به صورت تقسیم پذیر، شکل گرفته است.

.1 مقدمه

مساله 1VRP شامل یک یا چند محل ثابت است که دپوها در این محل ها استقرار یافتهاند . این دپوها میتوانند کارخانه، انبار مرکزي و یا خرده فروشان باشند. تعدادي مشتري هم براي خدمت رسانی به آن ها در دسترس است و کار سرویس رسانی به آن ها توسط ناوگانی از وسایل نقلیه صورت میگیرد که سفر خود را از انبارها شروع کرده و پس از طی مسیري، کالا را به مشتري تحویل داده و دوباره به انبار بازگردد . همان گونه که گفته شد، هدف تعیین بهینه مسیرهاي مناسب براي تحویل کالاهاست به نحوي که هزینه هاي ثابت و هزینه هاي حمل و نقل حداقل گردد. این مسأله از نوع مسائل دشوار - NP-hard - است که در دهه گذشته براي حل آنها از الگوریتم هاي ابتکاري و فرا ابتکاري مختلفی استفاده شده است.

سطح یک مربوط است به حمل و نقل بین تسهیلات مرتبه 0 و مرتبه 1، سطح دو مربوط است به حمل و نقل بین تسهیلات مرتبه 1 و مرتبه 2 و سطح سه مربوط است به حمل و نقل بین تسهیلات مرتبه 2 و مشتریان مرتبه .3 همانطور که مشخص است، در این مساله مشتریان باید به خرده فروشان، خرده فروشان به انبارهاي مرکزي و انبارهاي مرکزي به کارخانهها تخصیص داده شوند و بر اساس این تخصیصها، مسیرهاي بهینه بین آنها براي حمل کالاها مشخص شوند به نحوي که هزینه نهایی استفاده از وسایل نقلیه و همچنین هزینه هاي مربوط به سفر کمینه شود.

فرضیات کلی مساله VRP کلاسیک به این صورت است:

    وجود یک یا چند دپو براي عرضه محصولات

    وجود مشتریانی که باید به این دپوها تخصیص داده شوند

    وجود ناوگانی از وسایل نقلیه ظرفیت دار براي خدمت رسانی به مشتریان

مساله VRP با مساله - Location Routing Problem - LRP بسیار شبیه به هم هستند و در واقع می توان گفت که مساله مسیریابی، شاخه اي از مساله مکانیابی- مسیریابی است. تفاوت عمده اي که این دو مساله با یکدیگر دارند، محل استقرار دپوها میباشد. در مساله مکانیابی-مسیریابی، چندین محل بالقوه براي استقرار دپوها در اختیار داریم و مسیریابی را باید همزمان با بحث مکانیابی دپو انجام داد. در حالی که در مساله VRP، محل دپوها از قبل مشخص است و تنها باید مسیرهایی بین این دپوها و مشتریان ایجاد گردد. از این رو، محققین حوزه لجستیک و زنجیره تامین، براي انجام پژوهش هاي خود سعی دارند تا از موضوعات LRP و VRP به طور همزمان بهره ببرند. به همین جهت میتوان این مسائل را به طور زیر طبقه بندي کرد: [1]و[3]

دسته بندي بر اساس روش حل

1.    روش هاي دقیق

2.    روش هاي ابتکاري

3.    روش هاي فراابتکاري

دسته بندي بر اساس نوع مساله

1.    VRP با وسایل نقلیه بدون ظرفیت

2.    VRP با انبارهاي بدون ظرفیت

3.    VRP ظرفیت دار

4.    VRP دو سطحی

5.    مساله مسیریابی کامیون و تریلر

6.    VRP با چند تابع هدف یا توابع ویژه

7.    ویژگی هاي اضافه شده به گره ها و وسایل نقلیه

8.    VRP چند دوره اي

9.    VRP و مدیریت موجودي

10.    VRP با داده هاي نامعلوم

با وجود وسعت کاربرد مساله VRP، این مساله به صورت فزایندهاي در طول این سالها گسترش پیدا کرده است و براي نزدیک شدن آن به دنیاي واقعی، محدودیتهاي مختلفی به آن اضافه شده است که در قسمت مرور ادبیات بیشتر به آن پرداخته میشود. یکی از حالت هاي سلسله مراتبی بودن VRP بحث چند سفره یا چند وسیله نقلیه بودن مساله است. در حالت کلاسیک مسیریابی، هروسیله نقلیه مجاز است تنها در یک مسیر مورد استفاده قرار بگیرد. اما عواملی مانند قوانین شهري، محدودیت در مسیر و جاده ها، ظرفیت وسیله نقلیه و ... می توانند باعث این امر شوند که این فرض مطلق نادیده گرفته شود و وسیله نقلیه بتواند در چند مسیر حرکت کند.

به عنوان مثال فرض کنید کالایی که قرار است تحویل داده شود فاسدشدنی باشد و وسیله نقلیه مجاز به انجام سفرهاي طولانی نباشد. بنابراین، هر وسیله نقلیه میبایست در یک روز کاري به جاي طی کردن یک مسیر، چندین مسیر کوتاه را براي تحویل سفارشات مشتریان با توجه به بهینگی مسیرها انتخاب کند. تحویل چند بخشی1 یکی از مواردي است که به تازگی توجه محققان را به خود جلب کرده است.

در حالت کلاسیک فرض بر این بوده است که تقاضاي مشتریان در یک روز کاري و در اولین خدمتی که از وسیله نقلیه می گیرند باید به طور کامل برآورده شود. اما در حالت تحویل چند بخشی، در صورتی که مشتري این اجازه را بدهد که تقاضاي خود را در چند قسمت تحویل بگیرد، مسیریابی ها و تعداد وسایل نقلیه که به خدمت گرفته شده اند تحت تاثیر این موضوع قرار خواهند گرفت و در کاهش هزینه هاي مربوط به مسیر و وسیله نقلیه موثر خواهد بود. به طور مثال در شکل [28] 2، حالت - a - مربوط به حالتی است که مجاز به تحویل چند قسمتی نباشیم و در حالت - b - این اجازه به ما داده شده است. بنابراین تقاضاي مشتري گره 6 و 5 در دو نوبت براورده می شود و این امر باعث می شود تا وسایل نقلیه به کار گرفته شده کاهش یابد.

البته این مساله مستلزم این است که رضایت مشتریان نیز درنظرگرفته شود. به همین منظور باید یک پنجره زمانی هم در مساله درنظرگرفته شود تا این تحویل هاي چند بخشی به این گونه نشود که مشتریان ناراضی باشند. یک پنجره زمانی شامل حد پایین و یک حد بالا میباشد. پنجره زمانی بیانگر این است که سفارشات مشتري نباید زودتر از حد پایین و دیرتر از حد بالا به دست مشتري برسد. بنابراین اگر وسیله نقلیه در سفر خود زودتر از حد پایین پنجره زمانی به مشتري برسد باید صبر کند تا زمان مقرر فرارسد. همچنین اگر دیرتر از حد بالا و مشتري برسد میبایست جریمهاي بابت این دیرکرد پذیرا باشد. پس برنامهریزي سفرها باید به گونهاي باشد که علاوه بر این که هزینههاي مردم در سفرها را کاهش میدهیم باید براي افزایش رضایت مشتریان نیز حتیالمقدور سفارشات را در پنجره زمانی مربوط به مشتریان تحویل دهیم.

در دنیاي رقابتی امروز، دغدغه تمامی شرکت ها این است که هزینه هاي خود را کاهش دهند و یکی از تصمیم گیري هاي مهم براي کاهش هزینه ها در بخش لجستیک است که تصمیمات درست در بخش مکانیابی و مسیریابی منجر به کاهش هزینه هاي بسیاري خواهد شد. باتوجه به مطالعات صورت گرفته در زمینه هاي کارشده در بخش هاي مختلفVRP وLRP ، تحقیق حاضر با ترکیب مساله مسیریابی چند سفره و تحویل چند بخشی به همراه پنجره زمانی، تلاش کرده است تا این خلاء تحقیقاتی را درنظر بگیرد.

2.    سابقه تحقیق

براي مدتی طولانی دو مساله تصمیم گیري مکانیابی و مسیریابی به طور جداگانه بررسی می شده، اما پیشرفت مداوم در تکنیک هاي بهینه سازي امکان ادغام این دو مساله را فراهم ساخت . ایده ترکیب مکانیابی انبارها و مسیریابی وسایل نقلیه به 50 سال قبل برمی گردد. اهمیت درنظرگرفتن توام مکان یابی و مسیریابی براي اولین بار توسط Salhi وهمکاران - 1989 - مطرح شد. [2] پرودهن و پرینس [3] در بررسی که انجام داده است، به مطالعه مروري روي مقالات کار شده از سال 2007 به بعد پرداخته است و در مقاله خود به مطالعه مروري نگی و سالهی [4] اشاره کرده است و از بررسی مقالات از قبل سال 2007 اجتناب کرده است.

در ادمه به برخی از مقالات کارشده در بخش هاي مختلف مکان یابی- مسیریابی در سال هاي اخیر اشاره شده است و مقالات قدیمی تري که نگی و سالهی [4] بررسی کرده اند آورده نشده است: فاضل زرندي و همکاران [5] یک مساله MDCLRP با زمان سفر فازي بین دو نقطه را معرفی کرده اند. این مسئله با در نظر گرفتن ظرفیت محدود وسایل نقلیه، مشتریان با تقاضاي معین، هزینه باز انبارداري، پنجره زمانی براي برآورد تقاضاي مشتریان، وجود نقاط بالقوه براي جایابی انبارها به حل این مسئله پرداخته است و با روش فوق ابتکاري - SA - Simulated Annealing حل نموده اند و پس از اعتبار سنجی آن، این روش را روشی غنی و استوار و قابل تعمیم به دنیاي واقعی معرفی کرده است.

چابچوب و همکاران [6] نیز مساله MDCLRP بررسی کرده اند و از روش جستجوي محلی تکراري - ILS - براي حل آن استفاده کرده است. ویژگی اساسی آن بهبود حل با تشدید کردن فضاي حل با جستجوي محلی از طریق استفاده از ساختارهاي مختلف همسایگی ها است. این رویکرد با رویکرد هیورستیک تابو مقایسه عددي شده است. وینسنت و همکاران [7] روش فوق ابتکاري - SA - Simulated Annealing را براي مساله CLRP استفاده کرده اند. این روش با یک حل خاص کدگذاري شده است به طوریکه فضاي حل بزرگتري را به منظور یافتن حل بهتر تصمیمات مکان یابی و مسیر یابی به طور همزمان ارائه دهد. این روش می تواند براي مسائل مختلفی که داراي چند سطح تصمیم گیري مثل LRP ، مسائل چند سطحی مکان یابی و ... کاربرد داشته باشد.

این روش نه تنها عملکرد بهتري نسبت به روش هاي ابتکاري دیگر دارد، بلکه براي مسائل با اندازه واقعی، زمان منطقی تري را صرف می کند. استنگر و اشنایدر [8] مساله LRPSO مطرح کرده اند. این مقاله به بررسی تقاضاي شرکت هاي باربري کوچک با استفاده از مدل مکان یابی-مسیریابی می پردازد و بحث اسنفاده از انبارهاي قردادي را براي کاهش هزینه ها ارائه داده اند . روش حل، حل ابتکاري ترکیبی بر مبناي SA براي مرحله مکان یابی و جستجوي محلی متغیرها براي مسیریابی است.