Research ArticleOpen AccessGoogle Scholar indexed
Random Search Algorithm for the Generalized Weber Problem
Department of Information Technologies, Siberian State Aerospace University, Krasnoyarsk, Russian Federation
- 1 Department of Information Technologies, Siberian State Aerospace University, Krasnoyarsk, Russian Federation
Journal of Software Engineering and Applications·Volume 05 (2013)·Pages 59–65·Published 17 January 2013·DOI10.4236/jsea.2012.512B013
Copy link · social · email
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.
KeywordsDiscrete OptimizationWeber ProblemRandom SearchGenetic AlgorithmsParallel Algorithm
- G. Wesolowsky, ''The Weber Problem: History and Perspectives'', Location Science, 1,1993, pp. 5–23.
- R.Chen, ''Location Problems with Costs Being Sums of Powers of Euclidean Distances'', Com-puters & Ops. Res., 11, 1984, pp.285–294
- Z. Drezner and H. Hawacher, ''Facility Location: Applica-tions and Theory'', Berlin,, Springer-Verlag, 2004.
- 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
- 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
- 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
- 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
- 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.
- 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
- M.M. Deza and E. Deza, ''Encyclopedia of Distances'', Springer Ver-lag, 2009. doi: 10.1007/978-3-642-00234-2_19
- S.P. Fekete, ''On the Continuous Fermat-Weber Problem'', Operations Research, Vol. 53 1 2005,61–76 . doi: 10.1287/opre.1040.0137
- 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
- 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
- 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
- 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