柳 强，焦国帅

(辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺 113001)

0 引言

管路作为电、油、水、气等的载体，在工厂、航空、汽车、船舶等领域广泛应用，其设计质量对产品或整个系统的性能具有重要的影响。针对航空发动机出现的空中停车事故，美国通用电气公司经过一系列调查后[1]，发现引起空中停车事件的真正原因有一半由管路问题引起。例如，一台典型的航空发动机通常包括数百根管路及线缆，这些管路的排布质量和效率对发动机的设计周期、成本及效率有重要影响。由于三维空间内的管路敷设问题已属于非确定多项式(Non-Deterministic Polynomial, NP)难问题，同时还需考虑多种目标及约束，因此其管路设计问题已成为复杂产品开发的关键环节。

为提高管路系统的设计质量和效率，多年来国内外学者提出了多种自动敷设算法。Rourke[2]将迷宫算法应用于管路布局问题，详细描述了管路布局的几何结构，该算法虽然绕障能力强且能保证最短路径，但所需的容量大，操作速度慢；柳强等[3]和吴宏超等[4]分别提出基于工程规则的三维启发式布管算法和基于改进A*算法的管路自动布局优化方法，这种启发式搜索算法的优点是搜索速度快，存储空间小，缺点是不能保证最优路径；Liu等应用可视图法[5]建立曲面可视图来求解航空发动机机匣曲面的最短管路[6]，并将可视图法推广到曼哈顿空间,提出“曼哈顿可视图”[7]，这种基于图论的方法只要建立适当的图就可以保证找到最短路径，但其难以考虑其他目标和约束；……