ارائه مسأله مکان‌یابی هاب حداکثر پوشش سلسله ‌مراتبی در شرایط اختلال در هاب با استفاده از برنامه-ریزی دوسطحی

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

نویسندگان

1 دانشجوی دکترای مهندسی صنایع، گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کردستان، سنندج، ایران

2 دانشیار گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کردستان، سنندج، ایران

چکیده

مسأله مکان­یابی هاب از اساسی­ترین و مهم­ترین مسائل در حوزه­ی تصمیم­گیری و برنامه­ریزی سیستم‌های حمل­ونقل به­شمار می­رود. هدف اصلی مسأله مکان­یابی هاب، انتقال جریان بین نقاط تقاضا از طریق هاب یا هاب­هایی است که نقش اساسی را در این میان ایفا می­کنند. موضوع از کار افتادگی هاب­ها در این مسائل از مواردی است که سال­های اخیر مورد توجه برخی از محققان قرار گرفته است. در این تحقیق، مسأله مکان­یابی هاب سلسله­مراتبی با وجود اختلال در هاب­های شبکه بررسی شده و در قالب یک مدل برنامه­ریزی دوسطحی، مد‌ل‌سازی می­شود. مسأله مکان­یابی هاب ارائه شده از نوع مسائل حداکثر پوشش هاب است. از کار افتادگی هاب در این مدل به­صورت عمدی رخ داده و باعث اختلال فعالیت­ها در هاب­های غیرمرکزی می­شود. در سطح دوم تلاش می­شود تا با از کار انداختن یک هاب، پوشش­دهی مسأله به کمترین میزان خود برسد، درحالی‌که سطح اول مسأله می­خواهد خسارت به­وجود آمده را کاهش داده و پوشش­دهی مسأله را بالا ببرد. مسأله مورد بررسی با استفاده از الگوریتم‌های شمارش کامل و شبیه­سازی تبرید با داده­های متفاوت حل شده است. نتایج محاسباتی حل مدل پیشنهادی برای مسائل نمونه از جمله تقاضا و تعداد هاب­های متفاوت، فاکتور تخفیف بین هاب‌ها و شعاع پوشش مختلف بررسی شد. نتایج عددی نشان داد با افزایش شعاع پوشش، تعداد گره­های مکان­یابی شده و همچنین مقدار پوشش­دهی مسأله افزایش می­یابد. همچنین نشان داده شد که روش فراابتکاری پیاده شده کارایی دارد و توانایی حل داده­های بزرگ را نیز داراست.

کلیدواژه‌ها

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

A Bi-Level Programming Model for Hierarchical Maximal Covering Hub Location Problem under Disruption in Hubs

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

  • Mina Amani Ggaiuom 1
  • Abdolsalam Ghaderi 2
  • Anvar Mahmoudi 2
1 PhD student in Industrial Engineering, Department of Industrial Engineering, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran
2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran
چکیده [English]

The hub location problem is one of the most fundamental and crucial issues in transportation systems and decision-making. The primary purpose of a transportation network is to transfer traffic between demand points via a hub, and hubs are essential to this process. The failure of hubs has garnered considerable attention of researchers in recent years. This research examines the problem of hierarchical hub location using bi-level programming. This study presents a model for optimal hub coverage. In non-central hubs, disruptions are intentional. The objective function of the second level is to minimize the problem's coverage by disabling the hubs, whereas the objective function of the first level is to minimize the problem's damage while expanding its coverage. The studied problem was solved using the simulated annealing and the full enumeration method. The proposed model has been solved for a variety of different scenarios, including fluctuating demand and hub count, fluctuating discount factors between hubs, and fluctuating coverage radii. According to the numerical results, as the covering radius increases, the number of located nodes and the problem's coverage also increase. In conclusion, an analysis of the employed solution methods concludes that the proposed meta-heuristic method is both effective and applicable to larger data sets.

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

  • Maximal Covering
  • Bi-level Programming
  • Hierarchical Hub Location
  • Disruption

