ارزیابی کارایی الگوریتم های تخصیص در حل مساله مسیریابی وسایل نقلیه با چند دپو

مسئله مسیریابی وسایل نقلیه با چند دپو (MDVRP) یکی از نیازهای عمده صنعت حمل و نقل به شمار می آید. با توجه به پیچیدگی ذاتی این دسته از مسائل، روش های تقریبی که ابتدا خوشه بندی و سپس مسیریابی را انجام می دهند، برای مسائل با ابعاد بزرگ امیدوارکننده به نظر می رسند. مرحله اول، یعنی خوشه بندی، معمولا با استفاده از الگوریتم های تخصیص حل می شود. هزینه کلی یک راه حل برای مسئله به الگوریتم تخصیصی که در مرحله اول به کار رفته، وابسته است. این تخصیص باید به گونه ای باشد که در مسیریابی نهایی، صرفه جویی بیشتری در مسافت و زمان سفر حاصل شود. در این پژوهش، چندین روش تخصیص از جمله تخصیص به روش k-میانگین، نزدیکترین دپو و پیمایشی مورد بررسی قرار گرفته و بر روی چند نمونه با اندازه های مختلف آزمایش شده است. برای ارزیابی عملکرد این روش ها، الزم است که برای مشتریان تخصیص یافته به هر دپو، یک روش مسیریابی مشابه به کار گرفته شود تا کاراترین روش تخصیص برای استفاده انتخاب شود. در این تحقیق، از ترکیب ابتکاری الگوریتم پیمایشی و صرفه جویی برای مسیریابی استفاده شده است. نتایج حاصل از مقایسه روش های تخصیص نشان می دهند که تخصیص به روش نزدیکترین دپو و k-میانگین نتایج بهتری نسبت به تخصیص پیمایشی ارائه داده اند.

کلیدواژه ها:

مسیریابی وسایل نقلیه با چند دپو ، تخصیص ، حمل و نقل