Multi and Single-Period Uncertain Set Covering Location Problems with Robust Optimization Approach

Authors

https://doi.org/10.48314/anowa.v1i1.54

Abstract

In recent years, covering location problems, owing to their numerous applications, have attracted  significant attention. Since to the presence of uncertainty in real world data, in this paper a Single-Period Set Covering Location Problem (SPSCLP) as well as a Multi-Period Set Covering Location Problem (MPSCLP) under uncertainty in fixed establishment cost parameter are discussed by robust optimization approach. Various  robust optimization approaches such as box approach, ellipsoidal approach and conservatism by adjustment approach are developed to this end. The robust counterparts of  SPSCLP and MPSCLP are presented and then OR-Library dataset are  used to analyze the models.

Keywords:

Single-period set covering location problem, Multi-period set covering location problem, Uncertainty, Robust optimization

References

  1. [1] Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations research, 19(6), 1363–1373. https://doi.org/10.1287/opre.19.6.1363
  2. [2] Karp, R. M. (2009). Reducibility among combinatorial problems. In 50 years of integer programming 1958-2008: From the early years to the state-of-the-art (pp. 219–241). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68279-0_8
  3. [3] Zadeh, L. A. (1965). Fuzzy sets. Information and control, 8(3), 338–353. https://doi.org/10.1016/S0019-9958(65)90241-X
  4. [4] Eaton, D. J., Daskin, M. S., Simmons, D., Bulloch, B., & Jansma, G. (1985). Determining emergency medical service vehicle deployment in Austin, Texas. Interfaces, 15(1), 96-108. https://doi.org/10.1287/inte.15.1.96
  5. [5] Ceria, S., Nobili, P., & Sassano, A. (1998). A lagrangian-based heuristic for large-scale set covering problems. Mathematical programming, 81(2), 215-281. https://doi.org/10.1007/BF01581106
  6. [6] Desrochers, M., Dumas, Y., Soumis, F., & Trudeau, P. (1991). Column generation approaches to the airline crew scheduling problems. TRISTAN i (triennial symposium on transportation analysis) (pp. 1-133). TRISTAN I Program. https://tristanconference.org/system/tristan-i/documents/TRISTAN-I-program.pdf#page=20
  7. [7] Ahmed, Sh., & Papageorgiou, D. J. (2013). Probabilistic set covering with correlations. Operations research, 61(2), 438-452. https://doi.org/10.1287/opre.1120.1135
  8. [8] Zanjirani Farahani, R., & Hekmatfar, M. (2009). Facility location: Concepts, models, algorithms and case studies. Physica-Verlag Heidelber(Springer). https://doi.org/10.1007/978-3-7908-2151-2
  9. [9] Dantzig, G. B. (1955). Linear programming under uncertainty. Management science, 1(3), 197-203. https://doi.org/10.1287/mnsc.1.3-4.197
  10. [10] Deng, J. (1982). Control problems of grey systems. Systems & control letters, 1(5), 288–294. https://doi.org/10.1016/S0167-6911(82)80025-X
  11. [11] Beale, E. M. L., & Dantzig, G. B. (1955). On minimizing a convex function subject to linear inequalities. Journal of the royal statistical society: Series b (methodological), 17(2), 173-184. https://doi.org/10.1111/j.2517-6161.1955.tb00191.x
  12. [12] Cheng, Y., Chen, X., Li, H., Cheng, Z., Jiang, R., Lu, J., & Fu, H. (2018). Analysis and comparison of bayesian methods for measurement uncertainty evaluation. Mathematical problems in engineering, 7509046. https://doi.org/10.1155/2018/7509046
  13. [13] Liu, B. (2007). Uncertainty theory. Springer Berlin Heidelberg (Springer Verlag). https://doi.org/10.1007/978-3-540-73165-8
  14. [14] Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157. https://doi.org/10.1287/opre.21.5.1154
  15. [15] Beraldi, P., & Ruszczyński, A. (2002). The probabilistic set-covering problem. Operations research, 50(6), 956-967. https://doi.org/10.1287/opre.50.6.956.345
  16. [16] Hwang, H. S. (2004). A stochastic set-covering location model for both ameliorating and deteriorating items. Computers and industrial engineering, 46(2), 313-319. https://doi.org/10.1016/j.cie.2003.12.010
  17. [17] Chiang, C. I., Hwang, M. J., & Liu, Y. H. (2005). An alternative formulation for certain fuzzy set-covering problems. Mathematical and computer modelling, 42(4-3), 363-365. https://doi.org/10.1016/j.mcm.2004.05.012
  18. [18] Saxena, A., Goyal, V., & Lejeune, M. A. (2010). MIP reformulations of the probabilistic set covering problem. Mathematical programming, 121(1), 1-31. https://doi.org/10.1007/s10107-008-0224-y
  19. [19] Gunawardane, G. (1982). Dynamic versions of set covering type public facility location problems. European journal of operational research, 10(2), 190-195. https://doi.org/10.1016/0377-2217(82)90159-X
  20. [20] Moradi, M., Salahi, M., Bardsiri, M., & Jamalian, A. (2014). A new model based on supply chain network design under uncertainty. Journal of operations research in its applications, 11(2), 26-29. (In Persian). http://jamlu.liau.ac.ir/article-1-821-fa.html
  21. [21] Ben-Tal, A., El-Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Springer. https://www.torrossa.com/en/resources/an/5576051
  22. [22] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53. https://doi.org/10.1287/opre.1030.0065
  23. [23] Inuiguchi, M., & Sakawa, M. (1998). Robust optimization under softness in a fuzzy linear programming problem. International journal of approximate reasoning, 18(1-2), 21-34. https://doi.org/10.1016/S0888-613X(97)10002-0
  24. [24] Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations research, 43(2), 264-281. https://doi.org/10.1287/opre.43.2.264
  25. [25] Pan, F., & Nagi, R. (2010). Robust supply chain design under uncertain demand in agile manufacturing. Computers & operations research, 37(4), 668-683. https://doi.org/10.1016/j.cor.2009.06.017
  26. [26] Rezvani, S., Moghadas, M., & Zanjirani Farahani, D. (2019). The dynamic covering location problem with uncertainty [Thesis]. (In Persian). https://ganj.irandoc.ac.ir/#/articles/59b73a8999393ef0664a8ecaf73369b2
  27. [27] Pereira, J., & Averbakh, I. (2013). The robust set covering problem with interval data. Annals of operations research, 207(1), 217-235. https://doi.org/10.1007/s10479-011-0876-5%0A%0A
  28. [28] Lutter, P., Degel, D., Büsing, C., Koster, A. M. C. A., & Werners, B. (2017). Improved handling of uncertainty and robustness in set covering problems. European journal of operational research, 263(1), 35-49. https://doi.org/10.1016/j.ejor.2017.04.044
  29. [29] Ben-Tal, A., & Nemirovski, N. (1998). Robust convex optimization. Mathematics of operations research, 23(4), 769-805. https://doi.org/10.1287/moor.23.4.769
  30. [30] El Ghaoui, L., Lebret, H. (1997). Robust solutions to least-squares problems to uncertain data matrices. SIAM journal on matrix analysis and applications, 18(4), 1035-1064. https://doi.org/10.1137/S0895479896298130

Downloads

Published

2025-03-28

Issue

Vol. 1 No. 1 (2025): Annals of Optimization With Applications (ANOWA)

Section

Articles

How to Cite

Rezvani, S. ., Moeen Moghadas, F. ., & Dadi, Z. . (2025). Multi and Single-Period Uncertain Set Covering Location Problems with Robust Optimization Approach. Annals of Optimization With Applications, 1(1), 50-65. https://doi.org/10.48314/anowa.v1i1.54

Similar Articles

1-10 of 12

You may also start an advanced similarity search for this article.