8 周期的にサービスする施設の最適配置問題：定期市

8
周期的にサービスする施設の最適配置問題：
定期市問題
「利用者全体にとって最も便
利なように定期市を開くとした
ら、ｎ個の定期市場をどのよう
に配置すればよいか」
003057 鬼頭和久
施設配置の数理的最適化問題の観点から分析
（目次）




定期市問題の数学的定式化
・時間・距離コスト ⇒ 平均時間・距離コスト
・平均時間・距離コストの最小化の数学的問題
時空ボロノイ図
・線的地域に二つの市場がある場合
・平面地域の場合
平均時間・空間コスト最小化
・均一に利用者が住んでいる線的地域に二つの市場がある場合
・面的地域にｎ個の市場がある場合
定期市問題の一般化
・一般的時空・コスト関数
・サービス期間が長い場合
時間・距離コスト

時間的要因と距離的要因の兼ね合いを考える必要性がある。
距離のコスト+時間のコスト⇒時間・距離コスト
例１：
個人Aが市場に行くのを思い立った時点 t
一番近くに開かれる市場 i までの待ち時間 Ti(t)
個人Aの家 p から市場 i までの距離 d(p,pi)
待ち時間コストを距離時間コストに変換する定数 k （ kｋｍ / １日待ち)
時間・距離コスト＝C
⇒
C=kTi(t)+d(p,pi)
時間・距離コストの仮定



しかし、結局この関数形は人々の選択行動を観察して経験的に求め
なければならない。
ただし、時間・距離コストは
“利用者の位置p” “思い立ったときt” “市場iの位置pi”
“その市が開かれる最寄りの時点Ti”
ただし、ｋの値は単位のとり方によって変わる。
によっていると考えられる。
つまり待ち時間と距離の単位を適当に取ればk＝1とすることもできる。
それゆえに、Cをより明示的に C=(t,p;ti,pi)と表す。
式を簡略化するために、これ以降、k＝1とすることにする。
ここからは
C(t,p;ti,pi)=｛k^(2)Ti(t)^(2) +d(p,pi)^(2)｝^(1/2)
と仮定して話を進めていく。
平均時間・距離コスト


一利用者だけのことでなく、利用者全体の利便性こそが問題なので、全利用者に
わたった時間・距離コストの平均を求める必要がある。
そのために、ここでいくつかの仮定を加える。
・周期の仮定「もっとも単純な、市場1が開かれたs日後に市場2が開かれ、そのs日
後に市場3が・・・という場合を考える。」
⇒ ns (n=2,n=5,・・・)
・利用者がいつ市場に行くの思い立つか「たくさんの利用者をまとめて見れば、いつ
でもある一定程度の人数が思い立つと予測できる。」
⇒ 単位時間、単位あたり a
・市場の開かれる期間「市場の開かれている期間は、開かれていない期間と比較
ただし、このaの値は、ｋの値と同じく単位のとり方で変わってくるので
するときわめて短く、大局的に見れば無視できると仮定する。」
⇒ （市場の場合は）無視
単位を適当に選んでa=1と単純化しておく。
・利用者の分布「いままで通り、利用者密度関数f(x,y)で表す。」
⇒ f(x,y)
平均時間・距離コストの定式化



地点p=(x,y)を中心とする辺の長さが⊿x,⊿yからなるきわめて小さな地区に居る利用
者について考える。
利用者数＝f(x,y)⊿x⊿y
時点tからt+⊿tまでのきわめて短い期間に市場へ行くことを思い立つ利用者数
＝af(x,y)⊿x⊿y⊿t
⇒ ここでa=1と置けるので、 f(x,y)⊿x⊿y⊿t
そして、それぞれの市場までの時間・距離コストの集まり
{C(t,p;t1,p1)}, {C(t,p;t2,p2)}, ・・・,{C(t,p;tn,pn)}
を簡略化して{C(t,p;ti,pi)}と表した上で、この集まりの中の最小値を
min{C(t,p;tn,pn)} と書くとする。すると
地点pを中心とする微小地域区にいる利用者たちの中で
時点tからt+⊿tまでの間に市場へ行くのを思い立つ者たちの総時間・距離
コストは
min{C(t,p;ti,pi)}f(x,y) ⊿x⊿y⊿t
で表される。
平均時間・距離コストの定式化（2）

