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

DOI Web Site 1 Citations 10 References

Bibliographic Information

Other Title
  • ランダムドロネー網を用いた重み付きシュタイナー問題の発見的解法
  • Minimization of Land Compensation for Large-Scale Drone Airway Networks
  • 大型ドローン航空路網導入に伴う用地補償の最小化

Abstract

<p>This study develops a heuristic for the weighted Steiner tree problem, which is the minimization problem for the total edge cost of the graph interconnecting each terminal on a plane. This heuristic discretizes a plane by using a random Delaunay network and searches terminals’ spanning trees in a terminals’ Voronoi dual graph. Each edge on a tree is given by the weighted shortest path on a random Delaunay network. We show that this heuristic can get a closer result to the exact solution from the perspective of the tree shape and total cost than previous methods, and understand discontinuous changes in the tree shape due to weight changes. For the practicality verification of this heuristic, we apply it to the airway network of large-scale drones, which are poised to become a new passenger and logistics industry.</p>

Journal

Citations (1)*help

See more

References(10)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top