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

نویسندگان

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
Abdinnour-Helm, S. (1998). A hybrid heuristic for the uncapacitated hub location problem. European journal of operational research106(2-3), 489-499. https://doi.org/10.1016/S0377-2217(97)00286-5
Abdinnour-Helm, S., & Venkataramanan, M. A. (1998). Solution approaches to hub location problems. Annals of operations research78, 31-50. https://doi.org/10.1023/A:1018954217758
Abyazi-Sani, R., & Ghanbari, R. (2016). An efficient tabu search for solving the uncapacitated single allocation hub location problem. Computers & industrial engineering93, 99-109. https://doi.org/10.1016/j.cie.2015.12.028
Akbaripour, H., Masehian, E., & Roostaei, A. (2017). Landscape analysis and scatter search metaheuristic for solving the uncapacitated single allocation hub location problem. International journal of industrial and systems engineering26(4), 425-459. DOI: 10.1504/IJISE.2017.085207
Alumur, S., & Kara, B. Y. (2008). Network hub location problems: the state of the art. European journal of operational research190(1), 1-21. https://doi.org/10.1016/j.ejor.2007.06.008
Bailey, A., Ornbuki-Berrnan, B., & Asobiela, S. (2013, April). Discrete pso for the uncapacitated single allocation hub location problem. 2013 IEEE symposium on computational intelligence in production and logistics systems (CIPLS) (pp. 92-98). IEEE. DOI: 10.1109/CIPLS.2013.6595205
Bashiri, M., Karimi, H., Akhondzadeh, E., Dehghan, E., Karani, E., Ghasemi Nejad, A., Ramezani, M., Fotouhi, F., & Rajabali Kani, A. (2011). Design of industrial systems II (second Ed.). Shahed University Press. (In Persian). https://www.adinehbook.com/gp/product/6006121093
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the operational research society41(11), 1069-1072. https://doi.org/10.1057/jors.1990.166
De Carvalho, R., Gomes, B., Martins, A., Saldanha, R., & de Camargo, R. (2017). A multi-start heuristic for the design of hub-and-spoke networks. Proceeding Series of the Brazilian society of computational and applied mathematics5(1), 1-7. DOI: https://doi.org/10.5540/03.2017.005.01.0471  
Ernst, A. T., & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science4(3), 139-154. https://doi.org/10.1016/S0966-8349(96)00011-3
Filipović, V., Kratica, J., Tošić, D., & Dugošija, D. (2009). GA inspired heuristic for uncapacitated single allocation hub location problem. In Applications of soft computing (pp. 149-158). Springer, Berlin, Heidelberg.  https://doi.org/10.1007/978-3-540-89619-7_15
Ghaffarinasab, N., & Kara, B. Y. (2019). Benders decomposition algorithms for two variants of the single allocation hub location problem. Networks and spatial economics19(1), 83-108. https://doi.org/10.1007/s11067-018-9424-z
Guan, J., Lin, G., & Feng, H. B. (2018a). A learning-based probabilistic tabu search for the uncapacitated single allocation hub location problem. Computers & operations research98, 1-12. https://doi.org/10.1016/j.cor.2018.04.020
Guan, J., Lin, G., & Feng, H. B. (2018b). A multi-start iterated local search algorithm for the uncapacitated single allocation hub location problem. Applied soft computing73, 230-241. https://doi.org/10.1016/j.asoc.2018.08.035
Hekmatfar, M., & Pishvaee, M. (2009). Hub location problem. In R. Zanjirani Farahani & M. Hekmatfar (Eds), Facility Location (pp. 243-270). Physica, Heidelberg. https://doi.org/10.1007/978-3-7908-2151-2_11
Marić, M., Stanimirović, Z., & Stanojević, P. (2013). An efficient memetic algorithm for the uncapacitated single allocation hub location problem. Soft computing17(3), 445-466. https://doi.org/10.1007/s00500-012-0919-0
O'kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European journal of operational research32(3), 393-404. https://doi.org/10.1016/S0377-2217(87)80007-3
Rabbani, M., Farrokhi-Asl, H., & Heidari, R. (2017). Genetic algorithm-based optimization approach for an uncapacitated single allocation P-hub center problem with more realistic cost structure. Journal of industrial and systems engineering10(1), 108-124.
Silva, M. R., & Cunha, C. B. (2009). New simple and efficient heuristics for the uncapacitated single allocation hub location problem. Computers & operations research36(12), 3152-3165. https://doi.org/10.1016/j.cor.2008.12.019
Topcuoglu, H., Corut, F., Ermis, M., & Yilmaz, G. (2005). Solving the uncapacitated hub location problem using genetic algorithms. Computers & operations research32(4), 967-984. https://doi.org/10.1016/j.cor.2003.09.008