مسأله مسيريابي وسايل نقليه با تقسيم تحويل
بسط ديگري از VRP عبارت است از مسيريابي وسايل نقليه با تقسيم تحويل[1] (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).
روش‌هاي فراابتكاري نيز براي حل SDVRP توصيه مي‌شوند. در سال 2004 هو و هاگلند يك روش جستجو ممنوعه را براي حل مثال‌هايي از SDVRP همراه با پنجره زماني توسعه دادند. آنها يك جواب اوليه را با بررسي مشتري‌ها در يك توالي مشخص و افزودن نزديك‌ترين مشتري مسير داده نشده به آخرين مشتري مسير داده شده در راه‌هاي ممكن، ايجاد مي‌كنند. اگر تقاضاي مشتري از مجموع ظرفيت ماشين تجاوز كند، تقاضا مابين ماشين‌ها تقسيم خواهد شد، و مسير جديدي براي برآورده‌سازي اين تقاضا ايجاد مي‌شود. هنگاميكه برنامه مسيرها ايجاد شد، يك الگوريتم جستجو ممنوعه شروع بكار مي‌كند. در هر تكرار بهترين گزينه در ميان چهار همسايگي انتخاب مي‌شود، و جواب‌هاي همسايگي براي بهبود ارزيابي مي‌شوند. همسايگي‌هاي ارزيابي شده جايگزين يك مشتري در مسير مي‌شوند، تقسيم تحويل بين دو مسير را حذف مي‌كنند و يك تحويل جديد با دو مسير مشابه را ايجاد مي‌كنند، دو مشتري را مابين دو مسير معاوضه مي‌كنند، و يك دستوالعمل 2-opt را بين دو مسير به اجرا مي‌گذارند. آرچتي و همكارانش در سال2006 يك الگوريتم جستجو ممنوعه را براي حل SDVRP ارائه كردند، در جاييكه يك مشتري از يك مجموعه از مسيرهاي سرويس‌دهي حذف مي‌شود و در مسير جديد يا مسير موجودي كه ظرفيت استفاده نشده دارد، وارد مي‌شود (ظهره‌وند،2011).
[1] Split Delivery VRP