Solving continuous location-districting problems with Voronoi diagrams

Facility location problems are frequent in OR literature. In districting problems, on the other hand, the aim is to partition a territory into smaller units, called districts or zones, while an objective function is optimized and some constraints are satisfied, such as balance, contiguity, and compactness. Although many location and districting problems have been treated by assuming the region previously partitioned into a large number of elemental areas and further aggregating these units into districts with the aid of a mathematical programming model, continuous approximation, on the other hand, is based on the spatial density of demand, rather than on precise information on every elementary unit. Voronoi diagrams can be successfully used in association with continuous approximation models to solve location-districting problems, specially transportation and logistics applications. We discuss in the paper the context in which approximation algorithms can be used to solve this kind of problem. (C) 2007 Elsevier Ltd. All rights reserved.