Dual-based heuristics for a hierarchical covering location problem
A 2-level hierarchical extension of the maximal covering location problem is considered and an effective method for its solution developed. A combined Lagrangeansurrogate (LS) relaxation is defined which reduces to a 01 knapsack problem. Tests were carried out using a subgradient-based heuristic incorporating the LS relaxation, with the resulting knapsack problems being solved both with and without the integrality constraints relaxed. Results were obtained for test problems available in the literature ranging from 55-node to 700-node networks. These were compared, where possible, with exact results obtained using CPLEX. It was found that computing times were reasonable. Covering location models belong to a category of models that provide coverage to demand areas. In these models, often used in applications related to the location of emergency facilities, a demand area is considered covered if it is within a predefined service distance from at least one of the existing facilities. Hierarchical models may be important in some situations, for example in the location of schools and health care facilities. Moore and ReVelle (Manage. Sci. 28 (1982) 775) proposed a 2-level hierarchical extension of the maximal covering location problem and applied it to the health services of Honduras. In the present paper several relaxations are defined for this hierarchical problem, which is called the hierarchical covering location problem. A subgradient-based heuristic is developed using the proposed relaxations; this heuristic was tested on problems available in the literature. It was found that computing times are relatively low even for the largest test problems.
heuristics relaxations hierarchical location covering models