يك الگوريتم ژنتيك بهبوديافته با گوناگوني و جستجوي محلي براي حل مسئله مكان‌يابي بدون ظرفيت هاب با تخصيص تكي

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

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

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