The expropriation location problem

Abstract

In this paper, we consider the location of a new obnoxious facility that serves only a certain proportion of the demand. Each demand point can be bought by the developer at a given price. An expropriation budget is given. Demand points closest to the facility are expropriated within the given budget. The objective is to maximize the distance to the closest point not expropriated. The problem is formulated and polynomial algorithms are proposed for its solution both on the plane and on a network.

Keywords:

• obnoxious locations
• covering problems
• partial demand
• budget constraints
• expropriation

Acknowledgements

This research was supported, in part, by the Natural Sciences and Engineering Research Council of Canada. Part of this research was accomplished while the second author was visiting the Graduate School of Management, University of California, Irvine.