Simultaneous‎ ‎Location‎ ‎of k Portable Emergency Service Centers and Reconstruction of a Damaged Network

Document Type : Original Scientific Paper

Authors

1 ‎Department of Mathematics, ‎Shahed University,‎ ‎Tehran‎, ‎I‎. ‎R‎. ‎Iran

2 ‎Department of Computer Sciences, ‎Shahed University,‎ ‎Tehran‎, ‎I‎. ‎R‎. ‎Iran

10.22052/mir.2024.253656.1443

Abstract

‎This paper addresses the problem of optimizing the reconstruction of links in a network in the aftermath of natural disasters or human errors‎, ‎such as landslides‎, ‎floods‎, ‎storms‎, ‎earthquakes‎, ‎bombing‎, ‎war‎, ‎etc‎. We aim to determine the optimal sequence for reconstructing the destroyed links within a specific time horizon, while simultaneously locating ‎‎(k)‎‎ portable emergency service centers (where ‎‎(k > 2) throughout the entire network. ‎In this paper‎, ‎the problem is considered in a tree structure‎. ‎A greedy algorithm and a heuristic method‎, ‎namely‎, ‎maximum radius‎, ‎are proposed to solve the problem‎. ‎We evaluate the performance of the proposed algorithms using randomly generated data‎. ‎The experimental results confirm the effectiveness of the proposed methods‎.

Keywords

Main Subjects


[1] S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964) 450 - 459, https://doi.org/10.1287/opre.12.3.450.
[2] O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. II: The p-medians, SIAM J. Appl. Math. 37 (1979) 539 -560, https://doi.org/10.1137/0137041.
[3] A. J. Goldman, Optimal center location in simple networks, Transportation Sci. 5 (1971) 212 - 221, https://doi.org/10.1287/trsc.5.2.212.
[4] M. S. Daskin and K. L. Maass, The P-Median Problem, Location science. Springer, Cham, 2015.
[5] C. Duran-Mateluna, Z. Ales and S. Elloumi, An efficient Benders decomposition for the p-median problem, Eur. J. Oper. Res. 308 (2023) 84 - 96, https://doi.org/10.1016/j.ejor.2022.11.033.
[6] C. Wang, C. Han, T. Guo and M. Ding, Solving uncapacitated P-Median problem with reinforcement learning assisted by graph attention networks, Appl. Intell. 53 (2023) 2010 - 2025, https://doi.org/10.1007/s10489-022-03453-z.
[7] N. Megiddo, Linear-time algorithms for linear programming in R3 and related problems, SIAM J. Comput. 12 (1983) 759 - 776, https://doi.org/10.1137/0212052.
[8] O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. I: The p-centers, SIAM J. Appl. Math. 37 (1979) 513 - 538, https://doi.org/10.1137/0137040.
[9] N. Megiddo and A.Tamir, New results on the complexity of p-centre problems, SIAM J. Comput. 12 (1983) 751 - 758, https://doi.org/10.1137/0212051.
[10] M. Jeger and O. Kariv, Algorithms for finding P-centers on a weighted tree (for relatively small P), Networks 15 (1985) 381 - 389, https://doi.org/10.1002/net.3230150308.
[11] A. Banik, B. Bhattacharya, S. Das, T. Kameda and Z. Song, The p-center problem in tree networks revisited, arXiv preprint arXiv 1604.07535 (2016).
[12] H. Wang and J. Zhang, An O(n log n)-time algorithm for the k-center problem in trees, SIAM J. Comput. 50 (2021) 602 - 635, https://doi.org/10.1137/18M1196522.
[13] W. Wang, K. Yang, L. Yang and Z. Gao, Tractable approximations for the distributionally robust conditional vertex p-center problem: application to the location of high-speed railway emergency rescue stations, J. Oper. Res. Soc. 73 (2022) 525 - 539, https://doi.org/10.1080/01605682.2020.1843983.
[14] F. Kılcı, B. Y. Kara and B. Bozkaya, Locating temporary shelter areas after an earthquake: a case for Turkey, Eur. J. Oper. Res. 243 (2015) 323 - 332, https://doi.org/10.1016/j.ejor.2014.11.035.
[15] F. Cavdur, M. Kose-Kucuk and A. Sebatli, Allocation of temporary disaster response facilities under demand uncertainty: an earthquake case study, Int. J. Disaster Risk Reduct. 19 (2016) 159 - 166, https://doi.org/10.1016/j.ijdrr.2016.08.009.
[16] H. Li, L. Zhao, R. Huang and Q. Hu, Hierarchical earthquake shelter planning in urban areas: a case for Shanghai in China, Int. J. Disaster Risk Reduct. 22 (2017) 431 - 446, https://doi.org/10.1016/j.ijdrr.2017.01.007.
[17] E. Celik, A cause and effect relationship model for location of temporary shelters in disaster operations management, Int. J. Disaster Risk Reduct. 22 (2017) 257 - 268, https://doi.org/10.1016/j.ijdrr.2017.02.020.
[18] A. Trivedi, A multi-criteria decision approach based on DEMATEL to assess determinants of shelter site selection in disaster response, Int. J. Disaster Risk Reduct. 31 (2018) 722- 728, https://doi.org/10.1016/j.ijdrr.2018.07.019.
[19] M. Drakaki, H. G. Gören and P. Tzionas, An intelligent multi-agent based decision support system for refugee settlement siting, Int. J. Disaster Risk Reduct. 31 (2018) 576 - 588, https://doi.org/10.1016/j.ijdrr.2018.06.013.
[20] M. K. Oksuz and S. I. Satoglu, A two-stage stochastic model for location planning of temporary medical centers for disaster response, Int. J. Disaster Risk Reduct. 44 (2020) p. 101426, https://doi.org/10.1016/j.ijdrr.2019.101426.
[21] M. Karatas and E. Yakıcı, A multi-objective location analytics model for temporary emergency service center location decisions in disasters, Decis. Anal. J. 1 (2021) p. 100004, https://doi.org/10.1016/j.dajour.2021.100004.
[22] A. M. Sharp, Incremental Algorithms: Solving Problems in a Changing World, Cornell University, 2007.
[23] J. Hartline, Incremental Optimization, Cornell University, 2007.
[24] J. Hartline and A. Sharp, An Incremental Model for Combinatorial Maximization Problems, International Workshop on Experimental and Efficient Algorithms, Springer, Berlin, Heidelberg, 2006.
[25] F. Della Croce, U. Pferschy and R. Scatamacchia, Approximation Results for the Incremental Knapsack Problem, International Workshop on Combinatorial Algorithms, Springer, Cham. 2018.
[26] F. Della Croce, U. Pferschy and R. Scatamacchia, On approximating the incremental knapsack problem, Discrete Appl. Math. 264 (2019) 26 - 42, https://doi.org/10.1016/j.dam.2019.02.016.
[27] D. Bienstock, J. Sethuraman and C. Ye, Approximation algorithms for the incremental knapsack problem via disjunctive programming, arXiv preprint arXiv 1311.4563 (2013).
[28] Y. Faenza, D. Segev and L. Zhang, Approximation algorithms for the generalized incremental knapsack problem, Math. Program. 198 (2023) 27 - 83, https://doi.org/10.1007/s10107-021-01755-7.
[29] A. Aouad and D. Segev, An approximate dynamic programming approach to the incremental knapsack problem, Oper. Res. 71 (2023) 1414 - 1433, https://doi.org/10.1287/opre.2022.2268.
[30] K. Engel, T. Kalinowski and M. W. P. Savelsbergh, Incremental network design with minimum spanning trees, J. Graph Algorithms Appl. 21 (2017) 417 - 432, http://doi.org/10.7155/jgaa.00423.
[31] M. Baxter, T. Elgindy, A. T. Ernst, T. Kalinowski and M. W. P. Savelsbergh, Incremental network design with shortest paths, European J. Oper. Res. 238 (2014) 675 - 684, https://doi.org/10.1016/j.ejor.2014.04.018.
[32] T. Kalinowski, D. Matsypura and M. W. P. Savelsbergh, Incremental network design with maximum flows, European J. Oper. Res. 242 (2015) 51 - 62, https://doi.org/10.1016/j.ejor.2014.10.003.
[33] C. G. Plaxton, Approximation algorithms for hierarchical location problems, J. Comput. System Sci. 72 (2006) 425 - 443, https://doi.org/10.1016/j.jcss.2005.09.004.
[34] H. Du, Y. Xu and B. Zhu, An incremental version of the k-center problem on boundary of a convex polygon, J. Comb. Optim 30 (2015) 1219 - 1227, https://doi.org/10.1007/s10878-015-9933-3.
[35] A. Arulselvan, A. Bley and I. Ljubic, The incremental connected facility location problem, Comput. Oper. Res. 112 (2019) p. 104763, https://doi.org/10.1016/j.cor.2019.104763.
[36] C. Gokalp, P. N. Patil and S. D. Boyles, Post-disaster recovery sequencing strategy for road networks, Transp. Res. B: Methodol. 153 (2021) 228-245, https://doi.org/10.1016/j.trb.2021.09.007.