نشریه تخصصی مهندسی صنایع ،دوره 48، سال 1393، ویژه نامه دهمین کنفرانس بین المللی مهندسی صنایع ، از صفحه 11 تا 18
مسئله مسیریابی وسیله نقلیه چندانباري ظرفیت دار با در نظرگرفتن مسیر
بین انبارها

مصطفی ستاك*1 ، سهیل جلیلی بوالحسنی2، حسین کریمی3 و بهارك قربانی4
استادیار رشته مهندسی صنایع- دانشکده مهندسی صنایع- دانشگاه صنعتی خواجه نصیرالدین طوسی
دانش آموخته فوق لیسانس مهندسی صنایع- دانشکده مهندسی صنایع- دانشگاه صنعتی خواجه نصیرالدین طوسی
3دانشجوي دکتراي مهندسی صنایع- دانشکده مهندسی صنایع- دانشگاه صنعتی خواجه نصیرالدین طوسی
4دانشجوي فوق لیسانس مهندسی صنایع- دانشکده مهندسی صنایع- دانشگاه صنعتی خواجه نصیرالدین طوسی

چکیده
در این مقاله، مسئله مسیریابی وسیله نقلیه چندانباري، با در نظرگرفتن مسیر بین انبارها بررسی می شود که در آن وسایل نقلیه می توانند در دپوهاي میانی، بارگیري مجدد انجام دهند. وسایل نقلیه با بار کامل، از دپوي مبدأ شروع به حرکت مـی کننـد و مشـتریان را تـا پایـان بـارسرویس می دهند. آنها سپس می توانند براي بارگیري مجدد به دپوي میانی عزیمت کنند و سرانجام براي اتمام مسیر خود به دپوي مبـدأ بـازگردند. براي این مسئله، یک مدل ریاضی برنامه ریزي عدد صحیح مختلط معرفی می شود. هدف مسئله، یافتن مسیر براي وسایل نقلیه به گونه اي است که بدون نقض کردن محدودیت ظرفیت وسایل نقلیه، هزینه کل سفر و هزینه بارگیري هاي مجدد در دپوهاي میانی کمینه شـود . مسـئ له حاضر توسط حل کننده سیپلکس در نرم افزار گمز 5,23 و رویکردهاي الگوریتم ژنتیک و جستجوي ممنوع حل می شود. نتـایج محاسـباتی بـه دست آمده، کارآیی الگوریتم هاي پیشنهادشده را از نظر زمان حل و کیفیت جواب نشان می دهند.

واژه هاي کلیدي: مسئله مسیریابی وسیله نقلیه چندانباري، مسیر بین انبارها، دپوي میانی، بارگیري مجدد، الگوریتم ژنتیک، جستجوي ممنوع

مسئله مسیریابی وسیله نقلیه چندانباري1 در دنیاي واقعی، کاربردهاي فراوانی دارد، زیرا اغلب در زنجیره هاي تأمین و یا شهرهاي بزرگ براي ذخیره و توزیع کالاها از بیش از یک انبار استفاده می شود. هر مسئله مسیریابی وسیله نقلیه چندانباري را می توان به سه قسمت تجزیه کرد: قسمت اول مشخص می کند که هر مشتري توسط کدام انبار سرویس داده شود. قسمت دوم، تعیین مسیر سرویس دهی یا مسیریابی است. قسمت آخر نیز تعیین اولویت در سرویس دهی است که تقدم و تأخر ملاقات مشتریان در هر مسیر را مشخص می کند.
مقدمه Email: [email protected] ،84063373 :نویسنده مسئول: تلفن *

مسئله مسیریابی وسیله نقلیه چندانباري، با در نظر گرفتن مسیر بین انبارها2 مقوله یک شرکت حمل ونقل است که قصد استفاده از وسایل نقلیه کمتري (در حالت بهینه یک وسیله نقلیه) دارد که قادر به سفرهاي طولانی مدت براي خدمت رسانی به همه مشتریان باشند. این ویژگی مسئله، وقتی اتفاق می افتد که وسیله نقلیه، اجازه بارگیري مجدد در دپوهاي میانی در طول مسیر خود را قبل از بازگشت به دپوي مبدأ داشته باشد. این مقوله، نه تنها هزینه هاي سرمایه گذاري روي ناوگان حمل ونقل را کاهش می دهد، بلکه منجر به صرفه جویی در مصرف سوخت و آلودگی هواي کمتر می شود.
با توجه به اطلاعات ما، این مقاله اولین مطالعه اي است که یک مدل برنامه ریزي عدد صحیح مختلط مبتنی بر گره براي MDVRPIDR با معرفی نوع جدیدي از محدودیت هاي حذف زیرتور ارائه می دهد.

