Document Type : Research Paper
Authors
Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.
Abstract
In this paper, we discuss the obnoxious and semi-obnoxious version of the backup 2-median problem on a tree. In the obnoxious case of the 2-median problem, all vertices have negative weights, whereas in the semi-obnoxious model the vertices may have either positive or negative weights. In these two problems, we should find the location of two facility servers on the tree so that the sum of minimum weighted distances from vertices in the tree to the set of functioning servers is minimized. In the backup model, each facility server may probably fail. If a facility server fails, the remaining server should serve the clients. Vertex optimality is an important property for the 2-median problem. This property indicates that the set of vertices involves an optimal solution of the 2-median problem. We verify that the vertex optimality holds for the semi-obnoxious backup 2-median problem on a tree network. In the obnoxious 2-median problem, the set of leaves contains an optimal solution, we show that this property does not hold for the obnoxious backup 2-median problem.
Keywords
Main Subjects
- Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. i: the p-centers. SIAM journal on applied mathematics, 37(3), 513-538. https://doi.org/10.1137/0137040
- Tamir, A. (1996). An O (pn2) algorithm for the p-median and related problems on tree graphs. Operations research letters, 19(2), 59-64. https://doi.org/10.1016/0167-6377(96)00021-1
- Hua, L. K. (1962). Application of mathematical methods to wheat harvesting. Chinese math, 2, 77-91.
- Goldman, A. J. (1971). Optimal center location in simple networks. Transportation science, 5(2), 109-221. https://doi.org/10.1287/trsc.5.2.212
- Gavish, B., & Sridhar, S. (1995). Computing the 2‐median on tree networks in O (n lg n) time. Networks, 26(4), 305-317. https://doi.org/10.1002/net.3230260413
- Charikar, M., Guha, S., Tardos, É., & Shmoys, D. B. (2002). A constant-factor approximation algorithm for the k-median problem. Journal of computer and system sciences, 65(1), 129-149. https://doi.org/10.1006/jcss.2002.1882
- Gao, Y. (2012). Uncertain models for single facility location problems on networks. Applied mathematical modelling, 36(6), 2592-2599. https://doi.org/10.1016/j.apm.2011.09.042
- Alp, O., Erkut, E., & Drezner, Z. (2003). An efficient genetic algorithm for the p-median problem. Annals of operations research, 122(1), 21-42. https://doi.org/10.1023/A:1026130003508
- Fathali, J., & Taghizadeh Kakhki, H. (2006). Solving the p-median problem with pos/neg weights by variable neighborhood search and some results for special cases. European journal of operational research, 170(2), 440-462. https://doi.org/10.1016/j.ejor.2004.05.027
- Berman, O., & Wang, Q. (2007). Locating semi-obnoxious facilities with expropriation: minisum criterion. Journal of the operational research society, 58(3), 378-390. https://doi.org/10.1057/palgrave.jors.2602151
- Coutinho-Rodrigues, J., Tralhão, L., & Alçada-Almeida, L. (2012). A bi-objective modeling approach applied to an urban semi-desirable facility location problem. European journal of operational research, 223(1), 203-213. https://doi.org/10.1016/j.ejor.2012.05.037
- Eiselt, H. A., & Marianov, V. (2014). A bi-objective model for the location of landfills for municipal solid waste. European journal of operational research, 235(1), 187-194. https://doi.org/10.1016/j.ejor.2013.10.005
- Silva, S., Alçada-Almeida, L., & Dias, L. C. (2017). Multiobjective programming for sizing and locating biogas plants: a model and an application in a region of Portugal. Computers & operations research, 83, 189-198. https://doi.org/10.1016/j.cor.2017.02.016
- Colmenar, J. M., Martí, R., & Duarte, A. (2018). Multi-objective memetic optimization for the bi-objective obnoxious p-median problem. Knowledge-based systems, 144, 88-101. https://doi.org/10.1016/j.knosys.2017.12.028
- Song, B. D., Morrison, J. R., & Ko, Y. D. (2013). Efficient location and allocation strategies for undesirable facilities considering their fundamental properties. Computers & industrial engineering, 65(3), 475-484. https://doi.org/10.1016/j.cie.2013.03.009
- Colebrook, M., & Sicilia, J. (2013). Hazardous facility location models on networks. Handbook of OR/MS models in hazardous materials transportation (pp. 155-186). New York, NY: Springer. https://doi.org/10.1007/978-1-4614-6794-6_6
- Heydari, R., & Melachrinoudis, E. (2012). Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives. European journal of operational research, 223(2), 452-460. https://doi.org/10.1016/j.ejor.2012.06.039
- Burkard, R. E., & Krarup, J. (1998). A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing, 60(3), 193-215. https://doi.org/10.1007/BF02684332
- Burkard, R. E., Çela, E., & Dollani, H. (2000). 2-medians in trees with pos/neg weights. Discrete applied mathematics, 105(1-3), 51-71. https://doi.org/10.1016/S0166-218X(00)00177-3
- Benkoczi, R., Bhattacharya, B. K., & Breton, D. (2006). Efficient computation of 2-medians in a tree network with positive/negative weights. Discrete mathematics, 306(14), 1505-1516. https://doi.org/10.1016/j.disc.2005.11.031
- Burkard, R. E., Fathali, J., & Kakhki, H. T. (2007). The p-maxian problem on a tree. Operations research letters, 35(3), 331-335.
- Burkard, R. E., & Hatzl, J. (2010). Median problems with positive and negative weights on cycles and cacti. Journal of combinatorial optimization, 20(1), 27-46. https://doi.org/10.1007/s10878-008-9187-4
- Burkard, R. E., & Fathali, J. (2007). A polynomial method for the pos/neg weighted 3-median problem on a tree. Mathematical methods of operations research, 65(2), 229-238.
- Zaferanieh, M., & Fathali, J. (2012). Finding a core of a tree with pos/neg weight. Mathematical methods of operations research, 76(2), 147-160. https://doi.org/10.1007/s00186-012-0394-5
- Karataş, M., Razi, N., & Tozan, H. (2017). A multi-criteria assessment of the p-median, maximal coverage and p-center location models. Technical gazette, 24(2), 399-407. https://dx.doi.org/10.17559/TV-20160508131905
- Weaver, J. R., & Church, R. L. (1985). A median location model with nonclosest facility service. Transportation science, 19(1), 58-74. https://doi.org/10.1287/trsc.19.1.58
- Snyder, L. V., & Daskin, M. S. (2005). Reliability models for facility location: the expected failure cost case. Transportation science, 39(3), 400-416. https://doi.org/10.1287/trsc.1040.0107
- Wang, H. L., Wu, B. Y., & Chao, K. M. (2009). The backup 2‐center and backup 2‐median problems on trees. Networks: an international journal, 53(1), 39-49. https://doi.org/10.1002/net.20261
- Cheng, Y. K., Kang, L. Y., & Yan, H. (2014). The backup 2-median problem on block graphs. Acta mathematicae applicatae sinica, english series, 30(2), 309-320. https://doi.org/10.1007/s10255-014-0294-y
- Fathali, J. (2015). Backup multifacility location problem with lp norm. Opsearch, 52(2), 382-391. https://doi.org/10.1007/s12597-014-0180-7
- Nazari, M., & Fathali, J. (2018). Reverse backup 2-median problem with variable coordinate of vertices. Journal of operational research and its applications, 15(2), 63-88.
- Nazari, M., Fathali, J., Nazari, M., & Varedi Koulaei, S. M. (2018). Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane. Journal of production and operations management, 9(2), 115-137.
- Araz, C., Selim, H., & Ozkarahan, I. (2007). A fuzzy multi-objective covering-based vehicle location model for emergency services. Computers & operations research, 34(3), 705-726. https://doi.org/10.1016/j.cor.2005.03.021
- Chanta, S., Mayorga, M. E., & McLay, L. A. (2014). Improving emergency service in rural areas: a bi-objective covering location model for EMS systems. Annals of operations research, 221(1), 133-159. https://doi.org/10.1007/s10479-011-0972-6
- Curtin, K. M., Hayslett-McCall, K., & Qiu, F. (2010). Determining optimal police patrol areas with maximal covering and backup covering location models. Networks and spatial economics, 10(1), 125-145. https://doi.org/10.1007/s11067-007-9035-6
- Janosikova, L., Gabrisova, L., & Jezek, B. (2015). Load balancing location of emergency medical service stations. E+ M ekonomie a management, 18(3), 30-41.
- Kordjazi, M., & Kazemi, A. (2016). Presenting a three-objective model in location-allocation problems using combinational interval full-ranking and maximal covering with backup model. Journal of industrial and systems engineering, 9(special issue on location allocation and hub modeling), 53-70.
- P. B., & Francis, R. L. (1990). Discrete location theory. J. Wiley.
- Ting, S. S. (1984). A linear-time algorithm for maxisum facility location on tree networks. Transportation science, 18(1), 76-84. https://doi.org/10.1287/trsc.18.1.76