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, Journal of the Operational Research Society,41 (1990) 1069-1072, .
[2] O. Berman, Q. Wang, Locating a semi-obnoxious facility with expropriation, Comput. Operat. Res., 35 (2008)392-403.
[3] J. Brimberg, H. Juel, and A. Sch´obel, Locating a minisum circle in the plane, Discrete Applied Mathematics, 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, Mathematical Problems in Engineering, vol. 2019, Article ID 5213759, 12 pages, (2019).
[7] E.D. Dolan and J.J. More, Benchmarking optimization software with performance profiles, Math. Programming 91(2, Ser. A) (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, Computers and Operation Research, 29 (2002) 637–650.
[10] J. Fathali, A genetic algorithm for the p-median problem with pos/neg weights, Applied Mathematics and Computation, 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 Computing and Applications, 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, Computers and Industrial Engineering, 109 (2017) 71–78.
[14] S. Jafari, O. Bozorg-Haddad, X. Chu, Cuckoo optimization algorithm (COA), In: Bozorg-Haddad O. (eds.), Advanced Optimization by Nature-Inspired Algorithms, Studies in Computational Intelligence, vol 720 (pp. 39-
49), (2018), Springer, Singapore.
[15] M. Labb´e, G. Laporte, I. Rodriguez-Martin, J.J.S. Gonzalez, Locating median cycles in networks, Eur. J. Oper. Res., 160 (2005) 457–470
[16] Y. Ohsawa, K. Tamura, Efficient location for a semi-obnoxious facility, Ann. Operat. Res., 123(2003) 173–188.
[17] R. Rajabioun, Cuckoo optimization algorithm, Applied Soft Computing, 11 (2011) 5508–5518.
[18] X. S. Yang, and S. Deb, Cuckoo search via Levy flights, Proceeings of World Congress on Nature and Biologically Inspired Computing (NaBIC 2009,India), IEEE Publications, USA, pp. 210–214, 2009.
[19] H. Yapicioglu, A.E. Smith, G. Dozier, Solving the semi-desirable facility location problem using bi-objective particle swarm, Eur. J. Operat. 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
  • First Publish Date: 16 February 2021