分支管路的布局优化属于NP难问题，其多目标优化情况则更加复杂。针对航空发动机分支管路多目标敷设问题，以分支管路长度最小化、分支点数量最小化以及管路平滑度最优为优化目标，建立了基于避障Steiner树的分支管路多目标布局模型。考虑到模型的复杂性，设计基于多目标粒子群优化（Multi-objective particle swarm optimization，MOPSO）的模型求解算法。其中，以分支点数量和坐标作为决策变量；针对分支管路拓扑结构特点，提出一种分支管路平滑度计算方法，结合非支配排序和网格密度计算完成个体多目标评价；通过可视图和测地线处理约束条件；通过多目标粒子群进化计算求得Pareto解集。所建立的分支管路多目标布局模型及求解算法考虑了多端点情况、多目标优化以及避障约束。最后通过管路敷设算例验证了可行性。
The layout optimization of branch pipe is a NP hard problem, and the multi-objective case of which is more complex. The branch pipe routing problem is studied in the context of an aero-engine development, and a model of multi-objective routing for branch pipes is constructed based on Steiner tree, where pipe length, the number of branch points and pipeline smoothness are taken into consideration as optimal objectives. Considering the complexity of the problem, a multi-objective particle swarm optimization (MOPSO)-based layout method is designed to solve the constructed routing model. More specifically, the number and coordinates of branch points are selected as decision variables; according to the characteristic topological structure of branch pipes, a computation model of smoothness is presented, and the multi-objective evaluation is then completed by non-dominated sorting and grid density calculation; in addition, the visibility graph method and geodesic are integrated to handle routing constraints; The Pareto solution set is obtained through particle evolution. The presented routing model and method consider the cases of multiple pipe terminals, multi-objectives and obstacle-avoidance constraints. Finally, the feasibility of the proposed method is demonstrated by several numerical computations of branch pipe routing examples.
[1] LEE C Y. An algorithm for path connections and its application[J]. IRE Transactions on Electronic Computer,1961,10(3):346-364.
[2] WANG C E,LIU Q. Projection and geodesic-based pipe routing algorithm[J]. IEEE Transactions on Automation Science and Engineering,2011,8(3):641-645.
[3] 赵柏萱,刘检华,宁汝新,等. 一种基于工程规则的管路自动布局与综合优化技术[J]. 机械工程学报,2015, 51(21):121-131. ZHAO Boxuan,LIU Jianhua,NING Ruxin,et al. An automatic pipe routing and optimization technology based on engineering constraints[J]. Journal of Mechanical Engineering,2015,51(21):121-131.
[4] VELDEN C V D,BIL C,YU X H,et al. An intelligent system for automatic layout routing in aerospace design[J]. Innovations in Systems and Software Engineering,2007,3(2):117-128.
[5] LIU Q,WANG C E. A graph-based pipe routing algorithm in aero-engine rotational space[J]. Journal of Intelligent Manufacturing,2015,26(6):1077-1083.
[6] ITO T. A genetic algorithm approach to pipe route path planning[J]. Journal of Intelligent Manufacturing, 1999,10(1):103-114.
[7] 付宜利,封海波,孙建勋,等. 机电产品管路自动敷设的粒子群算法[J]. 机械工程学报,2007,43(11):194-199. FU Yili,FENG Haibo,SUN Jianxun,et al. Automatic pipe-routing particle swarm optimization algorithm in electromechamical products[J]. Chinese Journal of Mechanical Engineering,2007,43(11):194-199.
[8] REN T,ZHU Z L,DIMIROVSKI G M,et al. A new pipe routing method for aero-engines based on genetic algorithm[J]. Proceedings of the Institution of Mechanical Engineers,Part G:Journal of Aerospace Engineering,2014,228(3):424-434.
[9] PARK J H. Pipe-routing algorithm development for a ship engine room design[D]. Washington:University of Washington,2002.
[10] 樊江. 航空发动机外部管路多代理协同设计系统研究[D]. 北京:北京航空航天大学,2003. FAN Jiang. Research on MAS based distributed cooperative aeroengine outside pipe system design[D]. Beijing:Beihang University,2003.
[11] ASMARA A,NIENHUIS U. Automatic piping system in ship[C]//International Conference on Computer and IT Application(COMPIT),May 8-10,2006,Delft,Netherlands. 2006:269-280.
[12] 邬君. 基于协同进化的船舶分支管路空间布局优化[D].大连:大连理工大学,2008. WU Jun. Coevolutionary optimization algorithm for ship branch pipe routing[D]. Dalian:Dalian University of Technology,2008.
[13] 白晓兰,王成恩,张禹,等. 三点间管路布局方法研究[J]. 东北大学学报,2009,30(2):283-286. BAI Xiaolan,WANG Chengen,ZHANG Yu,et al. On the automatic route layout for connection of three pipeline terminals[J]. Journal of Northeastern University,2009,30(2):283-286.
[14] LIU Q,WANG C E. Multi-terminal pipe routing algorithm by steiner minimal tree and particle swarm optimization[J]. Enterprise Information Systems,2012,6(3):315-327.
[15] JIANG W,LIN Y,CHEN M,et al. A co-evolutionary improved multi-ant colony optimization for ship multiple and branch pipe route design[J]. Ocean Engineering, 2015,102:63-70.
[16] SUI H T,NIU W T. Branch-pipe-routing approach for ship using improved genetic algorithm[J]. Frontiers of Mechanical Engineering,2016,11(3):316-323.
[17] QU Y, JIANG D, YANG Q. Branch pipe routing based on 3D connection graph and concurrent ant colony optimization algorithm[J]. Journal of Intelligent Manufacturing,2016:1-11.
[18] PROVAN J S. An approximation scheme for finding steiner trees with obstacles[J]. SIAM Journal of Computing,1988,17(5):920-934.
[19] 周培德. 计算几何-算法设计与分析[M]. 4版. 北京:清华大学出版社,2011. ZHOU Peide. Computational geometry-algorithm design and analysis[M]. 4th ed. Beijing:Tsinghua University Press,2011.
[20] 公茂果,焦李成,杨咚咚,等. 进化多目标优化算法研究[J]. 软件学报,2009,20(2):273-289. GONG Maoguo,JIAO Licheng,YANG Dongdong,et al. Research on evolutionary multi-objective optimization algorithms[J]. Journal of Software,2009,20(2):273-289.
[21] COELLO C A C,PULIDO G T,LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(3):256-278.
[22] 范培蕾,杨涛,张晓今. 基于角度坐标的多目标粒子群优化算法[J]. 系统工程与电子技术,2010,32(8):1750-1753. FAN Peilei,YANG Tao,ZHANG Xiaojin. Method of multi-objective particle swarm optimization based on angular coordinates[J]. Systems Engineering and Electronics,2010,32(8):1750-1753.
[23] KENNEDY J,EBERHART R C. Particle swarm optimization[C]//IEEE International Conference on Neural Networks,1995.Perth,Australia. 1995,4:1942-1948.
[24] DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transaction on Evolutionary Computation,2002,6(2):182-197.
