Review of the hierarchical facility location problem
LIN Jianxin1, LIN Mengting2, WANG Wandong2, ZHANG Zhixuan2
1. Beijing Urban Transportation Infrastructure Engineering Technology Research Center, Beijing University of Civil Engineering and Architecture, Beijing 100044, China; 2. Beijing Collaborative Innovation Center for Metropolitan Transportation, Beijing University of Civil Engineering and Architecture, Beijing 100044, China
Abstract:Public infrastructure construction must be carefully coordinated with the construction of multi-center, multi-level, multi-node urban networks, especially transportation networks, to balance regional traffic demands. The hierarchical facility location problem (HFLP) optimizes facility locations so that the network provides efficient and economic services, which is a network design problem with various resources and limited services. This problem has attracted much attention because of the increased complexity of facility services and the diversified demands. This review of HFLP research over the past forty years, especially the past six years, shows that the main research trends involve traditional fields such as healthcare, transportation hubs, and supply chains. In order to balance multiple system planning requirements with the various characteristics and scales of various types of network facilities, and to solve problems related to the mismatch between the availability of system services and the actual needs, multi-objective nested models, dynamic and random constraints, the efficient optimization of heuristic algorithms with important issues like various search and stopping criteria have become the main research trends. Studies have also analyzed the supply chain reverse logistics system for product inspection and recycling, the design of waste storage facilities using the echelon classification processing model, and the optimization of transportation hub locations that serve passenger needs. With the improved service levels and efficiency requirements, the hierarchical concept can improve services for a broad range of applications in various areas such as the hierarchical location of urban agglomeration service facilities and the layouts of centralized electrical vehicle charging stations.
林建新, 林孟婷, 王皖东, 张智旋. 分级设施选址问题研究进展与展望[J]. 清华大学学报(自然科学版), 2022, 62(7): 1121-1131.
LIN Jianxin, LIN Mengting, WANG Wandong, ZHANG Zhixuan. Review of the hierarchical facility location problem. Journal of Tsinghua University(Science and Technology), 2022, 62(7): 1121-1131.
[1] 郭珂歆, 彭国庆, 郑新奇, 等. 北部湾城市群综合交通网络一体化分析与评价[J]. 地理与地理信息科学, 2021, 37(4):57-63. GUO K X, PENG G Q, ZHENG X Q, et al. Analysis and evaluation of comprehensive transportation network integration in Beibu gulf urban agglomeration[J]. Geography and Geo-information Science, 2021, 37(4):57-63. (in Chinese) [2] 刘海龙, 呼旭红, 郭政昇, 等. 中原城市群基本公共服务与城市化协调发展的时空演变及影响因素[J]. 湖南师范大学自然科学学报, 2021, 44(4):71-80. LIU H L, HU X H, GUO Z S, et al. Spatio-temporal evolution and influencing factors of the coordinated development of basic public services and urbanization in Zhongyuan urban agglomeration[J]. Journal of Natural Science of Hunan Normal University, 2021, 44(4):71-80. (in Chinese) [3] 周顺, 车旭, 刘静妍. 基于模糊评价的城市群综合客运枢纽选址方法[C]//2020年中国城市交通规划年会论文集. 北京:中国建筑工业出版社, 2020:8. ZHOU S, CHE X, LIU J Y. Site selection method for comprehensive passenger transport hubs of urban agglomerations based on fuzzy evaluation[C]//Proceedings of the 2020 China Urban Transport Planning Annual Conference. Beijing, China:China Architecture & Building Press, 2020:8. (in Chinese) [4] NARULA S C. Hierarchical location-allocation problems:A classification scheme[J]. European Journal of Operational Research, 1984, 15(1):93-99. [5] MIRCHANDANI P B. Generalized hierarchical facility locations[J]. Transportation Science, 1987, 21(2):123-125. [6] DASKIN M. Network and discrete location:Models, algorithms and applications[J]. Journal of the Operational Research Society, 1997, 48(7):763-764. [7] MARIANOV V, SERRA D. Hierarchical location-allocation models for congested systems[J]. European Journal of Operational Research, 2001, 135(1):195-208. [8] ŞAHIN G, SVRAL H, MERAL S. Locational analysis for regionalization of Turkish Red Crescent blood services[J]. Computers & Operations Research, 2007, 34(3):692-704. [9] FARAHANI R Z, HEKMATFAR M, FAHIMNIA B, et al. Hierarchical facility location problem:Models, classifications, techniques, and applications[J]. Computers & Industrial Engineering, 2014, 68:104-117. [10] ALIAKBARIAN N, DEHGHANIAN F, SALARI M. A bi-level programming model for protection of hierarchical facilities under imminent attacks[J]. Computers & Operations Research, 2015, 64:210-224. [11] 马祖军, 周愉峰. 考虑设施中断风险和防御的分销网络选址-库存问题[J]. 系统工程, 2015, 33(12):48-54. MA Z J, ZHOU Y F. Location-inventory problem with disruption risks and fortification in distribution network design[J]. Systems Engineering, 2015, 33(12):48-54. (in Chinese) [12] 任亚洗. 基于层级模型的城市群综合客运枢纽分层布局研究[D]. 北京:北京交通大学, 2019. REN Y X. Hierarchical location problem of comprehensive passenger transportation hub in city cluster based on hierarchy model[D]. Beijing:Beijing Jiaotong University, 2019. (in Chinese) [13] TIRKOLAEE E B, MAHDAVI I, ESFAHANI M M S, et al. A robust green location-allocation-inventory problem to design an urban waste management system under uncertainty[J]. Waste Management, 2020, 102:340-350. [14] 孙姣, 屈挺, 聂笃宪, 等. 双渠道多级分销网络选址-库存问题[J]. 计算机集成制造系统, 2021, 27(11):3305-3317. SUN J, QU T, NIE D X, et al. Location-inventory problem of dual-channel multi-echelon distribution network[J]. Computer Integrated Manufacturing Systems, 2021, 27(11):3305-3317. (in Chinese) [15] 张震, 李延晖, 张琦. 考虑退货的多商品多来源闭环选址库存问题模型与算法[J]. 工业工程与管理, 2018, 23(6):133-142. ZHANG Z, LI Y H, ZHANG Q. Model and algorithm for closed-loop location inventory problem with multi-commodity and multi-sourcing considering returns[J]. Industrial Engineering and Management, 2018, 23(6):133-142. (in Chinese) [16] KAUFMAN L, EEDE M V, HANSEN P. A plant and warehouse location problem[J]. Journal of the Operational Research Society, 1977, 28(3):547-554. [17] KRATICA J, DUGOŠIJA D, SAVIĆ A. A new mixed integer linear programming model for the multi level uncapacitated facility location problem[J]. Applied Mathematical Modelling, 2014, 38(7-8):2118-2129. [18] PARK G, LEE Y, HAN J. A two-level location-allocation problem in designing local access fiber optic networks[J]. Computers & Operations Research, 2014, 51:52-63. [19] CARDONA-VALDÉS Y, ÁLVAREZ A, PACHECO J. Metaheuristic procedure for a bi-objective supply chain design problem with uncertainty[J]. Transportation Research Part B:Methodological, 2014, 60:66-84. [20] YOLMEH A, SALEHI N. An outer approximation method for an integration of supply chain network designing and assembly line balancing under uncertainty[J]. Computers & Industrial Engineering, 2015, 83:297-306. [21] JALALI S, SEIFBARGHY M, SADEGHI J, et al. Optimizing a bi-objective reliable facility location problem with adapted stochastic measures using tuned-parameter multi-objective algorithms[J]. Knowledge-Based Systems, 2016, 95:45-47. [22] LI H Y, ZHAO L J, HUANG R B, et al. Hierarchical earthquake shelter planning in urban areas:A case for Shanghai in China[J]. International Journal of Disaster Risk Reduction, 2017, 22:431-446. [23] TORKESTANI S S, SEYEDHOSSEINI S M, MAKUI A, et al. The reliable design of a hierarchical multi-modes transportation hub location problems (HMMTHLP) under dynamic network disruption (DND)[J]. Computers & Industrial Engineering, 2018, 122:39-86. [24] XUE J, SONG J S, LIN Y Y, et al. A practical approach to constructing hierarchical networks for urban hazard mitigation planning using GIS:The case of Futian, Shenzhen[J]. International Journal of Disaster Risk Reduction, 2018, 28:629-639. [25] GHAFFARINASAB N, VAN WOENSEL T, MINNER S. A continuous approximation approach to the planar hub location-routing problem:Modeling and solution algorithms[J]. Computers & Operations Research, 2018, 100:140-154. [26] ARABI M, YAGHOUBI S, TAJIK J. A mathematical model for microalgae-based biobutanol supply chain network design under harvesting and drying uncertainties[J]. Energy, 2019, 179:1004-1016. [27] HU W J, DONG J J, HWANG B G, et al. Hybrid optimization procedures applying for two-echelon urban underground logistics network planning:A case study of Beijing[J]. Computers & Industrial Engineering, 2020, 144:106452. [28] MOORE G C, REVELLE C. The hierarchical service location problem[J]. Management Science, 1982, 28(7):775-780. [29] 万波, 杨超, 黄松, 等. 基于分级选址模型的学校选址问题[J]. 工业工程与管理, 2010, 15(6):62-67. WAN B, YANG C, HUANG S, et al. A school location problem based on hierarchical location model[J]. Industrial Engineering and Management, 2010, 15(6):62-67. (in Chinese) [30] FARAHANI R Z, HASSANI A, MOUSAVI S M, et al. A hybrid artificial bee colony for disruption in a hierarchical maximal covering location problem[J]. Computers & Industrial Engineering, 2014, 75:129-141. [31] WANG J, LIU H, AN S, et al. A new partial coverage locating model for cooperative fire services[J]. Information Sciences, 2016, 373:527-538. [32] DUKKANCI O, PEKER M, KARA B Y. Green hub location problem[J]. Transportation Research Part E:Logistics and Transportation Review, 2019, 125:116-139. [33] MOUSAZADEH M, TORABI S A, PISHVAEE M S, et al. Accessible, stable, and equitable health service network redesign:A robust mixed possibilistic-flexible approach[J]. Transportation Research Part E:Logistics and Transportation Review, 2018, 111:113-129. [34] RAHIMI Y, TAVAKKOLI-MOGHADDAM R, MOHAMMADI M, et al. Multi-objective hub network design under uncertainty considering congestion:An M/M/c/K queue system[J]. Applied Mathematical Modelling, 2016, 40(5-6):4179-4198. [35] HASANZADEH H, BASHIRI M, AMIRI A. A new approach to optimize a hub covering location problem with a queue estimation component using genetic programming[J]. Soft Computing, 2018, 22(3):949-961. [36] MOHAMMADI M, JOLAI F, ROSTAMI H. An M/M/c queue model for hub covering location problem[J]. Mathematical and Computer Modelling, 2011, 54(11-12):2623-2638. [37] KHODEMANI-YAZDI M, TAVAKKOLI-MOGHADDAM R, BASHIRI M, et al. Solving a new bi-objective hierarchical hub location problem with an M/M/c queuing framework[J]. Engineering Applications of Artificial Intelligence, 2019, 78:53-70. [38] SEDEHZADEH S, TAVAKKOLI-MOGHADDAM R, JOLAI F. A new multi-mode and multi-product hub covering problem:A priority M/M/c queue approach[J]. International Journal of Industrial Mathematics, 2015, 7(2):139-148. [39] 蔡丽艳. 不确定性物流中心选址问题研究[J]. 物流科技, 2013, 36(6):64-68. CAI L Y. Uncertain logistics hub location problem[J]. Logistics Sci-Tech, 2013, 36(6):64-68. (in Chinese) [40] NASRABADI A M, NAJAFI M, ZOLFAGHARINIA H. Considering short-term and long-term uncertainties in location and capacity planning of public healthcare facilities[J]. European Journal of Operational Research, 2020, 281(1):152-173. [41] 李昌兵, 张斐敏. 集成选址-路径-库存问题的逆向物流网络优化[J]. 计算机集成制造系统, 2014, 20(7):1793-1798. LI C B, ZHANG F M. Reverse logistics network optimization of integrated location-routing-inventory problem[J]. Computer Integrated Manufacturing Systems, 2014, 20(7):1793-1798. (in Chinese) [42] 冷龙龙, 赵燕伟, 张春苗. 基于共享机制的自适应超启发式算法求解区域化低碳选址-路径问题[J]. 计算机集成制造系统, 2020, 26(5):1407-1424. LENG L L, ZHAO Y W, ZHANG C M. Shared mechanism based self-adaptive hyper-heuristic for regional low-carbon location-routing problem[J]. Computer Integrated Manufacturing Systems, 2020, 26(5):1407-1424. (in Chinese) [43] 王万良, 朱文成, 赵燕伟. 基于全局边缘排序的超启发算法在绿色物流选址-路径优化问题中的应用[J]. 计算机集成制造系统, 2020, 26(4):1097-1107. WANG W L, ZHU W C, ZHAO Y W. Application of hyper-heuristic algorithm based on global margin ranking in environmental LRP[J]. Computer Integrated Manufacturing Systems, 2020, 26(4):1097-1107. (in Chinese) [44] BOONMEE C, ARIMURA M, ASADA T. Location and allocation optimization for integrated decisions on post-disaster waste supply chain management:On-site and off-site separation for recyclable materials[J]. International Journal of Disaster Risk Reduction, 2018, 31:902-917. [45] FATHOLLAHI-FARD A M, HAJIAGHAEI-KESHTELI M, MIRJALILI S. Hybrid optimizers to solve a tri-level programming model for a tire closed-loop supply chain network design problem[J]. Applied Soft Computing, 2018, 70:701-722. [46] SONG Y, TENG C M. Optimal decision model and improved genetic algorithm for disposition of hierarchical facilities under hybrid service availability[J]. Computers & Industrial Engineering, 2019, 130:420-429. [47] FAHIMNIA B, JABBARZADEH A, GHAVAMIFAR A, et al. Supply chain design for efficient and effective blood supply in disasters[J]. International Journal of Production Economics, 2017, 183:700-709. [48] FORGHANI A, DEHGHANIAN F, SALARI M, et al. A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities[J]. Computers & Operations Research, 2020, 114:104831. [49] ZARRINPOOR N, FALLAHNEZHAD M S, PISHVAEE M S, et al. Design of a reliable hierarchical location-allocation model under disruptions for health service networks:A two-stage robust approach[J]. Computers & Industrial Engineering, 2017, 109:130-150. [50] ZHAO J, HUANG L X, LEE D H, et al. Improved approaches to the network design problem in regional hazardous waste management systems[J]. Transportation Research Part E:Logistics and Transportation Review, 2016, 88:52-75. [51] WANG M, CHENG Q, HUANG J C, et al. Research on optimal hub location of agricultural product transportation network based on hierarchical hub-and-spoke network model[J]. Physica A:Statistical Mechanics and its Applications, 2021, 566:125412. [52] SANGSAWANG O, CHANTA S. Capacitated single-allocation hub location model for a flood relief distribution network[J]. Computational Intelligence, 2020, 36(3):1320-1347. [53] PAUL N R, LUNDAY B J, NURRE S G. A multiobjective, maximal conditional covering location problem applied to the relocation of hierarchical emergency response facilities[J]. Omega, 2017, 66:147-158. [54] ZARRINPOOR N, FALLAHNEZHAD M S, PISHVAEE M S. The design of a reliable and robust hierarchical health service network using an accelerated Benders decomposition algorithm[J]. European Journal of Operational Research, 2018, 265(3):1013-1032. [55] WANG Y, ASSOGBA K, LIU Y, et al. Two-echelon location-routing optimization with time windows based on customer clustering[J]. Expert Systems with Applications, 2018, 104:244-260. [56] ARAGHI M E, TAVAKKOLI-MOGHADDAM R, JOLAI F, et al. A green multi-facilities open location-routing problem with planar facility locations and uncertain customer[J]. Journal of Cleaner Production, 2021, 282:124343. [57] KAZANÇOǦLU Y, ÖZBILTEKIN M, ÖZKAN-ÖZEN Y D. Sustainability benchmarking for logistics center location decision:An example from an emerging country[J]. Management of Environmental Quality, 2020, 31(5):1239-1260. [58] SEKER S, AYDIN N. Hydrogen production facility location selection for Black Sea using entropy based TOPSIS under IVPF environment[J]. International Journal of Hydrogen Energy, 2020, 45(32):15855-15868. [59] 郭文尧, 刘维刚. 现代化都市圈建设的问题、国际借鉴及发展路径[J]. 经济问题, 2021(8):104-109. GUO W Y, LIU W G. Study on the problems' international reference and development path of constructing modern metropolis circle[J]. On Economic Problems, 2021(8):104-109. (in Chinese)