Premium
Exploiting self‐canceling demand point aggregation error for some planar rectilinear median location problems
Author(s) -
Francis R.L.,
Lowe T.J.,
Rayco M.B.,
Tamir A.
Publication year - 2003
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.10079
Subject(s) - aggregate (composite) , centroid , construct (python library) , focus (optics) , point (geometry) , function (biology) , mathematical optimization , computer science , mathematics , scale (ratio) , line (geometry) , algorithm , artificial intelligence , materials science , physics , geometry , evolutionary biology , optics , composite material , biology , programming language , quantum mechanics
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. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614–637, 2003.