Abstract: Euclidean Steiner minimum tree problem, a classical NP-hard problem in combination optimization, has been widely studied in many fields. Euclidean Steiner minimal tree problem in 3-space is the generalization of Euclidean Steiner minimum tree problem in 2-space. The research results on Euclidean Steiner minimal tree problem in 3-space have been rarely published because of their difficulties. In this paper, a hybrid intelligent method is designed by using Delaunay tetrahedron mesh generation technology to solve the Euclidean Steiner minimal tree problem in 3-space, which can not only avoid falling into local optima, but also has good effects in solving large scale problems. Promising results are obtained by using this hybrid method coded in MATLAB to solve series of Euclidean Steiner minimum tree problem instances in 3-space.

Key words: euclidean steiner minimum tree problem in 3-space, delaunay tetrahedron mesh generation, convex polyhedron decomposition, intelligent algorithm

摘要： Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。

关键词: 三维欧氏Steiner最小树, Delaunay四面体网格, 凸多面体剖分, 智能算法