مرور ادبیات
مسئله مسیریابی وسیله نقلیه چندانباري، اولین بار توسط سامیچراست و مارخام [1] فرمول بندي شد. هر چند محققان دیگري نظیر تیلمن و کین [2] و جیلت و جانسون [3] قبل از آنها این مسئله را مطرح کرده و براي آن، روش هاي حل ابتکاري ارائه کرده بودند، بدون آنکه مدل ریاضی براي مسئله پیشنهاد کنند. گیوسا و همکاران [4] مسئله مسیریابی چندانباري با پنجره زمانی را بررسی کردند. همچنین نجی و سالهی [5] مسئله مسیریابی چندانباري با بارگیري و تخلیه همزمان را تحلیل کردند.
محققان زیادي سعی در ارائه روش هاي حل ابتکاري و کارآ براي این دسته از مسائل داشته اند، طوري که بیش از 85 درصد روش هاي حل ارائه شده براي مسئله MDVRP به صورت ابتکاري یا فراابتکاري است. تانگیا و سالهی [6]، هو و همکاران [7] و دوندو و سردا [8] روش هاي ابتکاري مبتنی بر الگوریتم ژنتیک براي حل مسئله مزبور را توسعه دادند. در مطالعه نجی و سالهی [5] نیز MDVRP با مراحل خدمت دهی، جمع آوري و تحویل ارائه شد و حل این مسئله با استفاده از یک الگوریتم ابتکاري بر مبناي برخی رویکردهاي جستجوي همسایگی مانند opt-2 و معاوضه بررسی شد.
کرویر و همکاران [9] یک فرمول بندي مبتنی بر مسیر براي حالتی از مسئله مسیریابی وسیله نقلیه چندانباري معرفی کردند که در آن وسایل نقلیه همگن در دپوها مستقر هستند. وسایل نقلیه، دپوي مرکزي خود را ترك می کنند و تقاضاي مجموعه اي از مشتریان را برآورد می کنند. سپس براي بارگیري مجدد یا به دپوي مرکزي خود برمی گردند یا یک دپوي میانی را ملاقات می کنند. آنها سپس این مسئله را توسط یک الگوریتم ابتکاري الحاق کننده جستجوي ممنوع و برنامه ریزي عدد صحیح حل کردند. جوردن و بارنز [10] و جوردن [11] حالت ساده تري از مسئله را بررسی می کنند که در آن، تقاضاي مشتریان، همگی مساوي بوده و مسیرهاي بین دو دپو به صورت رفت و برگشتی هستند. آن ها این مسئله را توسط الگوریتم حریصانه حل کردند. تارانتیلیس و همکاران [12] یک نام جایگزین براي مسئله معرفی شده توسط کرویر و همکاران [9] به نام مسئله مسیریابی وسیله نقلیه با تسهیلات میانی بارگیري مجدد، پیشنهاد کردند تا هر دو مقوله، نقش بارگیري مجدد تسهیلات میانی و استفاده از یک دپوي مرکزي براي وسایل نقلیه را پررنگ تر کنند. آنها همچنین یک روش جستجوي همسایگی ترکیبی براي این مسئله ارائه کرده و آن را با رویکرد سه مرحله اي حل کردند. ایده آزادي در ملاقات دپوي ابتدایی و پایانی با عنوان “تخصیص انعطاف پذیر” توسط کک و همکاران [13] مطرح شد. بر اساس این تحقیق، دو حالت جدید از مسئله مسیریابی ظرفیت دار مورد مطالعه قرار گرفت. حالت اول، به بررسی مسئله مسیریابی ظرفیت دار با در نظر گرفتن محدودیت هاي ظرفیت وسایل حمل و حداکثر طول مجاز هر مسیر مربوط می شود، اما در مسئله دوم علاوه بر محدودیت هاي موجود در حالت اول به واسطه قابلیت هاي سیستم هاي هوشمند حمل ونقل، هر وسیله نقلیه مجاز به بارگیري مجدد در دپوهاي دیگر بوده و دپوي پایانی در هر مسیر، می تواند متفاوت از دپوي اولیه باشد.

