Cited By
View all- Aïder MAzzi AHifi M(2023)The ɛ-constraint as a learning strategy in the population-based algorithmKnowledge-Based Systems10.1016/j.knosys.2023.110363265:COnline publication date: 8-Apr-2023
The obnoxious facilities planar p-median problem
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.
References
[1]
Aneja Y and Parlar M Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel Transp Sci 1994 28 70-76
[2]
Antunes AP, Teixeira J, and Coutinho M Managing solid waste through discrete location analysis: a case study in central Portugal J Oper Res Soc 2008 59 1038-1046
[3]
Aurenhammer F, Klein R, and Lee D-T Voronoi diagrams and delaunay triangulations 2013 New Jersey World Scientific
[4]
Batta R and Chiu S Optimal obnoxious paths on a network: transportation of hazardous materials Oper Res 1988 36 84-92
[5]
Batta R, Ghose A, and Palekar U Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions Transp Sci 1989 23 26-36
[6]
Berman O and Simchi-Levi D The conditional location problem on networks Transp Sci 1990 24 77-78
[7]
Berman O, Drezner Z, and Krass D Big segment small segment global optimization algorithm on networks Networks 2011 58 1-11
[8]
Brimberg J, Hansen P, Mladenović N, and Taillard E Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem Oper Res 2000 48 444-460
[9]
Butt S and Cavalier T An efficient algorithm for facility location in the presence of forbidden regions Eur J Oper Res 1996 90 56-70
[10]
Calik H, Labbé M, Yaman H (2015) p-center problems. In: Location science. Springer, pp 79–92
[11]
Carrizosa E, Toth B (2019) Anti-covering problems. In: Location science. Springer, pp 123–141
[12]
Chen D and Chen R New relaxation-based algorithms for the optimal solution of the continuous and discrete -center problems Comput Oper Res 2009 36 1646-1655
[13]
Church RL, Drezner Z (2020) Review of obnoxious facilities location problems. Review
[14]
Church RL and Garfinkel RS Locating an obnoxious facility on a network Transp Sci 1978 12 107-118
[15]
Church RL and Meadows B Location modelling using maximum service distance criteria Geogr Anal 1979 11 358-373
[16]
CPLEX, IBM ILOG (2019) 12.10: User’s Manual for CPLEX. International Business Machines Corporation, Incline Village, NV
[17]
Daskin MS Network and discrete location: models, algorithms, and applications 1995 New York Wiley
[18]
Daskin MS and Maass KL Laporte G, Nickel S, and da Gama FS The p-median problem Location science 2015 Berlin Springer 21-45
[19]
Drezner Z and Drezner TD Biologically inspired parent selection in genetic algorithms Ann Oper Res 2020 287 161-183
[20]
Drezner Z and Suzuki A The big triangle small triangle method for the solution of non-convex facility location problems Oper Res 2004 52 128-135
[21]
Drezner Z and Wesolowsky GO Minimax and maximin facility location problems on a sphere Naval Res Logist Q 1983 30 305-312
[22]
Drezner Z and Wesolowsky GO Obnoxious facility location in the interior of a planar network J Reg Sci 1996 35 675-688
[23]
Drezner Z, Klamroth K, Schöbel A, and Wesolowsky GO Drezner Z and Hamacher HW The Weber problem Facility location: applications and theory 2002 Berlin Springer 1-36
[24]
Drezner T, Drezner Z, and Scott CH Location of a facility minimizing nuisance to or from a planar network Comput Oper Res 2009 36 135-148
[25]
Drezner Z, Scott CH, and Turner J Mixed planar and network single-facility location problems Networks 2016 68 271-282
[26]
Drezner T, Drezner Z, and Schöbel A The Weber obnoxious facility location model: a Big Arc Small Arc approach Comput Oper Res 2018 98 240-250
[27]
Drezner T, Drezner Z, and Kalczynski P The planar multifacility collection depots location problem Comput Oper Res 2019 102 121-129
[28]
Drezner Z, Kalczynski P, and Salhi S The multiple obnoxious facilities location problem on the plane: a Voronoi based heuristic OMEGA Int J Manag Sci 2019 87 105-116
[29]
Eiselt HA and Marianov V Location modeling for municipal solid waste facilities Comput Oper Res 2015 62 305-315
[30]
Erkut E and Neuman S Analytical models for locating undesirable facilities Eur J Oper Res 1989 40 275-291
[31]
Gill PE, Murray W, and Saunders MA SNOPT: an SQP algorithm for large-scale constrained optimization SIAM Rev 2005 47 99-131
[32]
Goldman AJ and Dearing PM Concepts of optimal location for partially noxious facilities Bull Oper Res Soc Am 1975 23 B85
[33]
Goldman AJ and Dearing PM Concepts of optimal location for partially noxious facilities 1975 Chicago ORSA/TIMS NationalMeeting
[34]
Hamacher HW and Schöbel A A note on center problems with forbidden polyhedra Oper Res Lett 1997 20 165-169
[35]
Hansen P, Peeters D, and Thisse J-F On the location of an obnoxious facility Sistemi Urbani 1981 3 299-317
[36]
Hansen P, Jaumard B, and Krau S An algorithm for Weber’s problem on the sphere Loc Sci 1995 3 217-237
[37]
Kariv O and Hakimi SL An algorithmic approach to network location problems. I: the -centers SIAM J Appl Math 1979 37 513-538
[38]
Katz I and Cooper L Facility location in the presence of forbidden regions i: formulation and the case of Euclidean distance with one forbidden circle Eur J Oper Res 1981 6 166-173
[39]
Kuenne RE and Soland RM Exact and approximate solutions to the multisource Weber problem Math Program 1972 3 193-209
[40]
Lee DT and Schachter BJ Two algorithms for constructing a Delaunay triangulation Int J Parallel Prog 1980 9 219-242
[41]
Love RF, Morris JG, and Wesolowsky GO Facilities location: models and methods 1988 New York North Holland
[42]
Minieka E Conditional centers and medians on a graph Networks 1980 10 265-272
[43]
Ogryczak W and Zawadzki M Conditional median: a parametric solution concept for location problems Ann Oper Res 2002 110 167-181
[44]
Ohya T, Iri M, and Murota K Improvements of the incremental method of the Voronoi diagram with computational comparison of various algorithms J Oper Res Soc Jpn 1984 27 306-337
[45]
Okabe A, Boots B, Sugihara K, and Chiu SN Spatial tessellations: concepts and applications of Voronoi diagrams 2000 Hoboken Wiley
[46]
ReVelle CS and Swain RW Central facilities location Geogr Anal 1970 2 30-42
[47]
Schöbel A and Scholz D The big cube small cube solution method for multidimensional facility location problems Comput Oper Res 2010 37 115-122
[48]
Shamos M, Hoey D (1975) Closest-point problems. In: Proceedings 16th Annual Symposium on the Foundations of Computer Science, Berkeley, CA, pp 151–162
[49]
Sugihara K and Iri M Construction of the voronoi diagram for one million generators in single-precision arithmetic Proc IEEE 1992 80 1471-1484
[50]
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
[51]
Suzuki A and Okabe A Drezner Z Using Voronoi diagrams Facility location: a survey of applications and methods 1995 New York Springer 103-118
[52]
Voronoï G 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 1908 134 198-287
[53]
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
[54]
Wesolowsky GO The Weber problem: history and perspectives Loc Sci 1993 1 5-23
[55]
Wolfram S (2020) Mathematica, Version 12.2. Champaign, IL. https://www.wolfram.com/mathematica
Recommendations
Review of obnoxious facilities location problems
Highlights- Review of Obnoxious Facilities location models.
- Historical overview of the problem.
- Single and multiple obnoxious facilities models.
- Models in discrete and continuous space.
- Suggestions for future research.
AbstractIn this paper we review research on the location of facilities that have a negative impact on surrounding communities which are defined in the literature, for example, as obnoxious, undesirable, or noxious facilities. Overall, the literature on ...
The dynamic p-median problem with mobile facilities
Highlights- The most general version of the dynamic p-median problem is studied.
- Mobile and ...
AbstractBeing motivated by real life applications in construction management, we consider the dynamic p-median problem and its extension with mobile facilities. The number of facilities changes over a planning horizon where one or more ...
Locating multiple facilities using the max-sum objective
Highlights- Two New obnoxious facilities location models are proposed.
- Special solution ...
AbstractWe propose to apply a multi-start sequential linear programming (MSLP) algorithm for the solution of two multiple obnoxious facility problems on the plane. One problem (Max-Sum1) considers obnoxious facilities and the other (Max-Sum2) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 June 2021
Accepted: 12 March 2021
Received: 17 June 2020
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024
Other Metrics
Citations
Cited By
View all- Aïder MAzzi AHifi M(2023)The ɛ-constraint as a learning strategy in the population-based algorithmKnowledge-Based Systems10.1016/j.knosys.2023.110363265:COnline publication date: 8-Apr-2023
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in