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

مسأله مسیریابی وسیله نقلیه با تحویل و جمع آوری[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).

[1] VRP with Pick-up and Delivery

[2] VRP with Simultaneously Pickup and Delivery

[3] VRP with Mixed Pickup and Delivery