ネットワークの等長分割問題
M2008MM028 武田好史
指導教員：腰塚武志

1

はじめに現代社会には様々なネットワークが存在しており, 道路ネットワークに着目してみると特定の店舗やサービスの需要を求める際には, 平面よりもむしろ道路ネットワークに沿って需要が発生している場合がある. それにも関わらず, これまで平面の均等分割については研究されてきたが, ネットワークを均等な長さに分割する方法は確立されていない.

2ネットワークの等長分割問題

ネットワークの等長分割問題とは, 独立した部分が存在しない連結なネットワーク N と分割数 p (正整数) が与えられ, F (N ) を N の総枝長としたとき, F (Ni ) = F (N )/p,i = 1, . . . , p となるような p 個の連結な部分ネットワーク
Ni を見つける問題である.
ネットワークをいくつかに分割すると, ネットワークの枝上に二つの異なる部分ネットワークを分断する境界となる点 (境界点) が新たにでき, 各部分ネットワークは境界点を除いて, Ni ∩ Nj = ∅, i ̸= j, i, j = 1, ..., p を満たすとする. つまり境界点以外の点は重複がないよういずれかの部分ネットワークに属する.
ネットワークの等長分割問題は古田ら [1] によって取り組まれているが, 分割数の増加とともに等長分割できない割合が増加する結果となったとされている.
そこで本研究では重み付きネットワークボロノイ図 [2]を用いることにより, 分割数が増加しても安定して等長分割できるような新たな解法を提案する.

3

V (gi , wi ) = {v | v ∈ V, d(gi , v) + wi ≤ d(gj , v) + wj ,j = 1, . . . , p, j ̸= i}, (i = 1, . . . , p).

重み付きネットワークボロノイ図

重み付きネットワークボロノイ図とは, ノード集合 V ={v1 , . . . , vm } と枝集合 E = {e1 , . . . , en } で構成されるネットワーク N (V, E) と母点集合 G = {g1 , . . . , gp } ⊂ Vと重み集合 W = {w1 , . . . , wp } が与えられたとき, 母点集合と重み集合によりネットワークを部分ネットワーク
N1 , ..., Np に分割したものである. このとき, ネットワー
ク上のノードは重み付き最短経路距離において最も近い(1)2 点 vs , vt ∈ V 間に枝 e ∈ E が存在するとき e = (vs , vt )と表すと, vs , vt がそれぞれ違う部分ネットワークのノード集合 V (gi ), V (gj ), (vs ∈ V (gi ), vt ∈ V (gj ), i ̸= j) に属している場合, 枝 e 上に境界点 b を d(gi , b) + wi = d(gj , b) +wj を満たすよう作成し, 境界点集合 B = {b1 , . . . , bq } とする.
枝集合 E を次のような性質をもつ部分ネットワークの枝集合 E(gi , wi ) ⊂ E, (i = 1, . . . , p) に分割する.
E(gi , wi ) = {e | e ∈ E, e = (vs , vt ), vs ∈ V (gi ) ⊂ V,vt ∈ V ∪ B}, (i = 1, . . . , p).

(2)

ノード集合 V (gi , wi ) と枝集合 E(gi , wi ) によって部分ネットワーク Ni が構成される (i = 1, ..., p).
重み付きネットワークボロノイ図を用いることで, 隣接する部分ネットワークに与えられた重みの差により境界点の位置を動かすことで部分ネットワークの総枝長を変化させることができる.
またネットワークボロノイ図とは「重み集合 W ={0, ..., 0} で重み付きネットワークボロノイ図を用いて分割することである」とも言える.

ネットワークボロノイ図と重み付きネット
4ワークボロノイ図

ネットワークを複数個に分割する方法として, ネットワークボロノイ図という手法があり, 本研究ではこのネットワークボロノイ図の拡張である重み付きネットワークボロノイ図を用いてネットワークの等長分割を行う.
そこでまずネットワークボロノイ図と, 重み付きネットワークボロノイ図について説明するのだが, ネットワークボロノイ図は重み付きネットワークボロノイ図によって説明可能であるため重み付きネットワークボロノイ図の作成手順についてのみ説明する.

