基于终端斯坦纳树的高效多分支线束自动布局方法

doi:10.3901/JME.2025.14.410

摘要/Abstract

摘要： 多分支线束布局具有数据量大、复杂度高等特点，难兼顾布局效率和质量。针对航空电气线路互联系统(Electrical wiring interconnection systems, EWIS)多分支线束自动布局问题，提出一种基于最小终端斯坦纳树(Terminal Steiner minimal tree，TSMT)的多分支线束自动布局方法。该方法首先根据接线终端坐标，构建连接所有接线终端的TSMT，将其中的斯坦纳点确立为线束分叉点，从而获得线束的初始布局拓扑。之后代入实际布线环境并以线束形态和线束总重为优化目标，使用改进粒子群算法优化调整分叉点位置，其中利用TSMT的先验知识辅助粒子编码、结合遗传算法优化粒子搜索策略和采用粗粒度并行改进粒子计算流程，从而提高优化效率和质量。与全过程迭代类方法相比，所提方法计算效率提高了83.8%，布局质量改进了15.2%，证明了所提方法的可行性。

关键词: 航空电气线路互联系统, 多分支线束, 自动布局, 最小终端斯坦纳树, 粒子群算法

Abstract: The layout of multi-branch cable harness has the characteristics of large amount of data and high complexity, and it is difficult to balance layout efficiency and quality. To solve the problem of the automatic layout of multi-branch cable harness in aviation electrical wiring interconnect system(EWIS), an automatic layout method based on terminal Steiner minimal tree(TSMT) is proposed. Firstly, the method constructs the TSMT connecting all wiring terminals according to their coordinates. The initial layout topology of the cable harness is obtained by establishing the Steiner point as the bifurcation point. Then, substituting into the actual wiring environment and taking the shape and the total weight of the cable harness as the optimization target, the position of the bifurcation point is optimized by the particle swarm optimization algorithm(PSO). During this process, the prior knowledge of TSMT is used to assist particle coding, the genetic algorithm is combined to optimize particle search strategy and the coarse-grained parallel is used to improve particle calculation process, so as to improve the optimization quality and efficiency of the algorithm. Compared with the whole-process iterative method, the calculation efficiency of the proposed method is increased by 83.8%, and the optimization effect is increased by 15.2%, which prove the feasibility of the proposed method.

Key words: electrical wiring interconnect system, multi-branch harness, automatic layout, terminal Steiner minimal tree, particle swarm optimization

中图分类号:

TP391

孙浩, 原野, 张琦, 张小贝. 基于终端斯坦纳树的高效多分支线束自动布局方法[J]. 机械工程学报, 2025, 61(14): 410-421.

SUN Hao, YUAN Ye, ZHANG Qi, ZHANG Xiaobei. Efficient Automatic Layout Method of Multi-branch Cable Harness Based on Terminal-SMT[J]. Journal of Mechanical Engineering, 2025, 61(14): 410-421.

参考文献

