Median and covering location problems with interconnected facilities

This paper introduces two classes of location problems with interconnected facilities. These problems differ from classical location problems in the sense that the facilities to be located must be interconnected, i.e. located within a prescribed distance of a central office or of each other. Such problems arise, for example, in contexts where forest fire-fighters must be able to reach each other by short-range radios, or when locating interconnected sensors. Median and covering problems are modeled through several formulations. A metaheuristic consisting of a hybrid construction phase followed by an iterative search process developed for the median and covering problems. Extensive tests are performed in order to assess the performance of the proposed methodology.