Aggregation of demand points for the planar covering location model [electronic resource] /
ABSTRACT: 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, for example, fire stations. The problem is NP-Hard in the plane. Therefore a common practice is to aggregate the demand points in order to reduce the computational burden. Other than the computational burden, confidentiality concerns and the ease of predicting the demand with aggregation are incentives for doing aggregation. Aggregation makes the size of the problem more manageable, but at the same time it introduces error due to loss of information. The subject of this study is identifying and controlling the magnitude of the error introduced by aggregation. We conclude that it is important how one measures infeasibility since it makes a big difference in the way one aggregates. We suggest a number of aggregation schemes and we conduct experiments to compare their worst-case performances. We also discuss how to determine an appropriate aggregation level in the lack of demand point information. Lastly, we investigate the average-case performance of one of the aggregation schemes. We conclude that, even though in the worst case the scheme's performance can be arbitrarily bad, on the average, it is acceptable.
School:University of Florida
School Location:USA - Florida
Source Type:Master's Thesis
Keywords:aggregation covering location problem
Date of Publication: