Forma, Vol. 23 (No. 2), pp. 73-79, 2008
Original Paper

A Voronoi Heuristic Approach to Dividing Networks into Equal-Sized Sub-Networks

Takehiro Furuta1*, Atsuo Suzuki2 and Atsuyuki Okabe3

1Faculty of Engineering, Tokyo University of Science, 1-14-6 Kudankita, Chiyoda-ku, Tokyo 102-0073, Japan
2Faculty of Mathematical Sciences and Information Engineering, Nanzan University
3Faculty of Engineering, The University of Tokyo
*E-mail address:

(Received May 31, 2008; Accepted October 27, 2008)

Keywords: Network Division Problem, Network Voronoi Diagram, Linear Programming

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

[Full text] (PDF 288 KB)