Abstract
This paper analyzes continuous single facility location problems where the demand is randomly defined by a given probability distribution. For these types of problems that deal with the minimization of average distances, we obtain geometrical characterizations of the entire set of optimal solutions. For the important case of total polyhedrality on the plane we derive efficient algorithms with polynomially bounded complexity. We also develop a discretization scheme that provides \({\varepsilon}\) -approximate solutions of the original problem by solving simpler location problems with points as demand facilities.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barbu V., Precupanu T.: Convexity and Optimization in Banach Spaces. Sijthoff & Noordhoff Publishers, Leiden (1975)
Bauer F.L., Stoer J., Witzgall C.: Absolute and monotonic norms. Numer. Math. 3, 257–264 (1961)
Brimberg J., Wesolowsky G.O.: Note: facility location with closest rectangular distances. Nav. Res. Logist. 47, 77–84 (2000)
Brimberg J., Wesolowsky G.O.: Locating facilities by minimax relative to closest points of demand areas. Comp. Oper. Res. 29, 625–636 (2002)
Brimberg J., Wesolowsky G.O.: Minisum location with closest Euclidean distances. Ann. Oper. Res. 111, 151–165 (2002)
Carrizosa E., Muñoz M., Puerto J.: The Weber problem with regional demand. Eur. J. Oper. Res. 104, 358–365 (1998)
Carrizosa E., Muñoz M., Puerto J.: Location and shape of a rectangular facility in \({\mathbb{R}^n}\) . Convexity properties. Math. Program. 83, 277–290 (1998)
Carrizosa E., Muñoz M., Puerto J.: A note on the optimal positioning of service units. Oper. Res. 46(1), 155–156 (1998)
Carrizosa E., Conde E., Muñoz M., Puerto J.: The generalized Weber problem with expected distances. RAIRO Rech. oper. 29, 35–57 (1995)
Drezner Z.: Location of regional facilities. Nav. Res. Logist. Q. 33, 523–529 (1986)
Drezner Z., Wesolowsky G.: Optimal location of a demand facility relative to area demand. Nav. Res. Logist. Q. 27, 199–206 (1980)
Durier R.: The general center location problem. Math. Oper. Res. 20, 400–414 (1995)
Durier R., Michelot C.: Geometrical properties of the Fermat-Weber problem. Eur. J. Oper. Res. 20, 332–343 (1985)
Edelsbrunner H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)
Ehrgott M.: Location of rescue helicopters in South Tyrol. Int. J. Ind. Eng. Theory Appl. Pract. 9, 16–22 (2002)
Garkavi A.L., Smatkov V.A.: On the Lamé point and its generalizations in a normed space. Math. USSR Sb. 24(2), 267–286 (1974)
Giles, J.R.: Convex analysis with applications in differentiation of convex functions. Research Notes in Math. n. 58, Pitman Advanced Publishing Program (1982)
Hakimi S.L.: Optimum location of switching centers and the absolute centers and medians of a graph. Oper. Res. 12, 450–459 (1964)
Hiriart-Urruty J.B., Lemarechal C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993)
Hooker J.N., Garfinkel R.S., Chen C.K.: Finite dominating sets for network location problems. Oper. Res. 39(1), 100–118 (1991)
Horváth J.: Topological Vector Spaces and Distributions, vol. I. Addison-Wesley, Reading (1966)
Ioffe A.D., Levin V.L.: Subdifferentials of convex functions. Trans. Mosc. Math. Soc. 26, 1–72 (1972)
Koshizuka T., Kurita O.: Approximate formulas of average distances associated with regions and applications to location problems. Math. Program. 52, 99–123 (1991)
Love R.F., Morris J.G., Wesolowsky G.O.: Facilities Location: Models and Methods. North Holland, New York (1988)
Luenberger D.G.: Optimization by Vector Space Methods. Wiley, New York (1969)
Nickel S., Puerto J.: Location Theory: A Unified Approach. Springer, Heidelberg (2005)
Nickel S., Puerto J., Rodríguez-Chía A.M.: An approach to location models involving sets as existing facilities. Math. Oper. Res. 28, 693–715 (2003)
Papini P.L.: Two new examples of sets without Centers. Top 13(2), 315–320 (2005)
Puerto J., Fernández F.R.: Geometrical properties of the symmetrical single facility location problem. J. Nonlinear Convex Anal. 1(3), 321–342 (2000)
Puerto J., Rodríguez-Chía A.M.: Robust positioning of service units. Stoch. Models 19(1), 125–147 (2003)
Rockafellar R.T.: Convex Analysis. Princeton Press, Princeton (1970)
Sharir M., Agarwal P.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)
Tapia R.A.: A characterization of inner product spaces. Proc. AMS 41, 569–574 (1973)
Valero-Franco C., Rodríguez-Chía A.M., Espejo-Miranda I.: The single facility location problem with average-distances. Top 16, 164–194 (2008)
Vickson R.G., Gerchak Y., Rotem D.: Optimal positioning of read/write head in mirrored disks. Locat. Sci. 3(2), 125–132 (1995)
Wendell R., Hurter A.: Location theory, dominance and convexity. Oper. Res. 21, 314–320 (1973)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by Spanish Ministry of Education and Science grants numbers MTM2007-67433-C02-(01,02), HI2006-0123, and Junta de Andalucía, grants numbers P06-FQM-01364 and P06-FQM-01366.
Rights and permissions
About this article
Cite this article
Puerto, J., Rodríguez-Chía, A.M. On the structure of the solution set for the single facility location problem with average distances. Math. Program. 128, 373–401 (2011). https://doi.org/10.1007/s10107-009-0308-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0308-3