Solving k-obnoxious facility location problem on a plane

Utpal Kumar Bhattacharya



In this paper k-obnoxious facility location problem has been modeled as a pure planner location problem.  Area restriction concept has been incorporated by inducting a convex polygon in the constraints set. A linear programming iterative algorithm for k- obnoxious facility locations has been developed. An upper bound has been incorporated in the algorithm to get the  optimal solution. Also the concept of upper bound has reduced  the number of linear programming problems to solved in the algorithm. Rectilinear distance norm has been considered as the distance measure as it is more appropriate to the various realistic situations. 


Obnoxious facility location; iterative algorith; rectilinear distance norm

Full Text:



G. Appa, I. Giannikos, Locating two obnoxious facilities in the plane under the rectilinear metric, LSE OR Working paper LSE 04-69, London School of Econimics, 2004.

C.K. Chen, R.S. Garfinkel, The generalized diameter of a graph, Networks 12 (1982) 335-340.

B. Dasarathy, and L.. White, A Maximin Location Problem, Operations Research, . 28 (1980) 1385-1401.

Z. Drezner, and G.O. Wesolowsky, A Maximin Location Problem with Maximum Distance Constraints, AIIE Transaction. 11 (1980) 249-252.

Z. Drezner, and G.O. Wesolowsky, Location of an Obnoxious Facility with Rectangular Distance, Journal of Regional Science. 23 (1983) 241-248.

Erhan, Erkut and Susan, Neuman, Analytical Models for Locating Undesirable Facilities, European Journal of Operational Research. 40 (1989) 275-291.

E. Erkut, The discrete p-dispersion problem, European J. Operations Research, 46 (1990) 48-60.

I. Giannikos, Optimal Location of single and multiple obnoxious facilities: algorithms for the MAXIMIN criterion under different norms, PhD Thesis. London School of Economics and Political Sciences, 1993.

A.J. Goldman, and P.M. Dearing, Concepts of optimal locations for partially noxious facilities, Bulletin of the Operational Research Society of America, 23/1, (1975), B85

P. Hansen, D. Peeters and J.F. Thisse, On the location of an obnoxious facility, Sistemi Unbeni 3, 299-317.

M.J. Kuby, Programming models for facility dispersion: the p dispersion and maximum dispersion problems, Geographical Anal. 19 (1987) 315-329.

E. Melachrinoudis, and T.P. Cullinane, Locating an Undesirable facility within a Geographical Region Using the Maximin Criterion, Journal of Regional Science. 25 (1985) 115-127.

E. Melachrindis An Efficient Computational Procedure for the Rectilinear Maximin Location Problem, Transportation Science. 22 (1988) 217-223.

A. Mehrez, Z. Sinuany-Stern, A. Stulman. An Enhancement of the Drezner- Wesolowsky Algorithm for Single Facility Location with Maximin of Rectangular Distance, Journal of Operations Research Society, 37 (1986) 971-977.

N. Shamos, Computational Geometry, PhD Dissertation, Department of Computer Science, Yale University . 1977.

A. Tamir, Obnoxious facility location on graphs, SIAM j. Discrete Math. 4 (1991) 550-567.

A Tamir. Locating Two Obnoxious Facilities using the Weighted Maximin Criterion., Operations Research Letter 34 (2006) 97-105.



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Creative Commons License

This site is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.