×

Distributionally robust facility location with bimodal random demand. (English) Zbl 1511.90289

Summary: In this paper, we consider a decision-maker who wants to determine a subset of locations from a given set of candidate sites to open facilities and accordingly assign customer demand to these open facilities. Unlike classical facility location settings, we focus on a new setting where customer demand is bimodal, i.e., display, or belong to, two spatially distinct probability distributions. We assume that these two distributions are ambiguous, and only their mean values and ranges are known. Therefore, we construct a scenario-wise ambiguity set with two scenarios corresponding to the demand’s two distinct distributions. Then, we formulate a distributionally robust facility location (DRFL) model that seeks to find the number and locations of facilities to open that minimize the fixed cost of opening facilities and the worst-case (maximum) expectation of transportation and unmet demand costs. We take the worst-case expectations over all possible demand distributions residing in the scenario-wise ambiguity set. We propose a decomposition-based algorithm to solve our min-max DRFL model and derive lower bound inequalities that accelerate the algorithm’s convergence. In a series of numerical experiments, we demonstrate our approach’s superior computational and operational performance compared with the stochastic programming approach and a distributionally robust approach that does not consider the demand’s bimodality. Our results draw attention to the need to consider the multi-modality and ambiguity of the demand distribution in many strategic real-world problems.

MSC:

90B80 Discrete location and assignment
90C15 Stochastic programming
90C17 Robustness in mathematical programming

Software:

