Name
Abstract | ||
|---|---|---|
This paper considers two covering location problems on a network where the demand is distributed along the edges. The first is the classical maximal covering location problem. The second problem is the obnoxious version where the coverage should be minimized subject to some distance constraints between the facilities. It is first shown that the finite dominating set for covering problems with nodal demand does not carry over to the case of edge based demands. Then, a solution approach for the single facility problem is presented. Afterwards, the multi-facility problem is discussed and several discretization results for tree networks are presented for the case that the demand is constant on each edge; unfortunately, these results do not carry over to general networks as a counter example shows. To tackle practical problems, the conditional version of the problem is considered and a greedy heuristic is introduced. Afterwards, numerical tests are presented to underline the practicality of the algorithms proposed and to understand the conditions under which accurate modeling of edge-based demand and a continuous edge-based location space are particularly important. HighlightsFirst study of covering location problems on networks with continuously distributed demand along edges.Discretization result for the 1-facility (obnoxious) MCLP where facilities can be located anywhere on the network.Finite dominating sets for the multi-facility (obnoxious) MCLP on trees with constant demand.Finite dominating sets do not carry over to general networks.Efficient solution approach for the conditional problem on general networks with arbitrary demand functions.Sketch of a heuristic solution framework.Numerical comparison with classical demand discretization approaches. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.cor.2015.04.005 | Computers and Operations Research |
Keywords | Field | DocType |
heuristics,networks,covering problems | Numerical tests,Discretization,Dominating set,Mathematical optimization,Heuristic,Greedy algorithm,Heuristics,Counterexample,Mathematics,Covering problems | Journal |
Volume | Issue | ISSN |
74 | C | 0305-0548 |
Citations | PageRank | References |
1 | 0.36 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| O. Berman | 1 | 1604 | 231.36 |
| jorg kalcsics | 2 | 1 | 0.70 |
| Dmitry Krass | 3 | 483 | 82.08 |