Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimisation
Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimisation
复制标题
DOI：
10.1080/17517575.2011.594910
复制
发表时间：
2012-08
影响因子：
4.4
通讯作者：
Qiang Liu;Chengen Wang
中科院分区：
文献类型：
--
作者：
Qiang Liu;Chengen Wang
计算机辅助布线设计对于复杂设备的开发具有重要意义。在本文中，在航空发动机集成设计工程的背景下，研究了具有多个终端的非直线分支管道布线，可以将其表述为带障碍的欧几里德施泰纳最小树（ESMTO）问题。与传统的按顺序连接管道终端的方法不同，本文提出了一种基于Steiner树理论的分支管道布线算法。本文首先提出了一种利用粒子群优化（PSO）求解ESMTO问题的新算法，然后利用测地线将该方法扩展到表面情况，以满足航空发动机表面非直线管道的布线要求。随后，采用自适应区域策略和基本可见图方法来提高计算效率。数值计算表明，所提出的路由算法可以在多项式时间内找到满意的路由布局。
Computer-aided design of pipe routing is of fundamental importance for complex equipments' developments. In this article, non-rectilinear branch pipe routing with multiple terminals that can be formulated as a Euclidean Steiner Minimal Tree with Obstacles (ESMTO) problem is studied in the context of an aeroengine-integrated design engineering. Unlike the traditional methods that connect pipe terminals sequentially, this article presents a new branch pipe routing algorithm based on the Steiner tree theory. The article begins with a new algorithm for solving the ESMTO problem by using particle swarm optimisation (PSO), and then extends the method to the surface cases by using geodesics to meet the requirements of routing non-rectilinear pipes on the surfaces of aeroengines. Subsequently, the adaptive region strategy and the basic visibility graph method are adopted to increase the computation efficiency. Numeral computations show that the proposed routing algorithm can find satisfactory routing layouts while running in polynomial time.