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

Document Type : Research Paper

Authors

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

Abstract

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.

Keywords


  • 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). الگوریتم‌های بهینه‌سازی فراابتکاری، انتشارات جهاد دانشگاهی واحد صنعتی امیر کبیر،شابک ‎۹۷۸−۹۶۴−۲۱۰−۰۷۸−۱.