A Heuristic for the Weighted Steiner Tree Problem by Using Random Delaunay Networks

A Heuristic for the Weighted Steiner Tree Problem by Using Random Delaunay Networks
复制标题

使用随机 Delaunay 网络启发式求解加权 Steiner 树问题

DOI：
10.11361/journalcpij.55.459
复制
发表时间：
2020
期刊：
Journal of the City Planning Institute of Japan
影响因子：
--
通讯作者：
今井 公太郎
今井 公太郎
中科院分区：
--
文献类型：
--
作者：
田端 祥太;新井 崇俊;本間 健太郎;今井 公太郎

文献摘要

相似文献

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