استفاده از تبدیل فضا برای حل مسئله فروشنده دوره گرد با معیار فاصله جغرافیایی

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

Keywords:

مسئله فروشنده دوره گرد , تبدیل فضا , تصویرسازی نقشه , فاصله غیر اقلیدسی , بهینه سازی