[1] 龙娟，杨硕，杨阳. EWIS数字化设计流程优化[J]. 飞机设计，2020，40(1):5-7. LONG Juan，YANG Shuo，YANG Yang. EWIS digital design process optimization[J]. Aircraft Design，2020，40(1):5-7.
[2] 王发麟，廖文和，郭宇，等. 复杂机电产品中线缆敷设质量控制及模糊综合评判[J]. 计算机集成制造系统，2017，23(3):515-524. WANG Falin，LIAO Wenhe，GUO Yu，et al. Quality control and fuzzy comprehensive evaluation of cable harness wiring in complex mechatronic products[J]. Computer Integrated Manufacturing Systems，2017，23(3):515-524.
[3] 孔瑞莲. 航空发动机可靠性工程[M]. 北京:航空工业出版社，1996. KONG Ruilian. Aero engine reliability engineering[M]. Beijing:Aviation Industry Press，1996.
[4] 李小宁，高朝晖，王爽，等. 飞机主电源系统关键器件健康状态评估研究[J]. 电气工程学报，2023，18(4):188-198. LI Xiaoning，GAO Zhaohui，WANG Shuang，et al. Research on health assessment method of key components in aircraft main power system[J]. Journal of Electrical Engineering，2023，18(4):188-198.
[5] 刘潇，刘检华，刘佳顺，等. 基于改进RRT算法的线缆自动布线技术[J]. 机械工程学报，2015，51(17):96-105. LIU Xiao，LIU Jianhua，LIU Jiashun，et al. Improved RRT based cable automatic routing[J]. Journal of Mechanical Engineering，2015，51(17):96-105.
[6] 吴宏超，刘检华，唐承统，等. 基于改进A^*算法的管路自动布局设计与优化方法[J]. 计算机集成制造系统，2016，22(4):945-954. WU Hongchao，LIU Jianhua，TANG Chengtong，et al. Automatic pipe layout design and optimization method based on improved A^* algorithm[J]. Computer Integrated Manufacturing Systems，2016，22(4):945-954.
[7] 姜康，马世纪. 基于改进A^*算法的线缆路径规划方法[J]. 中国机械工程，2019，30(6):699-708. JIANG Kang，MA Shiji. Cable path planning method based on improved A^* algorithm[J]. China Mechanical Engineering，2019，30(6):699-708.
[8] 李国闻，张丹，杜海遥，等. 基于遗传算法的机电产品布线结构优化设计方法[J]. 中国科技论文，2015，10(16):1944-1948，1952. LI Guowen，ZHANG Dan，DU Haiyao，et al. Configuration optimization for electromechanical products cable harness design based on genetic algorithm[J]. China Sciencepaper，2015，10(16):1944-1948，1952.
[9] ZHU Z，ROCCA G L，TOOREN M J L V. A methodology to enable automatic 3D routing of aircraft electrical wiring interconnection system[J]. CEAS Aeronautical Journal，2017，8(2):287-302.
[10] LIU H，SHAN T，WANG W. Automatic routing study of spacecraft cable based on A-star Algorithm[C]// 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference，June 12-14，2020，Chongqing，China. New York:IEEE，2020:716-719.
[11] CONRU A B. A genetic approach to the cable harness routing problem[C]// Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence，June 27-29，1994，Orlando，FL，USA. New York:IEEE，1994:200-205.
[12] LIN C W，RAO L，GIUSTO P，et al. Efficient wire routing and wire sizing for weight minimization of automotive systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2015，34(11):1730-1741.
[13] 徐金宝，刘检华，刘佳顺，等. 基于SMT和LDOB-PRM算法的分支线缆自动布局设计方法[J]. 计算机集成制造系统，2016，22(9):2099-2107. XU Jinbao，LIU Jianhua，LIU Jiashun，et al. Multi-branch cable automatic routing by SMT and LDOB-PRM algorithms[J]. Computer Integrated Manufacturing Systems，2016，22(9):2099-2107.
[14] 刘召朝. 基于MOPSO/D的电缆网布局优化设计技术研究[D]. 南京:南京航空航天大学，2020. LIU Zhaochao. Research on layout optimization technology of cable harness based on MOPSO/D[D]. Nanjing:Nanjing University of Aeronautics and Astronautics，2020.
[15] WANG T，WANG Z，MORAN B，et al. Latency-aware optimization of submarine communication cable systems with trunk-and-branch topologies[J]. Journal of Lightwave Technology，2022:40(17):5825-5841.
[16] LIN G，XUE G. On the terminal Steiner tree problem[J]. Information Processing Letters，2002，84(2):103-107.
[17] TRIETSCH D，HANDLER G Y. The gilbert and pollak conjecture—A generalization[J]. Networks，1985，15(3):365-380.
[18] HO J M，VIJAYAN G，WONG C K. New algorithms for the rectilinear Steiner tree problem[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，1990，9(2):185-193.
[19] AKBARI H，IRANMANESH Z，GHODSI M. Parallel minimum spanning tree heuristic for the steiner problem in graphs[C]// 2007 International Conference on Parallel and Distributed Systems，December 05-07，2007，Hsinchu，Taiwan，China. New York:IEEE，2007:1-8.
[20] BORAH M，OWENS R M，IRWIN M J. An edge-based heuristic for Steiner routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，1994，13(12):1563-1568.
[21] FUCHS B. A note on the terminal Steiner tree problem[J]. Information Processing Letters，2003，87(4):219-220.
[22] MARTINEZ F V，DE PINA J C，SOARES J. Algorithms for terminal Steiner trees[J]. Theoretical Computer Science，2007，389(1-2):133-142.
[23] KRUSKAL J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical Society，1956，7(1):48-50.
[24] 李静爽. 关于求解费马点问题的多种方法探究与综述[J]. 教育教学论坛，2016，259(21):231-233. LI Jingshuang. Exploration and review of various methods for solving Fermat point problems[J]. Education and Teaching Forum，2016，259(21):231-233.
[25] 马江涛，刘检华，徐联杰，等. 基于LTL-PRM算法的分支管路自动布局方法[J]. 机械工程学报，2018，54(15):160-170. MA Jiangtao，LIU Jianhua，XU Lianjie，et al. Method of automatic branch-pipe routing based LTL-PRM algorithm[J]. Journal of Mechanical Engineering，2018，54(15):160-170.
[26] Standards Policy and Strategy Committee. BS EN 3197:2010 Aerospace series-Design and installation of aircraft electrical and optical interconnection systems[S]. London:British Standards Institution，2011.
[27] LIU Q，WANG C. Multiterminal pipe routing by Steiner minimal tree and particle swarm optimisation[J]. Enterprise Information Systems，2011，6(3):315-327.
[28] 柳强，毛莉. 基于MOPSO的航空发动机分支管路多目标布局优化[J]. 机械工程学报，2018，54(19):197-203. LIU Qiang，MAO Li. Multi-objective layout optimization for branch pipe of aero-engine based on MOPSO[J]. Journal of Mechanical Engineering，2018，54(19):197-203.
[29] GLERC M. Initialisations for particle swarm optimization[EB/OL]. [2008-12-24]. http://clerc.maurice.free.fr/pso.
[30] 许诺. 基于改进PSO算法的UAV三维路径规划研究[J]. 电子测量技术，2022，45(2):78-83. XU Nuo. Research on UAV 3D path planning based on improved PSO algorithm[J]. Electronic Measurement Technology，2022，45(2):78-83.
[31] 林希，张浩民，刘振祥. 基于收缩因子改进PSO算法的J-A磁滞模型参数辨识[J]. 电气工程学报，2024，19(1):187-195. LIN Xi，ZHANG Haomin，LIU Zhenxiang. Parameter identification of J-A dynamic hysteresis model based on an improved constriction factor PSO algorithm[J]. Journal of Electrical Engineering，2024，19(1):187-195.
[32] HUSSAIN M M，FUJIMOTO N. GPU-based parallel multi-objective particle swarm optimization for large SWA-RMS and high dimensional problems[J]. Parallel Computing，2020，92:102589.
[33] MA Zhedong，WANG Shuo. Prediction and measurement techniques for radiated EMI of power converters with cables[J]. Chinese Journal of Electrical Engineering，2022，8(4):1-10.