Modeling and Solving Dynamic Maximal Covering Location Problem Considering Backup Services; Case Study of a Crisis Event in District 3 of Tehran

Document Type : Article

Authors

1 Department of Industrial Engineering, Faculty of Engineering Alzahra University, Tehran, Iran.

2 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.

Abstract

In this research, we look at a dynamic maximal covering location problem, where the structure of the service-providing facilities consists of independent units that have the ability to move, and these units are called modules. The main goal of the problem is to provide maximum service to people who are in crisis and need basic help. The model of this problem first determines the location of the facilities, and with the occurrence of each crisis, according to the needs that are created in each demand area, the modules responding to the same needs are sent to the facilities of those areas and are deployed in the location, from which they are moved away after the task of delivering service ends.  The innovation in this paper is that the modules may become unavailable for any reason and cannot cover the demand assigned to them. For this reason, modules, in addition to providing main services to demand points, in case of failure of some of these modules and their unavailability, the surrounding modules can cover the demand of points that have been neglected by providing backup service and compensate for this deficiency, where the amount of main and backup demand that each module responds to is determined by the model. The main goal of this research is to assign the maximum amount of main and backup service to people who are in crisis, which is of utmost importance to the livelihood of these people. In this research, we first created a mathematical model of mixed integer linear programming. Afterwards, we conducted a case study on Tehran's third district, where all the factors and parameters related to the model were considered with special attention to the real conditions of the studied area. After introducing the model and parameters related to district three, we solved the model using GAMS software. Furthermore, we implemented Bender's decomposition algorithm as an ultimate solution to the model.  Finally, we performed a sensitivity analysis on some parameters of the model. We observed that the changes in the parameters affect the backup service more than the base service. 

Keywords

Main Subjects

References

