Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The obnoxious facilities planar p-median problem

  • Original Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

In this paper, we propose the planar obnoxious facilities p-median problem. In the p-median problem the objective is to find p locations for facilities that minimize the weighted sum of distances between communities and their closest facility. In the obnoxious version, we add constraints that each facility must be located at least a certain distance from a partial set of communities because they generate nuisance affecting these communities. The resulting problem is extremely non-convex and traditional nonlinear solvers such as SNOPT are not efficient. An efficient solution method based on Voronoi diagrams is proposed and tested. We also constructed the efficient frontiers of the test problems, showing the trade-off between the required distance and the p-median objective, to assist the planers in making location decisions.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Aneja Y, Parlar M (1994) Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel. Transp Sci 28:70–76

    Article  Google Scholar 

  • Antunes AP, Teixeira J, Coutinho M (2008) Managing solid waste through discrete location analysis: a case study in central Portugal. J Oper Res Soc 59:1038–1046

    Article  Google Scholar 

  • Aurenhammer F, Klein R, Lee D-T (2013) Voronoi diagrams and delaunay triangulations. World Scientific, New Jersey

    Book  Google Scholar 

  • Batta R, Chiu S (1988) Optimal obnoxious paths on a network: transportation of hazardous materials. Oper Res 36:84–92

    Article  Google Scholar 

  • Batta R, Ghose A, Palekar U (1989) Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions. Transp Sci 23:26–36

    Article  Google Scholar 

  • Berman O, Simchi-Levi D (1990) The conditional location problem on networks. Transp Sci 24:77–78

    Article  Google Scholar 

  • Berman O, Drezner Z, Krass D (2011) Big segment small segment global optimization algorithm on networks. Networks 58:1–11

    Article  Google Scholar 

  • Brimberg J, Hansen P, Mladenović N, Taillard E (2000) Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Oper Res 48:444–460

    Article  Google Scholar 

  • Butt S, Cavalier T (1996) An efficient algorithm for facility location in the presence of forbidden regions. Eur J Oper Res 90:56–70

    Article  Google Scholar 

  • Calik H, Labbé M, Yaman H (2015) p-center problems. In: Location science. Springer, pp 79–92

  • Carrizosa E, Toth B (2019) Anti-covering problems. In: Location science. Springer, pp 123–141

  • Chen D, Chen R (2009) New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems. Comput Oper Res 36:1646–1655

    Article  Google Scholar 

  • Church RL, Drezner Z (2020) Review of obnoxious facilities location problems. Review

  • Church RL, Garfinkel RS (1978) Locating an obnoxious facility on a network. Transp Sci 12:107–118

    Article  Google Scholar 

  • Church RL, Meadows B (1979) Location modelling using maximum service distance criteria. Geogr Anal 11:358–373

    Article  Google Scholar 

  • CPLEX, IBM ILOG (2019) 12.10: User’s Manual for CPLEX. International Business Machines Corporation, Incline Village, NV

  • Daskin MS (1995) Network and discrete location: models, algorithms, and applications. Wiley, New York

    Book  Google Scholar 

  • Daskin MS, Maass KL (2015) The p-median problem. In: Laporte G, Nickel S, da Gama FS (eds) Location science. Springer, Berlin, pp 21–45

    Chapter  Google Scholar 

  • Drezner Z, Drezner TD (2020) Biologically inspired parent selection in genetic algorithms. Ann Oper Res 287:161–183

    Article  Google Scholar 

  • Drezner Z, Suzuki A (2004) The big triangle small triangle method for the solution of non-convex facility location problems. Oper Res 52:128–135

    Article  Google Scholar 

  • Drezner Z, Wesolowsky GO (1983) Minimax and maximin facility location problems on a sphere. Naval Res Logist Q 30:305–312

    Article  Google Scholar 

  • Drezner Z, Wesolowsky GO (1996) Obnoxious facility location in the interior of a planar network. J Reg Sci 35:675–688

    Article  Google Scholar 

  • Drezner Z, Klamroth K, Schöbel A, Wesolowsky GO (2002) The Weber problem. In: Drezner Z, Hamacher HW (eds) Facility location: applications and theory. Springer, Berlin, pp 1–36

    Chapter  Google Scholar 

  • Drezner T, Drezner Z, Scott CH (2009) Location of a facility minimizing nuisance to or from a planar network. Comput Oper Res 36:135–148

    Article  Google Scholar 

  • Drezner Z, Scott CH, Turner J (2016) Mixed planar and network single-facility location problems. Networks 68:271–282

    Article  Google Scholar 

  • Drezner T, Drezner Z, Schöbel A (2018) The Weber obnoxious facility location model: a big arc small arc approach. Comput Oper Res 98:240–250

    Article  Google Scholar 

  • Drezner T, Drezner Z, Kalczynski P (2019a) The planar multifacility collection depots location problem. Comput Oper Res 102:121–129

    Article  Google Scholar 

  • Drezner Z, Kalczynski P, Salhi S (2019b) The multiple obnoxious facilities location problem on the plane: a Voronoi based heuristic. OMEGA Int J Manag Sci 87:105–116

    Article  Google Scholar 

  • Eiselt HA, Marianov V (2015) Location modeling for municipal solid waste facilities. Comput Oper Res 62:305–315

    Article  Google Scholar 

  • Erkut E, Neuman S (1989) Analytical models for locating undesirable facilities. Eur J Oper Res 40:275–291

    Article  Google Scholar 

  • Gill PE, Murray W, Saunders MA (2005) SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev 47:99–131

    Article  Google Scholar 

  • Goldman AJ, Dearing PM (1975a) Concepts of optimal location for partially noxious facilities. Bull Oper Res Soc Am 23:B85

    Google Scholar 

  • Goldman AJ, Dearing PM (1975b) Concepts of optimal location for partially noxious facilities. ORSA/TIMS NationalMeeting, Chicago

    Google Scholar 

  • Hamacher HW, Schöbel A (1997) A note on center problems with forbidden polyhedra. Oper Res Lett 20:165–169

    Article  Google Scholar 

  • Hansen P, Peeters D, Thisse J-F (1981) On the location of an obnoxious facility. Sistemi Urbani 3:299–317

    Google Scholar 

  • Hansen P, Jaumard B, Krau S (1995) An algorithm for Weber’s problem on the sphere. Loc Sci 3:217–237

    Article  Google Scholar 

  • Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: the \(p\)-centers. SIAM J Appl Math 37:513–538

    Article  Google Scholar 

  • Katz I, Cooper L (1981) Facility location in the presence of forbidden regions i: Formulation and the case of Euclidean distance with one forbidden circle. Eur J Oper Res 6:166–173

    Article  Google Scholar 

  • Kuenne RE, Soland RM (1972) Exact and approximate solutions to the multisource Weber problem. Math Program 3:193–209

    Article  Google Scholar 

  • Lee DT, Schachter BJ (1980) Two algorithms for constructing a Delaunay triangulation. Int J Parallel Prog 9:219–242

    Google Scholar 

  • Love RF, Morris JG, Wesolowsky GO (1988) Facilities location: models and methods. North Holland, New York

    Google Scholar 

  • Minieka E (1980) Conditional centers and medians on a graph. Networks 10:265–272

    Article  Google Scholar 

  • Ogryczak W, Zawadzki M (2002) Conditional median: a parametric solution concept for location problems. Ann Oper Res 110:167–181

    Article  Google Scholar 

  • Ohya T, Iri M, Murota K (1984) Improvements of the incremental method of the Voronoi diagram with computational comparison of various algorithms. J Oper Res Soc Jpn 27:306–337

    Google Scholar 

  • Okabe A, Boots B, Sugihara K, Chiu SN (2000) Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley Series in Probability and Statistics. Wiley, Hoboken

    Book  Google Scholar 

  • ReVelle CS, Swain RW (1970) Central facilities location. Geogr Anal 2:30–42

    Article  Google Scholar 

  • Schöbel A, Scholz D (2010) The big cube small cube solution method for multidimensional facility location problems. Comput Oper Res 37:115–122

    Article  Google Scholar 

  • Shamos M, Hoey D (1975) Closest-point problems. In: Proceedings 16th Annual Symposium on the Foundations of Computer Science, Berkeley, CA, pp 151–162

  • Sugihara K, Iri M (1992) Construction of the voronoi diagram for one million generators in single-precision arithmetic. Proc IEEE 80:1471–1484

    Article  Google Scholar 

  • Suzuki A (2019) Big triangle small triangle method for the Weber problem on the sphere. In: Eiselt HA, Marianov V (eds) Contributions to Location Analysis—In Honor of Zvi Drezner’s 75th Birthday. Springer, pp 109–123

  • Suzuki A, Okabe A (1995) Using Voronoi diagrams. In: Drezner Z (ed) Facility location: a survey of applications and methods. Springer, New York, pp 103–118

    Chapter  Google Scholar 

  • Voronoï G (1908) Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. J Reine Angew Math 134:198–287

    Article  Google Scholar 

  • Weber A (1909) Über den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. English Translation: on the Location of Industries. University of Chicago Press, Chicago, IL. Translation published in 1929

  • Wesolowsky GO (1993) The Weber problem: history and perspectives. Loc Sci 1:5–23

    Google Scholar 

  • Wolfram S (2020) Mathematica, Version 12.2. Champaign, IL. https://www.wolfram.com/mathematica

Download references

Author information

Authors and Affiliations

  1. Steven G. Mihaylo College of Business and Economics, California State University-Fullerton, Fullerton, CA, 92834, USA

    Pawel Kalczynski & Zvi Drezner

Authors
  1. Pawel Kalczynski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zvi Drezner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zvi Drezner.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kalczynski, P., Drezner, Z. The obnoxious facilities planar p-median problem. OR Spectrum 43, 577–593 (2021). https://doi.org/10.1007/s00291-021-00626-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-021-00626-z

Keywords

Search

Navigation