Planar maximal covering location problem under different block norms

Abstract

<p>This study introduces a new model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating p facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization we introduce is that distance measures assigned to facilities are block norms of different types and different proximity measures. This problem is handled in three phases. First, a simple model based on the geometrical properties of the block norms' unit ball contours is formulated as a mixed integer program (MIP). The MIP formulation is more general than previous PMCLP's and can handle facilities with different coverage measures under block norm distance and different setup cost, and capacity. Second, an exact solution approach is presented based on: (1) An exact algorithm that is capable of handling a single facility efficiently. (2) An algorithm for an equivalent graph problem--the maximum clique problem (MCP). Finally, the PMCLP under different block norms is formulated as an equivalent graph problem. This graph problem is then modeled as an unconstrained binary quadratic problem (UQP) and solved by a genetic algorithm. Computational examples are provided for the MIP, the exact algorithm, and the genetic algorithm approaches.</p>