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

*Original Paper*

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

Takehiro Furuta^{1}*, Atsuo Suzuki^{2} and Atsuyuki Okabe^{3}

^{1}Faculty of Engineering, Tokyo University of Science, 1-14-6 Kudankita, Chiyoda-ku, Tokyo 102-0073, Japan

^{2}Faculty of Mathematical Sciences and Information Engineering, Nanzan University

^{3}Faculty of Engineering, The University of Tokyo

*E-mail address: takef@fw.ipsj.or.jp

(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)