شرح و مدل سازي مسئله
مسئله مسیریابی وسیله نقلیه چندانباري با در نظر گرفتن مسیر بین انبارها حالت خاصی از MDVRP است که در آن وسیله نقلیه با بار پر، دپوي مبدأ را ترك می کند و در طول یک دوره زمانی، کالا را به مشتریان تحویل می دهد. به محض اتمام بار ،وسیله نقلیه براي بارگیري مجدد، یکی از دپوها را ملاقات می کند. این فرآیند تا سرویس دهی همه مشتریان ادامه می یابد. سپس وسیله نقلیه به دپوي مبدأ باز می گردد. شکل (1) مثالی از MDVRPIDR با سه دپو و شش مشتري را نشان می دهد. مسیر وسیله نقلیه در این مثال، به صورت 0 6 B 5 4 3 A 2 1 0 است؛ بنابراین سه زیرمسیر براي سرویس دهی به همه مشتریان لازم است. اولین زیرمسیر از دپوي 0 شروع می شود، به مشتریان 1 و 2 می رود و سپس براي بارگیري مجدد، به دپوي A می رود. پس از بارگیري ،وسیله نقلیه به مشتریان 3 و 4 و 5 می رود و سپس براي بارگیري مجدد به دپوي B می رود. مشابه همین روند، زیرمسیر سوم به مشتري 6 ادامه پیدا می کند و سپس وسیله نقلیه براي اتمام مسیر خود به دپوي 0 باز می گردد.

شکل 1: مثالی از MDVRPIDR با سه دپو و شش مشتري MDVRPIDR به صورت زیر فرمول بندي می شود. فرض کنید G V, A یک گراف جهت داري باشد که در آن V v0,v1,…, vnd1 مجموعه رئوس گراف است که 0v و 1vnd به ترتیب بیانگر دپوي مبدأ و دپوي مقصد هستند(مکان آنها یکی است)، Vc v1,…,vn
Vd vn1,vn2,…,vnd ، مجموعه مشتریان است
مجموعه d، دپوي میانی است و
Avi ,v j :vi ,v j V,i  j مجموعه یال هاي گراف است. هر یال i, j)V) یک هزینه سفر به ازاي هر واحد زمانی cij و زمان سفر tij دارد که نامعادله مثلثی قوي در آن برقرار است (tij t jk tik ). دپوي مبدأ و همه دپوهاي میانی، مقدار عرضه نامحدود کالا دارند. هر دپوي میانی d Vd، هزینه بارگیري مجدد CID دارد. یک وسیله نقلیه با ظرفیت Q مستقر در دپوي مبدأ موجود است. هر مشتري iVc تقاضاي معلوم qi دارد. در زیر، متغیرهاي مورد استفاده در فرمول بندي بیان می شوند:
مقدار تقاضاي تجمعی برآوردشده توسط
uوسیله نقلیه پس از ملاقات گره i iV ،i
اگر وسیله نقلیه از گره i به گره j برود، 1xij در غیر این صورت، 0
تعداد دفعاتی که دپوي میانی d براي …,2,1,0z  بارگیري مجدد به کار می رود: d
با این فرضیات، مدل ریاضی به صورت زیر است:
MiniV jV xijtijcij  dVdCIDzd
ji
مقید به محدودیت هاي:
xij 1 iVc
jV
ji
jVc xv0, j 1
iVc xi,vnd1 1xdj  zd d Vd (5)
jVc
iV xij iV x ji 0 jV (6)
i ji j
ijji i{v0,Vd } jVci{Vd ,vnd1} jVc (7)
ui  qi iVc (8)
ui Q iVc (9)
ui Q(qi Q)xji iVc,

j{v0,Vd} (10)
u j ui q j QQxij
(Qq j qi )x ji
iVc ,

jVc (11)
xvnd1, j 0 jV (12)
xi,v0 0 iVc (13)
ui  0 iV \ Vc (14)
xij 0,1
i, jV,i  j (15)
zd  0,1,2,… d Vd (16)
iVc ui  0 (17)
 x   x 0