RSOME
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi-Javid, A.; Seyedi, P.; Syam, S. S., A survey of healthcare facility location, Computers & Operations Research, 79, 223-263 (2017) · Zbl 1391.90365
[2] Basciftci, B.; Ahmed, S.; Shen, S., Distributionally robust facility location problem under decision-dependent stochastic demand, European Journal of Operational Research (2020)
[3] Ben-Tal, A.; Den Hertog, D.; Vial, J.-P., Deriving robust counterparts of nonlinear uncertain inequalities, Mathematical Programming, 149, 1-2, 265-299 (2015) · Zbl 1308.65089
[4] Bertsimas, D.; Popescu, I., Optimal inequalities in probability theory: a convex optimization approach, SIAM Journal on Optimization, 15, 3, 780-804 (2005) · Zbl 1077.60020
[5] Bertsimas, D.; Sim, M., The price of robustness, Operations Research, 52, 1, 35-53 (2004) · Zbl 1165.90565
[6] Birge, J. R.; Louveaux, F., Introduction to Stochastic Programming (2011), Springer Science & Business Media · Zbl 1223.90001
[7] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[8] Burki, T., Global shortage of personal protective equipment, The Lancet Infectious Diseases, 20, 7, 785-786 (2020)
[9] Chan, Y., Location Theory and Decision Analysis (2001), Springer
[10] Chen, Z.; Sim, M.; Xiong, P., Robust stochastic optimization made easy with rsome, Management Science (2020)
[11] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58, 3, 595-612 (2010) · Zbl 1228.90064
[12] Hanasusanto, G. A.; Kuhn, D.; Wallace, S. W.; Zymler, S., Distributionally robust multi-item newsvendor problems with multimodal demand distributions, Mathematical Programming, 152, 1-2, 1-32 (2015) · Zbl 1327.90153
[13] Hao, Z.; He, L.; Hu, Z.; Jiang, J., Robust vehicle pre-allocation with uncertain covariates, Production and Operations Management (2019)
[14] Jiang, R.; Shen, S.; Zhang, Y., Integer programming approaches for appointment scheduling with random no-shows and service durations, Operations Research, 65, 6, 1638-1656 (2017) · Zbl 1382.90042
[15] Kim, S.; Pasupathy, R.; Henderson, S. G., A guide to sample average approximation, (Handbook of Simulation Optimization (2015), Springer), 207-243
[16] Kleywegt, A. J.; Shapiro, A.; Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM Journal on Optimization, 12, 2, 479-502 (2002) · Zbl 0991.90090
[17] Kundu, D.; Manglick, A., Discriminating between the weibull and log-normal distributions, Naval Research Logistics (NRL), 51, 6, 893-905 (2004) · Zbl 1052.62019
[18] Lei, C.; Lin, W.-H.; Miao, L., A multicut l-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem, European Journal of Operational Research, 238, 3, 699-710 (2014) · Zbl 1338.90054
[19] Lei, C.; Lin, W.-H.; Miao, L., A two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertainty, Computers & Operations Research, 67, 75-89 (2016) · Zbl 1349.90097
[20] Liu, K.; Li, Q.; Zhang, Z.-H., Distributionally robust optimization of an emergency medical service station location and sizing problem with joint chance constraints, Transportation Research Part B: Methodological, 119, 79-101 (2019)
[21] Luo, F.; Mehrotra, S., Distributionally robust optimization with decision dependent ambiguity sets, Optimization Letters, 14, 8, 2565-2594 (2020) · Zbl 1460.90121
[22] Mak, H.-Y.; Rong, Y.; Shen, Z.-J. M., Infrastructure planning for electric vehicles with battery swapping, Management Science, 59, 7, 1557-1575 (2013)
[23] Mak, H.-Y.; Rong, Y.; Zhang, J., Appointment scheduling with limited distributional information, Management Science, 61, 2, 316-334 (2014)
[24] Melo, M. T.; Nickel, S.; Saldanha-Da-Gama, F., Facility location and supply chain management-a review, European Journal of Operational Research, 196, 2, 401-412 (2009) · Zbl 1163.90341
[25] Mohajerin Esfahani, P.; Kuhn, D., Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations, Mathematical Programming, 171, 1-2, 115-166 (2018) · Zbl 1433.90095
[26] Owen, S. H.; Daskin, M. S., Strategic facility location: a review, European Journal of Operational Research, 111, 3, 423-447 (1998) · Zbl 0938.90048
[27] ReVelle, C. S.; Eiselt, H. A., Location analysis: a synthesis and survey, European Journal of Operational Research, 165, 1, 1-19 (2005) · Zbl 1112.90362
[28] Saif, A.; Delage, E., Data-driven distributionally robust capacitated facility location problem, European Journal of Operational Research (2020) · Zbl 1487.90446
[29] Santiváñez, J. A.; Carlo, H. J., Reliable capacitated facility location problem with service levels, EURO Journal on Transportation and Logistics, 7, 4, 315-341 (2018)
[30] Senaldi, E., Inventory management: connecting one arm to another (2018)
[31] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on Stochastic Programming: Modeling and Theory (2014), SIAM · Zbl 1302.90003
[32] Shehadeh, K.S., 2020. A distributionally robust optimization approach for a stochastic mobile facility routing and scheduling problem. arXiv preprint arXiv:2009.10894.
[33] Shehadeh, K. S.; Cohn, A. E.; Jiang, R., A distributionally robust optimization approach for outpatient colonoscopy scheduling, European Journal of Operational Research, 283, 2, 549-561 (2020) · Zbl 1431.90075
[34] Smith, J. E.; Winkler, R. L., The optimizer’s curse: Skepticism and postdecision surprise in decision analysis, Management Science, 52, 3, 311-322 (2006)
[35] Snyder, L. V., Facility location under uncertainty: a review, IIE Transactions, 38, 7, 547-564 (2006)
[36] Soyster, A. L., Convex programming with set-inclusive constraints and applications to inexact linear programming, Operations Research, 21, 5, 1154-1157 (1973) · Zbl 0266.90046
[37] Thiele, A., A note on issues of over-conservatism in robust optimization with cost uncertainty, Optimization, 59, 7, 1033-1040 (2010) · Zbl 1206.90086
[38] Thiele, A.; Terry, T.; Epelman, M., Robust linear optimization with recourse, Rapport Technique, 4-37 (2009)
[39] Turkoglu, D. C.; Genevois, M. E., A comparative survey of service facility location problems, Annals of Operations Research, 1-70 (2019)
[40] Vaagen, H.; Wallace, S. W., Product variety arising from hedging in the fashion supply chains, International Journal of Production Economics, 114, 2, 431-455 (2008)
[41] Wang, S.; Chen, Z.; Liu, T., Distributionally robust hub location, Transportation Science, 54, 5, 1189-1210 (2020)
[42] WHO, 2020. How WHO is re-imagining and fixing the links in the supply chains during COVID-19. https://www.who.int/news-room/feature-stories/detail/how-who-is-re-imagining-and-fixing-the-links-in-the-supply-chains-during-covid-19.
[43] Wu, C.; Du, D.; Xu, D., An approximation algorithm for the two-stage distributionally robust facility location problem, (Advances in Global Optimization (2015), Springer), 99-107 · Zbl 1327.90098
[44] Zhang, A.; Kang, J. E.; Kwon, C., Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles, Transportation Research Part B: Methodological, 103, 5-29 (2017)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.