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

Zvi Drezner, Pawel Kalczynski and Said Salhi

Omega, 2019, vol. 87, issue C, 105-116

Abstract: Consider a situation where a given number of facilities must be located in a convex polygon with the objective of maximizing the minimum distance between facilities and a given set of communities subject to the facilities being farther than a certain distance from one another. This continuous multiple obnoxious facility location problem is very difficult to solve by commercial nonlinear optimizers. We propose a mathematical formulation of two variants of the problem and a heuristic approach based on Voronoi diagrams and a binary linear program. We compare our heuristic with popular state of the art solvers which utilize the multi-start approach: interior point, sparse nonlinear optimizer (SNOPT), GA, IPOPT, and NOMAD running in Matlab. Each problem instance is solved using 100 randomly generated starting solutions, and the best solution is selected. We found that our results are much better and were obtained in a fraction of the time required by other methods. The multiple obnoxious location problem is a perfect example where all-purpose nonlinear non-convex solvers perform poorly and are significantly outperformed by custom designed heuristics.

Keywords: Location; Obnoxious facilities; Continuous location; Voronoi diagrams; Matlab; Heuristic; Binary linear program. (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048318301051
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:87:y:2019:i:c:p:105-116

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2018.08.013

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().