New heuristics for the Conditional Covering Problem

The Conditional Covering Problem is to locate a minimum number of facility sites such that they cover all demand points as well as the selected facility sites to be covered by each other. This problem is an important variation of the traditional set covering problem in which only the demand points need to be covered. The paper presents two new heuristics and reports on the present computational experience which shows an improvement over previously reported results.