استفاده از تبدیل فضا برای حل مسئله فروشنده دوره‌گرد با معیار فاصله جغرافیایی
|
|
|
|
|
|
|
|
نویسنده
|
مرتضوی رضا
|
|
منبع
|
مهندسي برق دانشگاه تبريز - 1396 - دوره : 47 - شماره : 4 - صفحه:1691 -1699
|
|
چکیده
|
یکی از مسائل بهینه‌سازی مهم در حوزه الگوریتم‌های ترکیباتی، مسئله فروشنده دوره‌گرد است. با توجه به کاربردهای فراوان، حل این مسئله مورد توجه پژوهشگران است و به‌طور خاص به‌عنوان یک مسئله مهم تحلیل شبکه در فناوری‌های اطلاعات مکانی کاربرد دارد. علی‌رغم صورت ساده، حل کلی این مسئله از درجه پیچیدگی npسخت است. به‌همین جهت روش‌های ابتکاری زیادی در کاربردهای عملی پیشنهاد شده است. در این مقاله از روش تصویرسازی نقشه برای تبدیل فضا از نسخه‌ای از مسئله فروشنده دوره‌گرد با معیار فاصله جغرافیایی به نسخه ساده‌تر با معیار فاصله اقلیدسی استفاده شده است. در ادامه مقاله یکی از روش‌های ابتکاری حل این مسئله بهبود داده شده است. نتایج تجربی بر روی مجموعه داده‌های واقعی در مقایسه با روش‌های مشابه، نشان‌دهنده برتری روش پیشنهادی به‌لحاظ کیفیت پاسخ و زمان دستیابی به آن است.
|
|
کلیدواژه
|
مسئله فروشنده دوره‌گرد، تبدیل فضا، تصویرسازی نقشه، فاصله غیر اقلیدسی، بهینه‌سازی
|
|
آدرس
|
دانشگاه دامغان, دانشکده فنی و مهندسی, ایران
|
|
پست الکترونیکی
|
r_mortazavi@du.ac.ir
|
|
|
|
|
|
|