Hierarchical Facility Location and Hub Network Problems: A literature review

Document Type : Review paper

Authors

Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran.

Abstract

In this paper, a complete review of published researches about hierarchical facility location and hub network problems is presented. Hierarchical network is a system where facilities with different service levels interact in a top-down way or vice versa. In Hierarchical systems, service levels are composed of different facilities. Published papers from (1970) to (2015) have been studied and a comprehensively classified and surveys is presented. Mathematical models are classified based on different properties such as: input, output, objective functions, constraints, applications, some of the real world case studies and solution methods. At the ends, according to classification, a conclusion based on the literature and the future research to tackle real world of hierarchical facility location problems and hierarchical hub network problems is presented. This study may be used as a comprehensive reference for researchers in the hierarchical facility location problems, particularly those of hierarchical location-based on hub networks.

Keywords

Main Subjects


Alumur, S., & Kara, B.Y. (2008). Network hub location problems: the state of the art. European Journal of Operational Research, 190(1), 1–21.
Aardal, K. (1998). Reformulation of capacitated facility location problems: how redundant information can help. Annals of Operations Research, 82(0), 289–308.
Aardal, K., Chudak, F.A., & Shmoys, D.B. (1999). A 3-approximation algorithm for the k-level uncapacitated facility location problem. Information Processing Letters, 72(5–6), 161–167.
Aardal, K., Labbe, M., Leung, J., & Queyranne, M. (1996). On the two-level uncapacitated facility location problem. INFORMS Journal on Computing, 8, 289–301.
Addis, B., Carello, G., & Ceselli, A. (2013). Combining very large scale and ILP based neighborhoods for a two-level location problem. European Journal of Operational Research, 231(3), 535–546.
Ageev, A.A. (2002). Improved approximation algorithms for multilevel facility location problems. Operations Research Letters, 30(5), 327–332.
Ageev, A.A., Ye Y.Y., & Zhang, J.W. (2004). Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM Journal on Discrete Mathematics, 18(1), 207–217.
Aliakbarian, N., Dehghanian F., & Salari, M. (2015). A bi-level programming model for protection of hierarchical facilities under imminent attacks. Computers & operations research, 64, 210–224.
Alminyana, M., Borras, F., & Pastor, J.T. (1998). A new directed heuristic for the PQ-median problem. Location Science, 6(1–4), 1–23.
Alumur, S.A., Yaman, H., & Kara, B.Y. (2012). Hierarchical multimodal hub location problem with time-definite deliveries. Transportation Research Part E, 48(6), 1107–1120.
Ayed, O.B. (2011). Parcel distribution network design problem. Operational Research International Journal, 3(2), 139–149.
Barros, A.I., Dekker, R., & Scholten, V. (1998). A two-level network for recycling sand: A case study. European Journal of Operational Research, 110(2), 199–214.
Bigotte, J.F., Krass, D., Antunes, A.P., & Berman, O. (2010). Integrated modeling of urban hierarchy and transportation network planning. Transportation Research Part A, 44(7), 506–522.
Bumb, A. (2001). An approximation algorithm for the maximization version of the two level uncapacitated facility location problem. Operations Research Letters, 29(4), 155–161.
Calvo, A.B., & Marks, D.H. (1973). Location of health care facilities: An analytical approach. Socio-Economic Planning Science, 7(5), 407–422.
Chardaire, P., Lutton, J.L., & Sutter, A. (1999). Upper and lower bounds for the two-level simple plant location problem. Annals of Operations Research, 86(0), 117–140.
Charnes, A., & Storbeck, J. (1980). A goal programming model for the siting of multilevel EMS systems. Socio-Economic Planning Science, 14(4), 155–161.
Chen, Sh.H. (2010). A heuristic algorithm for hierarchical hub-and-spoke network of time-definite common carrier operation planning problem. Network Spatial Economic. Springer Science, 10(4), 509–523.
Chi, T.H., Yang, H., & Hsiao, H.M. (2011). A new hierarchical facility location model and genetic algorithm for humanitarian relief. Information Science and Service Science (NISS). Conference Publications, 2, 367–374.
Chung, S.h., Myung, Y.s., & Tcha, D.w. (1992).Optimal design of a distributed network with a two-level hierarchical structure. European Journal of Operational Research, 62(1), 105–115.
Cinar, Y., & Yaman, H. (2011). The vendor location problem. Computers & Operations Research, 38(12), 1678–1695.
Contreras, I., Fernández, E., & Marín, A. (2010). The tree of hubs location problem. European Journal of Operational Research, 202(2), 390–400.
Costa, A.M., Franca, P.M., & Filho, Ch.L. (2011). Two-level network design with intermediate facilities: an application to electrical distribution systems. Omega, 39(1), 3–13.
Davari, S., & Zarandi, M.H.F. (2012). The single-allocation hierarchical hub median location problem with fuzzy demands. African Journal of Business Management, 6, 347–360.
Daskin, M.S., & Maass, K.L. (2015). The p-Median problem, Location Science, Springer, Chapter 2, (21–44).
Dokmeci, V.F. (1973). An optimization model for a hierarchical spatial system. Journal of Regional Science, 13(3), 439–451.
Drexl, M.A. (2011). An approximation algorithm for the k-level concentrator location problem. Operations Research Letters, 39(5), 355–358.
Eitan, Y., Narula, S.C., & Tien, J.M. (1991). A generalized approach to modeling the hierarchical location-allocation problem. IEEE Transportations on Systems, Man, and Cybernetics, 21(1), 39–46.
Espejo, L.G.A., Galvao, R.D., & Boffey, B. (2003). Dual-based heuristics for a hierarchical covering location problem. Computers & Operations Research, 30(2), 165–180.
Farahani, R.Z., Hassani, A., Mousavi, S.M., & Bakhashayeshi Baygi, M. (2014). A hybrid artificial bee colony for disruption in a hierarchical maximal covering location problem. Computers & Industrial Engineering, 75, 129–141.
Farahani, R.Z., Hekmatfar, M. (2009). Facility location: concepts, models, algorithms and case studies, Physica-Verlag, Springer Dordrecht Heidelberg London, New York, Chapter 8 (177–192). 
Farahani, R.Z., Hekmatfar, M. (2009). Facility location: concepts, models, algorithms and case studies, Physica-Verlag, Springer Dordrecht Heidelberg London, New York, Chapter 15 (219–242). 
Farahani, R.Z., Hekmatfar, M., Boloori Arabani, A., & Nikbakhsh, E. (2013). Hub location problems: a review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096–1109.
Farahani, R.Z., Hekmatfar, M., Fahimnia, B., & Kazemzadeh, N. (2014). Hierarchical facility location problem: models, classifications, techniques, and applications. Computers & Industrial Engineering, 68, 104–117.
Fazel Zarandi, M.H., Davari, S., & Haddad Sisakht S.A. (2015). An empirical comparison of simulated annealing and iterated local search for the hierarchical single allocation hub median location problem. Scientia Iranica E, 22(3), 1203–1217.
Fernández, E, &Landete, M. (2015). Fixed charge facility location problems, Location Science, Springer, Chapter 3, 47–73.
Flynn, J., & Ratick, S. (1988). A multi-objective hierarchical covering model for the essential air services program. Transportation Science, 22(2), 139–147.
Galvao, R.D., Espejo, L.G.A., & Boffey, B. (2002). A hierarchical model for the location of perinatal facilities in the municipality of Rio de Janeiro. European Journal of Operational Research, 138(3), 495–517.
Galvao, R.D., Espejo, L.G.A., Boffey, B., & Yates, D. (2006). Load balancing and capacity constraints in a hierarchical location model. European Journal of Operational Research, 172(2), 631–646.
Gao, L.L., & Robinson, E.P. (1992). A dual-based optimization procedure for the two-echelon uncapacitated facility location problem. Naval Research Logistics, 39(2), 191–212.
Garcia, S., & Marin, A. (2015). Covering location problems, Location Science, Springer, Chapter 5, (93–111).
Gelareh, S., & Nickel, S. (2011). Hub location problems in transportation networks. Transportation Research Part E, 47(6), 1092–1111.
Geoffrion, A.M., & Graves, G.W. (1974). Multi-commodity distribution system design by benders decomposition. Management Science, 20(5), 822–844.
Gerrard, R.A., & Church, R.L. (1994). A generalized approach to modeling the hierarchical maximal covering location problem with referral. Regional Science, 73(4), 425–453.
Gódor, I., & Magyar, G. (2005). Cost-optimal topology planning of hierarchical access networks. Computers & Operations Research, 32(1), 59–86.
Guha, S., Meyerson, A., & Munagala, K. (2000). Hierarchical placement and network design problems. In Proceedings of the 41st annual symposium on foundations of computer science, 603–612.
Hinojosa, Y., Puerto, J., & Fernandez, F.R. (2000). A multi-period two-echelon multi-commodity capacitated plant location problem. European Journal o Operational Research, 123(2), 271–291.
Hodgson, M.J. (1984). Alternative approaches to hierarchical location-allocation systems. Geographical Analysis, 16(3), 275–281.
Hodgson, M.J. (1986). A hierarchical location-allocation model with allocation based on facility size. Annals of Operations Research, 6(8), 273–289.
Hodgson, M.J. (1988). A hierarchical location-allocation model for primary health care delivery in a developing area. Social Science & Medicine, 26(1), 153–161.
Horner, M.W., & O’Kelly, M.E. (2005). A combined cluster and interaction model: the hierarchical assignment problem. Geographical Analysis, 37(3), 315–335.
Ignacio, A.A.V., Filho, V.J.M.F., & Galvao, R.D. (2008). Lower and upper bounds for a two-level hierarchical location problem in computer networks. Computers & Operations Research, 35(6), 1982–1998.
Jayaraman, V., Gupta, R., & Pirkul, H. (2003). Selecting hierarchical facilities in a service-operations environment. European Journal of Operational Research, 147(3), 613–628.
Johnson, M.P., Gorr, W.L., & Roehrig, S. (2005). Location of service facilities for the elderly. Annals of Operations Research, 136(1), 329–349.
Kantor, E., & Peleg, D. (2006). Approximate hierarchical facility location and applications to the shallow steiner tree and range assignment problems. Lecture Notes in Computer Science, 3998, 211–222.
Kantor, E., & Peleg, D. (2009). Approximate hierarchical facility location and applications to the bounded depth steiner tree and range assignment problems. Journal of Discrete Algorithms, 7(3), 341–362.
Kijmanawat, K., & Ieda, H. (2005). Development and application of CM-Gats algorithms in solving large multilevel hierarchical network design problems. Research in Transportation Economics, 13, 121–142.
Kim, J.G., & Tcha, D.w. (1992). Optimal design of a two-level hierarchical network with tree-star configuration. Computers and Industrial Engineering, 22(3), 273–281.
Kırca, O., & Erkip, N. (1988). Selecting transfer station locations for large solid waste systems. European Journal of Operational Research, 35(3), 339–349.
Klose, A. (2000). A lagrangean relax-And-cut approach for the two-stage capacitated facility location problem. European Journal of Operational Research, 126(2), 408–421.
Koksalan, M., Sural, H., & Kırca, O. (1995). A location–distribution application for a beer company. European Journal of Operational Research, 80(1), 16–24.
Lee, J.M., & Lee, Y.H. (2010). Tabu based heuristics for the generalized hierarchical covering location problem. Computers & Industrial Engineering, 58(4), 638–645.
Lin, Ch.Ch. (2010). The integrated secondary route network design model in the hierarchical hub and spoke network for dual express services. Int. J. Production Economics, 123(1), 20–30.
Lin, Ch.Ch.,& Chen, Sh.H. (2004). The hierarchical network design problem for time-definite express common carriers. Transportation Research Part B, 38(3), 271–283.
Lin, Ch.Ch.,& Chen, Sh.H. (2008). An integral constrained generalized hub-And-spoke network design problem. Transportation Research Part E, 44(6), 986–1003.
Mandell, M.B. (1998). Covering models for two-tiered emergency medical services systems. Location Science, 6(1–4), 355–368.
Marianov, V., & Serra, D. (2001). Hierarchical location–allocation models for congested systems. European Journal of Operational Research, 135(1), 195–208.
Marin, A., & Pelegrin, B. (1999). Applying lagrangian relaxation to the resolution of two-stage location problems. Annals of Operations Research, 86(0), 179–198.
Martin, de Sá E., Saraiva, de Camargo R., & de Miranda, G. (2013). Discrete optimization an improved benders decomposition algorithm for the tree of hubs location problem. European Journal of Operational Research, 226, 185–202.
Meyer, T., Ernst, A.T., & Krishnamoorthy, M. (2009). A 2-phase algorithm for solving the single allocation p-hub center problem. Computers and Operations Research, 36(12), 3143–3151.
Miranda, P.A., Garrido, R.A., & Ceroni, J.A. (2009). E-work based collaborative optimization approach for strategic logistic network design problem. Computers & Industrial Engineering, 57(1), 3–13.
Moore, G.C., & Revelle, C. (1982). The hierarchical service location problem. Management science, 28(7), 775–780.
Narasimhan, S., & Pirkul, H. (1992). Hierarchical concentrator location problem. Computer Communications, 15(3), 185–191.
Narula, S.C. (1984). Hierarchical location-allocation problems: a classification scheme. European Journal of Operational Research, 15(1), 93–99.
Narula, S.C. (1986). Minisum hierarchical location–allocation problem on a network: a survey. Annals of Operations Research, 6(8), 257–272.
Narula, S.C., & Ogbu, U.I. (1979). A hierarchal location-allocation problem. Omega, 7(2), 137–143.
Narula, S.C., & Ogbu, U.I. (1985). Lagrangean relaxation and decomposition in an uncapacitated 2-hierarchical location-allocation problem. Comput& Operation research, 12(2), 169–180.
O’Kelly, M.E., & Storbeck, J.E. (1985). Hierarchical location models with probabilistic allocation. Regional Studies, 18(2), 121–129.
Okabe, A., Okunuki, K.I., & Suzuki, T. (1997). A computational method for optimizing the hierarchy and spatial configuration of successively inclusive facilities on a continuous plane. Location Science, 5(4), 255–268.
Pirkul, H., & Jayaraman, V. (1996). Production, transportation and distribution planning in a multi-commodity tri-level system. Transportation Science, 30(4), 291–302.
Pirkul, H., & Jayaraman, V. (1998). A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Computers Ops Res, 25(10), 869–878.
Rajabi, Z., & Avakh Darestani, S. (2015). Optimizing a hierarchical hub covering problem with mandatory dispersion of central hubs. International Journal of Applied Operational Research, 5(1), 17–28.
Ratick, S.J., Osleeb, J.P., & Hozumi, D. (2009). Application and extension of the Moore and Revelle hierarchical maximal covering model. Social Economic Planning Sciences, 43(2), 92–101.
Rieck, J.R., & Zimmermann, C.E.J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863–878.
Ro, H.b., & Tcha, D.w. (1984). A branch-and-bound algorithm for the two-level uncapacitated facility location problem with some side constraints. European Journal of Operational Research, 18(3), 349–358.
Rodriguez-Martin, I., Salazar-Gonzalez, J.J., & Yaman, H. (2014). A branch-and-cut algorithm for the hub location and routing problem. Computers & Operations Research, 50, 161–174.
Saboury, A., Ghaffari-Nasab, N., Barzinpour, F., & Jabalameli M.S. (2013). Applying two efficient hybrid heuristics for hub location problem with fully inter connected backbone and access networks. Computers & Operations Research, 40(10), 2493–2507.
Sahin, G., & Sural, H. (2007). A review of hierarchical facility location models. Computers & Operations Research, 34(8), 2310–2331.
Sahin, G., Süral, H., & Meral, S. (2007). Locational analysis for regionalization of Turkish red crescent blood services. Computers & Operations Research, 34(3), 692–704.
Sahraeian, R., & Korani, E. (2010). The hierarchical hub maximal covering problem with determinate cover radiuses. Industrial Engineering and Engineering Management (IEEM). Conference Publications, 1329–1333.
Sarkis, J., & Sundarraj, R.P. (2022). Hub location at digital equipment corporation: a comprehensive analysis of qualitative and quantitative factors. European Journal of Operational Research, 137(2), 336–347.
Schultz, G.P. (1970). The logic of health care facility planning. Socio-Economic Planning Science, 4(3), 383–393.
Sender, J., & Clausen, U. (2011). A new hub location model for network design of wagonload traffic. Procedia Social and Behavioral Sciences, 20, 90–99.
Serra, D. (1996). The coherent covering location problem. Regional Science, 75(1), 79–101.
Serra, D., & ReVelle, Ch. (1994). The PQ-median problem: location and districting of hierarchical facilities II. Heuristic solution methods. Location Science, 1, 299–312.
Serra, D., Marianov, V., & Revelle, Ch. (1992). The maximum-capture hierarchical location problem. European Journal of Operational Research, 62(3), 363–371.
Shahanaghi, K., Yavari, A., & Hamidi, M. (2015). Developing a model for capacitated hierarchical hub location with considering delivery time restriction. Applied mathematics in Engineering, Management and Technology, 3(1), 540–548.
Shavandi, H., & Mahlooji, H. (2007). Fuzzy hierarchical location-allocation models for congested systems. Journal of Industrial and Systems Engineering, 1(2), 171–189.
Shaw, Sh.L. (1993). Hub structures of major US passenger airlines. Journal of Transport Geography, 1(1), 47–55.
Sheu, J.B., & Lin, A.Y.S. (2012). Hierarchical facility network planning model for global logistics network configurations. Applied Mathematical Modelling, 36(7), 3053–3066.
Shmoys, D.B., Tardos, E., & Aardal, K. (1998). Approximation algorithms for facility location problems. STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 265–274.
Sun, Z.B., Wang, P.Ch., Chan, Ch.T., Lee, Ch.L. (2004). Fast hierarchical FLP model for VoD server deployment. In The 6th international conference on advanced communication technology, 2, 883–887.
Tcha, D.w., & Lee, B.i. (1984). A branch-and-bound algorithm for the multi-level uncapacitated location problem. European Journal of Operational Research, 18(1), 35–43.
Teixeira, J.C., & Antunes, P.A. (2008). A hierarchical location model for public facility planning. European Journal of Operational Research, 185(1), 92–104.
Thomadsen, T., & Larsen, J. (2007). A hub location problem with fully interconnected backbone and access networks. Computers & Operations Research, 34(8), 2520–2531.
Tien, J.M., & El-Tell, Kh. (1984). A quasi-hierarchical location–allocation model for primary health care planning. IEEE Transactions on Systems, Management and Cybernetics, 14(3), 373–380.
Tien, J.M., EL-Tell, Kh.,& Simons G.R. (1983). Improved formulations to the hierarchical health facility location-allocation problem. IEEE Transaction on Systems, Man and Cybernetics, 13(6), 1128–1132.
Tragantalerngsak, S., Holt J., & Ronnqvist, M. (1997). Lagrangian heuristics for the two-echelon, single- source, capacitated facility location problem. European Journal of Operational Research, 102(3), 611–625.
Vernekar, A., Anandalingam, G., & Dorny, C.N. (1990). Optimization of resource location in hierarchical computer networks. Computers and Operations Research, 17(4), 375–388.
Wang, Zh., Du D., Gabor, A.F., & Xu, D. (2010). An approximation algorithm for the k-level stochastic facility location problem. Operations Research Letters, 38(5), 386–389.
Yaman, H. (2009). The hierarchical hub median problem with single assignment. Transportation Research Part B, 43(6), 643–658.
Yaman, H., & Elloumi, S. (2012). Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & Operations Research, 39(11), 2725–2732.
Yasenovskiy, V., & Hodgson, J. (2007). Hierarchical location-allocation with spatial choice interaction modeling. Annals of the Association of American Geographers, 97(3), 496–511.
Yu, J., Liu Y., Chang, G.L., Ma, W., & Yang, X. (2009). Cluster based hierarchical model for urban transit hub location planning formulation, solution, and case study. Journal of the Transportation Research Board, 2112, 8–16.