توسعه يك روش هيوريستيك تركيبي مقاوم براي حل مساله مكان­يابي تسهيلات هاب بدون محدوديت ظرفيت

A ROBUST HYBRID HEURISTIC FOR SOLVING THE UNCAPACITATED HUB LOCATION PROBLEM

مساله مكان­يابي و طراحي شبكه تسهيلات هاب به صورت گسترده­اي در تئوري مكان­يابي مورد بررسي قرار گرفته است. اين مساله معمولاً با تصميم­گيري همزمان در مورد تعداد بهينه تسهيلات هاب، مكان­ آن‌ها و تخصيص گره هاي غير­هاب همراه است. در اين مقاله، يك هيوريستيك جديد و مقاوم در چارچوپ الگوريتم تركيبي ژنتيك - تبريد شبيه­سازي شده (GA-SA) به منظور حل مساله مكان­يابي تسهيلات هاب با تخصيص يگانه و ظرفيت نامحدود توسعه داده شده است. در هيوريستيك ارائه شده، از الگوريتم ژنتيك در جهت تشكيل تعدادي از راه­حل­‌هاي آغازين متنوع استفاده مي­شود و در ادامه الگوريتم تبريد شبيه­سازي شده به منظور بهبود هر دو بردار مكان و تخصيص مساله به كار گرفته مي­شود. از آنجايي كه عملكرد الگوريتم‌هاي هيوريستيك به شدت تحت تاثير مقادير پارامترهاي آنها است، يك رويكرد تنظيم پارامتر مقاوم مبتني بر طراحي آزمايش­ها پيشنهاد شده است كه علاوه بر بهبود و حفظ توانايي الگوريتم در دستيابي به جواب مناسب، زمان اجراي الگوريتم را به طور قابل ملاحظه‌‌اي كاهش مي‌دهد. در راستاي تبيين كارايي الگوريتم توسعه داده شده، نتايج به دست آمده از اجراي الگوريتم بر روي مجموعه داده­هاي استاندارد CAB و AP با نتايج بهترين الگوريتم­هاي موجود در ادبيات مورد مقايسه قرار گرفت. اين نتايج بيان مي­دارند كه الگوريتم تركيبي ارائه شده علاوه بر سرعت محاسباتي بالاتر نسبت به ساير الگوريتم­ها، در دستيابي به پاسخ­هاي بهينه و يا نزديك به بهينه موفق است.

The hub-and-spoke network design problem is widely studied in facility location theory. Hub location problems usually involve decisions on optimal number and locations of hub nodes, and allocation of non-hub nodes to the hubs. In this paper, a new and robust hybrid Genetic Algorithm (GA)-Simulated Annealing (SA) heuristic is developed for solving the uncapacitated single-allocation hub location problem. In this method, GA is used for generating a number of diversified initial solutions, and SA is applied for improving both the hub selection and node assignment. Also, regarding the significant influence of parameter tuning on the performance of heuristic methods, we devised a robust parameter tuning method based on design of experiments, which not only considers the fitness of solutions, but also aims to minimize the overall runtime. The performance of the developed method was evaluated by solving a number of benchmark problems taken from the CAB and AP datasets and compared with the best existing algorithms in the literature. Computational results showed that the GA-SA hybrid heuristic is successful in finding optimal or near-optimal solutions faster than the competing algorithms.