A multiplicatively-weighted Voronoi diagram approach to logistics districting

The objective of districting in logistics distribution problems is to find a near optimal partition of the served region into delivery zones or districts. This kind of problem has been treated in the literature with geometric-shaped districts and continuous approximations. Usually it is assumed an underlying road network equivalent to a Euclidean, rectangular, or ring-radial metric. In most real problems, however, the road network is a coarse combination of metrics. In this context, it is unclear what is the optimal shape of the districts and how one should orientate them. A possibility is to treat the problem with a Voronoi diagram approach. Departing from a previously determined ring-radial districting pattern and relaxing the initial district boundaries, we apply the multiplicatively-weighted Voronoi diagram formulation in order to smooth district contours. The computing process is iterated until the convergence is attained. The model has been applied to solve a parcel delivery problem in the city of Sao Paulo, Brazil, whose results are presented and discussed in the paper. (c) 2004 Elsevier Ltd. All rights reserved.