講演番号[35]-[39]

[37] ランダムドロネー網を用いた重み付きシュタイナー問題の発見的解法

―大型ドローン航空路網導入に伴う用地補償の最小化

○田端 祥太¹、新井 崇俊²、本間 健太郎²、今井 公太郎² (1. 東京大学大学院工学系研究科建築学専攻、2. 東京大学生産技術研究所)

キーワード：シュタイナー問題、重み付き領域、ランダムドロネー網、ボロノイ図、大型ドローン

本研究は重み付きシュタイナー問題の発見的解法を開発する．重み付きシュタイナー問題は平面上の与点を連結するグラフの辺の総コストを最小化する問題である．本研究で構築する解法は，ランダムドロネー網を用いて連続平面を離散化し，与点のボロノイ図の双対グラフに含まれる全域木を探索する．木の辺は，ランダムドロネー網上の重み付き最短路で与えられる．近似解の形状と解の総コストの観点から，本手法が既往の重み付きシュタイナー木の発見的解法より厳密解に近い解が得られることを示す．さらに，重みの変化に対する木の形状の不連続な変化を把握する．最後に本手法を，新たな旅客，貨物輸送手段として期待されている大型ドローンの航空路網に適用し，本手法の実用性を検証する．