Planar maximal covering location problem under block norm distance measure

This paper introduces a new model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating g facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization, in this paper, is that the distance measures assigned to facilities are block norms of different types and different proximity measures. First, the PMCLP under different block norms is modelled as a maximum clique partition problem on an equivalent multi-interval graph. Then, the equivalent graph problem is modelled as an unconstrained binary quadratic problem (UQP). Both the maximum clique partition problem and the UQP are NP-hard problems; therefore, we solve the UQP format through a genetic algorithm heuristic. Computational examples are given.