Heuristics for k-domination models of facility location problems in street networks. (September 2021)

• Record Type: Journal Article
• Authors: Corcoran, Padraig; Gagarin, Andrei
• Is Part Of: Computers & operations research. Volume 133(2021)
• Publication Date: 2021-09
• Subjects: k-domination -- Heuristic methods -- Facility location; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105368
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: New heuristic methods proposed for finding small-size k-dominating sets in graphs. Empirical evaluation performed with respect to existing methods, using instances of graphs corresponding to street networks. The k-domination problem with respect to this class of graphs models the facility location problem. Experiments with large-scale real world road networks. New methods outperform the existing methods, and the performance gain is more significant for larger values of k . Abstract: We present new greedy and beam search heuristic methods to find small-size k -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 ( 1 -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 .