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

DOI Web Site 被引用文献1件 参考文献10件

書誌事項

タイトル別名
  • A Heuristic for the Weighted Steiner Tree Problem by Using Random Delaunay Networks
  • Minimization of Land Compensation for Large-Scale Drone Airway Networks
  • 大型ドローン航空路網導入に伴う用地補償の最小化

抄録

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

収録刊行物

  • 都市計画論文集

    都市計画論文集 55 (3), 459-466, 2020-10-25

    公益社団法人 日本都市計画学会

被引用文献 (1)*注記

もっと見る

参考文献 (10)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