数理解析研究所講究録
第 1864 巻 2013 年 31-38

31

確率的に出現するバリアーを考慮した配置問題
大阪府立大学大学院 理学系研究科 情報数理科学専攻
荒神隆史 北條仁志

Takashi Kojin Hitoshi Hohjo
Department of Mathematics and Information Sciences,
Graduate School of Science,
Osaka Prefecture University

1

はじめに

2011 年 3 月 11 日に起きた東日本大震災での津波は，安全とされる指定避難所まで押し寄せ，多くの人が犠牲となった．東日本大震災の実態を受け，日本中各地で災害対策への見直しが指摘され，再検討されている．特に，専門的な知識を基に想定される被害を考慮した防災対策を行っていくことに関心が集まっている．本研究は，土砂崩れや津波などの災害が起こった際の避難施設の配置場所の決定などに応用できると考えている．

学術面では，最適施設配置問題の分野において，バリアーを考慮した配置問題が広く研究されている．バリアーとは，施設配置及び通過が不可能な領域のことを言い，このような領域を考慮した配置問題は Katz and Cooper [5] によって初めて言及された．彼らは確定的な円形バリアーが一つ存在する Weber 問題を提案した．彼らはバリァーを考慮した距離関数を定義することで，バリアー付
き Weber 問題の定式化を行った．その後，Butt and Cavalier [2] により凸多角形バリアーを持つ配置問題が提案され，可視の概念が定義された．また，Klamroth [6] は可視の概念を用いて shadow 領域を形成し，実行可能領域を Cell に分割した．各 Cell ごとの部分問題を考えることでバリアー付き
Weber 問題をバリアー無しの Weber 問題へと帰着させた．これまでの研究では，バリアーの位置が確定的な下でのバリアー付き配置問題について言及されてきた．これに対し，2010 年に Canbolatand Wesolowsky [3] は確率的にバリアーが出現する Weber 問題を提案した．彼らは，一定の長さをもつ線分バリアーが座標平面上に確率的に出現するモデルを考え，需要点から施設までの重み付き距離の和の期待値を最小にする施設の配置を求める問題として定式化を行った．しかし，現実問題においてバリアーの大きさが一定で形状が線分であるような問題はあまり多くない．また，バリアーの位置が確定的である既存の Weber 問題では，施設がバリアー内に存在する場合の重み付き距離関数は定義されていない．

本稿では，長方形バリアーが確率的に出現する制約条件下での Weber 問題を提案する．特に我々は，確率的に出現するバリァーを考慮するために，施設がバリアー内に存在する場合の重み付き距離関数を定義する．さらに需要点がバリアー内に存在するならば，その点を需要点とみなさないという仮定により，需要点の数が変化することを考慮して目的関数の定式化を行う．

2

仮定と表記
本稿では，長方形領域$\Omega=\{(x, y)|0\leq x\leq\overline{x}, 0\leq y\leq\overline{y}\}$において，長方形バリアーが確率的に出現する制約条件下での一施設配置問題を扱う．モデルの仮定を以下に記す．

321.

$x$

$\ovalbox{\tt\small REJECT}$を配置する施設とする．

$x_{i},$$i=1,$$\cdots,$ $n$

を長方形領域$\Omega$上に存在する需要点とし，需要点の重みを競とする．

2. 距離は$l_{1^{-}}$

ノルムを用いる．の境界上に存在する．
$m$ が長方形領域
3. $m$ 箇所のバリアー基準点 $mj,j=1,$
はバリアー基準点 $mj$ から確率
4. 長方形バリアーで出現し，以下を満たす．
$\Omega$$\cdots,$$B_{jk}$$\alpha jk$$\alpha_{jk}\geq 0, j=1, \cdots, m, k=1, \cdots, l$$m$$\iota$$\sum_{j=1}\sum_{k=1}\alpha_{jk}=1$$\{m_{j}\}\subset B_{j1}\subset\cdots\subset B_{jl}\subset\Omega, j=1, \cdots, m$上にある．の境界の少なく とも一辺は長方形領域
5. 長方形バリアーは重ならない．
6. 相異なる 2 つのバリアー基準点 $mm$ から出現する最大のバリアー
すなわち，$\partial\Omega$$\Omega$$B_{jk}$$B_{jl},$$B_{j^{\wedge}\downarrow}$$B_{j\iota}\cap B_{\hat{j}l}=\phi, j\neq j, j=1, \cdots, m, j=1, \cdots, m$

7. 二つ以上のバリアーが同時に出現することはない．
内に需要点が含まれるならば， は需要点とみなさない．
8. もし発生したバリァは通行不可能である．の内部 intとバリアー
9. 長方形領域 の境界ー$B_{jk}$$x_{i}$$x_{i}$$B_{jk}$$B_{Jk}$$\partial\Omega$$\Omega$記号$\overline{x}$$\overline{y}$$n$$x_{i}$$y_{i}$$w_{i}$$m$$l$$\alpha jk$

:
:
:
:
:

長方形領域

:

需要点

:

:
:

$ajk(x)$:$ajk(y)$

:
:
:
:
:
:

$b_{jk}(x)$$b_{jk}(y)$$C_{jk}^{p}$$f_{jk}^{p}(x)$

$c$

長方形領域

$\Omega$の横幅$\Omega$の縦幅

需要点の総数

需要点

需要点$\nearrow\backslash ^{\backslash }\backslash$$\nearrow\backslash ^{\backslash }\backslash t)$の重み

アー基準点 $mj$ から出現するバリアー $B$露の総数が出現する確率アー$m,$ $k=1,$$j=1,$$l$$B_{Jk},$$\cdots,$$\cdots,$$B_{jk}$の頂点 $ajk$ の$x$

座標

ノアー

$B_{jk}$の頂点 $ajk$ の$y$

座標$\nearrow\backslash ^{\backslash }\backslash 1)$$\nearrow\backslash ^{*}$$x_{i}$の $y$ 座標

リアー$\nearrow\backslash *|$$J\grave{}*$$x_{i}$の $x$ 座標

リアー基準点 $mj$ の総数$J\backslash ^{\backslash }\backslash |)$$\nearrow\backslash ^{\backslash }\backslash$$x_{i}$アー $B_{jk}$ の頂点 $b_{jk}$ の $x$ 座標l ノアー$B_{jk}$の頂点$b_{jk}$の $y$ 座標

1 ノアー $B_{jk}$ に対する Cell, $p=0,1,2,3$

Cell$C_{jk}^{p}$における重み付き距離関数，$p=0,1,2,3$

実行可能領域$\mathcal{F}$を決定するしきい値

本問題ではこれらの記号を適用して，次節で数学的定式化を行う．

3

数学的定式化は，あ2 節で述べた仮定の下での Weber 問題を考える．本モデルにおける配置実行可能領域の和集合君を領域 から除く領域し，るしきい値 以上の確率で出現するすべてのバリアー$\mathcal{F}$$c$$B_{jk}$$\Omega$

式 (3), (4) で表す．我々の目的は，確率的に出現するバリアーを考慮した重み付き距離の和の期待値として表現される目的関数 $f(x)$ を最小化する施設$x\in \mathcal{F}$の配置を決定することである．数学的33
な定式化は以下のようになる．
(1)$\min f(x) = \sum_{j=1}^{m}\sum_{k=1}^{\iota}\alpha jkfjk(x)$

s.t.

$x$

(2)

$\mathcal{F}$

$\in$

ここで，

(3)

$\overline{B} = \{B_{jk}|\sum_{i=k}^{l}\alpha_{ji}\geq c, c\in \mathbb{R}\}$(4)$\mathcal{F} = \Omega\backslash \bigcup_{B_{jk}\in\overline{B}}intB_{jk}\cup\partial\Omega$$f_{jk}(x)$

$=$

(5)

$\{\begin{array}{l}f_{jk}^{0}(x) , x\in C_{jk}^{0}f_{jk}^{1}(x) , x\in C_{jk}^{1}f_{jk}^{2}(x) , x\in C_{jk}^{2}f_{jk}^{3}(x) , x\in C_{jk}^{3}\end{array}$(6)$f_{jk}^{p}(x) = \sum_{i=1}^{n}c_{jk}d_{B}(x, x_{i}),p=0,1,2,3$$c_{jk}$$=$(7)$\{\begin{array}{ll}w_{i}, x_{i}\not\in B_{jk}0, x_{i}\in B_{jk}\end{array}$

式 (5) は重み付き距離関数乃 $k(X)$ が各 Cellで表されることを述べている．あるバリアーを用いて shadow 領域を形成し，長方形領域$B_{jk}$$\Omega$, $p=0,1,2,3$ ごとの重み付き距離関数が長方形領域 内に出現したとき，可視の概念$f_{jk}^{p}(x)$$C_{jk}^{p}$$\Omega$からバリアー $B$鈎を除いた領域

る． ノルムでは，バリアー基準点 $mj$ が存在する長方形領域$l_{1^{-}}$

アー $B_{jk}$ の境界$\partial B$

飴の線分を延長する．このことは，領域$\Omega$の境界$\Omega\backslash B_{Jk}$$\partial\Omega$の一辺と平行なバリを 3 分割する領域を構成できることを表しており，3 分割された各領域を Cell と呼ぶ．この 3 つの Cell はバリアーとして時計回りに$\partial C_{j^{1}k}\cap B_{Jk}$$C_{jk}^{1},$とバリアー

側のバリアー$\Omega$$B_{jk}$$B_{jk}$と表す．また，Cell$C_{jk}^{3}$の線分 (長方形領域のうち，長方形領域$\partial C_{jk}^{3}$$C_{jk}^{2},$の境界$\Omega$$\partial\Omega$の共通部分の境界$\partial\Omega$$C_{jk}^{1}$の境界に垂直な Cell

$C_{jk}^{1}$$\partial C_{jk}^{1}$$\Omega$の境界る．このとき，各 Cell $C_{jk}^{p},p=0,1,2,3$ の重み付き距離関数$C_{jk}^{0}$側のバリアー $B$凶の一辺) の端点の線分 (長方形領域の一辺) の端点のうち，長方形領域

飴を$B$とバリアー $B_{jk}$ の共通部分に属していない点を $ajk$ とする．同様にして，Cell$\partial C_{jk}^{3}\cap B_{Jk}$を分割す$\Omega\backslash B_{jk}$$\Omega$$\partial\Omega$$f_{jk}^{p}(x)$の境界$\partial\Omega$$C_{jk}^{3}$の境界に垂直な Cellに属していない点を$b_{jk}$は， ノルムでの需要点$l_{1^{-}}$$C_{jk}^{3}$とす$x_{i}$

から施設 $x$ までの距離関数 $d_{1}(x, x_{i})$ を用いて

$f_{jk}(x)=\{\begin{array}{ll}f_{jk}^{0}(x)=\Sigma c_{jk}d_{1}(x, x_{i})+\Sigma c_{jk}d_{1}(x, a_{jk})+\Sigma c_{jk}d_{1}(x, b_{jk}) +\Sigma c_{jk}d_{1}(a_{jk}, x_{i})+\Sigma c_{jk}d_{1}(b_{jk}, x_{i}) , x\in C_{jk}^{0}f_{jk}^{1}(x)=\Sigma c_{jk}d_{1}(x, x_{i})+\Sigma c_{jk}d_{1}(x, a_{jk})+\Sigma c_{jk}d_{1}(a_{jk}, x_{i}) , x\in C_{jk}^{1}f_{jk}^{2}(x)=\Sigma c_{jk}d_{1}(x, x_{i}) , x\in C_{jk}^{2}f_{jk}^{3}(x)=\Sigma c_{jk}d_{1}(x, x_{i})+\Sigma c_{jk}d_{1}(x, b_{jk})+\Sigma c_{jk}d_{1}(b_{jk}, x_{i}) , x\in C_{jk}^{3}\end{array}$(8)

34と表すことができる．長方形領域$\Omega$の境界$\partial\Omega$

上にないバリアー$B_{jk}$の頂点 $(ajk$ または$b_{jk})$をを定式での重み付き距離関数代替点として用いた項と定数項の部分に分けて，各 Cellにおいてバリアー付きの Weber 問題を解くことは，化することができる．したがって，各 Cell$f_{jk}^{p}(x)$$C_{jk}^{p}$$C_{jk}^{p}$

バリアー $B_{jk}$ の頂点 $(ajk$ もしくは $b_{jk})$ を代替点と考えて，バリアーの存在を考慮しない Weber問題を解くことと同値であることを示している．
式 (6),(7) では” もし発生したバリアー $B$弛内に需要点$x_{i}$が含まれるならば，点娩は需要点とみなさない” という仮定により需要点の総数が変化することについて述べている．通常の Weber 問

題での重み付き距離関数は，需要点$x$$x_{i}$の重み$w_{i}$とバリアーを考慮した上での需要点$x_{i}$から施設までの経路距離 $d_{B}(x, x_{i})$ の積の総和$f_{jk}(x)= \sum_{i=1}^{n}w_{i}d_{B}(x, x_{i})$の中に点で表される．これに対し，本研究では先の仮定によりバリアーくつ含まれるかによって需要点の総数が変化する．このことから，需要点$B_{jk}$$x_{i},$$x_{i}$を用いて表すことにより各 Cell

$C_{jk}^{p}$での重み付き距離関数$f_{jk}^{p}(x)$$i=1,2,$$\ldots,$$n$

がいの重みを式 (7) の$\mathcal{C}jk$を式 (6) のように表している．

以上のことから，我々はバリアーが確率的に出現する Weber 問題に対して，各バリアーにおいて実行可能領域を Ce 旧こ分割し，それぞれの需要点がどの Ce 旧こ属するか判断し，施設から需要点までの重み付き距離関数の総和の期待値を求める．さらに，バリアーの頂点を用いて長方形領域を分割し，その領域ごとの部分問題を考えることで施設の配置を決定する．

4アルゴリズム
Weber 問題の目的関数 $f(x)$ は，需要点$x_{i}$の重みと$w_{i}$$l_{1^{-}}$

ノルム上での需要点$x_{i}$

から施設 $x$までの距離関数 $d_{1}(x, x_{i})$ を用いて$f(x)= \sum_{i=1}^{n}w_{i}d_{1}(x, x_{i})=\sum_{i=1}^{n}w_{i}\Vert x-x_{i}\Vert$と表すことができる．この問題を解く Weiszfeld アルゴリズムは，Weiszfeld [S] によって提案された．彼は，目的関数 $f(x)$ の一次の十分条件$\nabla f(x)=\sum_{i=1}^{n}\frac{w_{i}(x-x_{i})}{\Vert x-x_{i}||}=0$の解を$x=T(x)=\{\begin{array}{ll}\frac{\Sigma_{i=1}^{n}w_{i}X/||X-X_{i}\Vert}{\Sigma_{\mathfrak{i}=1}^{n}w_{i}/\Vert X-X_{i}||}, x\neq x_{i}, i=1, \cdots, nx_{i}, x=x_{i}, i\cong 1, \cdots, n\end{array}$(9)として反復法により計算した．しかしながら，Weiszfeld アルゴリズムでは反復点が最適でない$x=x_{i}$ に一度陥るとその点から抜け出すことができない．これに対し，1978 年に Ostresh [7] によって改良型 Weiszfeld アルゴリズムが提案された．彼らは，Weiszfeld アルゴリズムでの $T(x)$ を$T(x)=x- \frac{\nabla f(x)}{s(x)}$,$s(x)=\{\begin{array}{ll}\sum_{i=1}^{n}w_{i}/\Vert x-x_{i}\Vert, x\neq x_{i}, i=1, \cdots, n\sum_{i\neq j}^{n}w_{i}/\Vert x_{j}-x_{i}1, x=x_{j}, i=1, \cdots, n\end{array}$(10)(11)

35とすることで $x=x_{i}$ のとき，その点から抜け出すことができない問題を解決した．以下が改良型

Weisfeld アルゴリズムである．
$\langle$

改良型 Weiszfeld アルゴリズム$\rangle$

Step : 初期点, 許容誤差$x^{(k+1)}=T(x^{(k)})$とする．
Stepl :$x^{(0)}\in \mathbb{R}^{n}$$O$$\epsilon>0$を与える．

Step2 : $\Vert x^{(k+1)}-x^{(k)}\Vert<\epsilon$ ならば終了する．そうでなければ，stepl へ．
この改良型 Weiszfeld アルゴリズムを基にして，最適解を求めるアルゴリズムを考える．本問題

では，バリアーの頂点 $ajk=(ajk(x), ajk(y)),$ $b_{jk}=(b_{jk}(x), b_{jk}(y))$ を用いて長方形領域$\Omega$を分割して，それぞれの領域内での最適解を求め，すべての領域の最適解の最小値を求めることで大域的最適解を得る．本問題での大域的最適解を求めるアルゴリズムを次に記す．以下では$T(x)=x- \frac{\mu\cdot\nabla f(x)}{s(x)}$

,

(12)

$s(x)=\{\begin{array}{ll}\sum_{i=1}^{n}c_{jk}^{i}/\Vert x-x_{i}\Vert, x\neq x_{i}, i=1, \cdots, n\sum_{i\neq j}^{n}c_{jk}^{i}/\Vert x_{j}-x_{i}\Vert, x=x_{j}, j=1, \cdots, n\end{array}$$0<\mu\leq 1$ とする．
であるとし，アルゴリズム

入力．目的関数 $f(x),$,$\nabla f(x)$パラメータ露， $n,$ $m,$$l,$$x_{i}, y_{i}, w_{i}(i=1, \cdots, n)$,$\overline{y},$$\alpha jk, ajk(x), ajk(y), b_{Jk}(x), b_{jk(y)(j}=1, \cdots, m, k=1, \cdots, l)$,

しきい値 C,十分小さな正の値

Stepl.

$\epsilon$

すべての $ajk(x),$ $b_{Jk}(x),$$x_{(1)},$$\cdots,$$x_{(p)},$$\cdots,$$0,\overline{x}$$x_{(2ml+2)}$

同様にして，すべての $ajk(y),$序統計量

Step2.

第$p$$Y_{(1)},$$\cdots,$ $Y_{(q)},$

順序統計量, 第$X_{(p)}$$\cdot\prime\cdot\cdot,$に対して，小さい順に並べ替えを行い順序統計量を形成する．
$b_{jk}(y),$$Y_{(2ml+2)}$$0,\overline{y}$に対して，小さい順に並べ替えを行い順を形成する．と第 $(p+1)$ 順序統計量 $X_{(p+1)}$ でつくられる区間を順序統計量と第 $(q+1)$ 順序統計量 $Y_{(q+1)}$ でつくられる区間を $[Y_{(q)} , Y_{(q+1)}]$ とし，$p=1,$ $q=1$ とする．また $M=\infty$ とする．
$[X_{(p)}, X_{(p+1)}]$

Step3.

$Y_{(q)}$

初期点 $x^{(0)}=( \frac{X_{(p)}+X_{(p+1)}}{2}, Y_{(q)}+Y_{(q+1)}2)\in[x_{(p)}, x_{(p+1)}]\cross[Y_{(q)}, Y_{(q+1)}]$ とする．
$\mu=1$

Step4.

$q$とする．

$x^{(k+1)}=T(x^{(k)})$ を計算する．

(13)

36
Step5.

$x^{(k+1)}\in[X_{(p)}, X_{(p+1)}]\cross[Y_{(q)}, Y_{(q+1)}]$

ならば，Step6 へ．そうでなければ，$\mu=\mu 2$として Step4 へ戻る．

ならば，Step7. そうでなければ，Step4 へ戻る．

Step6.

$\Vert x^{(k+1)}-x^{(k)}\Vert<\epsilon$Step7.

$f(x^{(k+1)})<M$

Step8.

$p=p+1$ として$p=1$ として Step9 へ．そうでなければ，$p=2ml+1$ ならば，Step3 へ戻る．

Step9.

$q=q+1$$q=2ml+1$ ならば，大域的最適解をげとして終了．そうでなければ，として Step3 へ戻る．

ならば，$M=f(x^{(k+1)}),$ $x^{*}=x^{(k+1)}$ とする．

このアルゴリズムを用いて，実行可能領域上での大域的最適解を求める．次節に，異なる実行可能領域に対する最適解を求めた数値例を示す．

5

数値例
この節では 20 個の需要点，6 個の異なる大きさのバリアーとあるしきい値$\overline{x}=15.0,$$\overline{y}=10.0$$c\in \mathbb{R}$として長方形領域 $\Omega=\{(x, y)|0\leq x\leq 15.0,0\leq y\leq 10.0\}$に対して，にバリアー$20$ の$i=1,$で出現する Weber 問題を考える．需要点$j=1,2,$ $k=1,2,3$ が確率$j=1,2,$ $k=1,2,3$ を以下で与える．
$j=1,2,$ $k=1,2,3$ の領域，確率
座標，バリアー$B_{jk},$$x_{i},$$\alpha jk$$B_{Jk},$$\alpha jk,$

$B_{11}=\{(x, y)|4.5\leq x\leq 5.5,0\leq y\leq 1.5\}, \alpha_{11}=0.48$$B_{12}=\{(x, y)|4.0\leq x\leq 6.0,0\leq y\leq 3.0\}, \alpha_{12}=0.24$$B_{13}=\{(x, y)|3.0\leq x\leq 7.0,0\leq y\leq 4.5\}, \alpha_{13}=0.08$$B_{21}=\{(x, y)|9.0\leq x\leq 10.5,8.5\leq y\leq 10.0\}, \alpha_{21}=0.12$$B_{22}=\{(x, y)|8.0\leq x\leq 11.5,7.0\leq y\leq 10.0\}, \alpha_{22}=0.06$$B_{23}=\{(x, y)|7.5\leq x\leq 12.0,5.5\leq y\leq 10.0\}, \alpha_{23}=0.02$$\cdots,$

37
このとき，4 つのしきい値
例 1.

$c\in \mathbb{R}$について数値例を与える．

$c=0.40$ のとき$\overline{B}=\{B_{Jk}|\sum_{i=k^{\alpha}}^{\iota}ji\geq 0.40\}=B_{11}$となり，実行可能領域$\mathcal{F}$は$\mathcal{F}=\Omega\backslash \bigcup_{B_{jk}\in\overline{B}}intB_{jk}\cup\partial\Omega=\Omega\backslash (int(B_{11})\cup\partial\Omega)$となる．このとき，最適解は $x^{*}=(7.0,3.5)$ となる．
例 2.

$c=0.09$ のとき$\overline{B}=\{B_{jk}|\sum_{i=k}^{\iota}\alpha_{ji}\geq 0.09\}=B_{12}\cup B_{21}$となり，実行可能領域$\mathcal{F}$は$\mathcal{F}=\Omega\backslash \bigcup_{B_{jk}\in\overline{B}}intB_{jk}\cup\partial\Omega=\Omega\backslash (int(B_{12}\cup B_{21})\cup\partial\Omega)$となる．このとき，最適解は $x^{*}=(7.0,3.5)$ となる．
例 3.

$c=0.03$ のとき$\overline{B}=\{B_{jk}|\sum_{i=k}^{l}\alpha ji\geq 0.03\}=B_{13}\cup B_{22}$$\mathcal{F}=\Omega\backslash \bigcup_{B_{jk}\in\overline{B}}$intとなり，実行可能領域$\mathcal{F}$は$B_{jk}\cup\partial\Omega=\Omega\backslash (int(B_{13}\cup B_{22})\cup\partial\Omega)$となる．このとき，最適解は $x^{*}=(9.7,3.5)$ となる．
例 4.

$c=0.01$ のとき$\overline{B}=\{B_{jk}|\sum_{i=k}^{\iota}\alpha_{ji}\geq 0.01\}=B_{13}\cup B_{23}=\mathcal{B}$となり，実行可能領域$\mathcal{F}$は$\mathcal{F}=\Omega\backslash \bigcup_{B_{jk}\in\overline{B}}intB_{jk}\cup\partial\Omega=\Omega\backslash (int(\mathcal{B})\cup\partial\Omega)$となる．このとき，最適解は $x^{*}=(9.7,3.5)$ となる．
数値例の例 1 と例 2, 例 3 と例 4 の組み合わせに対して最適解が同じになった．これはバリアーに含まれる需要点の数が 2 つの例に対してほぼ同じになっていることが関係していると考えられに 4 つの需要点が含まれ目的る．また，例 2 と例 3 での最適解が異なる理由としてはバリアー$B_{13}$関数に影響したと考えている．さらに，すべての数値例での最適解の 座標の値が同じであることに関しては，長方形領域を上下に 2 分割したとき，需要点が上下ほぼ均等に分布していることが関$y$係していると考えている．これについては，上下で均等に分布していない需要点に対する数値例を考える必要がある．

6

まとめ
本稿では，長方形バリアーが確率的に出現する制約条件の下での Weber 問題を提案した．その際，実行可能領域を Cell に分割して代替点を用いて重み付き距離関数を表した．さら忙，バリアーの頂点を用いて長方形領域を分割した各領域での部分問題を考えることで，確率的に出現するバリアーの存在下において目的関数の最小化を行うことができることを示した．また，バリアー内に施設を配置する場合の重み付き距離関数を定義して，バリアーの出現が確率的であることを考慮して定式化を行った．さらに，バリアーの頂点を用いて長方形領域を分割して，それぞれの領域に限定し38た部分問題の最適解を求め，すべての部分問題の最適解の中での最小値を求めることで，大域的最適解を得るアルゴリズムを提案し，ある確率以上で発生するバリアーに対する最適な施設配置を行った．特に，地震によって起こる土砂崩れや津波などの被害区域をバリアーと考え，地震が起こ$B_{jk}$る確率を$\alpha jk$

として考えると，災害時の避難施設の最適な配置場所のシミュレーションに本問題が役立つと考えている．

今後の課題としては，バリアーの発生する確率を離散型から連続型に拡張することが考えられる．
それに伴い，バリアーの大きさを確率密度関数によって表す必要があると考えられる．また，本問題が鉦ノルムを用いていたのに対して， ノルム上での議論も必要と考えている．
$l_{2^{-}}$

参考文献[1] Aneja,Y. ., M.Parlar (1994) Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel, Transportation Science 28, 70-76.
$P$[2] Butt,S. ., T.M.Cavalier (1996) An efficient algorithm for facility loction in the presence offorbidden regions, European Journal of Operational Research 90, 56-70.
$E$[3] Canbolat,M. ., G.O.Wesolosky (2010) The rectilinear distance Weber problem in the presence of a probabilistic line barrier, European Journal of Operational Research 202, 114-121.
$S$[4] Drezner,Z., H.W.Hamacher (2004) Facility location: application and theory, Springer.

[5] Katz, $I,N$ ., L.Cooper (1981) Formulation and the case of Euclidean distance with one forbidden circle, European Joumal of Operational Research 6, 166-173.
[6] Klamroth,K. (2001) Single-facility location problems with barriers, European Joumal ofOperational Research 130, 486-497.

[7]stresh Jr,L. $M$ . (1978) On the convergence of a class of iterative methods for solving theWeber location problem. Operations Research 26, 597-609.
$O$[S] Weiszfeld,E. (1937) Sur le point pour lequel la somme des distances de points donn\’es est
minimum, Tohoku Mathematical Journal (first series) 43, 355-386 (in French).
$n$