災害時避難誘導システムにおける最速避難経路決定問題

摘要

2011年に起こった東日本大震災により，人々の防災意識が高まってきている．また，災害発生時に迅速に避難所へ避難することは災害による犠牲者を減らすうえで非常に重要である．地方公共団体などでは住民に避難所の位置や津波や地震などの災害でどのような被害が想定されるかを提示しているに過ぎず，災害発生時，様々な場所にいる人々が各々どのような経路で避難したらよいかがわからない．したがって，交通網の状況と避難所の位置，被災者数に応じて迅速に避難経路を決定しナビゲーションするシステムが必要である．災害時以外にも花火大会やコンサートなど群衆が狭い領域に密集している状態は危険であり適切な誘導が必要である．本稿ではこの適切な避難経路へ誘導する問題を最速避難問題として定式化し，NP完全性を証明した．さらに距離だけでなく，混雑を考慮に入れたうえで避難経路を決定するアルゴリズムを提案した．