Efficient methods for goal square Weber location problem

Iranian Journal of Numerical Analysis and Optimization

مقاله 4، دوره 7، شماره 1 - شماره پیاپی 11، تیر 2017، صفحه 65-82   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v7i1.52961

نویسندگان

J. Fathali^{* 1}؛ A. Jamalian²

¹Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran.

²Department of Computer Scince, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran.

چکیده

In this paper, we consider a special case of Weber location problem which we call goal location problem. The Weber location problem asks to find location of a point in the plane such that the sum of weighted distances between this point and n existing points is minimized. In the goal location problem each existing point Pi has a relevant radius ri and it’s ideal for us to locate a new facility on the distance ri from Pi for i = 1, ..., n. Since in the most instances there does not exist the location of a new facility such that its distance to each point Pi be exactly equal to ri. So we try to minimize the sum of the weighted square errors. We consider the case that the distances in the plane are measured by the Euclidean norm. We propose a Weiszfeld like algorithm for solving the problem and also we use two modifications of particle swarm optimization method for solving this problem. Finally the results of these algorithms are compared with results of BSSS algorithm.

کلیدواژه‌ها

Location theory؛ Weiszfeld method؛ Particle swarm optimization

مراجع

1. Ali, M.M. and Kaelo, P. Improved particle swarm algorithm for global optimization, Applied Mathematics and Computation, 2008, 196: 578-593.

2. Bazaraa, M.S., Sherali, H. and Jarvis, J. Linear Programming and Network Flows, Third ed., John Wiley & Sons; 2005.

3. Berman, O. and Huang, R. The minimum weighted covering location prob lem with distance constraints, Computers and Operations Research, 2008,35: 356-372.

4. Brimberg, J. The Fermat-Weber location problem revisited, Mathematical Programming, 1995, 71: 71-76.

5. Chen, R. Noniterative Solution of Some Fermat-Weber Location Problems, Advances in Operations Research, Volume 2011 (2011), Article ID 379505, 10 pages.

6. Church, R. and ReVelle, C. The maximal covering location problem, Papers of Regional Science Association, 1974, 32: 101-18.

7. Clerc, M. and Kennedy, J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 2002, 1: 58-73.

8. Courant, R. and Robbins, H. What is mathematics? Oxford: Oxford University Press, 1941.

9. Dantzig, G.B. and Thapa, M.N. Linear Programming 2: Theory and Ex tensions. Springer; 2003.

10. Drezner, Z. On convergence of the generalized Weiszfeld algorithm, Ann Oper Res. 2008; 167: 327-336.

11. Eberhart, R.C. and Kennedy, J. A new optimizer using particle swarm theory, proc. 6th int. Symp. Micro Machine and Human science, Nagoya, Japan, 1995; 39-43.

12. Fathali, J., Zaferanieh, M. and Nezakati, A. A BSSS algorithm for the location problem with minimum square error, Advances in Operations Research, Volume 2009 (2011), Article ID 212040, 10 pages.

13. Hansen, P., Peeters, D. and Thisse, J.F. On the location of an obnoxious facility, Sistemi Urbani, 1981; 3: 299-317.

14. Jamalian, A. and Fathali, J. Linear programming for the location problem with minimum absolute error, World Applied Sciences Journal 2009, 7: 1423-1427.

15. Jin, Y.X., Cheng, H.Z., Yan, J. and Zhang, L. New discrete method for particle swarm optimization and its application in transmission network expansion planning, Electric Power Systems Research, 2007, 77: 227-233.

16. Kuhn, H.W. On a pair of dual nonlinear programs. In: Nonlinear Programing, J.Abadie (eds.), North-Holand Publishers Co. Amsterdam, 1967, 37-54.

17. Kuhn, H.W. and Kuenne, R.E. An efficient algorithm for the Numerical Solution of the Generalized Weber Problem in spatial Economics, Journal of Regional Science, 1967; 4: 21-33.

18. Love, R.F., Morris, J.G. and Wesolowsky, G.O. Facility Location :models and methods., North-Holland,(1988).

19. Mangasarian, O.L. Nonlinear Programming. McGraw-Hill; 1969.

20. Plastria, F. GBSSS: the generalized big square small square method for planar single-facility location, European Journal of Operational Research, 1992; 62: 163-174.

21. Shi, Y. and Eberhart, R.C. Empirical study of particle swarm optimization, IEEE International Congress on Evolutionary Computation, 1999, 3: 101-106.

22. Skriver, A.J.V. and Andersen, K.A. The bicriterion semi-obnoxious location (BSL) problem solved by an ϵ-approximation, European Journal of Operational Research, 2003; 146: 517-528.

23. Trinh, M.H., Lee, B.H. and Ahn, H.S. The Fermat-Weber location problem in single integrator dynamics using only local bearing angles, Automatica, 2015; 59: 90-96.

24. Weiszfeld, E. Sur Le Point Pour Lequel La Somme Des Distances De N Points Donnes Est Minimum, Tohoku Mathematical Journal, 1937; 60: 355-386.

25. Zaferanieh, M., Kakhki, H.T., Brimberg, J. and Wesolowsky, G.O. A BSSS algorithm for the single facility location problem in two regions with different norms, European Journal of Operational Research, 2008; 190:

79-89.