数理解析研究所講究録
第 899 巻 1995 年 98-10598

競合環境下における施設配置問題
大阪府立大学総合科学部

大角盛広(OSUMI Shigehiro)

大阪大学 I 学部

石井博昭(ISHII Hiroaki)

学部

塩出省吾(SHIODE Shogo)

大阪府立大学総合科学部

寺岡義伸(TERAOKA Yoshinobu)

大阪大学

1

$\mathcal{I}$はじめに
競合環境下での施設の配置問題は、Hotelling [3] の研究に始まり、そこでは直線上の市場に競合する施設を配置する場合のナッシュ均衡問題が扱われている。
その後、 ネットワーク上の市場に 2 企業が順に施設を配置する場合のシュタッケ’$\triangleright$

ベ’$\triangleright$

グ均衡を扱った Hakimi [2] や、 それを平面上に拡張した Drezner [1]などさまざまな研究がなされてきた。
これまでの$\not\in$

デ- では、客が自分に最も近い施設を利用すると仮定されたも$\triangleright$のが多かったが、必要不可欠な需要が伴わない$\triangleright x$

トランや喫茶店などの施設の場合には、一定の限界距離を超えると客の利用意欲が急速に衰えることが考えられる。

本論文では、平面上の市場において、施設が客から一定の限界距離以内にある場合のみ利用されるとき、 2 企業がより多くの購買力の獲得をめざして順に1 つずつ施設を配置する問題を扱う。互いに競合関係にある 2 企業が施設を交互に配置する問題については、 2 つの問題、すなわちメジアノイド問題とセントロイド問題が考えられる。本研究ではこれを定式化し、 これらの問題に対して最適解を求める方法を提案する。

99

2問題の特徴定式化に先だって、単純な例で問題の特徴を述べておくことにする。購買力2,3,3,2 の需要点が図 1 の (i) のように重なっている市場を考える。円は需要点の購買力が及ぶ限界を示しており、需要点からの距離が一定の限界内である施設は均等に利用され購買力を分かち合うものとする。 このとき、購買力を取り合うのではなくお互いに分けあって両者が共に有利になる場合があることを示す。

図 1: (i) 各領域での購買力,$(ii)a$ 配置後の分割された領域を図 1 の (i) のように$b$獲得可能購 i 買力,(iii) 配置終了と名付ける

このとき、最初$R_{1}\cdots R_{7}$。に市場に参入する企業 A が施設 を最大の購買力が獲得できる亀の領域に配$a$置したとすると、次に参入する企業$B$

それぞれの領域で (ii) のようになる$R_{3},$ $R_{4},$ $R_{5}$。

が施設 を配置して得られる購買力は、$b$に配置した場合は必ず力を 2 分することを示している。 この状況では企業
れるように$R_{2}$

あるいは$R_{6}$$B$$a$と購買は最大の購買力が得らに施設を配置することになり、最終的に (iii) のように企業 A は 4.5 の購買力を獲得し、企業$B$は 3.5 の購買力を獲得することになる。

ここで、最初の段階で企業 A が施設 を図 1 の (i) における R2 領域に配置し$a$た場合を考えると、そのときは$B$は手付かずの$R_{6}${c 配置する こ とになり、最100

終的に企業 A と$B$とがともに 5 の購 i 買力を獲得する。 これは$B$はもちろん、A にとっても明らかに最初の配置よりも有利である。
従って、相手の購買力を減らすことを考えて配置する問題とは異なり、それぞれ自己の獲得できる購買力のみを考えそれを最大にするように配置することになる。そして先に配置する企業は、後から配置する企業が利己的な配置をする こ とを考慮に入れて施設の配置を考える必要がある。

3定式化
平面上に$n$個の需要点 (客) が存在する市場において、 2 企業が自己の利益のみを考え、 より多くの購買力の獲得をめざして施設を配置する問題を考える。

2 企業を A,B とし、この順に 1 つずつ施設を配置できるものとする。市場に関して以下の仮定を設ける。

1. 客は一定の限界距離以上には出かけない

2. 客は限界内の施設は均等に利用する
3. す$\wedge^{\backslash }\backslash$ての客の限界距離は等しい

このとき、図 2 のように需要点を p 凸で表し、その重みをする施設の限界距離を$r$$w_{i}$とする。 $pt$ が利用で表す。ただし、図 2 では距離としてユークリッド距離を用いて描いてあるが、直角距離などの距離を用いた場合も同様に定式化できる。

先に配置する企業 A が配置した施設を$a$とし、企業$B$が配置した施設を$b$とすると、それぞれが購買力を獲得可能な需要点は以下の領域に含まれる点である。

Br(a)$=$$\{$

副 $d(x, a)\leq r\}$$Br(b)=$ 倒 $d(x,b)\leq r\}$以下では直角距離に限定して問題を考える。平面上での 2 企業の配置戦略を扱った Drezner [1] の$\epsilon$

デ’ と同様に、以下に述べる 2 つの問題を考える。
$\triangleright$

101

図 2: (i) 需要点$p_{i}$,(ii) 施設 $a,b$ を利用する需要点の範囲

1. メジアノイド問題 : 企業 A が施設 を配置した後、その位置情報を知っ$a$

たうえで企業$B$が自己の獲得できる購買力を最大にするように施設ゐの配置を決定する問題。すなわち、$f(b|a)= \frac{1}{2}$$\sum$$w_{i}+_{p_{:^{\in}}\cap Br(\text{ゐ})}w_{i} \frac{\sum}{Br(a)}$$p_{i}\in Br(a)\cap Br($ゐ$)$を最大にするゐを求める問題である。

この解を $b^{*}(a)$ とする

2. セントロイド問題 : 企業 A が施設 a を配置した後で企業。

$B$が $B$ 自身に最適な位置に施設ゐを置くことを考慮に入れて、 A,B が施設を配置し終わった後の企業 A の獲得できる購買力が最大になるように施設 の配置$a$を決定する問題。すなわち、$g(a)= \frac{1}{2}\sum_{p_{i}\in Br(a)\cap Br(\text{ゐ^{}s}(a))}w_{i}+\sum_{(p_{i}\in Br(a)\cup\overline{Br(\text{ゐ^{}\sim}a))}}w_{i}$を最大にする $a$ を求める問題である。

ここで、市場の総購買力を $W$ とすると、両方の施設から限界距離以上に離れている需要点が存在することがあるため、ノ (b a)$|$$+$

9(a) $\leq W$である。従って必ずしも相手の購買力を減らす こ とが自己の購買力の獲得につながらないため、互いに相手の購買力を減らす配置を考えるのではなくて、そ102

れそれ自己の獲得できる購買力のみを考えそれを最大にするように配置することになる。

4解法

4.1

前処理

前処理として利用圏の重なりを列挙しそれぞれについて重みを求める。直角距離を用いた場合の領域の重なりは、正方形の重なりを調べる問題としてとらえることができ、重なる正方形を列挙するには今井 [4] で示されている$O$(Nlog N) のア$J\triangleright$

ゴリズムが利用できるが、本問題では、元の正方形どうしの重なりを判定して列挙するだけではなく重なって生成された長方形の領域との重なりも調べる必要がある。
これは前記ア’ ゴリズムに重なり方を求める手順を付加するだけであるが、$\triangleright$

最悪の場合
す$\wedge^{\backslash }\backslash$$N^{2}$で重なるため $O$ (Nlog N) のア$\supset\triangleright$

ゴリズムはないと予想される。ての重なりを列挙する前処理のア’ ゴリズムは以下の通りである。
$\triangleright$

Step 1. 直角距離の座標を 45 度半時計方向に回転させる

Step 2. 需要点の 座標の昇順に需要点をソートする$y$

Step 3.

$x$座標に並行な利用境界線で平面を $Y_{0}\cdots Y_{n}$ のスラブに分割する

Step 4. $i:=1$ とする
Step 5.

$Y_{0}\sim Y_{n}$について Step 6 を実行する

Step 6. スラブ内の矩形領域すべてについて、 Step $7\sim$ Step 9 を実行する
Step 7. $R[i].w:=0$ ,$R[i].list:=$$\{\}$とする

Step 8. 各需要点からの最短距離を調べて 以内であればその需要点の重みを$r$$R[i].w$ に加算し、需要点の番号を $R[i]$ .list に登録する

Step 9.

$i$を 1 増やす

上記の前処理において平面上の領域が以下のようにラベ J 付けされる。
$\triangleright$

103

図 3:

$x$

軸に並行な直線で平面を分割

1. $R[i].w=$ 領域 で獲得できる購買力$i$

2. $R[i]$ .list

$=$

領域

すなわち、需要点
需要点 $k,$

$1$

$i$

$k$

を構成する需要点のリストの位置を $(P[k].x,P[k].y)$ 、重みを $P[k].w$ で表したとき、の重なる領域は $R[i].w=P[k].w+P[1].w$ と $R[i]$ .list $=\{k,1\}$ で表されることになる。

4.2

解法

以上の準備の後、以下のア’ ゴリズムによってメジアノイド問題とセントロ$\triangleright$

イド問題の解を得ることができる。

Step 1. $R[i].w$ をソートキーとして領域表$R$を降順にソートする

Step 2. $h:=R[1].w/2$ , am $:=h$ とする
Step 3. $t:=1$ とし・ $R[t].w>h$ の間 Step4 $\sim 16$ を繰り返
Step 4. $R[t]$ .list 中の全要素$k$について $P[k].w$ を半分にする

Step 5. bm $:=h$ , bi $:=t$ とする.5-$\check$

104

Step 6. $s:=1$ とし、 $R[s].w>h$ の間 Step7$\sim$

9 を繰り返す

Slep 7. 領域 での獲得購買力 $R[s].w$ を $R[s]$ .list により再計算する$s$

Step 8. $R[s].w>$ bm ならば bi $:=s$ , bm $:=R[s].w$ とする

Step 9.

Step 10.

を 1 増やす$s$

この Step において、領域 bi が企業 A が領域 ai に配置した場合のメジアノイド問題の解であり、 bi に配置した企業$B$の獲得購買力は bmである

Step 11. $R[t]$ .list 中の全要素$k$

Step 12. $R[bi]$ .list 中の全要素について $P[k].w$ を初期値に戻す$k$について $P[k].w$ を $\neq$ 分にする

Step 13. 領域 での獲得購買力 $R[t].w$ を $R[t]$ .list により再計算する$t$

Step 14. $R[t].w>$ am ならば ai $:=t$ , am $:=R[t].w$ とする
Step 15. $R[bi]$ .list 中の全要素

Step 16.
Step 17.

$t$$k$について $P[k].w$ を初期値に戻すを 1 増やす

この Step にお}$\rho$て、領域 ai がセントロイド問題の解であり、 ai に配置した企業 A の獲得購買力は少なくとも am である

5

おわりに
ここでは直角距離を用いて考えたが、ユークリッド距離の場合にも利用圏の重なり領域を求める前処理段階が異なるだけで、最適配置の探索については同様のアルゴリズムが適用できる。
ただし、 ここで示したア$\triangleright$

ゴリズムはバックトラックを用いた悉皆探索であり効率の点で満足の行くものではなく、 より効率の良い今後の課題である。

$\vee 7-\triangleright$

ゴリズムの探求が

105

参考文献
[1] Z. Drezner: “ Competitive Location Strategies for Two Facilities”, Regional

Science and Urban Economics Vol. 12 (1982).
[2] S. L. Hakirm : “ On $Lo$ cating New Facilities in a Competitive Environment”,

European Journal of Operational Research Vol. 12 (1983)[3] H. Hotelling :“Stability in Competition”, Economic Journa139 (1929).
[4] Hiroshi IMAI :“ Finding Connected Components of An Intersection Graphof Squares in The Euclidean Plane”, Information Processing Letters,

Vol.15(1982).
[5] 伊理正夫監修, 腰塚武志編集 : 計算幾何学と地理情報処理, 共立出版 (1986).
[6] 塩出省吾 :“ 競合する施設の配置について”, BASIC 数学 7 月号 (1991).

[7] 塩出省吾 :” 競合状態下の配置問題”, 第 4(1992).