A discrete particle swarm optimization algorithm for rectilinear branch pipe routing

作者：Liu Qiang^*; Wang Chengen

来源：Assembly Automation, 2011, 31(4): 363-368.

DOI：10.1108/01445151111172952

• Aircraft engines
• Pipe routing
• Rectilinear paths
• Branches
• Particle swarm optimization
• Steiner tree
• Programming and algorithm theory

Purpose - The purpose of this paper is to develop a new rectilinear branch pipe-routing algorithm for automatic generation of rectilinear branch pipe routes in constrained spaces of aero-engines.
Design/methodology/approach - Rectilinear branch pipe routing that connects multiple terminals in a constrained space with obstacles can be formulated as a rectilinear Steiner minimum tree with obstacles (RSMTO) problem while meeting certain engineering rules, which has been proved to be an NP-hard and discrete problem. This paper presents a discrete particle swarm optimization (PSO) algorithm for rectilinear branch pipe routing (DPSO-RBPRA) problems, which adopts an attraction operator and an energy function to plan the shortest collision-free connecting networks in a discrete graph space. Moreover, this paper integrates several existing techniques to evaluate particles for the RSMTO problem in discrete Manhattan spaces. Further, the DPSO-RBPRA is extended to surface cases to adapt to requirements of routing pipes on the surfaces of aero-engines.
Findings - Pipe routing numeral computations show that, DPSO-RBPRA finds satisfactory connecting networks while considering several engineering rules, which demonstrates the effectiveness of the proposed method.
Originality/value - This paper applies the Steiner tree theory and develops a DPSO algorithm to plan the aero-engine rectilinear branch pipe-routing layouts.

• 出版日期2011
• 单位东北大学