Skip to main content

The planar multiple obnoxious facilities location problem: A Voronoi based heuristic

Drezner, Zvi, Kalczynski, Pawel, Salhi, Said (2019) The planar multiple obnoxious facilities location problem: A Voronoi based heuristic. Omega, 87 . pp. 105-116. ISSN 0305-0483. (doi:10.1016/ (KAR id:69370)

PDF Author's Accepted Manuscript
Language: English
Download (524kB) Preview
[thumbnail of obrevomeg1.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


Consider the situation where a given number of facilities are to be located in a convex polygon with the objective of maximizing the minimum distance between facilities and a given set of communities with the important additional condition that the facilities have to be farther than a certain distance from one another. This continuous multiple obnoxious facility location problem, which has two variants, is very complex to solve using commercial nonlinear optimizers. We propose a mathematical formulation and a heuristic approach based on Voronoi diagrams and an optimally solved binary linear program. As there are no nonlinear optimization solvers that guarantee optimality, we compare our results with a popular multi-start approach using interior point, genetic algorithm (GA), and sparse non-linear optimizer (SNOPT) solvers in Matlab. These are state of the art solvers for dealing with constrained non linear problems. Each instance is solved using 100 randomly generated starting solutions and the overall best is then selected. It was found that the proposed heuristic results are much better and were obtained in a fraction of the computer time required by the other methods.The multiple obnoxious location problem is a perfect example where all-purpose non-linear non-convex solvers perform poorly and hence the best way forward is to design and analyze heuristics that have the power and the exibility to deal with such a high level of complexity.

Item Type: Article
DOI/Identification number: 10.1016/
Uncontrolled keywords: Location; Obnoxious Facilities; Continuous Location; Voronoi Diagrams; Matlab; 24 Heuristic; Binary Linear Program
Divisions: Divisions > Kent Business School - Division > Centre for Logistics and Heuristic Optimisation (do not use)
Depositing User: Said Salhi
Date Deposited: 04 Oct 2018 13:43 UTC
Last Modified: 16 Feb 2021 13:58 UTC
Resource URI: (The current URI for this page, for reference purposes)
Salhi, Said:
  • Depositors only (login required):


Downloads per month over past year