The gradual minimum covering location problem

Abstract

The minimum covering location problem with distance constraints deals with locating a set of undesirable facilities on a geographical map, where there is a given minimum distance between any pair of located facilities. A covering radius is defined within which the population node is fully covered and beyond that it is not covered at all. This setting may not be applicable in practice because usually the coverage gradually decreases with an increase in the distance. Additionally, undesirable facilities may have a cooperative adverse impact on the nearby population. We introduce the gradual coverage to the problem that extends the classic definition of the coverage and is more suitable for modelling real-world applications. We name the problem the gradual minimum covering location problem with distance constraints (GMCLPDC). We propose a mixed-integer program for GMCLPDC where cooperation of facilities is also considered. We propose a threshold accepting heuristic as the solution method. We conduct computational experiments on instances with up to 10,000 nodes. The outcomes indicate that the heuristic delivers quality solutions and outperforms the solver Gurobi. We also show an application of our model in Sydney metropolitan area.

Keywords:

• Minimum covering
• gradual coverage
• cooperative coverage
• undesirable facility
• location problem

Acknowledgements

We thank the editors and anonymous referees for their valuable and constructive comments on an earlier version of the article. Mostafa Khatami is the recipient of the UTS International Research Scholarship (IRS) and the UTS President’s Scholarship (UTSP). Amir Salehipour is the recipient of an Australian Research Council Discovery Early Career Researcher Award (project number DE170100234) funded by the Australian Government.

Disclosure statement

No potential conflict of interest was reported by the authors.