ネットワークボロノイ図を用いたp メディアン問題の近似解法について
M2004MM041 内田 麻衣子
指導教員

1 はじめに
施設配置問題では, 公共のサービスなどを提供する施設を配置するモデルに p メディアン問題 [3, 4, 6] がある.
このモデルは, 施設配置場所から全需要ノードまでの総移

鈴木 敦夫
xi : i 番目の施設配置候補点, i = 1, . . . , p.
d(vi , vj ) : 需要ノード vi から需要ノード vj への最短経路距離, vi , vj ∈ V.
p メディアン問題を以下のように定義する.

動距離が最小となるように p 個の施設を配置することをd(v, Xp ) = min d(xi , v)
xi ∈Xp目的とする. また, 施設配置場所は一意に決まるとは限らず, ノード上のみならず枝上に配置される可能性がある.とする.

しかし, Hakimi の定理 [6] により少なくとも１つの最適解がネットワークのノード上の配置だけからなることがF (Xp ) =える.

p メディアン問題は整数計画問題として定式化し, 厳密解を求めることができる. しかし, p メディアン問題はNP 困難であるため, 実用的な規模の問題を解く際に, 複雑な問題になり, 計算時間が膨大になる. そのため, 厳密解を求めることが難しくなる. そこで, 近似解法が必要となってくる. p メディアン問題の厳密解を母点としたネットワークボロノイ図では, 各母点が部分ネットワークの 1メディアンとなっている. この性質を利用し, ネットワークボロノイ図を用いて, 各ネットワークボロノイ領域の 1メディアンを求めることで厳密解に近い解を求めることができるのではないかと考える.
本研究では, 施設配置場所をノード上のみとして考え,総移動距離を最小にするような施設を配置する p メディ
アン問題の近似解法を提案する. 解法には, ネットワークボロノイ図を用いる. 近似解の精度を調べるため, p メ
ディアン問題の厳密解を求め, 比較する. この問題に用いるネットワークを無向グラフとし, ドローネ三角網と国土地理院による数値地図 2500[1] より作成した名古屋市昭和区の道路網, 岐阜市の道路網, p メディアン問題用のテストデータに対する計算結果を示す.

2 p メディアン問題の定義
まず, p メディアン問題を定義する. そのため, 以下のような記号を用いる.
記号の定義

V : ノードの集合.
E : 枝の集合.
N : V と E で構成されているネットワーク,
N = (V, E).
Xp : p 個の施設配置候補点の集合, Xp ⊂ V.

d(v, Xp )(2)

F (Xp∗ ) = min F (Xp )(3)v∈V示されている. よって, 施設配置場所はノード上のみにあるとする. さらに需要ノードの重みはすべて 1 として考(1)とすると,
Xp ⊂Vとなるような Xp∗ を施設配置場所とし, p メディアンと呼ぶ.

3 ボロノイ図
ボロノイ図とは, ネットワーク上に与えられた複数の点に対して勢力圏を表したものである. これは, 最適施設配置問題を中心とした都市・地域解析などに応用されている [5]. ボロノイ図は母点とその母点を囲む領域 (これをボロノイ領域と呼ぶ) で構成されている. ここで, 母点とはネットワーク上にある指定された点の集合に属する点のことをいう. そのため, 地理的なバランスが直感的に把握できるだけでなく, 1 つの母点における 1 つの領域, つまり勢力圏を知ることができ, 最適施設配置問題に有効的に利用できる.
3.1 ネットワークボロノイ図
ネットワークボロノイ図とは, ネットワーク上にある母点のどれに一番近いかによってネットワークを分割したものである. ネットワークモデルでは, 高速道路網や一般道路網などの輸送を伴うネットワークを想定している. そして, 2 点間の距離は通常ネットワーク上の最短距離をダイクストラ法で求め, これを用いる. ネットワークボロノイ図はネットワーク上の施設配置問題に対する強力な解法のツールになると考えられている.
本研究では, 与えられた母点によってネットワークボロノイ図を構成することで, 施設配置場所を効率良く計算する.

3.2 ネットワークボロノイ図の定義
ネットワークボロノイ図を定義するため, 以下のような記号を用いる.

Xp : p 個の母点の集合．
xi : i 番目の母点, i = 1, . . . , p.
d(vi , vj ) : 需要点 vi から需要点 vj への最短経路距離,
vi , vj ∈ V ．
ネットワークボロノイ図を以下のように定義する.

(ν)

Step4. ネットワークボロノイ領域 V (Xp ) において,Xp(ν) = Xp(ν+1)となった時点で終了とする. このときの母点集合(ν)

Xpを解とする.

Xp(ν) = Xp(ν+1)

母点 xi ∈ Xp に対するネットワークボロノイ領域を(ν)

V (xi ) = {v ∈ V | d(xi , v) ≤ d(x, v)，∀x ∈ Xp } (4)(ν+1)となった場合, Xp を Xpに更新し, ν = ν+1として, Step2 へ.とするとき, ネットワークボロノイ図 V は

V = {V (x1 ), . . . , V (x i ), . . . , V (x p )}(5)

この解法は，Step2-Step4 を反復するごとに, 総移動距離の和が必ず減少するという特徴を持つ. しかし, 初期値の母点によっては局所最適解で終了してしまう可能性がとなる.
式 (4) はネットワーク上に母点 xi (i = 1, . . . , p) が与えられたとき, 需要点 v から母点 xi までの距離が需要点v から他の母点 x までの距離よりも短いという条件を満たすような需要点 v の集まりを意味している. つまり, 需
要点 v はもっとも近い母点 xi のネットワークボロノイ領域に含まれることを表している.

4 p メディアン問題のアルゴリズム
p メディアン問題の近似解法のアルゴリズムを以下に簡潔に示す.

4.1 準備• 初期値として施設配置候補点 xi (i = 1, . . . , p) は乱数で与える.
• 施設配置候補点 xi と需要点 v ∈ V との間の最短距離はダイクストラ法で距離行列を作り, それを用いる.
4.2 アルゴリズム(ν)
Step1. 初期値として p 個の施設配置候補点 xi (i = 1,. . . , p) を選び母点とし, ν = 0 とする. ここで,(ν)(ν)
xi の母点集合を Xp とする.
(ν)

Step2. p 個の母点 xi を用いて, ネットワークボロノイ図を作成する.
(ν)

(ν)

Step3. 各母点 xi のネットワークボロノイ領域 V (xi )(ν+1)
ごとに 1 メディアン xiを求める.
(ν+1)

xi(ν)

タートを用いる. マルチスタートで求めた解の中で最小の総移動距離となる母点の組合せを近似解とし, これを施設配置場所とする.

5 計算例
4 節で述べたアルゴリズムを用いて, p メディアン問題のプログラムを C 言語を用いて作成した. 計算機環境は,Intel Pentium 4(2.80GHz), メモリ 512MB である. プログラムは, ノード数, 枝数, 各ノードの座標などをデータとして用いる. 計算例には, 以下のようなネットワークを用いた.
• ドローネ三角網 (ノード数 100〜800, 施設数 3〜10).
• 名古屋市昭和区の道路網 (ノード数 100〜800, 施設数 3〜10).
• 岐阜市の道路網 (ノード数 1927, 施設数 3〜5).
• p メディアン問題用のテストデータ (ノード数 100〜900, 施設数 5〜200) [2].
ここでは, ドローネ三角網と名古屋市昭和区の道路網の計算例を示す. マルチスタートの回数は, 計算結果から各ノード数, 施設数に対して厳密解に近い解が求められる回数に決定している. 各ノード数, 施設数に対して表 3,4 で書かれているマルチスタートの回数で計算を行なった. 計
算時間は, 厳密解はデータの読み込みから計算結果の出力までの時間とする. 近似解はデータを読み込み, 計算が終∈ V (xi ) として,了するまでの時間とする. データのファイル数は, ノード

数 100, 200 は 10 個用いる. 以下に示されている計算例

min(ν+1)xiある. そこで, 初期値を変えて複数回実行するマルチス(ν)∈V (xi )(ν+1)

d(v, xi(ν)

v∈V (xi(ν+1)

min(ν+1)xi(ν+1)と す る と, F (Xpを求める.

(ν)∈V (xi)はノード数 100, 200 のデータの 1 つを用い, 施設を 3 箇所に配置する.となるような 1 メディアン xi(ν+1))=
F (xi))(ν)

v∈V (xi(ν+1)
d(v, xi))(ν+1)) = F (x1(ν+1)
F (xp) は目的関数値となる.

また, 近似解の精度を調べるため, 数理計画ソフトウェ
ア What’s Best!7.0 と CPLEX8.0 を用いて厳密解を求めた. What’s Best!7.0 と CPLEX8.0 で用いたデータは距離行列である. 計算機環境は, What’s Best!7.0 を使用した計算機は, Intel Pentium 4(2.80GHz), メモリ 512MB) + ··· +であり, CPLEX8.0 を使用した計算機は Intel Pentium4(3.0GHz), メモリ 2GB である.

5.1 計算例 1
単位正方形内に一様に分布する点を母点とするドロー

た. ここで用いたデータはノード数 200, 枝数 222 である.
●は需要ノードを表し, ▲は施設配置場所を示す.

ネ三角網を用いる. 厳密解, 近似解ともに目的関数値は22.16743 となった. 計算時間は図 1 では 15 秒, 図 2 では0.02 秒となった. マルチスタートを行ない, 10 通りの初期値から近似解を求めた結果, アルゴリズムの反復回数の平均値は 3.7 回となった. ここで用いたデータはノード数100, 枝数 284 である. ●は需要ノードを表し, ▲は施設配置場所を示す.

図 3 ノード数 200 枝数 222 の名古屋市昭和区の道路網に対する 3 メディアン問題の厳密解●は需要ノードを表し, ▲は施設配置場所を示す.

図 1 ノード数 100 枝数 284 のドローネ三角網に対する 3 メディアン問題の厳密解●は需要ノードを表し, ▲は施設配置場所を示す.

図 4 ノード数 200 枝数 222 の名古屋市昭和区の道路網に対する 3 メディアン問題の近似解●は需要ノードを表し, ▲は施設配置場所を示す.

図 2 ノード数 100 枝数 284 のドローネ三角網に対する 3 メディアン問題の近似解●は需要ノードを表し, ▲は施設配置場所を示す.

5.2 計算例 2
名古屋市昭和区の道路網からランダムに選んだノードとその周辺のノードからなるネットワークを用いる. 厳
密解, 近似解ともに目的関数値は 279823.71 となった. 計
算時間は図 3 で 1 分 14 秒, 図 4 で 0.05 秒となった. マル
チスタートを行ない, 10 通りの初期値から近似解を求めた結果, アルゴリズムの反復回数の平均値は 2.9 回となっ5.3 計算結果
表 1, 表 2 で書かれている計算時間は, 各ノード数・施設数に対して, 10 個のデータを用いて平均時間をとったものある. このとき, マルチスタートの回数は各ノード数,施設数に対して表 3, 表 4 を用いて解を計算している. 表3, 表 4 で書かれている平均反復回数は, 計算例 1 と計算
例 2 で用いたネットワークを使用し, マルチスタートの回数で平均値をとったものである. 図 5 では, ノード数 200,枝数 588 のドローネ三角網上に施設を 5 箇所に配置するとして, 厳密解の目的関数値を 1 としたときの近似解の目的関数値を示したものである. このときのマルチスター
トの回数は 200 回とする.

6 考察

表 1 ノード数 100 のドローネ三角網のデータ
10 個に対する平均計算時間 (単位：秒)

ノード数

施設数

100
100
100

3510

厳密解の近似解の計算時間

計算時間1516.313.60.015
0.082
4.962

