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

چکیده

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