| 学籍番号 | 90119158 | 所属研究室 | 藤重研 |
| 氏名 | 間々田 聡 子 | ||
| タイトル | 動的ネットワークフローと最速輸送問題 | ||
|
1.序論 物資輸送網等における問題を考える際には，ネットワークモデルが用いられる． 輸送問題において物の輸送時間を考慮するネットワークを動的ネットワークという. 本研究では，特に動的ネットワーク中のいくつかの供給点から需要点への定まった 量を最短時間で輸送する問題（これを最速輸送問題という）について考察する． さらに，Hoppe-Tardosの論文中のアルゴリズムを紹介し， さらにその応用例としてビル退避モデルの最適化とその解法について考察する． 2.最速輸送問題 Aはm本の枝集合，Vはn個の点集合，uは各枝に非負の実数を与える容量関数， τは輸送時間を与える整数値関数，Sは定められたk個の点集合であるとする． このようなネットワークを N=(G=(V,A),u,τ,S)と表す． 以下，静的フローと静的循環フローを従来の意味でのフローと循環フローとして扱う． フローfは容量条件および歪対称性条件を満たすと仮定する． 以上のようなネットワークを用いて，次の問題を考える． 動的輸送問題:(N,v,T)が与えられているとき，T時間で各始点や終点xにおける 供給量(あるいは需要量)を満たす動的フローを求める問題． 最速輸送問題:Sに含まれる各点に対して供給量(あるいは需要量)が与えられて いるとき，動的輸送問題(N,v,T)が実行可能となるような最小な時間T，および それを達成する動的フローを求める問題． 最速輸送問題で終点が１つという特別な場合が，ビル退避問題として考察されている． 3.アルゴリズム 動的輸送問題の実行可能性を判定する問題，最速輸送問題の ２つの問題に対する強多項式アルゴリズムを紹介する． ここで使う記号を次のように定義する． Sの部分集合をU，Uの供給量の合計をv(U)，Uの中の始点からS/Uの中の終点へ 他の点の需要量を気にせずに時間Tまでに流すことのできる最大流量を o(U)，点がn個，枝がm本のネットワークで最小費用 フローを求めるのにかかる時間をMCF(m,n)とする．また o(U)< v(U)のとき，U を不当であるとよぶ． 動的輸送問題の実行可能性を特徴づけるつぎの定理が成り立つ． 定理3.1: 動的輸送問題が実行可能であるための必要十分条件は，どんな部分集合 U/Sに対してもo(U) ≧ v(U) $が成り立つことである． つぎの定理により，動的輸送問題の実行可能性が多項式時間で解けることが示される． 定理3.2: 動的輸送問題の不当な集合を強多項式時間，あるいはO(2^kMCF(m,n)), またはO(k^2MCF(m,n)log(nTu{max}))時間で見出すことができる． また，最速輸送問題(N,v)を解くためには，動的輸送問題(N,v,T)が実行可能 であるような最小時間Tを求めなければならない．これは，2分探索法と定理 3.2を使うことによって多項式時間で解くことができる． 2分探索法を使うためには，最短時間Tの上限を知る必要がある．定理 3.1より，始点集合S^+から終点集合S^-へv(S^+)単位のフローを流すのに， 最速でT時間かかるような集合が存在する． これは始点と終点が１つずつの避難問題と考えることができる．従って，この 問題に対する上限は，最速輸送問題に対する上限である． 4.ビル退避モデル 最速輸送問題を応用して，ビル退避モデルについて考える． いま，(N,v)が与えられている．このとき，終点を１つ定め，どの点が 終点の場合に，与えられたvを最も速く流すことができるかを考える． この問題に対して，最短時間を２分探索法で見出すことによって， 多項式時間アルゴリズムを構成することができる． この問題の最適な点の全体は連結な誘導部分グラフ と予想されるが，これについて考えるのは今後の課題である． 参考文献 .Hoppe and .Tardos: The quickest transshipment problem. Mathmatics of Operations Research, 25 (2000) 36-62. |
|||