表 2 ノード数 200 の名古屋市昭和区の道路網のデータ 10 個に対する平均計算時間 (単位：秒)

ノード数

施設数

200200200

表33510厳密解の近似解の計算時間

計算時間

156.3
109.2
171.50.045
3.660
19.492

計算例 1 を用いたドローネ三角網に対する計算結果

平均反復回数は, マルチスタート 1 回当りの反復回数である.

ノード数100100100

施設数3510

マルチスタート

平均の回数

反復回数10100
6000

3.740
4.255
4.167

p メディアン問題の近似解の精度を厳密解と比較する.
表 1, 表 2 の計算時間では, 厳密解を求めるよりもかなり速い計算時間で近似解を求めることができた. 表 3, 表 4を見ると, ノード数 100, 200 では, わずか 10 通りの初期値を与えるだけで, 厳密解と一致する解を求めることができた. マルチスタートの回数がノード数, 施設数の組合せによって異なるのは, ノード数 100, 施設数 3 の場合にノード数 200, 施設数 10 の場合と同じ回数で計算を行なうと計算時間が余分にかかってしまう. よって, 近似解が厳密解に十分に収束している回数に決定する. 次に, 反復回数を見ると 2 回から 5 回で解を求めることができた.
さらに図 5 から, マルチスタートの回数 200 回に近づくにつれ, 近似解の目的関数値が厳密解の目的関数値に収束していくことがわかる. p メディアン問題での計算の手間は, n をノード数とし, O(n2 log n) となった.
5 節では, 需要ノードの重みを 1 として考えた. 実用的な問題では, 需要ノードの重みは異なる. そこで, 乱数を用いて需要ノードに重みを与え, 5 節と同様の計算を行なったところ, 速い計算時間で厳密解と解が一致した.

7 おわりに
本研究ではネットワークボロノイ図を用いた p メディ
アン問題の近似解法を提案した. ここで用いたデータに対して, 厳密解と近似解が一致したので近似解法として高速で精度の高い結果を得ることができた. その他のデータに対しても, 施設数が小さいものは厳密解と一致した解を得ることができた. ここで提案した手法は, 各ネットワー
クボロノイ領域ごとに独立した 1 メディアン問題を考え

表 4 計算例 2 を用いた名古屋市昭和区の道路網に対する計算結果

ることができる. あるネットワークボロノイ領域の 1 メ

平均反復回数は, マルチスタート 1 回当りの反復回数である.

ノード数200
200
200

施設数3510

マルチスタート

平均できるようにすると, 記憶領域の無駄を省くことができるの回数反復回数のではないかと考える. そのため, 今後これをふまえた研

10
1000
7000

2.900
4.526
5.264

究が必要である.

参考文献

目的関数値

1.008
1.007
1.006
1.005
1.004
1.003
1.002
1.001
1.000
0.999
050

ディアンを求めるとき, 他の領域の情報は必要としない.
そこで, 距離行列を求めず, 各領域ごとに最短経路を計算

100150

マルチスタート回数

図 5 ノード数 200 枝数 588 のドローネ三角網に対する 5 メディアン問題の厳密解の目的関数
値を 1 としたときの近似解の目的関数値
マルチスタートの回数は 200 回とする.

200[1] Geographical Survey Institute: GSI HOME PAGE,
http://www.gsi.go.jp/.
[2] J.E. Beasley: OR-LIBRARY,
http://people.brunel.ac.jp/˜mastjjb/jeb/info.html.
[3] M.S. Daskin: Network and Discrete Location Models, Algorithms, and Applications, John Wiley &Sons Inc., New York, 1995.
[4] 社団法人 日本建築学会: 建築・都市計画のためのモデ
ル分析の手法, 井上書院, 東京, 1992.
[5] 岡部篤行, 鈴木敦夫: 最適配置の数理, 朝倉書店, 東京,1992.
[6] S.L. Hakimi: Optimum distribution of swiching
centers in a communication network and some related graph theoretic problems, Operations Research, 13(1965), pp.462-475.