مراجع

  • Z. Farahani, M. Hekmatfar, A. B. Arabani, and E. Nikbakhsh, “Hub location problems: A review of models, classification, solution techniques, and applications,” Comput. Ind. Eng., vol. 64, no. 4, pp. 1096–1109, 2013.
  • Z. Farahani, M. Hekmatfar, B. Fahimnia, and N. Kazemzadeh, “Hierarchical facility location problem: Models, classifications, techniques, and applications,” Comput. Ind. Eng., vol. 68, no. 1, pp. 104–117, 2014.
  • Hekmatfar and M. Pishvaee, “Hub Location Problem,” Contrib. to Manag. Sci., p. 101, 2009.
  • Laporte and S. Nickel, Location Science. 2015.
  • Sinha, P. Malo, and K. Deb, “A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications,” IEEE Trans. Evol. Comput., vol. 22, no. 2, pp. 276–295, 2018.
  • L. Hakimi, “Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph,” Oper. Res., vol. 12, no. 3, pp. 450–459, 1964.
  • Toh and R. Higgins, “The Impact of Hub and Spoke Network Centralization and Route Monopoly on Domestic Airline Profitability,” Transp. J., vol. 24, no. 4, pp. 16–27, 1985.
  • E. O’Kelly, “Location of Interacting Hub Facilities.,” Transp. Sci., vol. 20, no. 2, pp. 92–106, 1986.
  • E. O’Kelly, “Activity Levels at Hub Facilities in Interacting Networks,” Geogr. Anal., vol. 18, no. 4, pp. 343–356, 1986.
  • F. Campbell and M. E. O’Kelly, “Twenty-five years of hub location research,” Transp. Sci., vol. 46, no. 2, pp. 153–169, 2012.
  • B. Calvo and D. H. Marks, “Location of health care facilities: An analytical approach,” Socioecon. Plann. Sci., vol. 7, no. 5, pp. 407–422, 1973.
  • F. Dökmeci, “an Optimization Model for a Hierarchical Spatial System,” J. Reg. Sci., vol. 13, no. 3, pp. 439–451, 1973.
  • Yaman, “The hierarchical hub median problem with single assignment,” Transp. Res. Part B Methodol., vol. 43, no. 6, pp. 643–658, 2009.
  • A. Alumur, H. Yaman, and B. Y. Kara, “Hierarchical multimodal hub location problem with time-definite deliveries,” Transp. Res. Part E Logist. Transp. Rev., vol. 48, no. 6, pp. 1107–1120, 2012.
  • Dukkanci and B. Y. Kara, “Routing and scheduling decisions in the hierarchical hub location problem,” Comput. Oper. Res., vol. 85, pp. 45–57, 2017.
  • Asadian, S. M. H. Hosseini, and A. A. Hassani, “Modeling and Solving the Hierarchical Hub Location Problem Considering Several Different Vehicle and Capacity for the Hubs,” J. Ind. Eng. Res. Prod. Syst., vol. 5, pp. 1–15, 2017.
  • Drezner, “Heuristic solution methods for two location problems with unreliable facilities,” J. Oper. Res. Soc., vol. 38, no. 6, pp. 509–514, 1987.
  • Der Lee, “On solving unreliable planar location problems,” Comput. Oper. Res., vol. 28, no. 4, pp. 329–344, 2001.
  • Berman, Z. Drezner, and G. O. Wesolowsky, “Locating service facilities whose reliability is distance dependent,” Comput. Oper. Res., vol. 30, no. 11, pp. 1683–1695, 2003.
  • V. Snyder and M. S. Daskin, “Reliability models for facility location: The expected failure cost case,” Transp. Sci., vol. 39, no. 3, pp. 400–416, 2005.
  • Kim and M. E. O’Kelly, “Reliable p-hub location problems in telecommunication networks,” Geogr. Anal., vol. 41, no. 3, pp. 283–306, 2009.
  • L. Lei, “Identifying critical facilities in hub-and-spoke networks: A hub interdiction median problem,” Geogr. Anal., vol. 45, no. 2, pp. 105–122, 2013.
  • Parvaresh, S. A. Hashemi Golpayegany, S. M. Moattar Husseini, and B. Karimi, “Solving the p-hub Median Problem Under Intentional Disruptions Using Simulated Annealing,” Networks Spat. Econ., vol. 13, no. 4, pp. 445–470, 2013.
  • Ebrahimi Zade, A. Sadegheih, and M. M. Lotfi, “A modified NSGA-II solution for a new multi-objective hub maximal covering problem under uncertain shipments,” J. Ind. Eng. Int., vol. 10, no. 4, pp. 185–197, 2014.
  • Sadeghi, F. Jolai, R. Tavakkoli-Moghaddam, and Y. Rahimi, “A new stochastic approach for a reliable p-hub covering location problem,” Comput. Ind. Eng., vol. 90, pp. 371–380, 2015.
  • R. Silva and C. B. Cunha, “A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem,” Eur. J. Oper. Res., vol. 262, no. 3, pp. 954–965, 2017.
  • R. Madani, A. Shahandeh Nookabadi, and S. R. Hejazi, “A bi-objective, reliable single allocation p-hub maximal covering location problem: Mathematical formulation and solution approach,” J. Air Transp. Manag., vol. 68, pp. 118–136, 2017.
  • Ghaffarinasab and A. Motallebzadeh, “Hub interdiction problem variants: Models and metaheuristic solution algorithms,” Eur. J. Oper. Res., vol. 267, no. 2, pp. 496–512, 2017.
  • Mohammadi, P. Jula, and R. Tavakkoli-Moghaddam, “Reliable single-allocation hub location problem with disruptions,” Transp. Res. Part E Logist. Transp. Rev., vol. 123, no. August 2018, pp. 90–120, 2019.
  • Shen, Y. Liang, and Z.-J. M. Shen, “Reliable Hub Location Model for Air Transportation Networks Under Random Disruptions,” Manuf. Serv. Oper. Manag., no. April, 2020.
  • Haghdoost and E. Roghanian, “Design of a Reliable Hub Location Network under Massive Disruption with Direct Connections between Non–Hub Nodes,” J. Transp. Res., vol. 18, no. 1, pp. 1–18, 2021.
  • Korani and A. Eydi, “Bi-level programming model and KKT penalty function solution approach for reliable hub location problem,” Expert Syst. Appl., vol. 184, no. April, p. 115505, 2021.
  • Soleimani, M. Khalilzadeh, A. Bahari, and A. Heidary, “NSGA-II algorithm for hub location-allocation problem considering hub disruption and backup hub allocation,” World J. Eng., Aug. 2021.
  • Khodaee, E. Roghanian, and N. Ghaffarinasab, “Competitive multiple allocation hub location problem considering primary and backup routes,” Comput. Appl. Math., vol. 41, no. 4, pp. 1–62, Apr. 2022.
  • K. Sangaiah and R. Khanduzi, “Tabu search with simulated annealing for solving a location–protection–disruption in hub network,” Appl. Soft Comput. J., vol. 114, 2022.
  • Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by Simulated Annealing. Morgan Kaufmann Publishers, Inc., 1987.
  • یقینی، مسعود، اخوان کاظم‌زاده، محمد رحیم (1395). الگوریتم‌های بهینه‌سازی فراابتکاری، انتشارات جهاد دانشگاهی واحد صنعتی امیر کبیر،شابک ‎۹۷۸−۹۶۴−۲۱۰−۰۷۸−۱.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 10، شماره 20
شهریور 1401
صفحه 33-47

فایل ها

هم رسانی

ارجاع به این مقاله

آمار