Reliable location-allocation model for congested systems under disruptions using accelerated Benders decomposition

Document Type : Research Paper


1 Department of industrial engineering, Yazd University, Yazd, Iran.

2 Department of industrial engineering, Iran University of Science and Technology, Tehran, Iran.


This paper aims to propose a reliable location-allocation model where facilities are subject to the risk of disruptions. Since service facilities are expected to satisfy random and heavy demands, we model the congested situations in the system within a queuing framework which handles two sources of uncertainty associated with demand and service. To insure the service quality, a minimum limit reflected in the customers’ expected waiting time is considered in the model. We also consider the geographical accessibility of the service network in terms of the proximity of a facility to the potential demands. The model determines the optimal number and locations of facilities and the corresponding customer assignments in such a way as to minimize the fixed installation cost as well as expected traveling, serving and penalty costs. To obtain exact solution of the proposed model, a Benders decomposition algorithm enhanced by two efficient accelerating methods including valid inequalities and knapsack inequalities is proposed. Numerical results illustrate the applicability of the proposed model as well as the effectiveness of the designed solution procedure.


Main Subjects

Aboolian, R., Berman, O., & Drezner, Z. (2009). The multiple server center location problem. Annals of Operations Research, 167(1), 337–352.
Alcaraz, J., Landete, M., Monge, J.F., & Sainz-Pardo, J.L. (2015). Strengthening the reliability fixed-charge location model using clique constraints. Computers &Operations Research, 60, 14–26.
An, Y., Zeng, B., Zhang, Y., & Zhao, L. (2014). Reliable p-median facility location problem: two-stage robust models and algorithms. Transportation Research Part B, 64, 54–72.
Aydin, N., & Murat, A. (2013). A swarm intelligence based sample average approximation algorithm for the capacitated reliable facility location problem. International Journal of Production Economics, 145(1), 173–183.
Benders, J.F., 1962. Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik,4(1), 238–252.
Berman Berman,O., Krass, D., & Menezes, M.B.C. (2007). Facility reliability issues in network p-Median problems: strategic centralization and co-location effects. Operations Research, 55(2), 332–350.
Boffey, B., Galvao, R., & Espejo, L.  (2007). A review of congestion models in the location of facilities with immobile servers. European Journal of Operational Research, 178(3), 643–662.
Camargo, R.S.D., Miranda, G., Luna, H.P., 2008. Benders decomposition for the uncapacitated multiple allocation hub location problem.Computers & Operations Research, 35, 1047–1064.
Castillo, I., Ingolfsson, A., Sim, T., 2009. Social Optimal Location of Facilities with Fixed Servers, Stochastic Demand and Congestion, Production and Operations Management, 18, 721 – 736.
Chen, Q., Li, X., & Ouyang, Y. (2011). Joint inventory-location problem under the risk of probabilistic facility disruptions. Transportation Research Part B, 45(7), 991–1003.
Cordeau, J.F., Pasin, F., Solomon, M.M., (2006). An integrated model for logistics network design. Annals of Operations Research, 144 (1), 59–82.
Cui, T., Ouyang, Y., & Shen, Z.M. (2010).Reliable facility location under the risk of disruptions. Operations Research, 58(4), 998–1011.
Drezner, Z. (1987). Heuristic solution methods for two location problems with unreliable facilities. Journal of the Operational Research Society, 38(6), 509–514.
Gross, D., Harris, C.M. Fundamental of Queuing Theory, 3rd ed., Wiley Interscience, New York, 1988.
Hajipour, V., Rahmati, S.H.A., Pasandideh, S.H.R., & Niaki, S.T.A. (2014). A multi-objective harmony search algorithm to optimize multi-server location–allocation problem in congested systems. Computers & Industrial Engineering, 72, 187–197.
Hajipour, V., Zanjirani Farahani, R., & Fattahi, P. (2016). Bi-objective vibration damping optimization for congested location-pricing problem. Computers & Operations Research, 70, 87-100.
Huang, S., Batta, R., & Nagi, R. (2005). Distribution network design: selection and sizing of congested connections. Naval Research Logistics, 52(8), 701–712.
Li, X., & Ouyang, Y. (2010). A continuum approximation approach to reliable facility location design under correlated probabilistic disruptions. Transportation Research Part B, 44(4), 535–548.
Li, X., Ouyang, Y., & Peng, F. (2013a). A supporting station model for reliable infrastructure location design under interdependent disruptions. Transportation Research Part E, 60,  80–93.
Li, Q., Zeng, B., & Savachkin, A. (2013b). Reliable facility location design under disruptions. Computers & Operations Research, 40(4), 901–909.
Lim, M., Daskin, M., Bassamboo, A., & Chopra, S. (2010). A facility reliability problem: formulation, properties, and algorithm. Naval Research Logistics, 57(1), 58–70.
Lim, M.K., Bassamboo, A., Chopra, S., & Daskin, M.S. (2013). Facility location decisions with random disruption and imperfect estimation. Manufacturing & Service Operations Management, 15(2), 239–249.
Marianov,V., & Serra, D. (1998). Probabilistic maximal covering location-allocation models for congested systems. Journal of Regional Science, 38, 401–424.
Marianov, V., &Serra, D. (2001). Hierarchical location-allocation models for congested systems. European Journal of Operational Research, 135(1), 195–208.
Marianov, V. (2003). Location of multiple–server congestible facilities for maximizing expected demand, when services are non-essential. Annals of Operations Research, 123(1), 125–141.
Marianov, V., Rı´os, M., & Icaza, M.J.  (2008).  Facility location for market capture when users rank facilities by shorter travel and waiting times. European Journal of Operational Research, 191(1), 32–44.
Nosek, R.A., & Wilson, J.P. (2001). Queuing theory and customer satisfaction: a review of terminology, trends, and applications to pharmacy practice. Hospital Pharmacy, 36(3), 275–279.
Peng, P., Snyder, L.V., Liu, Z., & Lim, A. (2011). Design of reliable logistics networks with facility disruptions. Transportation Research Part B, 45(8), 1190–1211.
Pishvaee, M.S., Razmi, J., & Torabi, S.A. (2014). An accelerated Benders decomposition algorithm for sustainable supply chain network design under uncertainty: A case study of medical needle and syringe supply chain. Transportation Research Part E , 67, 14–38.
Preater, J. (2002). Queues in health. Health Care Management Science, 5(4), 283.
Rahmati, S. H. A., Hajipour, V.,  & Niaki, S. T. A. (2013). A soft-computing Pareto based meta-heuristic algorithm for a multi-objective multi-server facility location problem. Applied Soft Computing, 13(4), 1728–1740.
Rei, W., Cordeau, J.F., Gendreau, M., Soriano, P., 2009. Accelerating benders decomposition by local branching. INFORMS Journal on Computing, 21(2), 333–345.
ReVelle, C.S., & Eiselt, H.A. (2005).Location analysis: A synthesis and survey. European Journal of Operational Research, 165(1), 1–19.
Revelle, C. S., Eiselt, H. A., & Daskin, M. S. (2008). A bibliography for some fundamental problem categories in discrete location science. European Journal of Operational Research, 184(3), 817–848.
Santoso, T., Ahmed, S., Goetschalckx, M., &Shapiro, A.(2005). A stochastic programming approach for supply chain network design under uncertainty, European Journal of  Operational Research, 167(1), 96–115.
Shavandi, H., & Mahlooji, H. (2006). A fuzzy queuing location model with a genetic algorithm for congested systems. Applied Mathematics and Computation, 181(1), 440–456.
Shen, Z., Zhan, R., & Zhang, J. (2011). The reliable facility location problem: formulations, heuristics, and approximation algorithms. INFORMS Journal on Computing, 23(3), 470–482.
Snyder, L.V., & Daskin, M.S. (2005). Reliability models for facility location: the expected failure case. Transportation Science, 39(3), 400–416.
Syam, S.S. (2008).  A multiple server location-allocation model for service system design. Computers and Operations Research, 35(7), 2248–2265.
Vatsa, A.K., Jayaswal, S., (2016). A new formulation and Benders decomposition for the multi-period maximal covering facility location problem with server uncertainty. European Journal of Operational Research, 251(2), 404–418.
Verstichel, J., Kinable, J., Causmaecker, P.D., &Berghe, G.V., (2015). A Combinatorial Benders׳ decomposition for the lock scheduling problem. Computers & Operations Research, 54, 117–128.
Wang, Q., Batta, R., &Rump, C. (2002). Algorithms for a facility location problem with stochastic customer demand and immobile servers. Annals of Operations Research, 111(1), 17–34.
Wang, X., & Ouyang, Y. (2013). A continuum approximation approach to competitive facility location design under facility disruption risks. Transportation Research Part B, 50, 90–103.
Weber, Uber den Standort der Industrian, University of Chicago Press, 1909, Translated as (in 1929): Alfred Weber’s Theory of the Location of Industries.
Yun, L., Qin, Y., Fan, H., Ji, C., Li, X., Jia, L., (2015). A reliability model for facility location design under imperfect information. Transportation Research Part B, 81, 596–615.
Zarrinpoor, N., & Seifbarghy, M. (2011). A competitive location model to obtain a specific market share while ranking facilities by shorter travel time. International Journal of Advanced Manufacturing Technology, 55(5), 807–816.
Zhang, Y., Berman, O., &Verter, V. (2009). Incorporating congestion in preventive healthcare facility network design, European Journal of Operational Research, 198(3), 922–935.
Zhang,Y., Berman,O., Verter,V.,2012. The impact of client choice on preventive healthcare facility network design, OR Spectrum, 34, 349–370.
Zhang,Y., Snyder, L.V., Qi, M., Miao, L. (2016). A heterogeneous reliable location model with risk pooling under supply disruptions. Transportation Research Part B, 83, 151–178.