Planar maximal covering location problem under block norm distance measure

Planar maximal covering location problem under block norm distance measure

0.00 Avg rating0 Votes
Article ID: iaor20082191
Country: United Kingdom
Volume: 58
Issue: 6
Start Page Number: 740
End Page Number: 750
Publication Date: Jun 2007
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: graphs, heuristics: genetic algorithms, programming: quadratic
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.

Reviews

Required fields are marked *. Your email address will not be published.