Group for Research in Decision Analysis


Median and covering location problems with interconnected facilities

, , and

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. Median and covering problems are modeled through several formulations. A greedy randomized adaptive search procedure (GRASP) is then developed. Extensive tests are performed on instances of the median problem in order to compare two of the models and to assess the performance of the GRASP.

, 20 pages