نوع مقاله : مقاله پژوهشی
نویسندگان
1 گروه مهندسی صنایع، دانشگاه بجنورد، بجنورد، ایران.
2 گروه مهندسی کامپیوتر، دانشگاه بجنورد، بجنورد، ایران.
چکیده
هدف: هدف این مقاله ارائه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی است. روشهای پیشین حل مسئله کمتر به گوناگونی جوابها در جمعیت توجه داشتهاند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار میشوند.
روششناسی پژوهش: روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده میکند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسائل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریعتر روش پیشنهادی شد و زمان حل مسئله را درمجموع برای مسائل بزرگ کاهش داد.
یافتهها: ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (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 1
1 Department of Industrial Engineering, University of Bojnord, Bojnord, Iran.
2 Department of Computer Engineering, University of Bojnord, Bojnord, Iran
چکیده [English]
Purpose: 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.
Methodology: 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.
Findings: 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%.
Originality/Value: 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