1. ¹United Arab Emirate University, Al-Ain, UAE
2. ²McMaster University, Hamilton, Ontario, Canada

Correspondence: GO Wesolowsky, Faculty of Business, McMaster University, Hamilton, Ontario, Canada, L8S 4M4. E-mail: wesolows@mcmail.cis.mcmaster.ca

Received April 2005; Accepted December 2005; Published online 29 March 2006.

Abstract

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.