A continuous districting model focusing on intra- and inter-zonal squared distances and its Voronoi-based heuristic
A continuous districting model focusing on intra- and inter-zonal squared distances and its Voronoi-based heuristic
复制标题
DOI：
10.1111/itor.12893
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
K. Morimoto;Ken-ichi Tanaka
中科院分区：
文献类型：
--
作者：
K. Morimoto;Ken-ichi Tanaka
我们考虑了将一个给定的凸多边形分成称为区域的凸多边形的问题，每个区域都有一个指定的土地面积。确定每个区域的位置和形状，以便有效地执行所产生的区域的区域内和区域间行程。为了评价结果区域的紧致性，我们推导了均匀分布在每个区域中的两个点之间的平均平方距离，以及均匀分布在两个区域中的两个点之间的平均平方距离。以这些度量的加权和作为目标函数，提出了一种基于Voronoi的启发式算法，迭代地更新凸多边形内生成点的位置。该方法被用来划分几个规则的多边形，结果表明：(I)当区域内行程优先时，区域变得圆整；(Ii)当区域间行程优先时，区域变得更长，边界线变长。
We consider the problem of dividing a given convex polygon intopconvex 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 ofpgenerator 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.