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

بسط دیگری از 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