On worst-case aggregation analysis for network location problems

Network location problems occur when new facilities must be located on a network, and the network distances between new and existing facilities are important. In urban, regional, or geographic contexts, there may be hundreds of thousands (or more) of existing facilities, in which case it is common to aggregate existing facilities, e.g. represent all the existing facility locations in a zip code area by a centroid. This aggregation makes the size of the problem more manageable for data collection and data processing purposes, as well as for purposes of analysis; at the same time, it introduces errors, and results in an approximating location problem being solved. There seems to be relatively little theory for doing aggregation, or evaluating the results of aggregation; most approaches are based on experimentation or computational studies. We propose a theory that has the potential to improve the means available for doing aggregation.This research was supported in part by the National Science Foundation, Grant No. DDM-9023392.