3.1

母点の部分ネットワークに属する.
母点集合 G, 重み集合 W の重み付きネットワークボロ
ノイ図は次のような性質をもつノード集合 V (gi , wi ) ⊂V, (i = 1, . . . , p) に分割される.

等長分割の解法

ネットワークの等長分割を行うにあたり, 母点集合 G,重み集合 W , 境界点集合 B で分割したときの目的関数として以下のような 2 次目的式 (3) を設定し, 2 次目的式 (3)が最小となるような分割の母点集合 G∗ , 重み集合 W ∗ , 境界点集合 B ∗ を求める問題として考える.

f (G, W, B) =}2p {∑F (N ).
F (Ni ) −pi=1(3)

図 1 のフローチャートにそった等長分割の解法において, U ∗ = f (G∗ , W ∗ , B ∗ ) とし, U ∗ < 10−5 (ϵ は微小数,10−5 など) となったとき等長分割ができたことにする. また計算機実験の際にかかる時間の都合上, 一定回数の反復を行っても等長分割できない場合は打ち切ることにした.
以降, 「母点集合 G = {g1 , . . . , gp }, 重み集合 W ={w1 , . . . , wp } を用いて, 重み付きネットワークボロノ
イ図によりネットワーク N (V, E) を部分ネットワーク
N1 , . . . , Np に分割する. 」を「G, W で分割する. 」と省略して表記する.

Start4.4

no4.5

記号の定義 境界点 bj を持つ枝 ek = (vs , vt ) を e1k =(vs , bj ) と e2k = (vt , bj ) に分けたとき, 新たに以下の記号を定義する.

End

Mij : 境界点 bj , j = 1, . . . , q (bj は枝 e = (vs , vt ) ∈E 上に存在する), を移動させたとき, 部分ネッ
トワーク Ni , i = 1, . . . , p の総枝長 F (Ni ) の増減を場合分けするための係数行列.
図 2 のように bj を e = (vs , vt ) 上において正方向 (vt 方向) へ xj 移動させたとき, 部分ネット
ワーク Ni の総枝長 F (Ni ) が境界点 bj の移動によって

yes

4.1

4.3

4.2

4.6

noyes

4.7

図 1 等長分割解法のフローチャート

4.1

前処理 : 母点集合の作成, および初期化• 増加する場合 (vs ∈ Ni ), Mij = 1.
• 減少する場合 (vt ∈ Ni ), Mij = −1.

ネットワーク N (V, E) と分割数 p が与えられたとし, まずネットワークボロノイ図を作成するために母点集合 G を作成する. ノード集合 V からランダムに p 個選び, それを母点集合 G = {g1 , . . . , gp } とする. G と W = {0, . . . , 0}で分割し境界点集合 B を求め, 現時点での局所最適解とする.

4.2

l1j : 枝 e1k = (vs , bj ) の長さ, j = 1, . . . , q.
l2j : 枝 e2k = (vt , bj ) の長さ, j = 1, . . . , q.
xj : 境界点 bj , j = 1, . . . , q (bj は枝 e = (vs , vt ) ∈ E上に存在する) を vt 方向へ移動させる移動量,
j = 1, . . . , q.

第 1 段階 : 母点の移動による発見的解法

f (G, W, B) が小さくなるようネットワークボロノイ図を用いた母点となるノードを変更していく発見的解法によって母点集合 G を求める.
V (gi ), (i = 1, . . . , p) の要素数が多い順に変更順序を決定し, 各 i に対して母点 gi を, 「他の母点として選ばれておらず, gi と v をつなぐ枝 ek = (gi , v) ∈ E が存在する
ノード v ∈ V 」に変更したときの 2 次目的式 (3) の値が最小となった v に対して gi = v とする.
2 次目的式 (3) の値が改善しなくなるまで母点 gi を移動させていく. 改善解が存在しなくなったら変更順序において次の i に対して同じ作業を行い, 全ての i = 1, . . . , pに対して母点の変更ができなくなったら終了する.
母点と枝でつながっているノードのみに探索範囲を限定することで, 短い計算時間で改善解を求めることができる.
4.3• 変化がない場合 (vs , vt ̸∈ Ni ), Mij = 0.

第 2 段階 : 境界点の移動による等長分割

境界点をその境界点が存在する枝上において動かすことで等長分割を行う. 境界点 bj ∈ B を移動させるとき,移動前の位置を 0 とし, bj が存在する枝 ek = (vs , vt ) ∈E, vs , vt ∈ V の上を vt 方向への移動量を正, vs 方向への移動量を負として考えたとき, bj の移動量を xj ∈ ℜとする. この問題を解くため以下の記号を定義し, ILOG
CPLEX 10.1(ILOG) を用いて解いた.

決定変数

xj ,j = 1, . . . , q.

目的関数

min
p 
∑
i=1



F (Ni ) +q∑

Mij xj −j=1

2
F (N ) p

l1j-l1jvt

bj
xj−l1j ≤ xj ≤ l2j ,j = 1, . . . , q.

(5)

xj ∈ ℜ ,j = 1, . . . , q.

(6)

最後に境界点 bj , (j = 1, . . . , q) を xj だけ移動させた境界点集合 B を求め, U = f (G, W, B) とする.

4.4

条件分岐 1 : 境界点の移動による等長分割の必要条件

境界点の移動による等長分割は以下の条件を満たさない場合は絶対に等長分割できない. そこで以下の条件を満たさない場合は重み付きネットワークボロノイ図を用いた手順 4.5 を経ることで等長分割に近づける.
全ての i = 1, . . . , p について枝集合 Ei− , Ei+ を次のように定義する.

Ei− = {e | e ∈ E, e = (va , vb ),Ei+ = {e | e ∈ E,

図 2 境界点の移動+l2j(7)e = (va , vb ), va , vb ∈ V,va ∈ V (gi ) or vb ∈ V (gi )}.

l2j0(4)

制約条件

va , vb ∈ V (gi ) ⊂ V }.
vs.

(8)

そして枝 e ∈ E の長さを |e| と表すとすると全てのi = 1, . . . , p について,∑∑|ek |, (9)|ek |,F (Ni )+ =F (Ni )− =ek ∈Ei−ek ∈Ei+としたとき,

F (Ni )− ≤F (N )≤ F (Ni )+ , i = 1, . . . , pp(10)を満たす場合, 境界点の移動による等長分割の必要条件を満たしているといえる.
式 (10) を満たさない場合は境界点の移動により等長分割はできないので, 手順 4.5 の作業を行った後に手順 4.3を行う. しかし手順 4.5 を経てもこの必要条件を満たさない可能性もあるが, その場合は等長分割はできないものの手順 4.3 によって等長分割に近づき改善解が求まるので, この条件分岐を経ずに手順 4.3 を行うことにする.

4.5

第 3 段階 : 競合学習法による重みの設定

競合学習法 [3] の考え方を応用し, 重み付きネットワー
クボロノイ図を用いることで, 部分ネットワークを順番に平均総枝長へと近づけていく. この作業の反復で 2 次目
的式 (3) が最小となる重み集合を W を求める. 手順は以下の通り.

Step 3.1 初期化.
(s)(s)
s = 0, t = 0, W (s) = {w1 , . . . , wp } = {0, . . . , 0}とし, 手順 4.5 の Step 3.2 〜 Step 3.4 の最大反復回
数 T を与え G, W (s) で分割する.
Step 3.2 探索順序の決定
t = t + 1 とし, ランダムに決定した探索順序に従い全ての i = 1, . . . , p に対し Step 3.3 の作業を繰り返す.
Step 3.3 重みの算出.
全体反復 s 回目における部分ネットワーク Ni の総枝長と平均総枝長の差を,∆F (Ni )(s) = F (Ni )(s) −F (N )p(11)としたとき, 全体反復 s + 1 回目で,

F (Ni )(s+1) = F (Ni )(s) − {F (Ni )(s) − F (N )/p}ηt ,(0 < ηt ≤ 1)(12)(s+1)となるような重み wiを求める (本研究では ηt =(s+1)
1/t と定めた). また wiは (13) 式のように求め,{}F (N )(s+1)(s). (13)wi= wi + α F (Ni )(s) −p式 (12) の左辺から右辺を引いた値が最小となるス
テップ幅 α を式 (14) を満たすように直線探索 [4] で求める (arg min は最小値を実現する変数値を表す).
{α = arg min F (Ni )(s+1) − (1 − ηt )F (Ni )(s)α∈ℜ− ηt F (N )/p | α ≥ 0} .

(14)
(s+1)

他の部分ネットワークの重み wj(s+1)(s), (j = 1, . . . , p,j ̸= i) は変更せず, wj= wj とする. 2 次目的式 (3) の値が局所最適解の 2 次目的式 (3) の値より小さくなった場合重み集合 W を記憶する.
s = s + 1 とし, 探索順序において次の i ついて Step
3.3 を繰り返す.

Step 3.4 終了条件
U < ϵ (ϵ は微小数) となった場合終了. また t = Tの場合, 等長分割できていなくても手順 4.5 を打ち切る. それ以外の場合 Step 3.2 へ.
4.6

条件分岐 2 : 終了条件

手順 4.2 〜4.5 で求めた分割の状態を G, W, B, 2 次目
的式 (3) の値 U が,

• U < U ∗ の場合, 改善解となったので現在の分割を局所最適解とする. このとき, U ∗ < ϵ ならば等長分割ができたので終了する.
• 一定回数の反復作業で等長分割できなかった場合, 等長分割の反復を打ち切る.
• U ≥ U ∗ の場合, 改悪解となってしまったのでネットワークの分割を局所最適解の状態に戻して手順 4.7 へ.
4.7

第 4 段階 : 母点の変更

手順 4.2 〜4.5 で等長分割できなかった場合, ネットワー
クの端や中心に存在するような小さな部分ネットワークの母点を近くに母点が無いような他のノードに変更し, 再度等長分割の反復を行う. そこで総枝長が最小の部分ネッ
トワーク Ns の母点 gs ∈ G を以下の条件を満たすノードt ∈ V に変更する.

• t は部分ネットワーク Ns に属していない.
• t はなるべく他の母点から離れた場所のノード.
• 手順 4.2 〜4.5 で改善解が求まらなかった場合, t は以前の手順 4.7 で選ばれていないノード.
4.8

計算機実験

4 章で提案した等長分割の解法において, Intel Core 2プロセッサ (1.80GHz), 2GB のメインメモリを持つ計算機上で計算機実験を行った. その際に, 手順 4.2 〜4.7 の最大反復回数は 101 回, 手順 4.5 の最大反復回数 T = 10とした.
ネットワークデータは数値地図 2500 (空間データ基盤)
愛知県名古屋市からランダムに抜き出した道路網データで, これらの条件でノード数 m = 100, 500, 1000 に定め,それぞれのノード数に対して 4 種類のネットワークを用意し, 各ネットワークデータについて p = 5, 10, 20, 30 という 4 種類の分割数で, (等長分割の解法にランダムな要素があり毎回結果が異なるため) それぞれ 5 回の実験を行った. 実験の結果を表 1 に示す. なおノード数 m, 分割数 p 以外の表中の属性は以下の通りである.
# 1 等長分割できた回数 (最大で 20 回).
time 等長分割の解法にかかった時間の平均値 (秒).
平均反復回数 等長分割の解法の平均反復回数.

# 2 等長分割の解法のうち手順 4.5 の実行回数の平均.
表 1 から全体で 240 回の実験を行ったうち 223 回が等長分割に成功していることが分かる. 分割数が増加するにつれ手順 4.5 の実行回数が増加していることと, 表 1 には掲載していないが, 等長分割ができた 223 回のうち 137回は手順 4.5 を行った反復で等長分割できたことからも,

m
100
100
100
100
500
500
500
500
1000
1000
1000
1000

p
5
10203051020305102030

#1
20
20
18
1120
20
20
20
2020
1915

表 1 実験結果
time 平均反復回数
0.10
1.45
1.15
6.45
13.90
36.25
38.95
64.00
0.35
1.25
3.70
3.20
34.60
14.00
112.80
28.90
2.40
2.15
10.20
3.90
137.2523.00
524.05
52.85

5.1
#2
0.70
5.40
30.55
57.55
0.40
2.50
11.30
23.45
1.65
3.30
20.60
48.55

2 段階分割の手順

まず以下の条件を満たす p1 , p2 を求める.
{(p − p3 )p1 p2 + 1 p は奇数
p=, p2 =,p1p1 p2p は偶数

p1 = arg min{p1 − p2 | 1 < p2 ≤ p1 < p}.
p が奇数の場合 p が奇数の場合, 2 段階分割を行う前に平均総枝長 F (N )/p の部分ネットワークを 1 つ作成し 2段階分割を行う (p が偶数の場合 Stage 1 から行う).
そこでまず, F̄ (N1 ) = F (N )/p, F̄ (N2 ) = F (N ) −F (N )/p とし, F (N1 ) = F̄ (N ), F (N2 ) = F̄ (N2 ) となるように 2 分割する. このようにそれぞれ異なる総枝長に分割するには, 2 次目的式 (3) と 4 章 手順
4.5 の式 (4) を式 (15), (16) のように変更することによって実現できる.

本研究で提案した手順 4.5 の重要性が見て取れる.
しかし等長分割が 1 度も成功しなかったネットワークも存在し, 等長分割できなかったネットワークと他のものとの違いは, ネットワークに密な部分と疎な部分の偏りがあるということであることが分かった. ネットワークの密度にバラつきがある場合, 分割数の増加によって等長分割が困難になるのではないだろうか.
(参考として m = 100, p = 10 で等長分割できた例を図 3に示す. 図中の■は母点, × は境界点を表す. )f (G, W, B) =2∑{}2F (Ni ) − F̄ (Ni ) . (15)

i=1

2

q2 

∑
∑
F (Ni ) +Mij xj − F̄ (Ni ). (16)
min

i=1

j=1

N1 はネットワークを p 分割した際の平均総枝長となっているので N2 を Stage 1 で更に分割する.
Stage 1 ネットワークを p1 分割し, p1 個の部分ネットワークを Stage 2 で分割するネットワークとする.
Stage 2 Stage 1 でできた p1 個のネットワークを p2 分割する.

6

おわりに

本研究では安定してネットワークを等長分割できる解法を考案することを目的としたが, やはり分割数が増加していくと等長分割できない割合が増える結果となったものの, 実験結果全体をみるとある程度安定して等長分割ができているといえるのではないだろうか. また分割数の増加以外にもネットワークの形状によって等長分割できるかどうかは大きく左右されてしまうことも分かった.
そして本研究をどのような問題へ適用するかが今後の課題になってくるだろう.
図 3 等長分割でた例 (m = 100, p = 10)

52 段階分割

4 章の実験から考案した等長分割の解法は多くの場合等長分割できるものの, ノード数, 分割数が増加すると等長分割にかかる時間も大幅に増加する結果となった. しかし分割数が少ないとき等長分割にかかった時間は短いことが分かる.
そこで分割数 p を p1 , p2 に分け, 初めにネットワークをp1 分割し, 次に分割しでできた部分ネットワークを p2 分割する 2 段階分割によって最終的に p 分割の等長分割ができ, 等長分割にかかる時間を減らせるのではないかと考えた. 2 段階分割の手順は以下の通り.

参考文献[1] Takehiro Furuta, Atsuo Suzuki and Atsuyuki Okabe:
A Voronoi Heuristic Approach to Dividing Networks
into Equal-Sized Sub-Networks, Forma, 23, 73-79(2008).
[2] 古田 壮宏: ネットワークボロノイ図とその施設配置問題への応用, 南山大学大学院 博士 (経営学) 論文(2006).
[3] 中野良平: ニューラル情報処理の基礎数理, 数理工学社 (2005).
[4] 今野浩, 山下浩: 非線形計画法, 日科技連出版社 (1978).