مسأله مسیریابی وسایل نقلیه با تقسیم تحویل

بسط دیگری از VRP عبارت است از مسیریابی وسایل نقلیه با تقسیم تحویل (SDVRP) است، در جاییکه یک ناوگان از ماشین‌های یکسان با ظرفیت محدود می‌بایست به یک مجموعه از مشتری‌ها سرویس دهند، هر مشتری می‌تواند بیش از یک بار ملاقات شود؛ برخلاف آنچه که به طور رایج در VRP کلاسیک مفروض بوده است، و تقاضای هر مشتری می‌تواند از ظرفیت ماشین‌ها بیشتر باشد. تنها یک انبار برای کلیه ماشین‌ها موجود است و کلیه آنها می‌بایست مسیر خود را از آن آغاز و به آن ختم کنند. مسأله شامل یافتن یک مجموعه از مسیرهای ماشین است که به تمامی مشتری‌ها سرویس داده شود، بشرطی که مجموع مقادیر انتقال در هر تور از ظرفیت ماشین تجاوز نکند، تقاضای تمامی مشتریان به طور کامل برآورده شود، و کل مسافت پیموده شده حداقل گردد. به عبارت دیگر، در SDVRP محدودیت ملاقات یک باره هر مشتری برداشته شده است. SDVRP یک مسأله NP-Hard است، تا زمانیکه شرایط محدودکننده هزینه‌ها برقرار باشد، و تمامی ماشین‌ها دارای ظرفیتی بزرگتر از دو باشند، در حالیکه اگر کلیه ماشین‌ها دارای حداکثر ظرفیت دو باشند در یک زمان چندجمله‌ای قابل حل است (ظهره‌وند،2011).

روش‌های موجود برای حل SDVRP به سه دسته : روش‌های دقیق، روش‌های ابتکاری، و روش‌های فراابتکاری تقسیم‌بندی می‌شوند.

الگوریتم‌های محدودی در ادبیات موضوع یافت می‌شود، که بطور دقیق SDVRP را حل کرده باشند. یافتن جواب بهینه در مسائل مسیریابی، اغلب به علت نیاز به امکانات محاسباتی فراوان، عملی نیست. بطوریکه تنها سه روش حل دقیق برای SDVRP موجود است. درور و همکارانش در سال1994یک الگوریتم شاخه و کران را برای یک فرمول‌بندی خطی و عددصحیح SDVRP توسعه دادند، که در آن دسته‌ه ای جدیدی از نابرابری‌های معتبر به مسأله افزوده شده‌اند. دستورالعمل آنها بر روی سه مثال در اندازه کوچک همراه با حداکثر 20 مشتری و تقاضاهای متفاوت برای هر یک بررسی شده است. در سال 2000 بلنگوئر و همکارانش یک کران پایین را برای SDVRP بر مبنای مطالعه چند وجهی مسأله ارائه دادند. این مطالعه نابرابری‌های مجاز جدیدی را در بر می‌گرفت. آنها یک الگوریتم صفحات برشی را برای حل مثال‌های اندازه کوچک توسعه دادند. برای مثال‌های با اندازه بزرگتر، مقادیر عددصحیح از روش شاخه و کران بدست می‌آید. لی و همکارانش در سال 2006 یک روش کاملا جدید را برای مسأله مسیریابی وسایل نقلیه چندگانه با تقسیم برداشت (MSDVRP)، بر مبنای مدل برنامه ریزی پویای قطعی و الگوریتم جستجو کوتاه‌ترین مسیر معرفی کردند. بر مبنای چند ویژگی جواب‌های بهینه MSDVRP، آنها مدل پویای اولیه را برای یافتن یک مدل معادل، مجدد فرمول‌بندی کردند. این مدل کوچک شده، با یک شبکه برای‌دار مرتبط است، که سپس توسط الگوریتم کوتاه‌ترین مسیر حل خواهد شد(ظهره‌وند،2011).

به مانند سایر گونه‌های VRP، روش‌های ابتکاری بطور وسیعی در حل SDVRP مورد استفاده‌اند. درور و ترودئو در سال 1989یک روش جستجو محلی را برای حل SDVRP پیشنهاد کردند. روش آنها یک الگوریتم دو مرحله‌ای است، در مرحله اول یک جواب شدنی را برای VRP تولید می‌کند و سپس از روی آن یک حل شدنی را برای SDVRP ایجاد می‌کند. در مرحله اول از سه روال استفاده می‌شود: (i) یک تولید کننده اولیه مسیر برمبنای الگوریتم کلارک و رایت،  (ii)یک تعویض گره بر مبنای جابجایی تک گره و دو گره، (iii) یک بهبود مسیر بر مبنای یک دستورالعمل 2-opt. مرحله بعدی از، (i) یک تعویض 2-split، و (ii) یک روال افزایش مسیر، بهره می‌جوید. برای هر نقطه تقاضا داده شده، 2-split یک همسایگی را ایجاد می‌کند با تمام جایگزین‌ها که نقطه تقاضا را حذف کرده، و آنها را در دو مسیر دیگر که ترکیب ظرفیت آنها برای برآورده‌سازی تقاضا کافیست وارد می‌کند. در هر تکرار، داوطلب با بیش‌ترین صرفه‌جویی انتخاب می‌شود و جستجو زمانی پایان می‌پذیرد، که دیگر بهبودی حاصل نشود. پس از اینکه جستجو محلی به اتمام رسید، یک روال افزایش مسیر، مسیرهای جدیدی را برای حذف تقسیم تحویل‌ها برای کاهش هزینه کلی مسیرها، به جریان می‌افتد(ظهره‌وند،2011).

Split Delivery VRP