رابطه (1) تابع هدف مدل به معنی کمینه کردن هزینه خدمت دهی کلی مشتریان است که عبارت است از:
xijtijcij هزینه سفر
iV jV
ji
هزینه تعداد بارگیريهاي مجدد CIDzd
dVd معادله (2) ایجاب می کند که هر مشتري فقط یک خروجی داشته باشد. محدودیتهاي (3) و (4) به ترتیب موجب می شوند وسیله نقلیه فقط یک بار دپوي مبدأ و دپوي مقصد را ملاقات کند. محدودیت هاي (5) باعث میشوند وسیله نقلیه از هر دپوي میانی به تعداد دفعاتی که آن دپو براي بارگیري مجدد استفاده میشود، عبور کند. محدودیت هاي (6) بیانگر حفظ جریان در گرهها هستند. محدودیت هاي (7) ایجاب می کنند که حفظ جریان در دپوها از طریق وادار کردن وسیله نقلیه به بازگشت به دپوي مبدأ باشد. محدودیتهاي (8) تا (11) محدودیت هاي حذف زیرتور و ظرفیت هستند. مقدار ui باید حداقل به اندازه تقاضاي مشتري i (8) و کمتر از ظرفیت وسیله نقلیه (9) باشد. اگر مشتري i، اولین مشتري یک تور باشد، ui مساوي تقاضاي این مشتري است. این مطلب از طریق سه محدودیت (8)، (9) و (10) بیان می شود. فرض کنید که i مشتري اول تور نیست. آنگاه ui باید برابر با جمع تقاضاهاي برآورد شده بین دپو (میانی یا مبدأ) و مشتري i باشد، یعنی اگر مشتري j بلافاصله پس از مشتري i سرویسدهی شود، u j باید مساوي تقاضاي برآوردشده روي تور از دپو به i به اضافه مقدار سفارش داده شده توسط j باشد. این موضوع در محدودیت (11) نهفته است. حتی وقتی j بلافاصله پس از i نباشد، محدودیت (11) معتبر است. محدودیت هاي (12) و (13) به ترتیب جریان کالاي وسیله نقلیه را در دپوي مقصد و مبدأ ختم و شروع می کنند. محدودیت هاي (14) متغیر ui را در دپوها برابر صفر قرار می دهند.
محدودیتهاي (15)، (16) و (17) نشان می دهند که xij متغیر صفر و یک ،zd متغیر عدد صحیح و ui متغیر غیر صفر هستند.

الگوریتم هاي حل فرا ابتکاري
از آنجا که مسئله مسیریابی وسیله نقلیه، یک مسئله NP-hard است، با افزایش ابعاد مسئله زمان حل آن به شکل نمایی افزایش می یابد. براي کاهش زمان محاسباتی در مسائلی با ابعاد بزرگ تر ،دو رویکرد فراابتکاري مبتنی بر الگوریتم هاي ژنتیک3 و جستجوي ممنوع4 براي حل این مسئله پیشنهاد می شود. ابتدا باید ساختاري به منظور دست یابی به جواب هاي اولیه شدنی ایجاد کرد. بدین منظور، ابتدا یک توالی از مشتریان تولید می شود. توالی مورد نظر، وارد فرآیندي می شود که طبق آن براي جلوگیري از تجاوز از حداکثر ظرفیت وسیله نقلیه ،مشتریان دسته بندي می شوند. براي این کار، با شروع از مشتري اول در توالی، تقاضاها با هم جمع می شوند. این کار تا زمانی که جمع تقاضاها از ظرفیت وسیله نقلیه تجاوز نکند، ادامه می یابد. به محض اینکه جمع تقاضاها از ظرفیت وسیله نقلیه بیشتر شد، وسیله نقلیه براي بارگیري مجدد به یک دپوي میانی می رود. سپس این روند بار دیگر تکرار می شود و تا سرویس دهی به همه مشتریان ادامه می یابد. در نهایت یک جواب شدنی به صورت شکل (2) نمایش داده می شود.
.

شکل
2
:
شدنی

جواب

تولید

روند



قیمت: تومان


دیدگاهتان را بنویسید