The semi-obnoxious minisum circle location problem with Euclidean norm

Document Type : Research Paper


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


‎The objective of the classical version of the minisum circle location problem is finding a circle $C$ in the plane such that the sum of the weighted distances from the circumference of $C$ to a set of given points is minimized‎, ‎where every point has a positive weight‎. ‎In this paper‎, ‎we investigate the semi-obnoxious case‎, ‎where every existing facility has either a positive or negative weight‎. ‎The distances are measured by the Euclidean norm‎. ‎Therefore‎, ‎the problem has a nonlinear objective function and global nonlinear optimization methods are required to solve this problem‎. ‎Some properties of the semi-obnoxious minisum circle location problem with Euclidean norm are discussed‎. ‎Then a cuckoo optimization algorithm is presented for finding the solution of this problem‎.


[1] J.E. Beasley, OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc. 41 (1990) 1069-1072.
[2] O. Berman, Q. Wang, Locating a semi-obnoxious facility with expropriation, Comput. Oper. Res. 35 (2008) 392-403.
[3] J. Brimberg, H. Juel, and A. Schobel, Locating a minimum circle in the plane, Discrete Appl. Math.157 (2009) 901–912.
[4] R.E. Burkard, E. Cela, H. Dollani, 2-Median in trees with pos/neg weights, Discrete Appl. Math. 105 (2000) 51–71.
[5] R.E. Burkard, J. Krarup, A linear algorithm for the pos/neg weighted 1-median problem on a cactus, Computing 60 (1998) 193–215.
[6] J. Ding, Q. Wang, Q. Zhang, Q. Ye, and Y. Ma, A hybrid particle swarm optimization-cuckoo search algorithm and its engineering applications, Math. Prob. Engin. 2019 (2019), Article ID 5213759, 12 pages.
[7] E.D. Dolan and J.J. More, Benchmarking optimization software with performance profiles, Math. Program. Ser. A 91(2) (2002) 201-213.
[8] Z. Drezner and G.O. Wesolowsky, The Weber problem on the plane with some negative weights, INFOR  29 (1990) 87- 99.
[9] Z. Drezner, G. Steiner, and G.O. Wesolowsky, On the circle closest to a set of points, Comput. Oper. Res. 29 (2002) 637–650.
[10] J. Fathali, A genetic algorithm for the p-median problem with pos/neg weights, Appl. Math. Comput.183 (2007) 1071-1083.
[11] J. Fathali, H.T. Kakhki, R.E. Burkard, An ant colony algorithm for the pos/neg weighted p-median problem, Cent. Eur. J. Operat. Res. 14 (2006) 229–246.
[12] M. Golpayegani, J. Fathali, and I. Khosravian, Median line location problem with positive and negative weights and Euclidean norm, Neural Comput. Appl. 24 (2014) 613–619.
[13] M. Golpayegani, J. Fathali, and H. Moradi, A particle swarm optimization method for semi-obnoxious line location problem with rectilinear norm, Comput. Ind. Engin.109 (2017) 71–78.
[14] S. Jafari, O. Bozorg-Haddad, and X. Chu, Cuckoo optimization algorithm (COA), Bozorg-Haddad O. (eds.), Advanced Optimization by Nature-Inspired Algorithms, Studies in Computational Intelligence, Springer, Singapore, vol 720, (2018), pp. 39-49.
[15] M. Labbe, G. Laporte, I. Rodriguez-Martin, and  J.J.S. Gonzalez, Locating median cycles in networks, Eur. J. Oper. Res. 160 (2005) 457–470.
[16] Y. Ohsawa and K. Tamura, Efficient location for a semi-obnoxious facility, Ann. Operat. Res. 123 (2003) 173–188.
[17] R. Rajabioun, Cuckoo optimization algorithm, Appl. Soft Comput. 11 (2011) 5508–5518.
[18] X.S. Yang and S. Deb, Cuckoo search via Levy flights, Proc. World Cong. Nature and Bio.  Inspired Comput. (NaBIC 2009, India), IEEE Publications, USA, 2009, pp. 210–214.
[19] H. Yapicioglu, A.E. Smith, G. Dozier, Solving the semi-desirable facility location problem using bi-objective particle swarm, Eur. J. Oper. Res., 177 (2007) 733–749.
Volume 12, Issue 1
May 2021
Pages 669-678
  • Receive Date: 13 April 2019
  • Revise Date: 28 October 2019
  • Accept Date: 17 November 2020