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

Takehiro Furuta¹*, Atsuo Suzuki² and Atsuyuki Okabe³

¹Faculty of Engineering, Tokyo University of Science, 1-14-6 Kudankita, Chiyoda-ku, Tokyo 102-0073, Japan
²Faculty of Mathematical Sciences and Information Engineering, Nanzan University
³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.