Heuristics for k-domination models of facility location problems in street networks
arXiv:2111.07885 · doi:10.1016/j.cor.2021.105368
Abstract
We present new greedy and beam search heuristic methods to find small-size -dominating sets in graphs. The methods are inspired by a new problem formulation which explicitly highlights a certain structure of the problem. An empirical evaluation of the new methods is done with respect to two existing methods, using instances of graphs corresponding to street networks. The k-domination problem with respect to this class of graphs can be used to model real-world facility location problem scenarios. For the classic minimum dominating set (-domination) problem, all except one methods perform similarly, which is due to their equivalence in this particular case. However, for the k-domination problem with k>1, the new methods outperform the benchmark methods, and the performance gain is more significant for larger values of k.