×

zbMATH — the first resource for mathematics

A two-stage robust model for a reliable \(p\)-center facility location problem. (English) Zbl 1443.90239
Summary: We propose a two-stage robust model for reliable facility location when some facilities can be disrupted, for instance by a natural disaster. A reliable network is designed in a “proactive” planning phase, and when a facility is disrupted, its original clients can be reallocated to another available facility in a “reactive” phase. When demand and cost are uncertain, the initial design is also robust against the realizations (scenarios) of these parameters, which will only be revealed post-disruption. Based on the \(p\)-center location model, which attempts to optimize the worst-case performance of the network, our model is concerned with the reliability for every client. Three solution methods have been implemented and tested to solve the model, namely, a linear reformulation, a Benders dual cutting plane method, and a column-and-constraint generation method. We present an extensive numerical study to compare the performance of these methods. We find that, depending on the size of the instance (as given by the number of client sites and scenarios), either the Benders dual cutting plane method or column-and-constraint generation performs best. The effectiveness of our model is also examined in comparison with alternative facility location models.

MSC:
90B80 Discrete location and assignment
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Laporte, G.; Nickel, S.; Da Gama, F. S., Location Science (2015), Springer · Zbl 1329.90003
[2] An, Y.; Zeng, B.; Zhang, Y.; Zhao, L., Reliable p-median facility location problem: two-stage robust models and algorithms, Transp. Res. Part B: Methodol., 64, 54-72 (2014)
[3] Ben-Tal, A.; Ghaoui, L. E.; Nemirovski, A., Robust Optimization (2009), Princeton University Press
[4] Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 1, 35-53 (2004) · Zbl 1165.90565
[5] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 3, 464-501 (2011) · Zbl 1233.90259
[6] Kouvelis, P.; Yu, G., Robust Discrete Optimization and Its Applications (1997), Kluwer · Zbl 0873.90071
[7] Opher, B.; Joseph, M.; Hussein, N., Facility location: a robust optimization approach, Prod. Oper. Manag., 20, 5, 772-785 (2011)
[8] Lu, C. C., Robust weighted vertex p-center model considering uncertain data: an application to emergency management, Eur. J. Oper. Res., 230, 1, 113-121 (2013) · Zbl 1317.90166
[9] Atamtürk, A.; Zhang, M., Two-stage robust network flow and design under demand uncertainty, Oper. Res., 55, 4, 662-673 (2007) · Zbl 1167.90409
[10] Gabrel, V.; Lacroix, M.; Murat, C.; Remli, N., Robust location transportation problems under uncertain demands, Discret. Appl. Math., 164, 1, 100-111 (2014) · Zbl 1331.90096
[11] Caunhye, A. M.; Zhang, Y.; Li, M.; Nie, X., A location-routing model for prepositioning and distributing emergency supplies, Transp. Res. Part E: Logist. Transp. Rev., 90, 161-176 (2016)
[12] Álvarez-Miranda, E.; Fernández, E.; Ljubić, I., The recoverable robust facility location problem, Transp. Res. Part B: Methodol., 79, 93-120 (2015)
[13] Snyder, L. V.; Daskin, M. S., Reliability models for facility location: the expected failure cost case, Transp. Sci., 39, 3, 400-416 (2005)
[14] Cui, T.; Ouyang, Y.; Shen, Z. J.M., Reliable facility location design under the risk of disruptions, Oper. Res., 58, 4, 998-1011 (2010) · Zbl 1231.90266
[15] Shen, Z. J.M.; Zhan, R. L.; Zhang, J., The reliable facility location problem: formulations, heuristics, and approximation algorithms, INFORMS J. Comput., 23, 3, 470-482 (2011) · Zbl 1243.90096
[16] Li, Q.; Zeng, B.; Savachkin, A., Reliable facility location design under disruptions, Comput. Oper. Res., 40, 4, 901-909 (2013) · Zbl 1349.90168
[17] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Math. Program., 99, 2, 351-376 (2004) · Zbl 1089.90037
[18] Liebchen, C.; Lübbecke, M.; Möhring, R.; Stiller, S., The concept of recoverable robustness, linear programming recovery, and railway applications, (Ahuja, R. K.; Möhring, R. H.; Zaroliagis, C. D., Robust and Online Large-scale Optimization (2009), Springer), 1-27 · Zbl 1266.90044
[19] Goerigk, M.; Schöbel, A., Algorithm engineering in robust optimization, (Kliemann, L.; Sanders, P., Algorithm Engineering (2016), Springer), 245-279
[20] Daskin, M. S., Network and Discrete Location: Models, Algorithms, and Applications (2013), Wiley · Zbl 1276.90038
[21] Jia, H.; Ordóñez, F.; Dessouky, M., A modeling framework for facility location of medical services for large-scale emergencies, IIE Trans., 39, 1, 41-55 (2007)
[22] Huang, R.; Kim, S.; Menezes, M. B.C., Facility location for large-scale emergencies, Ann. Oper. Res., 181, 1, 271-286 (2010) · Zbl 1209.90236
[23] Averbakh, I.; Berman, O., Minimax regret p-center location on a network with demand uncertainty, Locat. Sci., 5, 4, 247-254 (1998) · Zbl 0928.90042
[24] Mladenovic, N.; Labbé, M.; Hansen, P., Solving the p-center problem with tabu search and variable neighborhood search, Networks, 42, 1, 48-64 (2003) · Zbl 1036.90046
[25] Snyder, L. V., Facility location under uncertainty: a review, IIE Trans., 38, 7, 547-564 (2006)
[26] Albareda-Sambola, M.; Landete, M.; Monge, J. F.; Sainz-Pardo, J. L., Introducing capacities in the location of unreliable facilities, Eur. J. Oper. Res., 259, 1, 175-188 (2017) · Zbl 1394.90382
[27] Azad, N.; Hassini, E., Recovery strategies from major supply disruptions in single and multiple sourcing networks, Eur. J. Oper. Res., 275, 2, 481-501 (2019) · Zbl 1430.90370
[28] Govindan, K.; Fattahi, M.; Keyvanshokooh, E., Supply chain network design under uncertainty: a comprehensive review and future research directions, Eur. J. Oper. Res., 263, 1, 108-141 (2017) · Zbl 1380.90041
[29] Snyder, L. V.; Atan, Z.; Peng, P.; Rong, Y.; Schmitt, A. J.; Sinsoysal, B., OR/MS models for supply chain disruptions: A review, IIE Trans., 48, 2, 89-109 (2016)
[30] Louveaux, F., Discrete stochastic location models, Ann. Oper. Res., 6, 2, 23-34 (1986)
[31] Ljubić, I.; Mutzel, P.; Zey, B., Stochastic survivable network design problems: theory and practice, Eur. J. Oper. Res., 256, 2, 333-348 (2017) · Zbl 1394.90450
[32] Bayram, V.; Yaman, H., Shelter location and evacuation route assignment under uncertainty: a Benders decomposition approach, Transp. Sci., 52, 2, 416-436 (2017)
[33] Rohaninejad, M.; Sahraeian, R.; Tavakkoli-Moghaddam, R., An accelerated Benders decomposition algorithm for reliable facility location problems in multi-echelon networks, Comput. Ind. Eng., 124, 523-534 (2018)
[34] Zarrinpoor, N.; Fallahnezhad, M. S.; Pishvaee, M. S., Design of a reliable hierarchical location-allocation model under disruptions for health service networks: a two-stage robust approach, Comput. Ind. Eng., 109, 130-150 (2017)
[35] Cheng, C.; Qi, M.; Zhang, Y.; Rousseau, L. M., A two-stage robust approach for the reliable logistics network design problem, Transp. Res. Part B Methodol., 111, 185-202 (2018)
[36] http://www.optimization-online.org/DB_FILE/2009/03/2263.pdf.
[37] Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 5, 457-461 (2013) · Zbl 1286.90143
[38] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems. I: the p-centers, SIAM J. Appl. Math., 37, 3, 513-538 (1979) · Zbl 0432.90074
[39] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252 (1962) · Zbl 0109.38302
[40] Geoffrion, A. M., Generalized Benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024
[41] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley · Zbl 0652.90067
[42] Talla Nobibon, F.; Leus, R., Complexity results and exact algorithms for robust knapsack problems, J. Optim. Theory Appl., 161, 2, 533-552 (2014) · Zbl 1291.90209
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.