[2I5-OS-9b] AIと制約プログラミング

[2I5-OS-9b-04] ZDDによる災害時の効率的かつ網羅的な広報車巡回路の列挙

〇原田 そら¹、石畠 正和² (1. 木更津工業高等専門学校、2. NTT コミュニケーション科学基礎研究所)

キーワード：ZDD、巡回路列挙、グラフアルゴリズム、フロンティア法

災害時における地域住民への情報伝達は、避難誘導や支援物資の配布など、重要な役割を果たす。そのため通信インフラが災害により被害を受けた場合、人手での情報伝達が試みられる。例えば、2019年の台風15号では長期にわたり電力網や通信が寸断し、自治体は広報車を巡回することで情報伝達を行った。
災害時の情報伝達では、緊急性や人的コストに関わる効率性と、公共的な情報を全住民へと伝える網羅性の双方を考慮する必要がある。また、災害による道路状況の変化を考慮し、安全な巡回路を能動的に選ぶ必要がある。
本研究では、効率的かつ網羅的な巡回路を表現するZDDの構築手法を提案する。ZDDとは集合族の効率的なグラフ表現であり、様々なグラフの部分集合を効率的に扱うために利用されている。本研究では、巡回路の効率性と網羅性をグラフ制約として表現し、それらの制約を満たすグラフ集合を表現するZDDを効率的に構築する。また、提案手法を実際の地理データに適用し、得られた経路の効率性や網羅性を評価する。