A Partitioning Problem with Applications in Regional Design

Abstract

Many problems in two-dimensional location analysis can be formulated as one of optimally dividing a given region into n subregions with specified areas. Examples are problems involving districting, facility design, warehouse layout, and urban planning. This paper contains a study of such a partitioning problem. Theoretical results are presented for a problem of optimally partitioning a given set of points in k-dimensional Euclidean space into n subsets, where each subset has a specified Lebesgue measure. The existence of an optimal solution is established, and necessary and sufficient optimality conditions are proved. Models are then formulated in terms of this partitioning problem for specific districting and warehouse-layout problems.