Demand Point Aggregation for Planar Covering Location Models

The covering location problem seeks the minimum number of facilities such that each demand point is within some given radius of its nearest facility. Such a model finds application mostly in locating emergency types of facilities. Since the problem is NP-hard in the plane, a common practice is to ag...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2005-04, Vol.136 (1), p.175-192
Main Authors: Emir-Farinas, H., Francis, R. L.
Format: Article
Language:English
Subjects:
Customers
Facilities planning
Location analysis
Operations research
Spatial data
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The covering location problem seeks the minimum number of facilities such that each demand point is within some given radius of its nearest facility. Such a model finds application mostly in locating emergency types of facilities. Since the problem is NP-hard in the plane, a common practice is to aggregate the demand points in order to reduce the computational burden. Aggregation makes the size of the problem more manageable but also introduces error. Identifying and controlling the magnitude of the error is the subject of this study. We suggest several aggregation methods with a priori error bounds, and conduct experiments to compare their performance. We find that the manner by which infeasibility is measured greatly affects the best choice of an aggregation method. [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-005-2044-2