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/j.omega.2018.08.013) (Access to this publication is currently restricted. You may be able to access a copy if URLs are provided)

PDF - Author's Accepted Manuscript
Restricted to Repository staff only until 23 August 2020.
Contact us about this Publication Download (524kB)
[img]
Official URL
https://doi.org/10.1016/j.omega.2018.08.013

Abstract

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/j.omega.2018.08.013
Uncontrolled keywords: Location; Obnoxious Facilities; Continuous Location; Voronoi Diagrams; Matlab; 24 Heuristic; Binary Linear Program
Divisions: Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 04 Oct 2018 13:43 UTC
Last Modified: 15 Jul 2019 07:50 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/69370 (The current URI for this page, for reference purposes)
Salhi, Said: https://orcid.org/0000-0002-3384-5240
  • Depositors only (login required):

Downloads

Downloads per month over past year