Skip to main content
SpringerLink
Log in

Planar Location Problems with Block Distance and Barriers

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper considers one facility planar location problems using block distance and assuming barriers to travel. Barriers are defined as generalized convex sets relative to the block distance. The objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. The problem is solved by modifying the barriers to obtain an equivalent problem and by decomposing the feasible region into a polynomial number of convex subsets on which the objective function is convex. It is shown that solving a planar location problem with block distance and barriers requires at most a polynomial amount of additional time over solving the same problem without barriers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agarwal, P.K. and M. Sharir. (2000). “Arrangements and Their Applications.” In J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. Elsevier Science.

  • Aneja, Y.P. and M. Parlar. (1994). “Algorithms for Weber Facility Location in the Presence of Forbidden Regions and/or Barriers to Travel.” Transportation Science 28, 70–76.

    Google Scholar 

  • Apostol, T. (1960). Mathematical Analysis, A Modern Approach to Advanced Calculus. Addison-Wesley, Reading Massachusetts, U.S.A.

    Google Scholar 

  • Batta, R., A. Ghose, and U.S. Palekar. (1989). “Locating Facilities on the Manhattan Metric with Arbitrarily Shaped Barriers and Convex Forbidden Regions.” Transportation Science 23, 26–36.

    Google Scholar 

  • Ben-Moshe, B., M.J. Katz, and J.S.B. Mitchell. (2001). “Farthest Neighbors and Center Points in the Presence of Rectangular Obstacles.” In Proc. 17th ACM Symposium on Computational Geometry.

  • Butt, E.S. (1994). “Facility Location in the Presence of Forbidden Regions.” Ph.D. thesis, Department of Industrial and Management Systems Engineering, Pennsylvania State University, PR.

  • Butt, S.E. and Cavalier, T.M. (1996). “An Efficient Algorithm for Facility Location in the Presence of Forbidden Regions.” European Journal of Operational Research 90, 56–70.

    Article  Google Scholar 

  • Choi, J., C.-S. Shin, and S.K. Kim. (1998). “Computing Weighted Rectilinear Median and Center set in the Presence of Obstacles.” In Proc. 9th Annu. Internat. Sympos. Algorithms Comput., Vol. 1533 of Lecture Notes in Computer Science, Springer-Verlag, pp. 29–38.

  • Dearing, P.M. and R. Segars Jr. (2002a). “An Equivalence Result for Single Facility Planar Location Problems with Rectilinear Distance and Barriers.” Annals of Operations Research 111, 89–110.

    Article  Google Scholar 

  • Dearing, P.M. and R. Segars Jr. (2002b). “Solving Rectilinear Planar Location Problems with Barriers by a Polynomial Partitioning.” Annals of Operations Research, 111, 111–133.

    Article  Google Scholar 

  • Dearing, P.M., H.W. Hamacher, and K. Klamroth. (2002). “Dominating Sets for Rectilinear Center Location Problems with Polyhedral Barriers.” Naval Research Logistics 49, 647–665.

    Article  Google Scholar 

  • Fliege, J. (1997). Effiziente Dimensionsreduktion in Multilokationsproblemen. Aachen: Shaker Verlag.

    Google Scholar 

  • Hamacher, H.W. and K. Klamroth. (2000). “Planar Location Problems with Barriers Under Polyhedral Gauges.” Annals of Operations Research 96, 191–208.

    Article  Google Scholar 

  • Hansen, P., B. Jaumard, and H. Tuy. (1995). “Global Optimization in Location.” In Z. Drezner (ed.), Facility Location, Springer Series in Operations Research, pp. 43–68.

  • Hansen, P., S. Krau, D. Peeters, and J.-F. Thisse. (2000). “Weber's Problem with Forbidden Regions for Location and Transportation.” Technical Report G-2000-26, Les Cahiers du Gerad.

  • Katz, I.N. and L. Cooper. (1981). “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, 166–173.

    Article  Google Scholar 

  • Klamroth, K. (2001a). “Planar Weber Location Problems with Line Barriers.” Optimization 49, 517–527.

    Google Scholar 

  • Klamroth, K. (2001b). “A Reduction Result for Location Problems with Polyhedral Barriers.” European Journal of Operational Research 130, 486–497.

    Article  Google Scholar 

  • Klamroth, K. (2002). Single Facility Location Problems with Barriers. New York: Springer-Verlag.

    Google Scholar 

  • Klamroth, K. and M. Wiecek. (2002). “A Bi-Objective Median Location Problem with a Line Barrier.” Operations Research 50, 670–679.

    Article  Google Scholar 

  • S. Krau. (1996). “Extensions du Problème de Weber.” Ph.D. thesis, Département de Mathématiques et de Génie Industriel, Université de Montréal.

  • Kusakari, Y. and T. Nishizeki. (1997). “An Algorithm for Finding a Region with the Minimum Total L 1 from Prescribed Terminals.” In Proc. of ISAAC'97. Vol. 1350 of Lecture Notes in Computer Science, Springer-Verlag.

  • Larson, R.C. and G. Sadiq. (1983). “Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel.” Operations Research 31, 652–669.

    Google Scholar 

  • Minkowski, H. (1911). Gesammelte Abhandlungen, zweiter Band. D. Hilbert (ed.). Leipzig und Berlin: Teubner Verlag. Also in Chelsea Publishing Company, New York, 1967.

  • Mitchell, J.S.B. (2000). “Geometric Shortest Paths and Network Optimization.” In J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. Elsevier Science.

  • Ottmann, T., E. Soisalon-Soininen, and D. Wood. (1984). “On the Definition and Computation of Rectilinear Convex Hulls.” Information Sciences 33, 157–171.

    Article  Google Scholar 

  • Savaş, S., R. Batta, and R. Nagi. (2002). “Finite-Size Facility Placement in the Presence of Barriers to Rectilinear Travel.” To appear.

  • Segars Jr., R. (2000). “Location Problems with Barriers Using Rectilinear Distance.” Ph.D. thesis, Dept. of Mathematical Sciences, Clemson University, SC.

  • Ward, J.E. and R.E. Wendell. (1985). “Using Block Norms for Location Modeling.” Operations Research 33, 1074–1090.

    Article  Google Scholar 

  • Widmayer, P., Y.F. Wu, and C.K. Wong. (1987). “On Some Distance Problems in Fixed Orientations.” SIAM Journal on Computing 16, 728–746.

    Article  Google Scholar 

  • Witzgall, C. (1964). “Optimal Location of a Central Facility: Mathematical Models and Concepts.” Technical Report 8388, National Bureau of Standards, Washington D.C.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Clemson University, Clemson, SC

    P. M. Dearing & R. Segars Jr.

  2. Institute of Applied Mathematics, University of Erlangen-Nuremberg, Germany

    K. Klamroth

Authors
  1. P. M. Dearing
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K. Klamroth
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Segars Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dearing, P.M., Klamroth, K. & Segars, R. Planar Location Problems with Block Distance and Barriers. Ann Oper Res 136, 117–143 (2005). https://doi.org/10.1007/s10479-005-2042-4

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-2042-4

Keywords

Search

Navigation