Abstract
This paper considers planar location problems with rectilinear distance and barriers, where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. A modification of the barriers is developed based on properties of the rectilinear distance. It is shown that the original problem with barriers is equivalent to the problem with modified barriers. A particular modification is given that reduces the feasible region and permits its partitioning into convex subsets on which the objective function is convex. A solution algorithm based on the partitioning is the subject of a companion paper.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y.P. Aneja and M. Parlar, Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel, Transportation Science 28 (1994) 70-76.
T.M. Apostol, Mathematical Analysis, A Modern Approach to Advanced Calculus (Addison-Wesley, Reading, MA, 1960).
R. Batta, A. Ghose and U.S. Palekar, Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions, Transportation Science 23 (1989) 26-36.
R. Batta and L.A. Leifer, On the accuracy of demand point solutions to the planar, Manhattan metric, p-median problem, with and without barrier to travel, Computers and Operations Research 15 (1988) 253-262.
S.E. Butt and T.M. Cavalier, An efficient algorithm for facility location in the presence of forbidden regions, European Journal of Operational Research 90 (1996) 56-70.
P.M. Dearing, H.W. Hamacher and K. Klamroth, Dominating sets for rectilinear center location problems with polynomial barriers, Naval Research Logistics 49 (2002) 647-665.
P.M. Dearing and R. Segars, Solving rectilinear planar location problems with barriers by a polynomial time partitioning, Annals of Operations Research 111 (2002) 109-131.
R.L. Francis, L.F. McGinnis and J.A. White, Facility Layout and Location: An Analytical Approach, 2nd ed. (Prentice-Hall, New York, 1992).
H.W. Hamacher, Mathematical Methods in Planar Locational Planning (in German) (Vieweg, Braunschweig, 1995).
H.W. Hamacher and K. Klamroth, Planar location problems with barriers under polyhedral gauges, Technical Report No. 21, Department of Mathematics, Universität Kaiserslautern (1997).
H.W. Hamacher and S. Nickel, Restricted planar location problems and applications, Naval Research Logistics 42 (1995) 967-992.
I.N. Katz and L. Cooper, Facility location in the presence of forbidden regions, I: Formulation and the case of Euclidean distance with one forbidden circle, European Journal of Operational Research 6 (1981) 166-173.
K. Klamroth, Single facility location problems with barriers, Habilitations-schrift, Department of Mathematics, Universität Kaiserslautern (2000).
K. Klamroth, Planar location problems with line barriers, Optimization 49 (2001) 517-527.
K. Klamroth, A reduction result for location problems with polygon barriers, European Journal of Operational Research 130 (2001) 486-497.
K. Klamroth and M. Wiecek, A bi-objective planar location problem with a line barrier, Operations Research, to appear 2001.
R.C. Larson and V.O.K. Li, Finding minimum rectilinear distance paths in the presence of barriers, Networks 11 (1981) 285-304.
R.C. Larson and G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research 31 (1983) 652-669.
R.F. Love, J.G. Morris and G.O. Wesolowsky, Facilities Location: Models & Methods (North-Holland, New York, 1988).
P. Nandikota, R. Batta and R. Nagi, The weighted one-center problem with arbitrarily shaped barriers, Presented at INFORMS, Salt Lake City (May, 2000).
S. Nickel, Restricted center problems under polyhedral gauges, European Journal of Operational Research 104 (1998) 343-357.
R. Segars, Location problems with barriers using rectilinear distance, Ph.D. dissertation,Management Science, Clemson University (2000).
J.E.Ward and R.E.Wendell, Using block norms for location modeling, Operations Research 33 (1985) 1074-1090.
Rights and permissions
About this article
Cite this article
Dearing, P., Segars, R. An Equivalence Result for Single Facility Planar Location Problems with Rectilinear Distance and Barriers. Annals of Operations Research 111, 89–110 (2002). https://doi.org/10.1023/A:1020945501716
Issue Date:
DOI: https://doi.org/10.1023/A:1020945501716