Premium
A continuous districting model focusing on intra‐ and inter‐zonal squared distances and its Voronoi‐based heuristic
Author(s) -
Morimoto Keitaro,
Tanaka Kenichi
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12893
Subject(s) - polygon (computer graphics) , voronoi diagram , regular polygon , heuristic , boundary (topology) , convex polygon , position (finance) , mathematics , euclidean geometry , mathematical optimization , geometry , computer science , mathematical analysis , telecommunications , finance , frame (networking) , economics
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.