حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی

مسیریابی وسیله نقلیه با تحویل و جمع آوری

مسأله مسیریابی وسیله نقلیه با تحویل و جمع آوری[1] (VRPPD) بسیار شبیه به مسیریابی وسایل نقلیه با حمل در بازگشت می‌باشد؛ در این مسأله نیز مقداری کالا به مشتریان تحویل داده می‌شود، از مشتریانی نیز کالا دریافت می‌شود. تفاوت اصلی این مسأله در آن است که کالاهایی که از مشتریان دریافت می‌شود به مشتریان دیگری در مسیری تحویل می‌شود و موادی به محل دپو برگردانده نمی‌شود. هدف از ارائه این مدل حداقل نمودن جریان وسایل نقلیه و مجموع زمان سفر می‌باشد. شرط موجه بودن این مسأله آن است که کل کالایی که به مسیر تخصیص داده شده از ظرفیت وسیله نقلیه مفروض تجاوز ننماید و وسیله نقلیه ظرفیت کافی برای تحویل کالا از مشتریان را داشته باشد(ظهره‌وند،2011).

ادبیات موضوع در بخش VRPPD، به دو دسته کلی: VRP با تجدید و تحویل همزمان[2] (VRPSPD)، و VRP با ترکیب تجدید و تحویل[3] (VRPMPD)، تقسیم می‌شوند. در حالت VRPSPD، تمامی مشتری‌ها نه فقط به تحویل کالا، همچنین بطور همزمان به تجدید کالا نیز نیازمندند. یک فرض اصلی در این مسائل عبارت است از اینکه کلیه کالاهای تحویل داده شده از انبار آمده‌اند، و همچنین تمامی کالاهای تجدید شده به انبار باز گردانده می‌شوند. در حالت VRPMPD، بعضی از مشتری‌ها نیازمند تحویل کالا، و برخی دیگر نیازمند تجدید کالا می‌باشند. به عبارت دیگر، VRPMPD بعنوان یک حالتی خاص از VRPSPDمی‌تواند در نظر گرفته شود، که در آن یکی از موارد تجدید یا تحویل برای هر مشتری برابر صفر است.

مین در سال1989، اولین فردی بود که به بررسی VRP بشکل تحویل و تجدید همزمان پرداخت. او یک مسأله عملی را که یک کتابخانه عمومی شامل یک انبار مرکزی، دو وسیله نقلیه، و 22 مشتری می‌شد، را در نظر گرفت. در الگوریتم پیشنهادی او، ابتدا مشتری‌ها در گروه‌هایی طبقه بندی می‌شدند و سپس در هر گروه یک مسأله فروشنده دوره گرد حل می‌شد. در سال 1992 هالس، گونه‌هایی از VRP را مورد مطالعه قرار داد که شامل حمل در بازگشت[4] و تجدید و تحویل می‌شدند. او مسأله دوم را ابتدا با استفاده از الگوریتم ابتدا خوشه‌بندی سپس مسیریابی حل کرد. در مرحله اول، مشتری‌ها به وسایل نقلیه تخصیص می‌یابند، سپس یک دستورالعمل مسیریابی بر اساس روش بهبود 3-opt مورد استفاده قرار می‌گیرد. در سال 1999، گندرائو و همکارانش مسأله فروشنده دوره‌گرد همراه با تجدید و تحویل (TSPPD) را بسط داده‌اند. درابتدا مسأله TSP بدون در نظر گرفتن تجدید و تحویل حل خواهد شد، سپس سفارشات مربوط به تجدید و تحویل روی مسیر مشخص می‌شود(ظهره‌وند،2011).

تحقیقات اندکی بر روی مسأله VRPMPD  صورت گرفته است. گلدن و همکارانش در سال 1985، روشی را بر اساس تقسیم مشتری‌ها به دو دسته تحویل در بازگشت (تجدید) و تحویل در مسیر (تحویل)، معرفی کردند. در فرمول الحاقی آنها از یک فاکتور جریمه ای استفاده می‌شد، که تعداد مشتری‌های تحویلی را در سمت چپ مسیر در نظر می‌گرفت. کاسکو و همکارانش در سال1988، یک دستوالعمل تعبیه بر اساس حجم بار را توسعه دادند. هزینه الحاق برای مشتری‌ها با تجدید برابر با باری است که می‌بایست، در ادامه مسیر تحویل داده شود. صالحی و ناگی در سال 1999، روش الحاقی کاسکو و همکارانش، ورود تحویل‌های در بازگشت به خوشه‌بندی را برخلاف روش‌های قبلی که بصورت تک به تک بود، آزاد کردند. این روش تنها نیاز به اندکی محاسبات بیش‌تر داشت، ولی قابلیت حل مسائل همراه به تجدید و تحویل همزمان را دارا بود. (ظهره‌وند،2011).

2-8-5- مسأله مسیریابی دوره‌ای وسایل نقلیه

دسته دیگر از انواع مسایل VRP که آنرا در این بخش معرفی می‌کنیم عبارت است از مسأله مسیریابی دوره‌ای وسایل نقلیه (PVRP). همانند VRP عمومی، موقعیت تک تک مشتری‌ها به همراه تابع تقاضای قطعی آنها کاملا مشخص است. مسأله PVRP دارای یک افق برنامه‌ریزی مشتمل بر T روز است، و تواتر بازدید برای هر مشتری مشخص می‌کند که در این T-روزه هر چند وقت یکبار می‌بایست بازدید شود. یک جواب برای PVRP مشتمل بر T مجموعه از مسیرها است که در مجموع محدودیت‌های تقاضا و تواتر بازدید را برآورده می‌سازند. در این مسأله، تابع هدف معمولا حداقل نمودن مجموع هزینه‌های تمامی مسیرها در طول دوره برنامه‌ریزی است. واضح است که این دسته از مسایل حداقل به دشواری VRP است. انواع گوناگونی از PVRP در ادبیات موضوع معرفی شده است. یک طبقه‌بندی از انواع گوناگون PVRP را می‌توان در تحقیق که توسط مورگای و وندربک انجام گرفته است، یافت. تابع هدف‌های مختلف از یکدیگر متمایزند، به طور مثال حداقل‌سازی مسافت پیموده شده، زمان انتقال، و یا مجموع هزینه حمل و نقل؛ بنابراین منطقه‌بندی مسیرها، تقسیم یک بار کاری یکسان بر روی ماشین‌ها، و کیفیت سرویس‌دهی می‌تواند بخشی از تابع بهینه‌سازی باشد. تفاوت‌ها اغلب در محدودیت‌ها که می‌توانند به سه دسته کلی تقسیم شوند، رخ می‌دهد: محدودیت‌هایی که شامل (1) برنامه‌ریزی ملاقات‌ها (تواترهای مختلف، محدودیت در روزهای ویژه، و غیره)، (2) نوع تقاضا (ثابت و یا متغیر)، و (3) ناوگان ماشین‌ها (یکسان و یا غیریکسان) می‌شوند (مورگای و وندربک،2006).

.دانلود پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد

 

[1] VRP with Pick-up and Delivery

[2] VRP with Simultaneously Pickup and Delivery

[3] VRP with Mixed Pickup and Delivery

[4] Backhaul