媒介変数表示される重みに対する最大後悔最小化1‑
センター問題に関する研究
著者 大勝 章平
URL http://hdl.handle.net/10236/00028896
2019 年度 修士論文要旨
媒介変数表示される重みに対する
最大後悔最小化 1- センター問題に関する研究
関西学院大学大学院理工学研究科 情報科学専攻 巳波研究室 大勝 章平
概要
近年，地震・津波・台風などの大規模な自然災害が世界的に頻繁に発生している．また日 本国内では今後３０年以内に70∼80%の確率で起こるとされている南海トラフ巨大地震 など，これからも大規模自然災害の発生が予想されている．それに伴い今後の避難計画に 関して，都市における避難施設配置は非常に重要な問題である．しかし，避難計画立案は 容易ではない．これは災害発生時における様々な不確定性が要因であり，より良い避難計 画を考える際にはこの不確定性は考慮するべきである．これに対してどのような状況に対 しても一定の効果を保証するような避難計画を事前に決定する手法がある．災害発生時の あらゆる人口分布に対して，避難完了時間が最悪の場合でも一定の効果が得られるように 避難施設を配置する問題である．本研究での人口分布はtに関する線形関数として表して いる．また複数の時刻帯に分け，それぞれで解を求めることでより複雑な人口分布を表現 することが可能である．本研究においては，この避難計画問題を無向グラフにおける最大 後悔最小化施設配置問題として定式化して考えた．特に，時刻tにおける施設配置点xの 配置コストを，重み付き1-センター問題に対応する「xに対する各頂点の最大重み付き距 離」とし，グラフがパスの場合について多項式時間アルゴリズムの設計を行った．
