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 nonconvex objective function. Based on an equivalent problem with modified barriers, derived in a companion paper [3], the non convex feasible set is partitioned into a network and rectangular cells. The rectangular cells are further partitioned into a polynomial number of convex subcells, called convex domains, on which the distance function, and hence the objective function, is convex. Then the problem is solved over the network and convex domains for an optimal solution. Bounds are given that reduce the number of convex domains to be examined. The number of convex domains is bounded above by a polynomial in the size of the problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
P.M. Dearing and R. Segars, An equivalence result for planar location problems with rectilinear distance and barriers, Annals of Operations Research 111 (2002) 87-108.
J. Hooker, Solving nonlinear single-facility network location problems, Operations Research 34 (1986) 732-743.
K. Klamroth, Single facility location problems with barriers, Habilitations-schrift, Department of Mathematics, Universität Kaiserslautern (2000).
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.
G.L. Nemhauser and L.A.Wolsey, Integer and Combinatorial Optimization (Wiley, New York, 1988).
R. Segars, Location problems with barriers using rectilinear distance, Ph.D. Dissertation, Management Science, Clemson University (2000).
D.R. Shier, Mathematics of discrete structures, combinatorics, in: Encyclopedia of Physical Science and Technology, Vol. 9 (1992).
Rights and permissions
About this article
Cite this article
Dearing, P., Segars, R. Solving Rectilinear Planar Location Problems with Barriers by a Polynomial Partitioning. Annals of Operations Research 111, 111–133 (2002). https://doi.org/10.1023/A:1020997518554
Issue Date:
DOI: https://doi.org/10.1023/A:1020997518554