Random Search Algorithm for the Generalized Weber Problem

Lev Kazakovtsev

Department of Information Technologies, Siberian State Aerospace University, Krasnoyarsk, Russian Federation.

DOI: 10.4236/jsea.2012.512B013                

Abstract

In this paper, we consider the planar multi-facility Weber problem with restricted zones and non-Euclidean distances, propose an algorithm based on the probability changing method (special kind of genetic algorithms) and prove its efficiency for approximate solving this problem by replacing the continuous coordinate values by discrete ones. Version of the algorithm for multiprocessor systems is proposed. Experimental results for a high-performance cluster are given.

 

Keywords

Discrete Optimization; Weber Problem; Random Search; Genetic Algorithms; Parallel Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. Wesolowsky, ''The Weber Problem: History and Perspectives'', Location Science, 1,1993, pp. 5–23.
[2]	R.Chen, ''Location Problems with Costs Being Sums of Powers of Euclidean Distances'', Com-puters & Ops. Res., 11, 1984, pp.285–294
[3]	Z. Drezner and H. Hawacher, ''Facility Location: Applica-tions and Theory'', Berlin,, Springer-Verlag, 2004.
[4]	R.F. Love and J.G. Morris, ''Computation Procedure for the Exact Solution of Location-Allocation Problems with Rectangular Distances'', Naval Research Logistics Quarterly, 22, 1975, pp.441–453. doi: 10.1002/nav.3800220304
[5]	J.E. Ward and R.E. Wenll, ''Using Block Norms for Location Modeling'', Operations Research, 33, 1985, pp.1074–1090. doi: 10.1287/opre.33.5.1074
[6]	R.F.Love, W.G. Truscott and J. Walker, ''Terminal Location Problem: A Case Study Supporting the Status Quo'', J. Opl Res. Soc., 36,1985, pp.131-136. doi:10.1057/jors.1985.26
[7]	M.J. Hodgson, R.T. Wong and J.Honsaker, ''The P-Centroid Problem on an Inclined Plane'', Operations Research, Issue 35,1987, pp. 221–233. doi: 10.1287/opre.35.2.221
[8]	J. Brimberg and R.F.Love, ''Properties of Ordinary and Weighted Sums of Order p Used for Distance Estimation'', Recherche Operationnelle, Issue 29,1995, pp. 59–72.
[9]	L. Cooper, ''An extension of the generalized Weber problem'', Journal of Regional Science, Vol.8, Issue 2, 1968, pp. 181–197l. doi: 10.1111/j.1467-9787.1968.tb01323.x
[10]	M.M. Deza and E. Deza, ''Encyclopedia of Distances'', Springer Ver-lag, 2009. doi: 10.1007/978-3-642-00234-2_19
[11]	S.P. Fekete, ''On the Continuous Fermat-Weber Problem'', Operations Research, Vol. 53 1 2005,61–76 . doi: 10.1287/opre.1040.0137
[12]	M. Gugat and B. Pfeiffer, ''Weber Problems with Mixed Distances and Regional Demand'', Math Meth Oper Res, issue 66, 2007, pp.419–449. doi:10.1007/s00186-007-0165-x
[13]	S.L. Hakimi, ''Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph'', Opera-tions Research, 12(3), 1964, pp.450–459. doi: 10.1287/opre.12.3.450
[14]	S.L. Hakimi, ''Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems'', Operations Research, 13(3), 1965, pp.462–475. doi: 10.1287/opre.13.3.462
[15]	O. Kariv and S.L. Hakimi, ''An algorithmic approach to network location problems. II. The p-medians'', SIAM Journal on Applied Mathe-matics, 37(3), 1979, pp.539–560. oi: 10.1137/0137041
[16]	A.V. Cabot, R.L. Francis and M.A. Stary, ''A Network Flow Solution to a Rectilinear Distance Facility Location Problem'', American Institute of Industrial Engineers Transactions 2, 1970, pp. 132–141.
[17]	S. Stanimirovic, M. Ciric, ''Single-facility Weber Location Problem Based On The Lift Metric''. http://arxiv.org/abs/1105.0757
[18]	M. Bischoff, T. Fleischmann and K. Klamroth, ''The Mul-ti-Facility Location-Allocation Problem with Polyhedral Barriers'', Computers and Operations Research, 36, 2009, pp.1376–1392. doi: 10.1016/j.cor.2008.02.014
[19]	A.N. Antamoshkin, ''Optimizatsiya Funktsionalov s Bulevymi Peremennymi'' (''Optimization of Functionals with Boolean Variables''), TGU, Tomsk, 1987
[20]	A.Antamoshkin, H.P. Schwefel, A. Toern, G. Yin and A.Zhilinskas, ''System Analysis, Desing and Optimization. An Introduction'', Ofset, Krasnoyarsk, 1993
[21]	Yu. Finkelstein et al. ''Diskretnaya Optimzatsiya'' (''Discrete Optimization''), Metody Optimizatsii v Ekonomiko-Matematicheskom Modelirovanii, Nauka, Moscow, 1991, pp. 350-367
[22]	L.Kazakovtsev, “Adaptive Model of Static Routing for Traffic Balance between Multiple Telecommunication channels to different ISPs”, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.9445&rep=rep1&type=pdf (accessed 01.08.2012)
[23]	L.A.Kazakovtsev and A.A.Stupina, ''Parallelnaya Realizatsiya Metoda Izmenyayushikhsya Veroyatnostey'' (''Parallel Realization of the Probability Changing Method''), Sovremennye problemy nauki i obrazovaniya, №4, 2012, http://www.science-education.ru/104-6810
[24]	T.S. Rappaport, ''Wireless Communications: Principles and Practice'', 2nd ed.–IEEE Press, 2002
[25]	J.Hu and E. Goodman, ''Wireless Access Point Configuration by Ge-netic Programming'', in Evolutionary Computation, 2004. CEC2004. Congress on, vol.1, 2004,pp. 1178- 1184
[26]	P.M. Pardalos, L.Pitsoulis, T. Mavridou and M.G.C. Resende, ''Parallel Search for Combinatorial Op-timization: Genetic Algorithms, Simulated Annealing, Tabu Search and GRASP'', in Parallel Algorithms for Irregularly Structured Problems: Lecture Notes in Computer Science, issue 980, 1995, pp 317- 331. doi: 10.1007/3-540-60321-2_26
[27]	L.Dagum, R.Menon, ''OpenMP: An Industry-Standard API for Shared-Memory Programming'', IEEE Computational Science and Engineering (IEEE Computer Society Press), Vol. 5, Issue 1, 1998, p.46–55.
[28]	A.Messina, “Meet Argo”, http://argo.ictp.