References
Church, R. and Velle, C.R., 1974. The maximal covering location problem. Papers In Regional science, 32(1), pp.101-118. https://doi.org/10.1111/j.1435-5597.1974.tb00902.x
2. Alizadeh, R., Nishi, T., Bagherinejad, J. and Bashiri, M., 2021. Multi-period maximal covering location problem with capacitated facilities and modules for natural disaster relief services. Applied Sciences, 11(1), p.397. https://doi.org/10.3390/app11010397
Vatsa, A.K. and 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), pp.404-418. https://doi.org/10.1016/j.ejor.2015.11.025
Allman, A. and Zhang, Q., 2020. Dynamic location of modular manufacturing facilities with relocation of individual modules. European Journal of Operational Research, 286(2), pp.494-507. https://doi.org/10.1016/j.ejor.2020.03.045
Atta, S., Sinha Mahapatra, P.R. and Mukhopadhyay, A., 2018. Solving maximal covering location problem using genetic algorithm with local refinement. Soft Computing, 22, pp.3891-3906. https:// doi.org/ 10.1007/s00500-017-2598-3
Porras, C., Fajardo, J., Rosete, A. and Masegosa, A.D., 2021. Partial evaluation and efficient discarding for the maximal covering location problem. IEEE Access, 9, pp.20542-20556. https://doi.org/10.1109/ACCESS.2021.3055295
Zarandi, M.H.F., Davari, S. and Sisakht, S.A.H., 2013. The large-scale dynamic maximal covering location problem. Mathematical and Computer Modelling, 57(3-4), pp.710-719. https://doi.org/10.1016/j.mcm.2012.07.028
Jia, H., Ordóñez, F. and Dessouky, M., 2007. A modeling framework for facility location of medical services for large-scale emergencies. IIE Transactions, 39(1), pp.41-55. https://doi.org/10.1080/07408170500539113
Ala, A., Deveci, M., Bani, E.A. and Sadeghi, A.H., 2024. Dynamic capacitated facility location problem in mobile renewable energy charging stations under sustainability consideration. Sustainable Computing: Informatics and Systems, 41, p.100954. https://doi.org/10.1016/j.suscom.2023.100954
ElKady, S.K. and Abdelsalam, H.M., 2016. A modified particle swarm optimization algorithm for solving capacitated maximal covering location problem in healthcare systems. Applications of Intelligent Optimization in Biology and Medicine: Current Trends and Open Problems, pp.117-133. https://doi.org /10.1007/978-3-319-21212-8_5
Xu, J., Murray, A., Wang, Z. and Church, R., 2020. Challenges in applying capacitated covering models. Transactions in GIS, 24(2), pp.268-290. https://doi.org/10.1111/tgis.12608
Gazani, M. and Niaki, S., 2021. The capacitated maximal covering location problem with heterogeneous facilities and vehicles and different setup costs: An effective heuristic approach. International Journal of Industrial Engineering Computations, 12(1), pp.79-90. https://doi.org/10.5267/j.ijiec.2020.9.002
13. Vatsa, A.K. and Jayaswal, S., 2021. Capacitated multi-period maximal covering location problem with server uncertainty. European Journal of Operational Research, 289(3), pp.1107-1126. https://doi.org/10.1016/j.ejor.2020.07.061
Zhang, G., Ma, R., Kong, Y., Lian, C., Guo, H. and Zhai, S., 2024. A multi-period capacitated facility location problem with maximum travel time and backup service for locating and sizing EMS stations. Computational Urban Science, 4(1), pp.1-14. https://doi.org /10.1007/s43762-024-00143-z
Calderín, J.F., Masegosa, A.D. and Pelta, D.A., 2017. An algorithm portfolio for the dynamic maximal covering location problem. Memetic Computing, 9(2), pp.141-151. https://doi.org /10.1007/s12293-016-0210-5
Hajipour, V., Fattahi, P., Bagheri, H. and Babaei Morad, S., 2022. Dynamic maximal covering location problem for fire stations under uncertainty: soft-computing approaches. International Journal of System Assurance Engineering and Management, 13(1), pp.90-112. https://doi.org /10.1007/s13198-021-01109-8
Zarandi, M.H.F., Davari, S. and Sisakht, S.A.H., 2013. The large-scale dynamic maximal covering location problem. Mathematical and Computer Modelling, 57(3-4), pp.710-719. https://doi.org/10.1016/j.mcm.2012.07.028
Marín, A., Martínez-Merino, L.I., Rodríguez-Chía, A.M. and Saldanha-da-Gama, F., 2018. Multi-period stochastic covering location problems: Modeling framework and solution approach. European Journal of Operational Research, 268(2), pp.432-449. https://doi.org/10.1016/j.ejor.2018.01.040
Sonego, M., Echeveste, M.E.S. and Debarba, H.G., 2018. The role of modularity in sustainable design: A systematic review. Journal of Cleaner Production, 176, pp.196-209. https://doi.org/10.1016/j.jclepro.2017.12.106
20. Silva, A., Aloise, D., Coelho, L.C. and Rocha, C., 2021. Heuristics for the dynamic facility location problem with modular capacities. European Journal of Operational Research, 290(2), pp.435-452. https://doi.org/10.1016/j.ejor.2020.08.018
Belieres, S., Hewitt, M., Jozefowiez, N., Semet, F. and Van Woensel, T., 2020. A Benders decomposition-based approach for logistics service network design. European Journal of Operational Research, 286(2), pp.523-537. https://doi.org/10.1016/j.ejor.2020.03.056
Bucarey, V., Fortz, B., González-Blanco, N., Labbé, M. and Mesa, J.A., 2022. Benders decomposition for network design covering problems. Computers & Operations Research, 137, p.105417. https://doi.org/10.1016/j.cor.2021.105417
Liu, B., Bissuel, C., Courtot, F., Gicquel, C. and Quadri, D., 2024. A generalized Benders decomposition approach for the optimal design of a local multi-energy system. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2024.05.013
Weng, W., Chu, C. and Wu, P., 2024. A Benders decomposition algorithm for resource allocation with multi-resource operations. International Journal of Production Research, pp.1-17. https://doi.org /10.1080/00207543.2024.2334419
Cordeau, J.F., Furini, F. and Ljubić, I., 2019. Benders decomposition for very large scale partial set covering and maximal covering location problems. European Journal of Operational Research, 275(3), pp.882-896 https://doi.org/10.1016/j.ejor.2018.12.021.
Azad, N. and Hassini, E., 2019. A benders decomposition method for designing reliable supply chain networks accounting for multimitigation strategies and demand losses. Transportation Science, 53(5), pp.1287-1312. https://doi.org/10.1287/trsc.2018.0875
 
Sabiza, H., 2024. Modeling of dynamic maximal covering location problem considering module breakdown. Unpublished master’s thesis. Faculty of Engineering Alzahra University. Tehran, Iran. [In Persian].
 
 
 
 
 
Sharif Journal of Industrial Engineering & Management
Volume 41, Issue 2 - Serial Number 2
February 2026
Pages 93-110

Files

Share

How to cite

Statistics