A continuous districting model focusing on intra‐ and inter‐zonal squared distances and its Voronoi‐based heuristic. (26th October 2020)

• Record Type: Journal Article
• Authors: Morimoto, Keitaro; Tanaka, Ken‐ichi
• Is Part Of: International transactions in operational research. Volume 28:Number 3(2021)
• Page Start: 1109
• Page End: 1134
• Publication Date: 2020-10-26
• Subjects: continuous districting problem -- intra‐ and inter‐zonal trips -- squared distance -- Voronoi tessellation; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12893
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: 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.