روش دسته بندی گره ها برای بهینه سازی مسئله مسیریابی وسایل نقلیه

در این مطالعه با مسئله مربوط به مسیریابی وسایل نقلیه برای یک شبکه سرویس تعمیرات لوازمخانگی روبرو هستیم. شبکه مذکور متشکل از یک تعمیرگاه مرکزی و تعدادی مشتری است. هر وسیله نقلیه دارای ظرفیت مشخصی برای حمل و نقل دستگاه های خراب است. با توجه به اینکه مسئله مسیریابی وسیله نقلیه با ظرفیت محدود از نوع Np-hard است برای حل مسئله پیچیده ذکرشده در زمان کمتر و با جواب نزدیک به دقیق که شاخصی از کیفیت جواب روش هست، روش های متعدد دقیق و غیردقیقی ارائه شده است. در این مقاله، یک هسته ابتکاری با نام دسته بندی تعمیم یافته جهت استفاده در الگوریتم فراابتکاری بیان می شود. این روش یک روش حل مبتنی بر موقعیت زاویه ای نقاط است وبا توجه به ظرفیت وسیله نقلیه به دسته بندی نقاط می پردازد. ظرفیت هر دسته همان ظرفیت وسایل نقلیه خواهد بود. برای بهینه سازیمسئله از الگوریتم ژنتیک با هسته ی ابتکاری ذکرشده استفاده می شود. ایجاد تنوع در دسته بندی های مختلف باعث جستجوی بیشتر و بهتر در فضای جواب می گردد و منجر به بهبود جواب و تابع هدف خواهد شد.

Keywords:

مسیریابی , شبکه تعمیرات , الگوریتم فراابتکاری , دسته بندی , موقعیت زاویه ای