| 学籍番号 | 90109080 | 所属研究室 | 藤重研 |
| 氏名 | 斎 藤 秀 樹 | ||
| タイトル | グリッド状のネットワークにおけるミニマックスリグレットメディアン配置問題 | ||
|
1. 序論 入力データに不確かさをもった組合せ最適化問題の扱いの一つとして最悪ケースアプローチがあり，ミニマックスリグレットという指標を使うこと ができる．本研究では1-メディアン問題の最悪ケースアプローチを扱う． Averbakh--Berman [1]は，一般のグラフにおけるミニマックスリグレットメディアンを解く多項式時間アルゴリズムを提案している． 本研究では，特にグリッド（格子）状のネットワークにおける問題についての，高速アルゴリズムについて提案する． 2. 1-メディアン問題 本論文ではグラフは頂点集合Vと枝集合Eをもった無向グラフG=(V,E)を用いる. |V|=n,~|E|=mと表記する．また枝を線分とみなし，線分上の点も含めたネットワーク上すべての点集合をGを用いて表す．さらにGの各枝に対し非負の枝長l: \rightarrow R_{+}を,各頂点には非負の重みw:V \rightarrow R_{+}を与えられたものをネットワークと考える． またグラフG上の2点p,q\in G間の最短路の長さをd(p,q)と表すことにする．ここで以下に1-メディアン問題 1-MEDを定義する． 1-MED Find y\in G that minimizes F(y). ここで，F(x) = \sum_{v\in V}w_{v}d(v,x)である. またこの問題の基本的な性質として,以下の事実が知られている. 定理1 1-メディアン問題は常に頂点に最適解を持つ． また本研究で扱うグリッド状のグラフとは, 2次元空間の整数格子点の部分集合に対応する頂点集合を持ち, 一つの座標値が同じで, もう一つの座標値がちょうど 1 だけ違う頂点間すべてに枝長 1 の枝を持つグラフである. 3. ミニマックスリグレット1-メディアン問題 グラフG=(V,E)と各頂点に対する重みの上限w^{+}: v \rightarrow R_{+},下限w^{-}: v \rightarrow R_{+}が与えられた時,ミニマックスリグレット1-メディアン問題ROBMEDを ROBMED \min_{x\in G}\max_{w \in WW}\max_{y\in G}\{ F(w,x)-F(w,y)\} と定義する.但し,w^{-}(v)\leq w^{+}(v)を前提とし,WW=\{w\in R^{v}|w^{-}(v) \leq w(v) \leq w^{+}(v)(v\in V)\},およびF(w,x)=\sum_{v\in V}w_{v}d(v,x)とする. ここで任意の2点にy,x\in Gに対する最適化問題, \max_{w\in WW}\{F(w,x)-F(w,y)\} を定義し,最適値をREGR(x,y)とすれば,REGR(x,y)は配置x,yに関する目的関数値の最大可能差,つまり,配置yに対する配置xの最悪ケースリグレットとなる.ここでシナリオw^{*}(x,y)~=~\{w_{v}^{*}(x,y):v\in V\}を以下に定義すれば，これは明らかに(3)の最適解である． w_{v}^{*}(x,y) = w_{v}^{+} (if~d(x,v)~\geq~d(y,v)) w_{v}^{-} (if~d(x,v)~<~d(y,v)) 4.~ アルゴリズム 本研究では[1]のアルゴリズムに基づいてグリッド状のグラフにおけるミニマックスリグレットメディアン問題のアルゴリズムを提案する.その概要は以下の通りである． 基本的には一つの枝上に限定した問題ROBMEDを解いて,得られた各枝上の最適解の中から最良のものをROBMEDの解として採用するという方法である． ある特定のy\in Vに対するREGR(x,y)の値は，xがある枝上を動くとき線形関数となる．一つの枝上のROBMEDは，定理1により， 各y\in Vに対応したn個の線形関数の最大値が最も小さくなる枝上の点を求める問題となる．このn個の関数を求めるために, すべての頂点のペアx, yに対するREGR(x,y)の値が必要となる. 本研究のアルゴリズムのポイントは，同一のyに対するxとその隣接点x^{'}の最悪ケースシナリオの違いがほとんど無いことを利用して，REGR(x,y)の時の計算の結果からREGR(x^{'},y)の計算を効率的に行うというところである． これらの工夫により, r×cのグリッド状のグラフのミニマックスリグレットメディアンをO(\min\{c^{2}r^{3},c^{3}r^{2}\})で求められるアルゴリズムが得られた.[1]のアルゴリズムを適用した場合のO(c^{3}r^{3}\log{cr})より高速であるといえる． 参考文献 [1] I.~Averbakh and O.~Berman: Minmax Regret Median Location under Uncertainty, INFORMS Journal on Computing J81-A (2000) 104--110. |
|||