On covering location problems on networks with edge demand

Oded Berman, Jörg Kalcsics*, Dmitry Krass

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.

Original languageEnglish
Pages (from-to)214-227
Number of pages14
JournalComputers and Operations Research
Early online date18 Apr 2015
Publication statusPublished - Oct 2016

Keywords / Materials (for Non-textual outputs)

  • Continuous demand
  • Covering problems
  • Finite dominating sets
  • Heuristics
  • Networks
  • Obnoxious


Dive into the research topics of 'On covering location problems on networks with edge demand'. Together they form a unique fingerprint.

Cite this