Document Type : Research Paper


Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.


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.


Main Subjects

  • Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. i: the p-centers. SIAM journal on applied mathematics37(3), 513-538.
  • Tamir, A. (1996). An O (pn2) algorithm for the p-median and related problems on tree graphs. Operations research letters19(2), 59-64.
  • Hua, L. K. (1962). Application of mathematical methods to wheat harvesting. Chinese math2, 77-91.
  • Goldman, A. J. (1971). Optimal center location in simple networks. Transportation science5(2), 109-221.
  • Gavish, B., & Sridhar, S. (1995). Computing the 2‐median on tree networks in O (n lg n) time. Networks26(4), 305-317.
  • Charikar, M., Guha, S., Tardos, É., & Shmoys, D. B. (2002). A constant-factor approximation algorithm for the k-median problem. Journal of computer and system sciences65(1), 129-149.
  • Gao, Y. (2012). Uncertain models for single facility location problems on networks. Applied mathematical modelling36(6), 2592-2599.
  • Alp, O., Erkut, E., & Drezner, Z. (2003). An efficient genetic algorithm for the p-median problem. Annals of operations research122(1), 21-42.
  • 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 research170(2), 440-462.
  • Berman, O., & Wang, Q. (2007). Locating semi-obnoxious facilities with expropriation: minisum criterion. Journal of the operational research society58(3), 378-390.
  • 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 research223(1), 203-213.
  • Eiselt, H. A., & Marianov, V. (2014). A bi-objective model for the location of landfills for municipal solid waste. European journal of operational research235(1), 187-194.
  • 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 research83, 189-198.
  • Colmenar, J. M., Martí, R., & Duarte, A. (2018). Multi-objective memetic optimization for the bi-objective obnoxious p-median problem. Knowledge-based systems144, 88-101.
  • Song, B. D., Morrison, J. R., & Ko, Y. D. (2013). Efficient location and allocation strategies for undesirable facilities considering their fundamental properties. Computers & industrial engineering65(3), 475-484.
  • 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.
  • Heydari, R., & Melachrinoudis, E. (2012). Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives. European journal of operational research223(2), 452-460.
  • Burkard, R. E., & Krarup, J. (1998). A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing60(3), 193-215.
  • Burkard, R. E., Çela, E., & Dollani, H. (2000). 2-medians in trees with pos/neg weights. Discrete applied mathematics105(1-3), 51-71.
  • Benkoczi, R., Bhattacharya, B. K., & Breton, D. (2006). Efficient computation of 2-medians in a tree network with positive/negative weights. Discrete mathematics306(14), 1505-1516.
  • Burkard, R. E., Fathali, J., & Kakhki, H. T. (2007). The p-maxian problem on a tree. Operations research letters35(3), 331-335.
  • Burkard, R. E., & Hatzl, J. (2010). Median problems with positive and negative weights on cycles and cacti. Journal of combinatorial optimization20(1), 27-46.
  • Burkard, R. E., & Fathali, J. (2007). A polynomial method for the pos/neg weighted 3-median problem on a tree. Mathematical methods of operations research65(2), 229-238.
  • Zaferanieh, M., & Fathali, J. (2012). Finding a core of a tree with pos/neg weight. Mathematical methods of operations research76(2), 147-160.
  • 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.
  • Weaver, J. R., & Church, R. L. (1985). A median location model with nonclosest facility service. Transportation science19(1), 58-74.
  • Snyder, L. V., & Daskin, M. S. (2005). Reliability models for facility location: the expected failure cost case. Transportation science39(3), 400-416.
  • Wang, H. L., Wu, B. Y., & Chao, K. M. (2009). The backup 2‐center and backup 2‐median problems on trees. Networks: an international journal53(1), 39-49.
  • Cheng, Y. K., Kang, L. Y., & Yan, H. (2014). The backup 2-median problem on block graphs. Acta mathematicae applicatae sinica, english series30(2), 309-320.
  • Fathali, J. (2015). Backup multifacility location problem with lp norm. Opsearch52(2), 382-391.
  • 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 management9(2), 115-137.
  • Araz, C., Selim, H., & Ozkarahan, I. (2007). A fuzzy multi-objective covering-based vehicle location model for emergency services. Computers & operations research34(3), 705-726.
  • 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 research221(1), 133-159.
  • 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 economics10(1), 125-145.
  • Janosikova, L., Gabrisova, L., & Jezek, B. (2015). Load balancing location of emergency medical service stations. E+ M ekonomie a management18(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 engineering9(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 science18(1), 76-84.