حل مسئله مسیریابی ظرفیت‌دار با استفاده از تقلیل به مسئله کوله‌پشتی و ارائه روش ابتکاری مبتنی بر کلاسه‌بندی حریصانه

Abstract

مسئله مسیریابی وسایل نقلیه یکی از شناخته­‌شده‌ترین مسائل بهینه‌سازی محسوب می­‌شود که هدف آن، طراحی مجموعۀ بهینه‌ای از مسیرها با کمترین هزینه برای سرویس‌دهی به مشتریان است؛ به‌گونه‌ای که با محدودیت‌های موجود سازگار باشد. کاربرد عملی زیاد و وسعت حوزه این مسئله باعث توجه بسیار زیاد پژوهشگران به این مسئله شده است؛ اما سختی حل این مسئله مشکلاتی را ایجاد کرده که نیاز به وجود روش­‌های حل ابتکاری و فراابتکاری را افزایش داده است. این پژوهش یک روش ابتکاری حریصانه بر پایه روش­‌های ابتدا دسته­‌بندی، سپس مسیریابی، برای حل مسئله مسیریابی وسایل نقلیه ظرفیت­‌دار (CVRP) با استفاده از قابلیت‌های تقلیل مسئله به مسئله کوله­‌پشتی ارائه کرده است. از مزایای این روش می­‌توان به مواردی همچون درنظر­گرفتن توأم معیارهای مؤثر مانند فاصله بین مشتری­‌ها، فاصله تا دپو و تقاضای نقاط در تصمیم­‌گیری، سرعت و کیفیت جواب خوب و توانایی استفاده از مزایای تقلیل اشاره کرد. برای بررسی نتایج و مقایسه آن­ها از نمونه­‌های استاندارد مربوط به CVRPLIB استفاده شده است.