動線を最適化する平面計画問題に対する効率的な組合せ最適化アルゴリズムの研究

点击翻译按钮获取中文摘要

本年度は,動線を最適化する平面計画問題として,大規模災害時に住民を迅速に避難させる問題をモデル化した動的ネットワーク上の避難計画問題と,都市における避難において優先的に確保すべき道路を決定する問題や避難地図を作成する問題をモデル化した有向グラフ上の有向木問題の研究を行い,以下の成果を得た.まず,避難計画問題に関する成果を説明する.避難計画問題では,最後にシンクに到着する人の避難完了時間を最小にするフローを求めることを目的としているが,現実問題としては任意の時刻において可能な限りの人がシンクに到着しているような最速フローが望ましい.この問題に対して,本研究では,現実のモデル化の際に頻出する全ての辺の容量が一定のグリッド構造ネットワークを一般化したネットワークに対する多項式時間アルゴリズムを開発することに成功した.次に,有向グラフ上の有向木問題に関する成果を説明する.まず,都市ネットワークにおける避難地図を作成する問題をモデル化した有向木被覆問題に対する多項式時間アルゴリズムを開発した.さらに,この有向木被覆問題をさらに一般化した,避難地図の総長を最小化する問題に関しても,部分的な場合に対して多項式時間アルゴリズムを開発した.都市における避難において優先的に確保すべき道路を決定する問題をモデル化した有向木詰込問題に関しては,単に辺素な有向木を詰め込むだけではなく,各点から根に向かう辺に関して点素であるような一般化された問題を扱い,本研究では,いくつかの場合に対してそのような有向木が存在する必要十分条件を明らかにし,同時にそのような有向木を見つける多項式時間アルゴリズムも与えた.