جستجوی ترکیبی با کاهش همسایگی برای مسئله چند فروشنده دوره گرد

چکیده

ما یک الگوریتم ترکیبی موثر با کاهش همسایگی برای حل مسئله چند فروشنده دوره گرد (mTSP) ارائه می‌کنیم. اهداف این مشکل بهینه سازی یکی از دو هدف می باشد: به حداقل رساندن کل مسافت طی شده (حداقل mTSP) یا به طولانی ترین تور را به حداقل برساند (حداکثر mTSP). الگوریتم پیشنهادی هیبرید می شود بهینه سازی بین-تورها با جستجوی محله کارآمد بر اساس جستجوی تابو و بهینه سازی درون توری با استفاده از EAX اکتشافی فروشنده دوره گرد. اختصاص داده شده استراتژی کاهش محلی برای جلوگیری از بررسی راه حل های نامزد غیر امیدبخش و در نتیجه سرعت بخشیدن به جستجوی محلی معرفی شده است. نتایج آزمایش‌های محاسباتی گسترده بر روی 41 نمونه محبوب منابع و 36 نمونه بزرگ جدید از چندین مورد نشان داده شده است. مقایسه با روش های پیشرفته در ادبیات، رقابت پذیری بالای الگوریتم پیشنهادی را نشان می دهد. آزمایش‌های اضافی در مورد اعمال یک اکتشافی TSP کلاسیک به mTSP حداقل نمونه ها نتایج عالی را نشان می دهند.

کلمات کلیدی: فروشنده دوره گرد; چند فروشنده دوره گرد؛ اکتشافی ترکیبی