Median line location problem with positive and negative weights and Euclidean norm

Neural Computing and Applications - Tập 24 - Trang 613-619 - 2012
Mehdi Golpayegani1, Jafar Fathali1, Eiman Khosravian2
1Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
2Department of Engineering, Shahrood University of Technology, Shahrood, Iran

Tóm tắt

Let n existing facilities be given in the plane. The classical version of the median line location problem asks to find a line L in the plane, so that the sum of the weighted distances from L to all existing facilities is minimized. We consider the semi-obnoxious case, where every point has either a positive or a negative weight. In this paper, we discuss some properties of semi-obnoxious median line location problem with Euclidean norm and propose a particle swarm optimization algorithm for this problem.

Tài liệu tham khảo

Abido MA (2002) Optimal power flow using particle swarm optimization. Int J Elect Power Energy Syst 24(7):563–571 Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Operat Res Soc 41:1069–1072 Berman O, Wang Q (2008) Locating a semi-obnoxious facility with expropriation. Comput Operat Res 35:392–403 Blanquero R, Carrizosa E, Schobel A, Scholz D (2011) A global optimization procedure for the location of a median line in the three-dimensional space. Eur J Operat Res 215:14–20 Brimberg J, Juel H, Schobel A (2003) Properties of three-dimensional median line location models. Ann Operat Res 122:71–85 Burkard RE, Çela E, Dollani H (2000) 2-Median in trees with pos/neg weights. Discrete Appl Math 105:51–71 Burkard RE, Krarup J (1998) A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing 60:193–215 Carrizosa E, Plastria F (1999) Location of semi-obnoxious facilities. Stud Locat Stud 12:1–27 Chen DZ, Wang H (2009) Locating an Obnoxious line among planar objects. Dong Y , Du D-Z , Ibarra O (eds) ISAAC 2009, LNCS 5878, pp. 740–749 Clerc M (2004) Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Onwubolu GC, Babu BV (eds) New optimization techniques in engineering. Springer, Heidelberg, pp 219–239 Drezner Z, Wesolowsky GO (1989) Location of an obnoxious route. J Operat Res Soc 40(11):1011–1018 Eberhart RC, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the 6th international symposium on micro machine and human science, Nagoya, Japan, pp 39–43 Fathali J, Kakhki HT, Burkard RE (2006) An ant colony algorithm for the pos/neg weighted p-median problem. Cent Eur J Operat Res, 14:229–246 Kennedy J, Eberhart R, Shi Y (2001) Swarm intelligence, Morgan Kaufmann Publishers, San Francisco Lee DT, Ching YT (1985) The power of geometric duality revisited. Inf Process Lett 21:117–122 MacKinnon R, Barber GM (1972) A new approach to network generation and map representation: the linear case of the location-allocation problem. Geogr Anal 4:156–168 Megiddo N, Tamir A (1983) Finding least-distance lines, SIAM J Algeb Disc Methods, 4:207–211 Mendes R, Cortez P, Rocha M, Neves J, Particle swarms for feedforward neural network training. In: Proceedings of the international joint conference on neural networks (IJCNN 2002), pp 1895–1899 Morris JG, Norback JP (1980) A simple approach to linear facility location. Transport Sci 14:1–8 Morris JG, Norback JP (1983) Linear facility location-solving extensions on the basic problems. Eur J Oper Res 12:90–94 Ohsawa Y, Tamura K (2003) Efficient location for a semi-obnoxious facility. Ann Operat Res 123:173–188 Parsopoulos KE, Papageorgiou EI, Groumpos PP, Vrahatis MN, (2003) A first study of fuzzy cognitive maps learning using particle swarm optimization. In: Proceedings of IEEE congress on evolutionary computation (CEC 2003), Canbella, Australia, pp 1440–1447 Poli R, Kennedy J, Blackwell T, (2007) Particle swarm optimization an overview. Swarm Intell 1:33–57 Schobel A (1999) Locating lines and hyperplanes: theory and algorithms. Kluwer, Dordrecht Shi Y, Eberhart RC (1998) A modified particle swarm optimizer. In: Proceedings of IEEE international conference on evolutionary computation, Anchorage, AK, pp 69–73 Shi Y, Eberhart RC (1999) Empirical study of particle swarm optimization. In: Proceedings of congress on evolutionary computation, Washington, DC, pp 1945–1949 Tandon V, El-Mounayri H, Kishawy H (2002). NC end milling optimization using evolutionary computation. Int J Mach Tools Manuf 42:595–605 Venayagamoorthy GK, Doctor S (2004) Navigation of mobile sensors using PSO and embedded PSO in a fuzzy logic controller. In: Proceedings of the 39th IEEE IAS annual meeting on industry applications, Seattle, USA, pp 1200–1206 Van den Bergh F, Engelbrecht AP, (2000) Cooperative learning in neural network using particle swarm optimizers. S Afr Comput J 26:84–90 Wesolowsky GO (1975) Location of the median line for weighted points. Environ Plann A7:163–170 Yapicioglu H, Smith AE, Dozier G (2007) Solving the semi-desirable facility location problem using bi-objective particle swarm. Eur J Operat Res 177:733–749