×

The 1-center problem in the plane with independent random weights. (English) Zbl 1278.90219

Summary: The 1-center problem in the plane with random weights has only been studied for a few specific probability distributions and distance measures. In this paper we deal with this problem in a general framework, where weights are supposed to be independent random variables with arbitrary probability distributions and distances are measured by any norm function. Two objective functions are considered to evaluate the performance of any location. The first is defined as the probability of covering all demand points within a given threshold, the second is the threshold for which the probability of covering is bounded from below by a given value. We first present some properties related to the corresponding optimization problems, assuming random weights with both discrete and absolutely continuous probability distributions. For weights with discrete distributions, enumeration techniques can be used to solve the problems. For weights continuously distributed, interval branch and bound algorithms are proposed to solve the problems whatever the probability distributions are. Computational experience using the uniform and the gamma probability distributions is reported.

MSC:

90B85 Continuous location
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fernández, J.; Fernández, P.; Pelegrín, B., Estimating actual distances by norm functions: a comparison between the \(l_{k, p, \theta}\)-norm and the \(l_{b_1, b_2, \theta}\)-norm and a study about the selection of the data set, Computers and Operations Research, 29, 609-623 (2002) · Zbl 0995.90058
[2] Pelegrín, B., A general approach to the 1-center problem, Cahiers du CERO, 28, 293-301 (1986) · Zbl 0615.90034
[3] Sylvester, J. J., A question in geometry of siyuation, Quarterly Journal of Pure Applied Mathematics, 1, 79 (1857)
[4] Elzinga, J.; Hearn, D. W., Geometric solutions for some minimax location problems, Transportation Science, 6, 379-394 (1972)
[5] Charalambous, C., Extension of the Elzinga and Hearn algorithm to the weighted case, Operations Research, 30, 591-594 (1982) · Zbl 0484.90030
[6] Hearn, D. W.; Vijay, J., Efficient algorithms for the weighted minimum circle problem, Operations Research, 30, 777-795 (1982) · Zbl 0486.90039
[7] Francis, R. L.; McGinnis, L. F.; White, J. A., Facility layout and location: an analytical approach (1992), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[8] Aneja, Y. T.; Chandrasekaran, R.; Nir, K. P.K., A note on the \(m\)-center problem with rectilinear distances, European Journal of Operational Research, 35, 118-123 (1988) · Zbl 0699.90028
[9] Chandrasekaran, R.; Tamir, A., Polynomially bounded algorithms for locating \(p\)-center problems on a tree, Mathematical Programming, 22, 304-315 (1982) · Zbl 0486.90036
[10] Drezner, Z., The \(p\)-center problem: heuristics and optimal algorithms, Journal of the Operational Research Society, 35, 741-748 (1984) · Zbl 0544.90024
[11] Drezner, Z., On the rectangular \(p\)-center problem, Naval Research Logistics, 34, 229-234 (1987) · Zbl 0614.90034
[12] Dyer, M. E.; Frieze, A. M., A simple heuristic for the \(p\)-center problem, Operations Research Letters, 3, 285-288 (1985) · Zbl 0556.90019
[13] Pelegrín B. The \(p\)-center problem under bidirectional polyhedral norms. In: Pelegrín P, editor. Proceedings EWGLA, vol. III. Publicaciones de la Universidad de Sevilla; 1998. p. 151-169.; Pelegrín B. The \(p\)-center problem under bidirectional polyhedral norms. In: Pelegrín P, editor. Proceedings EWGLA, vol. III. Publicaciones de la Universidad de Sevilla; 1998. p. 151-169.
[14] Pelegrín, B., Heuristics methods for the \(p\)-center problem, RAIRO Recherche Opérationnelle, 25, 65-72 (1991) · Zbl 0732.90056
[15] Vijay, J., An algorithm for the \(p\)-center problem in the plane, Transportation Science, 19, 235-245 (1985) · Zbl 0608.90020
[16] Elzinga, J.; Hearn, D. W., The minimum covering sphere problem, Management Science, 19, 96-104 (1972) · Zbl 0242.90061
[17] Pelegrín, B., The \(p\)-center problem in \(R^n\) with weighted Tchebychell norms, JORBEL, 31, 49-62 (1991) · Zbl 0747.90059
[18] Pelegrín B. El problema general del \(p\)-centro en \(\mathbb{R}^n\). En: Puerto, editor. Lecturas en teoría de localización. Publicaciones de la Universidad de Sevilla; 1996. p. 149-166.; Pelegrín B. El problema general del \(p\)-centro en \(\mathbb{R}^n\). En: Puerto, editor. Lecturas en teoría de localización. Publicaciones de la Universidad de Sevilla; 1996. p. 149-166.
[19] Pelegrín, B.; Cánovas, L., The minimum \(l_{pb}\)-hypersphere problem, Computational Optimization and Applications, 9, 85-97 (1998) · Zbl 0905.90136
[20] Kaufman, L.; Rousseauw, P. J., Finding groups in data (1990), Wiley: Wiley New York
[21] Späth, H., Cluster analysis algorithms for data reduction and classification of objects (1985), Ellis Horwood: Ellis Horwood Chichester, UK
[22] Frank, H., Optimal locations on a graph with probabilistic demands, Operations Research, 14, 409-421 (1966) · Zbl 0142.17704
[23] Frank, H., Optimal locations on a graph with correlated normal demands, Operations Research, 15, 552-557 (1967) · Zbl 0152.38204
[24] Berman O, Krass D. Facility location problems with stochastic demands and congestion. In: Drezner Z, Hamacher H, editors. Facility location: applications and theory. Berlin: Springer; 2002. p. 329-371.; Berman O, Krass D. Facility location problems with stochastic demands and congestion. In: Drezner Z, Hamacher H, editors. Facility location: applications and theory. Berlin: Springer; 2002. p. 329-371. · Zbl 1061.90068
[25] Daskin, M. S., A maximum expected covering location model: formulations, properties and heuristic solution, Transportation Science, 17, 48-70 (1983)
[26] Louveaux, F., Stochastic location analysis, Location Science, 1, 127-154 (1993) · Zbl 0923.90113
[27] Marianov, V.; ReVelle, C., Sitting emergency services, (Drezner, Z., Facility location: a survey of applications and methods (1995), Springer: Springer Berlin)
[28] Wesolowsky, G. O., Probabilistic weights in the one-dimensional location problem, Management Science, 24, 224-229 (1977) · Zbl 0372.90068
[29] Berman, O.; Drezner, Z.; Wang, J.; Wesolowsky, G. O., The minimax and maximin location problems on a network with uniform distributed weights, IIE Transactions, 35, 1017-1025 (2003)
[30] Berman, O.; Wang, J.; Drezner, Z.; Wesolowsky, G. O., A probabilistic minimax location problem on the plane, Annals of Operations Research, 122, 59-70 (2003) · Zbl 1038.90534
[31] Berman, O.; Drezner, Z., A probabilistic one-center location problem on a network, Journal of the Operational Research Society, 54, 871-877 (2003) · Zbl 1095.90521
[32] Berman, O.; Drezner, Z.; Wesolowsky, G. O., The expected maximum distance objective in facility location, Journal of Regional Science, 43, 735-748 (2003)
[33] Hansen, E., Global optimization using interval analysis (1992), Marcel Dekker: Marcel Dekker New York · Zbl 0762.90069
[34] Kearfott, R. B., Rigorous global search: continuous problems (1996), Kluwer: Kluwer Dordrecht · Zbl 0876.90082
[35] Ratschek, H.; Rokne, J., New computer methods for global optimization (1988), Ellis Horwood: Ellis Horwood Chichester, UK · Zbl 0648.65049
[36] Johnson, N. L.; Kotz, S.; Kemp, A. W., Univariate discrete distributions (1992), Wiley: Wiley New York · Zbl 0773.62007
[37] Johnson NL, Kotz S, Balakrishnan N. Continuous univariate distributions, vol. I. New York: Wiley; 1994.; Johnson NL, Kotz S, Balakrishnan N. Continuous univariate distributions, vol. I. New York: Wiley; 1994. · Zbl 0811.62001
[38] Johnson NL, Kotz S, Balakrishnan N. Continuous univariate distributions, vol. II. New York: Wiley; 1994.; Johnson NL, Kotz S, Balakrishnan N. Continuous univariate distributions, vol. II. New York: Wiley; 1994. · Zbl 0811.62001
[39] Wendell, R. E.; Hurter, A. P., Location theory, dominance, and convexity, Operations Research, 21, 314-320 (1973) · Zbl 0265.90040
[40] Pelegrín, B.; Michelot, C.; Plastria, F., On the uniqueness of optimal solutions in continuous location theory, European Journal of Operations Research, 29, 98-110 (1985)
[41] Pelegrín B. Localización minimax con incertidumbre. En: Alonso et al., editors. Optimización bajo incertidumbre. Tirant lo Blanch; 2004. p. 271-292.; Pelegrín B. Localización minimax con incertidumbre. En: Alonso et al., editors. Optimización bajo incertidumbre. Tirant lo Blanch; 2004. p. 271-292.
[42] Fernández, J.; Fernández, P.; Pelegrıın, B., A continuous location model for siting a non-noxious undesirable facility within a geographical region, European Journal of Operational Research, 121, 259-274 (2000) · Zbl 1040.90531
[43] Fernández, J.; Pelegrín, B., Sensitivity analysis in continuous location models via interval analysis, Studies in Locational Analysis, 14, 121-136 (2000) · Zbl 0972.90043
[44] Fernández, J.; Pelegrín, B., Using interval analysis for solving planar single-facility location problems: new discarding tests, Journal of Global Optimization, 19, 61-81 (2001) · Zbl 1168.90537
[45] Fernández J, Pelegrín B, Plastria F, Tóth B. Solving a Huff-like competitive location and design model for profit maximization in the plane. European Journal of Operational Research, 2006, forthcoming.; Fernández J, Pelegrín B, Plastria F, Tóth B. Solving a Huff-like competitive location and design model for profit maximization in the plane. European Journal of Operational Research, 2006, forthcoming.
[46] Markót MC, Fernández J, Casado LG, Csendes T. New interval methods for constrained global optimization. Mathematical Programming Series A 2006;106:287-318.; Markót MC, Fernández J, Casado LG, Csendes T. New interval methods for constrained global optimization. Mathematical Programming Series A 2006;106:287-318.
[47] Kearfott RB, Nakao MT, Neumaier A, Rump SM, Shary SP, van Hentenryck P. Standardized notation in interval analysis. Reliable Computing, 2002, available at ∼;; Kearfott RB, Nakao MT, Neumaier A, Rump SM, Shary SP, van Hentenryck P. Standardized notation in interval analysis. Reliable Computing, 2002, available at ∼; · Zbl 1196.65088
[48] Hammer, R.; Hocks, M.; Kulisch, U.; Ratz, D., \(C ++\) toolbox for verified computing (1995), Springer: Springer Berlin · Zbl 0828.68041
[49] Rall LB. Automatic differentiation, techniques and applications. Lecture notes in computer science, no. 120. Berlin: Springer; 1981.; Rall LB. Automatic differentiation, techniques and applications. Lecture notes in computer science, no. 120. Berlin: Springer; 1981.
[50] Knüppel, O., PROFIL/BIAS—a fast interval library, Computing, 53, 277-287 (1994) · Zbl 0808.65055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.