時点tからt+⊿tまでの間に地域全体(S)で市場に行くことを思い立つ利用者達の総
時間・距離コストは、第３章式（3.4）のやり方で
∬min{C(t,p;ti,pi)}f(x,y)dxdy⊿t と表せる。

時間にわたる総時間・距離コストについては、第３章式(3.4)で表される縮小期間の
総時間・距離コストを一定期間にわたってたし合わせればよい。（この場合はn個
の市の周期である、期間nsの間だけ考えればよい。）
∫∬min{C(t,p;ti,pi)}f(x,y)dxdydt この積分式で求められる。
最後に、平均時間・距離コストを求める。
これは上の式の値を、全利用者数Nと１周期の長さnsで割ることで得られる。
しかしNnsは定数で、この値は単位を適当に選ぶとNns=1とすることができるから、
結局上の式を平均時間・距離コストと見なすことができる。
（これ以降においては上の式を平均時間・距離コストとして扱う。）
平均時間・距離コストの最小化の数学的問題



前ページで与えられた平均時間・距離コストは、n個の市場の配置
（xi,yi),i=1,2,…,nが変わるともちろん変わる。
それでは、「平均時間・距離コストが最小となる配置はどのような配置だ
ろうか。」
これこそまさに最初に提起された問題である。すなわち、
最初の問題を次のような数学的問題として定式化できる。
平均時間・距離コストを最小化する配置問題
⇒min∫∬min[{T(t,ti)^2+d(p,pi)^2}^(1/2)]f(x,y)dsdydt
（この式を α式と置く。）
施設配置の数理的最適化問題の観点から分析




定期市問題の数学的定式化
・時間・距離コスト ⇒ 平均時間・距離コスト
・平均時間・距離コストの最小化の数学的問題
時空ボロノイ図
・線的地域に二つの市場がある場合
・平面地域の場合
平均時間・空間コスト最小化
・均一に利用者が住んでいる線的地域に二つの市場がある場合
・面的地域にｎ個の市場がある場合
定期市問題の一般化
・一般的時空・コスト関数
・サービス期間が長い場合
線的地域に二つの市場がある場合




地域がx軸上の線分(0≦x≦1)で表される。
二つの市場1,2があり、それぞれの位置がx1,x2。
二つの市場はそれぞれ一定周期2sで開かれる。
この時間的・空間的位置を表現するために
時空平面を使用する。
時空ボロノイ図


このようにして得られた図形は、第２章で示したものとは少々異なるが、
やはりボロノイ図の一種といえよう。
このボロノイ図は、時間と空間でのボロノイ図であるから便宜的に、時空
ボロノイ図と呼ぶことにする。
時空ボロノイ図を使うと、8ページのα式は、次のように表すことができる。
min∑∬{(is-t)^(2)+(x-x1)^(2)}^(1/2)f(x)dsdt
（この式を β式と置く。）
平面地形の場合
平面地域の場合も、線的地域の場合とまったく同じ方法で時空ボロノイ図
を得られる。
この時空ボロノイ図を使うと、8ページのα式は次のように表せる。


平均時間・距離コストを最小化する配置問題
min∑∫∬{(is-t)^(2)+(x-x1)^(2)+(y-y1)^(2)}f(x,y)dxdydt


この式を第３章の問題8.4、式（3.7）と比べてみると、こちらの方が変数が
一つ増えて（t）いることに気づく。
しかし両式の形式を比べてみると、どちらも[距離]・[利用者密度]をボロノ
イ多角形にわたって、たし合わせた式である。数学的には、両式とも同じ
形式であることがわかる。
施設配置の数理的最適化問題の観点から分析




