انجمن کامپیوتر ایران

مسئله مسیریابی وسیله نقلیه یکی از مهمترین مسائل بهینه¬سازی ترکیبیاتی است. با وجود تلاش¬های زیادی که برای حل کردن این مسئله با روش¬های مختلف صورت گرفته است، متاسفانه تابحال هیچ روشی برای حل این مسئله ارائه نشده است که بتواند راه¬حل بهینه هر نمونه از این مسئله را در بدترین حالت در زمان چندجمله¬ای پیدا کرده و این بهینگی را نیز ضمانت کند.از اینرو، با توجه به اینکه کامپیوترهای امروزی در حل دقیق نمونه¬های بزرگ مسائل با پیچیدگی زمانی بزرگتر از چندجمله¬ای با مشکل مواجه هستند، ناچارا برای حل نمونه¬های بزرگ مسئله مسیریابی وسیله نقلیه باید از روش¬های حل تقریبی مانند روش¬های فرا ابتکاری استفاده کرد. در این مقاله، مسئله مسیریابی وسیله نقلیه با استفاده از الگوریتم جستجوی گرانشی ترکیبیاتی که نسخه تعمیم¬یافته الگوریتم جستجوی گرانشی پیوسته برای حل مسائل بهینه¬سازی ترکیبیاتی است، حل شده است. نتایج پیاده¬سازی الگوریتم و مقایسات، کاراییتقریبا مناسب روش پیشنهادیرا در حل مسئله مسیریابی وسیله نقلیه نشان می¬دهد.