1-III_pm

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

Minimization of Land Compensation for Large-Scale Drone Airway Networks

○Shota Tabata¹, Takatoshi Arai², Kentaro Homma², Kotaro Imai² (1. Department of Architecture, The Univ. Tokyo, 2. Institute of Industrial Science, the Univ. of Tokyo)

Keywords:Steiner tree problem, weighted area, random Delaunay network, Voronoi diagram, large-scale drone

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.