定期市問題の数学的定式化
・時間・距離コスト ⇒ 平均時間・距離コスト
・平均時間・距離コストの最小化の数学的問題
時空ボロノイ図
・線的地域に二つの市場がある場合
・平面地域の場合
平均時間・空間コスト最小化
・均一に利用者が住んでいる線的地域に二つの市場がある場合
・面的地域にｎ個の市場がある場合
定期市問題の一般化
・一般的時空・コスト関数
・サービス期間が長い場合
均一に利用者が住んでいる線的地域に
二つの市場がある場合

この場合の問題は、12ページのβ式
でf(x)=1とした場合である。したがってこの式の最小値は、この代数
式の最小値を第３章,∮3.4.1の場合と同じ方法で求めればよい。
さて、答えはどうなるか？極端な場合を考えると・・・
①一日でも多く待つくらいなら、遠くに行くのはいとわない場合
⇒あたかも１つの市が半分の周期で開いているようにすればよい。
②一歩でも遠く歩くくらいなら、待つのはいとわない場合
⇒時間的要因を無視して２つの市場を空間的にのみ最適配置すれ
ばよい。
⇒∮3.4.1で示したように、市場を1/4・3/4の地点に配置すればいい。
均一に利用者が住んでいる線的地域に
二つの市場がある場合（２）

これら両極端の間の最適配置は、ｋの値、すなわち時間に対し距離を
どのくらい重視するかの度合いによって変わってくる。
・k=0の場合、前ページで推測されたようにx1=1/4, x2=3/4となる。
・kの値が大きくなるにつれて、二つの市場の最適位置は中央へ。
・そしてkの値がある値を超えると、突然、x1=x2=1/2となる。
これは待ち時間に対する距離重視の度合いがある限界を超えると
二つの市場を中央に配置するのが最適であることを示している。
↑参考に、テキストにあるグラフを表示します。
面的地域にｎ個の市場がある場合



前ページまでの単純な問題と違い、このような場
合は解析的方法で解くことができない。
解析的方法がとれないので、
ここでは探索的方法をとらざるをえない。
ここでの探索的方法については、第３章で扱わ
れていた方法とほぼ同じものである。
施設配置の数理的最適化問題の観点から分析




定期市問題の数学的定式化
・時間・距離コスト ⇒ 平均時間・距離コスト
・平均時間・距離コストの最小化の数学的問題
時空ボロノイ図
・線的地域に二つの市場がある場合
・平面地域の場合
平均時間・空間コスト最小化
・均一に利用者が住んでいる線的地域に二つの市場がある場合
・面的地域にｎ個の市場がある場合
定期市問題の一般化
・一般的時空・コスト関数
・サービス期間が長い場合
一般的時間・空間コスト関数




時間・距離コスト関数は四ページ目において｛k^(2)Ti(t)^(2) +d(p,pi)^(2)｝^(1/2)
と仮定してきたが他の関数の方がよいかもしれない。
たとえば三ページ目の「C=kTi(t)+d(p,pi)」
この場合、時間・距離コストは、時空空間で表すと、マンハッタン距離となる。（こ
れを応用するとマンハッタン距離の時空ボロノイ図が得られる）
この時空ボロノイ図を使うとこれまでと同じような方法で最適配置を求められる。
・より一般的には、時間・距離コスト関数で表される距離を直線距離に代えて
解けばよい。この場合、第２章で述べられた一般ボロノイズを適用することになる。
・そのような場合でも、基本的には、これまでとほぼ同じような方法で最適配置を
求めることができるであろう。
↑参考
マンハッタン距離の時空ボロノイ図のテキスト例
サービス期間が長い場合


施設によってはサービス期間がある一定期間にわたって続くような場合もある
このような問題を解くには、点の時空ボロノイ図を線の時空ボロノイ図へと一般
化すればよい。このボロノイ図を使うことで、これまで示してきたものと同じような
方法で最適配置を求めることができよう。
←参考
線の時空ボロノイ図
のテキスト例

Download Report