نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد / دانشگاه بجنورد

2 عضو هیئت علمی / دانشگاه بجنورد

10.22105/dmor.2021.272989.1325

چکیده

هدف این مقاله ارائه یک الگوریتم ژنتیک بهبود یافته برای حل مسئله مکان‌یابی بدون ظرفیت هاب با تخصیص تکی است. روش‌های پیشین حل مسئله کمتر به گوناگونی جواب‌ها در جمعیت توجه داشته‌اند، و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند، و در سایر اجراها در بهینه محلی گرفتار می‌شوند. روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت، و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده می‌کند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسائل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریع‌تر روش پیشنهادی شد، و زمان حل مسئله را در مجموع برای مسائل بزرگ کاهش داد. ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (AP) نشان داد که بهبودهای انجام شده ضمن حفظ سرعت اجرا، کارایی الگوریتم ژنتیک را در دستیابی به جواب بهینه برای مسائلی به بزرگی 200 گره از 2% به بیش از 85% افزایش می‌دهد. این مطالعه نشان داد که الگوریتم‌های فرا ابتکاری و نسخه‌های بهبود یافته آن‌ها می‌توانند روش‌های مناسبی برای حل انواع مسائل مکان‌یابی هاب در زمان کوتاه و محدود باشند.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Improved Genetic Algorithm with Diversity and Local Search for Uncapacitated Single Allocation Hub Location Problem

نویسندگان [English]

  • Mona Alizadeh Firozi 1
  • Vahid Kiani 2
  • Hossein Karimi 2

1 Master of Science Student / University of Bojnord

2 Assistant Professor / University of Bojnord

چکیده [English]

The purpose of this paper is to propose an improved genetic algorithm to solve the problem of Uncapacitated Single-allocation Hub Location. Previous methods have paid less attention to the diversity of population, and due to insufficient vairation in mutation operators, they perform well only in a few runs, and in other runs they are caught in the local optimum. The proposed method uses appropriate genetic operators to increase diversity of the population and performs local search around the best answer to exploit promising areas of the solution space. The use of hub mutation operators along with allocation mutation operators in the proposed algorithm has increased its exploration ability and effectiveness, which has led to discovery of the optimal answer in most runs for large size problems. Also, searching for the local neighborhood of the best answer made convergence faster and reduced the total running time for large instances. Evaluation of the proposed method and base algorithm on the Australian Post (AP) dataset showed that the improvements increased efficiency of the genetic algorithm in achieving optimal solutions for problems as large as 200 nodes from 2% to more than 85%. This study showed that meta-heuristic algorithms and their improved versions are suitable methods for solving hub location problems in a short and limited time.

کلیدواژه‌ها [English]

  • Genetic Algorithm
  • meta-heuristic algorithms
  • Local Search
  • Hub Location