A Voronoi Heuristic Approach to Dividing Networks into Equal-Sized Sub-Networks
Takehiro Furuta, Atsuo Suzuki, Atsuyuki Okabe · 2008
We analyze the division of a connected network into p connected sub-networks with equal sizes in terms of network edge length. To find divisions, we minimize the sum of the absolute values of the difference between the average total edge length of p sub-networks from the total edge length of the network and the total edge length of each sub-network. Here, we propose a heuristic approach to the problem using a network Voronoi diagram and a linear programming formulation, and report computational experiments for actual road networks in Japan.