Abstract | ||
---|---|---|
AbstractIn 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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 634, 334-349 2014 |
Year | DOI | Venue |
---|---|---|
2014 | 10.1002/net.21549 | Periodicals |
Keywords | Field | DocType |
covering problems,networks,cooperative,finite dominating sets,integer programming formulations | Mathematical optimization,Combinatorics,Exact algorithm,Algorithm,Heuristics,Signal strength,Polynomial algorithm,Piecewise linear function,Mathematics,Covering problems | Journal |
Volume | Issue | ISSN |
63 | 4 | 0028-3045 |
Citations | PageRank | References |
2 | 0.40 | 4 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Igor Averbakh | 1 | 6 | 1.49 |
O. Berman | 2 | 1604 | 231.36 |
Dmitry Krass | 3 | 483 | 82.08 |
JöRg Kalcsics | 4 | 170 | 23.42 |
Stefan Nickel | 5 | 427 | 41.70 |