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 an underlying road network is assumed 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 São Paulo, Brazil, whose results are presented and discussed in the paper.