This paper describes four mathematical models for the single-facility location problems based on four special distance metrics and algorithms for solving such problems. In this study, algorithms of solving Weber problems using four distance predicting functions (DPFs) are proposed in accordance with four strategies for manipulator control. A numerical example is presented in this proposal as an analytical proof of the optimality of their results. 1. Introduction Generally, the purpose of a location problem is to determine locations of one or several new facilities on a plane or in a space where some objects (facilities) have been already placed [1]. Usually, the number of possible arrangements for new facilities is infinite [2]. Location problems occur frequently in real life. Some of them include the distribution systems such as locating warehouses within supply chain to minimize average transportation time to market, locating hazardous material so as to minimize its exposure to the public, determining bank account and lockboxes location to maximize clearing time or float, and problems of locating a computer, telecommunication equipment, and wireless base stations [3]. Many of such practical problems of this kind involve emergency facilities such as hospitals, fire stations, accident rescue, or civil defense. The usual objective here is to minimize the maximum among weighted distances between facilities to be located and all demand points. Details of other useful applications can be found in [4, 5]. Similar problems are formulated in approximation theory, problems of estimation in statistics [6], signal and image processing, and so forth [7–9]. Distance is the length of the shortest path between two points. However, the path depends on properties of space and a way of movement in it. In continuous spaces, the most commonly used metrics are rectangular or Manhattan (), Euclidean (), and Tchebychev (). Indeed, many results have been generalized for -dimensional space; however, practical applications usually occur within the context of two-dimensional and three-dimensional spaces. Therefore, in the subsequent sections, DPF is used for modeling distances in 2-dimensional space (unless it is otherwise stated). The Euclidean distance between two points does not reflect the cost of moving between them in the systems which use rotating mechanisms (telescopic boom, etc.) as transportation means. These systems include automated lifting cranes and manipulators. This kind of problems lies behind many important applications. Unfortunately, there exist only a few
References
[1]
R. Z. Farahani and M. Hekmatfar, Eds., Facility Location Concepts, Models, Algorithms and Case Studies, Springer, Berlin, Germany, 2009.
[2]
G. O. Wesolowsky, “The Weber problem: history and perspectives,” Location Science, vol. 1, pp. 5–23, 1993.
[3]
P. González-Brevis, J. Gondzio, Y. Fan et al., “Base station location optimization for minimal energy consumption in wireless networks,” in Proceedings of the IEEE 73rd Vehicular Technology Conference (VTC '11), pp. 1–5, May 2011.
[4]
T. S. Hale and C. R. Moberg, “Location science research: a review,” Annals of Operations Research, vol. 123, pp. 21–35, 2003.
[5]
M. Kon and S. Kushimoto, “A single facility minisum location problem under the -distance,” Journal of the Operations Research Society of Japan, vol. 40, no. 1, pp. 10–20, 1997.
[6]
O. R. Oniyide and I. A. Osinuga, “On the existence of best sample in simple random sampling,” Journal of the Mathematical Association of Nigeria, vol. 33, no. 2B, pp. 290–294, 2006.
[7]
P. J. S. G. Ferreira and P. Jorge, “The existence and uniqueness of the minimum norm solution to certain linear and nonlinear problems,” Signal Processing, vol. 55, no. 1, pp. 137–139, 1996.
[8]
L. A. Kazakovtsev, “Adaptation of the probability changing method for Weber problem with an arbitrary metric,” Facta Universitatis, Series: Mathematics and Informatics, vol. 27, no. 2, pp. 93–110, 2012.
[9]
G. O. Wesolowsky, “Location problems on a sphere,” Regional Science and Urban Economics, vol. 12, no. 4, pp. 495–508, 1982.
[10]
P. Kolesar, W. Walker, and J. Hausner, “Determining the relation between the engine travel times and travel distances in New York City,” Operations Research, vol. 23, no. 4, pp. 614–627, 1975.
[11]
J. H. Walter, An empirical study of round and block norms for modeling actual distances [Ph.D. Dissertation], McMaster University, Hamilton, Canada, 1991.
[12]
J. B. Westwood, “A transport planning model for primary distribution,” Interfaces, vol. 8, pp. 1–10, 1977.
[13]
R. F. Love and J. G. Morris, “Mathematical model of road travel distances,” Management Science, vol. 25, no. 2, pp. 130–139, 1979.
[14]
C. S. Revelle and G. Laporte, “The plant location problem: new models and research prospects,” Operations Research, vol. 44, no. 6, pp. 864–874, 1996.
[15]
C. Singhtaun and P. Charnsethikul, “Comparison of exact algorithms for rectilinear distance single-source capacitated multi-facility Weber Problems,” Journal of Computer Science, vol. 6, no. 2, pp. 112–116, 2010.
[16]
M. Parthasarathy, T. Hale, J. Blackhurst, and M. Frank, “The three-dimensional Fermat-Weber problem with Tchebychev distances,” Advanced Modeling and Optimization, vol. 8, no. 1, pp. 65–71, 2006.
[17]
J. Krarup and P. M. Pruzan, “The impact of distance on location problems,” European Journal of Operational Research, vol. 4, no. 4, pp. 256–269, 1980.
[18]
J. Perreur and J. Thisse, “Central metrics and optimal location,” Journal of Regional Science, vol. 14, no. 3, pp. 411–421, 1974.
[19]
J. Ward and R. Wendell, “A new norm for measuring distance which yields linear location problem,” Operations Research, vol. 28, pp. 836–844, 1980.
[20]
M. Gugat and B. Pfeiffer, “Weber problems with mixed distances and regional demand,” Mathematical Methods of Operations Research, vol. 66, no. 3, pp. 419–449, 2007.
[21]
J. Brimberg, R. Love, and N. Mladenovi{\'c}, “Extension of the Weiszfeld procedure to a single facility minisum location model with mixed norms,” Mathematical Methods of Operations Research, vol. 70, no. 2, pp. 269–283, 2009.
[22]
B. Pfeiffer and K. Klamroth, “A unified model for Weber problems with continuous and network distances,” Computers & Operations Research, vol. 35, no. 2, pp. 312–326, 2008.
[23]
J. R. Evans and E. Minieka, Optimisation Algorithms for Network and Graphs, Marcel Dekker, New York, NY, USA, 2nd edition, 1992.
[24]
F. Baroughi Bonab, R. E. Burkard, and E. Gassner, “Inverse -median problems with variable edge lengths,” Mathematical Methods of Operations Research, vol. 73, no. 2, pp. 263–280, 2011.
[25]
J. Fathali and M. Zaferanieh, “Location problems in regions with and Block norms,” Iranian Journal Operations Research, vol. 2, no. 2, pp. 72–87, 2011.
[26]
S. Stanimirovi？ Predrag and ？. Marija, “Discrete location problem on arbitrary surface in ,” Facta Universitatis—Series: Mathematics and Informatics, vol. 25, pp. 47–56, 2010.
[27]
H. Sp？th, “The minisum location problem for the Jaccard metric,” OR Spektrum: Quantitative Approaches in Management, no. 3, pp. 91–94, 1981.
[28]
F. Chierichetti, R. Kumar, S. Pandey, and S. Vassilvitskii, “Finding the jaccard median,” in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 293–311, 2010.
[29]
G. A. Watson, “An algorithm for the single facility location problem using the Jaccard metric,” SIAM Journal Scientific and Statistical Computing, vol. 4, no. 4, pp. 748–756, 1983.
[30]
P. S. Stanimirovi？, M. S. ？iri？, L. A. Kazakovtsev, and I. A. Osinuga, “Single-facility Weber location problem based on the lift metric,” Facta Universitatis. Series: Mathematics and Informatics, vol. 27, no. 2, pp. 175–190, 2012.
[31]
R. Klein, “Voronoi diagrams in the Moscow metric,” in Graph-Theoretic Concepts in Computer Science: International Workshop WG'88 Amsterdam, The Netherlands, June 15-17, vol. 344 of Lecture Notes in Computer Science, pp. 434–444, 1989.
[32]
O. Kariv and S. L. Hakimi, “An algorithmic approach to network location problems. II. The -medians,” SIAM Journal on Applied Mathematics, vol. 37, no. 3, pp. 539–560, 1979.
[33]
L. Kazakovtsev, “Algorithm for approximate solution of the generalized Weber problem with an arbitrary metric,” in Proceedings of the 6th UKSim/AMSS European Symposium on Computer Modeling and Simulation (EMS '12), pp. 109–114, November 2012.
[34]
I. A. Osinuga, L. A. Kazakovtsev, and P. S. Stanimirovic, “Planar Weber location problem with French metro metric,” Review Bulletin of the Calcutta Mathematical Society, vol. 21, no. 1, pp. 7–20, 2013.
[35]
M. M. Deza and E. Deza, Encyclopedya of Distances, Springer, Berlin, Germany, 2009.
[36]
P. Moon and D. E. Spencer, “Circular-cylinder coordinates ,” in Field Theory Handbook, Including Coordinate Systems, Differential Equations, and Their Solutions (corrected 2nd ed.), pp. 12–17, Springer, New York, NY, USA, 1988.
[37]
L. A. Kazakovtsev, “Algorithm for the location problem with non-Euclidean metric based on angular distances,” Fundamental Research, vol. 9, pp. 918–923, 2012 (Russian).
[38]
L. A. Kazakovtsev, P. S. Stanimirovic, and I. A. Osinuga, “Decomposition of the continuous Weber problem with French Metro metric,” in Proceedings of the International Conference on Problems of Modern Agrarian Science: Collected Scientific Works, 2012, http://www.kgau.ru/new/all/konferenc/konferenc/2012/e2.doc.
[39]
L. A. Kazakovtsev and P. S. Stanimirovi？, “An approach to the multi-facility weber problem with special metrics,” in Proceedings of the 7th European Modelling Symposium on Computer Modelling and Simulation (EMS '13), pp. 119–124, November 2013.
[40]
R. F. Love and J. G. Morris, “A computation procedure for the exact solution of location-allocation problems with rectangular distances,” Naval Research Logistics Quarterly, vol. 22, no. 3, pp. 441–453, 1975.
[41]
V. A. Trubin, “An effective algorithm for the Weber problem with a rectangular metric,” Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainsko\u \i\ SSR. Kibernetika, no. 6, pp. 67–70, 1978.
[42]
R. Chen, “Noniterative solution of some Fermat-Weber location problems,” Advances in Operations Research, vol. 2011, Article ID 379505, 10 pages, 2011.
