Cooperative covering problems on networks

Cooperative covering problems on networks

0.00 Avg rating0 Votes
Article ID: iaor201522245
Volume: 63
Issue: 4
Start Page Number: 334
End Page Number: 349
Publication Date: Jul 2014
Journal: Networks
Authors: , , , ,
Keywords: combinatorial optimization, heuristics
Abstract:

In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain ‘signal’ whose strength decays over distance according to some ‘signal strength function.’ A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments.

Reviews

Required fields are marked *. Your email address will not be published.