Exploiting Self-Canceling Demand Point Aggregation Error for Some Planar Rectilinear Median Location Problems

摘要

When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1-median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row-column aggregations, and make use of aggregation results for 1-median problems on the line to do aggregation for 1-median problems in the plane. The aggregations developed for the 1-median problem are then used to construct approximate n-median problems. We test the theory computationally on n-median problems (n ≥ 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale.