多様な基準を考慮した施設配置問題の考察

多様な基準を考慮した施設配置問題の考察

著者

佐々木 祐介

多様な基準を考慮した

施設配置問題の考察

関西学院大学大学院 理工学研究科 数理科学専攻

佐々木祐介

目次

1

はじめに

3

2

直角距離とユークリッド距離

4

3

A-

距離

[8]

5

4

複合施設における配置問題のあらすじ

5

5

問題の定式化

6

6

解法

9

非劣解 10

7

複合施設の配置問題のまとめ

11

8

給食センターにおける配置問題のあらすじ

12

9

定式化

12

r グループへの学校の分け方 13 候補地が幾つかの長方形領域に限定されている場合 14

10

問題例

17

11

給食センターの配置問題のまとめ

29

謝辞

30

参考文献

31

1

はじめに

施設配置問題の研究は Weber[1] の研究に始まり、Elzinga と Hearn[2] に よる素晴らしい論文以来これまで膨大な研究 [4],[5],[6],[7] があり、Hamacher [3] 等は待ち行列あるいはスケジューリングへの分類コードと類似した方 法でこれらを分類している。施設はその利用形態から大きく２つに分け て考えることができる。１つは施設に利用者が訪れることによってサー ビスを受ける形態の施設、もう１つは施設側からの訪問により利用者が サービスを受ける形態の施設である。数理計画問題に関連して重要な双 方の違いに、移動にかかわる費用を利用者が負担するか、あるいはサー ビスを提供する側が負担するかということがある。ここで、移動にかか わる費用とは一般的には距離概念であり、地理的な距離、時間的な距離 または経済的距離であり、対象とする施設を配置する地域の特性により 施設を分類することができる。施設の中では需要度が高い望まれる施設 と需要度が低い望まれない施設がある。ここではまず１つ目の研究とし てこれら双方の施設を複合施設として配置する問題を考える。さらに施 設には商店や学校など、日常の中で各サービスごとに必ずしも緊急性を 要求されない施設と警察署や消防署など各サービスごとに緊急性を要求 される施設が存在する。ここで２つ目の研究として給食センターの配置 問題を考える。給食センターは前者の分類と考えられがちだが、料理が 完成してから、生徒が食べるまでの時間制約が存在する。さらに時間が 経てば料理の鮮度が落ちてしまうため、緊急性を要する後者に分類され る。

2

直角距離とユークリッド距離

需要点から施設までの距離を直角距離を用いて考える。ユークリッド 距離は直線距離であり、通常、距離はユークリッド距離をさす。しかし、 実際の２点間の距離がすべてユークリッド距離で表されることは難しい。 まず、直角距離とユークリッド距離の違いを述べる。 ユークリッド距離において、２点 A(x1, y1), B(x2, y2) 間の距離 d2(A, B) は d2(A, B) = √ (x1− x2)2 − (y1− y2)2 と表される。 ここで、碁盤の目のような市街地を移動するときを考える。このとき、 ２点間の最短距離は直角に折れ曲がった線になり、その距離は２点間の 線分を対角にもつ長方形の２辺の長さの和と等しくなる。 ２点間の直角距離 d1(A, B) は d1(A, B) =|x1− x2| + |y1− y2| で定義される。また直角距離は以下の公理を満たす。 • d1(p, q)≥ 0 かつ d1(p, q) = 0⇐⇒ p = q （非負性） • d1(p, q) = d1(q, p)  （対称性） • 任意の３点 p, q, r について、d1(p, q) + d1(q, r)≥ d1(p, r)   （三角不等式）

3

A-

距離

[8]

• 平面において与えられた複数の方向の集合 A = {α1, α2,· · · , αa} と する。ただし、αi, i = 1, 2, . . . , a は直交座標系において x 軸となす 角度で、0o _{≤ α} 1 < α2,· · · < αa< 180oとする。 • 直線や半直線、線分の方向が A に属しているとき、これらは A-方 向であるという。 • 2 点 p1_{, p}2 _{∈ R}2_{の A-距離 d} Aを次のように定義する。 dA(p1, p2) =          d2(p1, p2) (p1, p2が１つのA−方向直線上のとき)   min p3_∈R2{dA(p 1 , p3) + dA(p3, p2)} (その他) ただし、d2(p1, p2) は p1, p2間のユークリッド距離とする。

4

複合施設における配置問題のあらすじ

本研究では望まれる施設と望まれない施設を建設する際に、同じ場所 に複合施設として建設するべきか、別々の場所に単独の施設として建設 すべきかを考える。この問題について定式化し、その解法を与える。

5

問題の定式化

(1) 需要点を Di = (ai, bi), i = 1, 2, . . . , m とする。いくつかの障害物 Bk = {(x, y)|B1 k ≤ x ≤ B 2 k, B 3 k ≤ y ≤ B 4 k}, (k = 1, 2, . . . , s) がある都市部 X = {(x, y)|0 ≤ x ≤ p0, 0 ≤ y ≤ q0} に施設の建設候補地 F Pj = (pj, qj), (j = 1, 2, . . . , n) があるとする。 (2) A : 望ましい施設 （需要点からの最大の距離が最小となるようにする。） B : 望ましくない施設 （需要点からの最小の距離が最大となるようにする。） この施設 A と B は１つの複合施設として建設をするべきか、また別々の 施設として建設するべきかを考える。各建設候補地 F Pjに A, B それぞ れの建設費用を仮定する。建設費用は確率変数として A, B それぞれを CAj, CBj とする。また、同様に複合施設に関しては CSjとする。 • CAj : 平均 m1j, 分散 σ1j2 である正規分布に従う確率変数として考 える。 • CBj : 平均 m2j, 分散 σ22jである正規分布に従う確率変数として考 える。 また、全体の建設費は A と B の合計とする。 • CSj : 平均 m3j, 分散 σ3j2 である正規分布に従う確率変数として考 える. (3) まず、確率 α > 1 2のもとで予算 f を考える。このとき、できるだけ予 算 f を少なくしたい。 Pr{CAj ≤ f} ≥ α ⇔ Pr {_CA j − m1j σ1j ≤ f − m1j σ1j } ≥ α ⇔ f ≥ m1j+Kασ1j

CAj − m1j σ1j : 標準的な正規分布に従う確率変数 Kα : 標準正規分布の累積分布関数 F がαとなる点 F (Kα) = α すなわち          f ≥ m1j + Kασ1j (A : 場所 j) f ≥ m2j + Kασ2j (B : 場所 j) f ≥ m3j + Kασ3j (A, B : 場所 j) ※ただし、A と B がそれぞれ別々の候補地で建設されるとき、建設費の 分布を独立と仮定すると、予算の制限は f ≥ (m1i+ m2j) + Kα(σ1i+ σ2j) となる。 (4) 需要点 Di, (i = 1, 2, . . . , m) と候補地 F Pj, (j = 1, 2, . . . , n) との距離を d(i, j) とする。この d(i, j) をネットワークアルゴリズムの最短経路の求め る方法を用いて計算する。N (V, E)   (Lawler,1976)[9] ここでは、距離行列を用いる方法のみを述べる。他に、Floyd-Warshall 法 などがあるが、ここでは省略する。 まず、行列の新しい掛け算⊗を定義する。

定義

⊗

C = (cij), D = (dij) とすると、P = C ⊗ D の要素 pijは、pij = mink{cik+ dkj} である。もちろん、この掛け算が定義できるためには、左の行列の 列の数と右の行列の行の数が同じでなければならない点は通常の掛け算 と同じである。uij(m)を m 以下のアークを用いたときの viから vjへの最 短経路の長さとすると、n × n 行列 u(m) _{= (u} ij(m)) はいわば m 次の近似 となり、次の関係により得られる。

ただし、 U(0) =         0 . .. ∞ ∞ . .. 0         すなわち、対角要素は 0、他は∞ とする。 U(1)= U(0)⊗A U(2)= U(1)⊗A = (U(0)⊗A)⊗A .. . U(n−1) _{= U}(n−2)⊗_{A = (}· · · (U(0)⊗_A)· · ·⊗_A U(0)_{はこの掛け算の単位行列であることと結合法則が成立することにより} U(n−1) = An−1 と書ける。 以下のネットワークに対してすべての 2 点間の最短経路を求める方法を 用いて距離を計算すると、 V = {D1, D2, . . . , Dm, (B11, B13), (B11, B14), (B12, B13), (B12, B14), . . . , (Bi1, Bi3), (B1 i, Bi4), (Bi2, Bi3), (Bi2, Bi4), . . . , (Bs1, Bs3), (Bs1, Bs4), (Bs2, Bs3), (Bs2, Bs4), F P1, F P2, . . . , F Pn} = ({v1, v2, . . . , vm, vm+1, . . . , vm+4s, vm+4s+1, . . . , vm+4s+n}) E = {(vi, vj)|i ̸= j, i = j = 1, 2, . . . , m + 4s + n} (ただし、viと vjは可視であるとする。)

ここで、可視性について、出発地から目的地に行ける場合を可視とし、そ うでない場合は不可視とする。

•  まず、dA(j) = max{d(i, j)|i = 1, 2, . . . , m} について考える。こ

のとき、dA(j), j = 1, 2, . . . , n の中で最小を与える j = jAを考える。

•  次に、dB(j) = max{d(i, j)|i = 1, 2, . . . , m} について考える。こ

のとき、dB(j), j = 1, 2, . . . , n の中で最小を与える j = jBを考える。 •  そして、予算の最小値 F を求める。 F = min{m1jA + Kασ1jA + m2jB + Kασ2jB, m3jC + Kασ3jC} jA : 施設Aの設置場所 jB : 施設Bの設置場所（ただしAと別々に設置されたとき） jC : 複合施設の設置場所（AとBが１つの施設として設置されたとき） もし、(i, j) が m1i+ m2j + Kα(σ1i+ σ2j) > max{m3i+ Kασ3i, m3j+ Kασ3j} となるならば、 F = min{m3i+ Kασ3i|i = 1, 2, . . . , n} となる。

6

解法

X = (jX A, jBX) で表される解 X に対応するベクトル VX = (V1X, V2X, V3X) を考える。jX A, jBXはそれぞれ A, B の建設場所とする。

このとき、 V₁X = max{d(i, j_AX)|i = 1, 2, . . . , m} V₂X = min{d(i, j_BX)|i = 1, 2, . . . , m} V₃X =    m_1jX A + m1jBX + Kα(σ1jAX + σ1jBX) (j X A ̸= jBX) m_3jX A + Kασ3jXA (j X A = jBX) とする。

非劣解

解 X1, X2が V1X1 ≤ V X2 1 , V X1 2 ≥ V X2 2 , V X1 3 ≤ V X2 3 と VX1 ̸= VX2を満たし ているならば X1が X2に優越しているとする。 もし、優越している解 X が存在していない場合、X は非劣解とする。 min{dA(j)|j = 1, 2, . . . , n} ≤ max{d(i, jc)|i = 1, 2, . . . , m} max{dB(j)|j = 1, 2, . . . , n} ≥ min{d(i, jc)|i = 1, 2, . . . , m} jc: min{m3i+ Kασ3i|i = 1, 2, . . . , n} を最小にするもの もし、施設 A と B を候補地 jcに複合施設として建設するならば以下の式 が成り立つかを確認する。 min{dA(j)|j = 1, 2, . . . , n} = max{d(i, jc)|i = 1, 2, . . . , m} max{dB(j)|j = 1, 2, . . . , n} = min{d(i, jc)|i = 1, 2, . . . , m} (5) 複合施設の建設場所 F Pjcの解が非劣解となる。

(6) jAに関して min{dA(j)|j = 1, 2, . . . , n} を最小にするもの、そして jBに関して max{dB(j)|j = 1, 2, . . . , n} を最大にするものを見つける。 A が jAに建設され、B が jBに建設された解は非劣解となる。 (7) dA(j)と dB(j)の重みがつけられた凸和 W (j) = w1dA w2dB , w1 > 0, w2 > 0, w1+ w2 = 1 を考慮し、jwを最小にするものを見つける。A と B が複合施設として jw に建設されたときの解は非劣解とする。 W (j) = w1dA(j) + w2dB(j), w1 > 0, w2 > 0, w1+ w2 = 1 (8) dA(j)と dB(j)について限界値を定める。そして、建設候補地 j ∈ F T = {j|dA(j)≤ g, dB(j)≥ s} を絞っていく。候補地 j ∈ F T を選ぶために （5）,（6）,（7）の手順を繰り返し行い、非劣解を見つける。

7

複合施設の配置問題のまとめ

本研究では候補地を有限個で考えているが、候補地がいくつかのブロッ クの中の点に限定されている場合へと拡張したい。さらには、A-距離へ 拡張することによって、より現実的なモデルとなる。

8

給食センターにおける配置問題のあらすじ

本研究ではある地域での学校給食を提供するセンターの最適建設場所と その配達方法を決定するモデルを考察する。学校給食は小学校等の児童 に十分な栄養を与えるという重要な課題である。すべての小学校に昼食 までの給食を届けるためには学校への距離や材料の準備から考えてセン ターの位置が鍵となる。通常建設可能な場所は限られているので、候補 地は有限あるいは限定された場所と仮定する。問題の定式化の後、最初 候補地が有限個の場合を考える。この場合の結果に基づいて次に候補地 が無限であるが有限個の長方形領域に限定されている場合について考察 する。最後に結果を要約し、今後の課題について議論する。

9

定式化

次の施設配置問題を考える。 (1) ある都市地域に m 個の学校 S1, S2, . . . , Smと新しい給食センターの n 個の候補地 F1, F2, . . . , Fnがある。 (2) 毎朝業者がセンターに給食の材料を届ける。その後、センターは給 食つくりを始め、給食配達車がスタートする前に完了する。配達車 は受け持ちの学校に昼食時間前に給食を届ける。このため、学校を r 個の配達車 T1, T2, . . . , Trにグループ分けする。 (3) センターから業者、すべての学校への直角距離を考慮して、すべて の学校の中で、給食配達時間がもっとも遅くなる時間を最小にする ようにセンターの最適建設場所を決める。

最初に各候補地 Fi, i = 1, 2, . . . , n から各学校 Sj, j = 1, 2, . . . , m への直 角距離 dij を計算する。Fi = (cix, ciy), Sj = (sjx, sjy) とすると dij = |cix − sj x| + |ciy− sjy| であり、 dijを各 Fiごとにソートして dii(1)≤ dii(2) ≤ · · · ≤ dii(k) ≤ · · · ≤ dii(m)とする。それからセンターを Fiに設置した場合の学 校の ｒ 個配送トラックへの受け持ち割り当てを以下のように決定する。 ただし、容量の関係でトラックは 1 回に１校に給食を運んで帰ってくる とする、また、時間は距離に完全に比例するとする。したがって、最後 に配送する学校以外は１回の往復で対応する学校への距離の２倍かかる ので、分割は各配送車について最後の学校への距離＋途中の配達の学校 の距離の２倍の和を考え、この和を最小にするように学校を分割すれば よい。したがって次のような分割法が考えられる。 まず、長い方から r 個の距離を選んで、学校 Si(m−t+1)を配送車 Tt, t = 1, 2, . . . , r へ１つずつ割り当てる。また残りの学校 Si(k)に対して ¯dik = 2dii(k), k = 1, 2, . . . , m− r とする。

9.1

r

グループへの学校の分け方

(Step1) Bi(t) = dii(m−t+1), t = 1, 2, . . . , r− 1

Bi(r) = dii(m−r+1)+ dii(m−r), k = m− r

G(t) ={S_i(m−t+1)}, t = 1, 2, . . . , r − 1 G(r) ={Si(m−r+1), Si(m−r)} とおいて (Step2) へ (Step2) k← k − 1 とする。もし k = 0 なら終了。そうでなければ、(Step3) へ (Step3) B(m)← min{Bi(u)|u = 1, 2, . . . , r}、最小の B(m) を与えるトラックの番 号を t(k) とする。

それから、Bi(t(k)) = Bi(t(k))+dii(k)¯ , G(t(k)) = G(t(k))∪ {Si(k)} として、 (Step3) へ戻る。 この手順における最終の Bi(u)を標準の速度で割ったものが配送トラッ ク Tuを使って学校群 G(u), u = 1, 2, . . . r のトータルの配送時間を示して いる。この方法はヒューリスティックであるが、できるだけ負荷を等分化し ようとしている。すなわち最大負荷を最小化しようとしている。Fiにおけ

る上記の方法による最大負荷を M (i) とすると min{M(i)|i = 1, 2, . . . , n} を与える候補地が妥当な建設場所となる。ここまでは業者からの距離を 考慮してこなかったが、実際問題として業者からあまりに遠い候補地は 給食を作り始める時間が遅れてしまうので最初から排除するのが妥当と 思っている。

9.2

候補地が幾つかの長方形領域に限定されている場合

幾つかの長方形の任意の点に候補地が限定されている場合を次に考え る。長方形が１点に縮約される場合は前の有限個の候補地の場合になる ので、この意味では前の一般化になっている。図１のようにこの h 個の 長方形の１つを R(v)、その４つの頂点を vA, vB, vC, vDとする。 最初にもとの領域 X を以下のようにして部分領域に分割する。 まず直線 x = vAx, vBx vCx, vDx v = 1, 2, . . . , h x = sjx, j = 1, 2, . . . , m x = X0, X1 y = vAy, vBy vCy, vDy v = 1, 2, . . . , h y = sjy, j = 1, 2, . . . , m y = Y0, Y1 をひく。

図 1: R(v) の 4 つの頂点 その結果、全部でできる q 個の部分長方形領域を反時計回りに SR(1), SR(2), . . . , SR(k), . . . , SR(q) と番号付けをする。ここで、q = O((h + m)2_{)、そして部分領域 SR(k) の} 頂点を図２のように Ak, Bk, Ck, Dkで示す。 もしセンターを SR(k) の点を (x, y) ととると、センター LC から学校への 図 2: SR(k) の 4 つの頂点 距離は学校を SR(k) に対する位置の方向に従って４つの群 NW (k), N E(k),

SW (k), SE(k) に分割して計算される。 ここで、ax(k)≤ x ≤ bx(k), by(k)≤ y ≤ ay(k) で N W (k) = {Sj|sjx ≤ ax(k), sjy ≥ ay(k)} N E(k) = {Sj|sjx ≥ bx(k), sjy ≥ ay(k)} SW (k) = {Sj|sjx ≤ ax(k), sjy ≤ by(k)} SE(k) = {Sj|sjx ≥ bx(k), sjy ≤ by(k)} であり、 センターから Sj ∈ NW (k) に対する距離は Akからの距離を通して Sj + x− ax(k) + ay(k)− y となる。 センターから Sj ∈ NE(k) に対する距離は Bkからの距離を通して Sj + bx(k)− x + ay(k)− y となる。 センターから Sj ∈ SW (k) に対する距離は Ckからの距離を通して Sj + x− ax(k) + y− by(k) となる。 センターから Sj ∈ SE(k) に対する距離は Dkからの距離を通して Sj + bx(k)− x + y − by(k) となる。

したがって、まずは４ h 個の候補地 Ak, Bk, Ck, Dk, k = 1, 2, . . . , h に対 して前の有限個の候補地に対する手順を適用する。それから、これらから 候補地を上記の距離計算から SR(k), k = 1, 2, . . . , h の内部に動かして改 善されるかを調べる。調べた結果から妥当なセンターの建設場所を得る。

10

問題例

ここで、実際例を紹介する。関西学院大学三田キャンパスが位置する 三田市を例に挙げて計算する。三田市に新規の給食センターを建設する ことを考える。現在、給食センターが受け持っている施設は三田市には 39ヶ所存在する。配送車を 13 台あるとし、配送車 1 台平均 3ヶ所受け持 つものとする。給食センターを建設する候補地は Ａ, Ｂ, Ｃ の 3 つとする。 この場合の最適候補地は C の場所となる。

11

給食センターの配置問題のまとめ

給食センターの妥当な建設場所について考察した。学校のグループと その配送順について考えたが、最適なものになっていないが、この問題 はたぶん NP 完全な難しい問題であるので、最適配置場所を求めるのは 困難である。しかし、もっとシンプルで効率的かつよりよい近似解を求 める手順を編み出すことが重要であり、これからの課題である。もちろ ん現実的には既存のセンターが既にあって、新しいセンターをその建設 是非を含めて考えて行かねばならないと思われる。さらには地産地消の 観点から、業者をその位置、新鮮さを含めてどのように選ぶかも重要で ある。

謝辞

この研究を修士論文として形にすることが出来たのは、担当して頂い た石井教授の熱心なご指導や、三田市ゆりのき台給食センターの中田先 生が貴重な時間を割き給食センターにかかわる資料を提供していただい たおかげです。協力していただいた皆様へ心から感謝の気持ちと御礼を 申し上げたく、謝辞にかえさせていただきます。

参考文献

[1] Weber, A. (1909) U ber Den Stand Der Industrien 1. Teil:˙ ReineTheorie Des Standortes,

[2] Elzinga J. and Hearn D.W. (1972). Geometric Solutions for Some Minimax Location Problem. Transportation Science, 6, 379-394. [3] Hamacher W. H. and Stefan N. (1998). Classification of location

models, Location Science, 6, .229-242.

[4] Ishii, H. Lee Y. L. and Yeh K. Y. (2007) Facility location problem with preference of candidate sites. Fuzzy Sets and Systems 158, 1922-1930.

[5] Ohsawa Y. (2000). Bicriteria Euclidean Location Associated with Maximin and Minimax Criteria. Naval Research Logistics, 47, 581-592.

[6] Osumi S. and Ishii H. (2005) .Obnoxious facility Location Problem with Forbidden Region. Asia Pacific Management Review, 10, 255-258.

[7] T. Matutomi and H. Ishii, Minimax location problem with A-distance, Journal of the Operations Research Society of Japan,Vol.41, pp. 181-185, 1998.

[8] P. Widmayer et al, On some distance problems in fixed orienta-tions, SIAM J. on Computing, Vol.16, pp.728-746, 1987.

[9] Lawler, E. L.(1976). Combinatorial Optimization: Networks and Matroid, Rinehart and Winston, New York.

[10] Ishii,H. and Sasaki,Y. (2014) Optimal facility location problem under stochastic construction cost and barriers. 16th Asia Pacific Management Conference, Kobe.

[11] Sasaki,Y. and Ishii,H. (2015) Facility location problem for supply center of school lunch. 17th Asia Pacific Management Conference, Seoul.