A continuous districting model focusing on intra- and inter-zonal squared distances and its Voronoi-based heuristic

We consider the problem of dividing a given convex polygon into p convex polygons called zones, each of which receives a designated land area. The position and shape of each zone is determined so that intra- and inter-zonal trips for the resulting zones are conducted efficiently. To evaluate the compactness of the resulting zones, we derive the average squared distance between two points uniformly distributed in each zone, as well as the average squared distance between two points uniformly distributed in two zones. The weighted sum of these measures is used as the objective function, and a Voronoi-based heuristic algorithm is proposed that iteratively updates the positions of p generator points placed inside a convex polygon. The method is used to divide several regular polygons, and the results show that zones become (i) rounded when intra-zonal trips are prioritized and (ii) elongated with longer boundary lines when inter-zonal trips are prioritized.