船舶三维管路智能布局优化算法

熊 勇，张 加，余嘉俊，张本任，梁萱卓，朱奇舸

（1.武汉理工大学航运学院，武汉 430063；2.湖北省内河航运技术重点实验室（武汉理工大学），武汉 430063；3.国家水运安全工程技术研究中心（武汉理工大学），武汉 430063）

（*通信作者电子邮箱1195574893@qq.com）

0 引言

管路布局问题涉及到各个领域，如化工厂管路、自来水管路、船舶管路、飞机管路等，管路设计是系统设计中极为关键的一步，良好的管路布局设计，对于保证系统的可靠性、稳定性、安全性等有着至关重要的意义。

船舶管路具有复杂庞大、空间有限、规则约束繁多、连接附件种类多样等特点，依靠人工敷设，难度大、耗时长且管路布局质量难以保证，随着计算机技术和人工智能算法的不断发展，实现管路自动布局成为可能。国内外学者在管路自动布局问题上给出了许多解决方法，主要分为启发式搜索算法和非启发式搜索算法，启发式搜索算法包括遗传算法［1-2］、蚁群算法［3-4］（Ant Colony，ACO）、粒子群优化（Particle Swarm Optimization，PSO）算法［5］等，非启发式搜索算法包括迷宫算法［6］、逃逸算法［7］、A*算法［8］等，Park［9］采用单元生成法对船舶管路的布局问题进行研究；Guirardello 等［10］提出一种解决化工厂管路布局优化方法；Van de Velden 等［11］对飞机管路进行了研究，建立了搜索空间内的三维结构和障碍物网格，获取满足相关规则和约束的最短路径；樊江等［12］应用迷宫算法对分支管路端点进行串行连接，达到了一定的效果，却不能保证最优解；Wang 等［13］提出了一种人机协作改进的蚁群优化算法，该算法不仅提高了收敛速度，而且提高了搜索效率；隋海腾等［14］将迷宫算法与遗传算法相结合，研究了船舶管路的优化设计，通过仿真实验表明方法的可行性；Jiang 等［15］设计了基于粒子群和蚁群混合算法的船舶机舱规划方法，该方法考虑设备布置和管路敷设两者之间的耦合作用，从而获得整体最优的设计方案；董宗然等［16］提出一种基于最短路径快速算法的船舶管路自动敷设方法，将网格能量值引入距离松弛函数，将可以通过网格能量描述的布置约束考虑其中，并分别给出了单管路和分支管路的敷设方法；柳强等［17］提出基于多目标粒子群优化（Muti-Objective Partical Swarm Optimization，MOPSO）的航空发动机分支管路多目标布局优化方法，给出一种分支管路平滑度计算方法，结合非支配排序和网格密度计算完成个体多目标评价。现有的管路自动敷设方法为船舶管路自动敷设问题做出了十分有益的探索，但船舶管路的自动敷设问题仍有以下问题需要深入研究：1）船舶管路往往复杂而庞大，当障碍物增多时，容易导致算法陷入局部最优解，甚至会出现无法搜索到路径的情况，算法的搜索效率和成功率也会急剧降低，因此，当出现多个障碍物时，如何能够获得最优解并且保证算法的搜索效率和成功率仍需要深入研究；2）船舶管路敷设规则繁多，并且很多规则难以进行量化，导致管路布局方案无法应用于实际工程，因此，如何获得满足工程规则的最优管路布局方案，需要进一步深入研究。

蚁群算法［18］是一种模拟蚂蚁觅食行为的模拟优化算法，具有较强的鲁棒性和自适应性，并且易与其他算法结合，较适合于解决组合优化问题，在解决路径规划问题上有着良好的表现，但蚁群算法也有自身的局限性，在解决大规模、复杂约束、障碍物较多的路径规划问题上，易出现无法快速地搜索到最优路径、收敛速度下降、局部最优解等情况。快速扩展随机树算法（Rapidly-exploring Random Tree，RRT）［19］通过对状态空间中的采样点进行碰撞检测，避免了对空间的建模，能够有效地解决高维空间和复杂约束的路径规划问题，在含有多个障碍物的空间内也能够快速有效地搜索到可行路径。因此，针对三维管路布局问题，对蚁群算法和RRT 算法进行改进并将两种算法进行结合，利用RRT 算法较强的路径搜索能力进行路径的搜索，再用蚁群算法进行循环迭代优化，在选择最优路径时，对船舶管路敷设规则中较为主要的规则进行了量化处理，建立优化评价函数，综合考虑各种管路敷设的工程规则，以期得到满足实际工程的最优管路布局方案。

1 问题描述

船舶三维管路布局问题，实则是一种三维空间下的多目标、多约束路径规划问题。如图1 所示，空间C为管路布局空间，Ob1、Ob2、Ob3、Ob4、Ob5为布局空间内障碍物，Start和Goal分别为管路的起点和终点，布局优化问题即为找到连接点Start和点Goal的路径，并且不与障碍物发生碰撞，同时需要满足路径短、弯头少、走直线等要求的路径规划问题。

图1 管路布局空间Fig.1 Pipe layout space

1.1 布局空间与敷管规则描述

建立布局空间是将三维实体进行数学形式的表达，采用轴平行包围盒（Aixe Align Bounding Box，AABB）的方法对三维实体进行包络，实体的长宽高分别为l×w×h，定义管路布局空间的大小，管路必须在布局空间内，对管路布局的区域进行限定，则有0 ≤x≤l，0 ≤y≤w，0 ≤z≤h，(x，y，z)为布局空间内的任意一点坐标，为方便表达将布局空间进行离散化，将其离散化为l×w×h个点；布局空间分为可布管空间和障碍物空间，对存在障碍的空间进行标记，障碍物的标记同样也采用区域限定的方式，建立障碍物集合如下：

没有进行标记的空间则为可布管空间。

船舶管路布局问题与路径规划问题类似，但不尽相同，船舶管路的敷设需要综合考虑多种工程规则，是一个具有多目标、多约束的复杂路径规划问题，具体的敷管目标和约束如下。

G1：保证管路起点和终点之间的连通性；

G2：不与其他设备发生碰撞；

R1：管道长度尽可能短；

R2：弯头数量尽可能少；

R3：管道走直线，不走斜线；

R4：管道尽可能贴近障碍物表面或空间内壁；

G1和G2构成目标集合G={G1，G2}，R1、R2、R3、R4构成约束集合R={R1，R2，R3，R4}，管路是由一个个节点连成的线段组成，定义起点坐标为(x0，y0，z0)，终点坐标(xn，yn，zn)，管路节点集合的数学表达式 ：path_node={(x0，y0，z0)，(x1，y1，z1)，(x2，y2，z2)，(x3，y3，z3)，…，(xi，yi，zi)}，0 ≤i≤n，针对上述规则做如下处理。

1）对于规则R1，管路路径的长度：path_length=，即让path_length尽量小。

2）对于规则R2，弯头数量bend_number的计算：n1=((xi-xi-1)，(yi-yi-1)，(zi-zi-1))，n2=((xi+1-xi)，(yi+1-yi)，(zi+1-zi))，如果n1*n2=0，则bend_number加1，即保证bend_number尽量小。

3）对于规则R3，管道走直线，若当前点坐标值为(x，y，z)，则下一步可选节点方向的集合：{(x-1，y，z)，(x，y-1，z)，(x，y，z-1)，(x+1，y，z)，(x，y+1，z)，(x，y，z+1)}，即可保证管道走直线不走斜线。

4）对于规则R4，管道上任意一节点的能量与障碍物的距离d呈反比，能量函数采用距离，Ei为某一节点能量常数。

1.2 建立优化评价函数

针对上述约束集合，建立求解优化评价函数，path_length、bend_number和分别表示为管路路径的总长度、弯头的总数量和总能量值，w1、w2、w3则分别为管道长度、弯头数量和能量值的权重因子，评价函数Fit如下式所示：

在最优路径的选择时，即求解Fit最小时，管路路径点的集合则加入到最优解集中，再通过循环迭代优化，找到所有满足目标和约束的最小值Fit所对应的管路路径节点集合，最后综合考虑敷管规则，输出最优布管方案。

2 管路自动敷设算法设计

本文将管路敷设问题分为两步：第一步，利用RRT 算法在复杂、多维环境下较强的路径搜索能力，搜索可行路径，并将其存在可行解集中；第二步，采用蚁群算法对可行解集中的可行路径进行迭代优化，寻找最优解，并将最优解存储在最优解集中，通过对路径不断的迭代优化，最后找到综合最优路径。算法详细步骤如下：

步骤1 初始化各项参数。

步骤2 判断是否达到最大迭代次数，若达到，输出全局最优路径，结束循环；若没有达到，进行下一步。

步骤3 确定生长点，更新各生长方向上节点上的信息素浓度。

步骤4 根据各点的信息素浓度计算出各个方向的概率大小，根据概率的大小选择下一步的生长方向Direction，更新生长点NewPoint=Start+Stepsize*Direction(i)，NewPoint则为新的生长节点，更新NewPoint点的信息素浓度。

步骤5 对新生成的路径是否与障碍物发生碰撞进行检测，如果新的路径发生干涉则返回步骤3，然后重新选择生长方向，并且把当前生长方向从本次生长要选择的方向中删除，避免再次选择不可行的方向进行生长；如果新的路径没有发生干涉，则执行下一步。

步骤6 将新的节点添加至RRTree集合中，并且更新生长点Start。

步骤7 判断是否到达目标点，若没有达到，则返回步骤3 继续寻找路径；若到达目标点，则说明完成一次路径搜索，将本次路径搜索过程中所经历的节点存在可行解集Path中。

步骤8 派出n只蚂蚁，重复上述步骤3～7，得到n条路径。

步骤9 建立Fit适应度函数，寻找本轮n只蚂蚁寻找的n条路径中最优路径Bestpath，并更新Bestpath中所有节点的信息素浓度。

步骤10 更新全局信息素浓度的值，并返回步骤2 进行循环迭代优化，直到达到最大迭代次数，输出全局最优路径。算法实现伪代码如下：

算法1 管路自动布局算法。

输入：管道起点和终点，布局空间C；

输出：Bestpath最优路径节点集合。

2.1 路径搜索算法设计

RRT 算法由Lavalle［20］于1998 年提出，其基本思想是通过随机选择生长方向，由初始状态不断向外增量式生长，形成新的节点，每个节点代表一个状态，最后达到目标点或附近。该方法较常用于机器人路径规划问题，RRT 算法的优势在于只要路径客观存在，就一定能被找到。

如图2 所示，Sample为样本空间，xinit为随机树的起始点，xgoal为终点，xrand为样本空间中随机产生的一点。RRT 算法是通过不断向外增量式扩展来完成随机树的生长，其中RRT 生长方向的确定是通过在样本空间中随机选取一点xrand，在已有随机树节点中寻找距xrand最近点xnear，连接点xnear和xrand，则方向向量XnearXrand为随机树的生长方向，设：点xnear和xrand的坐标分别为xnear=(x1，y1，z1)、xrand=(x2，y2，z2)，则有：

Stepsize为RRT 算法向外生长的步长，则新的叶节点xnew的求解如下式所示：

图2 RRT算法示意图Fig.2 Schematic diagram of RRT algorithm

2.1.1 方向选择策略

路径搜索最为关键的问题是下一个节点该如何选择，如果没有其他约束，当处在三维空间的某一个节点时，下一节点的选择理论上有无数个，但船舶管路的走向不能是无序、杂乱的，在没有与障碍物发生干涉时，管道应沿着当前方向或垂直方向布管。如图3 所示，几何中心点表示当前节点所在位置，下一节点可选择的生长方向有6个，生长方向集合为：

在初始化时，空间内的每个节点都会有一个初始的信息素浓度pheromone，每个方向被选择的概率大小：

图3 方向选择示意图Fig.3 Schematic diagram of direction selection

2.1.2 避障策略

在生成新的节点时，对于新节点与当前节点的连线需要进行碰撞检测，当新生成的节点路径不与障碍物发生干涉，才会被加入到随机树中，在仿真环境中对障碍物进行了简化处理，障碍物形状主要为长方体。

由图4绕障示意图可知，与障碍物发生干涉有两种情形：

情形一 新生成的节点在障碍物内，则该新生成节点与上一节点的连线必会穿过障碍物；

情形二 新生成的节点不在障碍物内，则该新生成节点与上一节点的连线穿过障碍物，如图3 黑色虚线段所示。针对上述两种情形给出如下避障策略：

第一步在管路布局空间中所有的障碍物已经经过标记，被标记的障碍物节点值为1，自由空间节点值则为0，因此，可以直接判断新生成的节点是否在障碍物内。

第二步当新生成的节点不在障碍物内时，此时就需要判断新生成的节点的连线是否穿过障碍物，将节点连线进行栅格化离散，然后判断连线上的点是否在障碍物内：若不存在，则新生成节点满足要求，可加入随机树中；若存在节点在障碍物内，则认为新生成路径与障碍物发生干涉，此次生长失败，返回重新选择下一节点。

图4 绕障示意图Fig.4 Schematic diagram of obstacle avoidance

2.1.3 变步长策略

在路径搜索过程中，步长的选择往往决定了算法的成功率和搜索效率，在传统的RRT 算法中，往往采用的是定步长的方式，定步长的缺陷在于：1）当终点与起始点距离不满足步长的整数倍关系时，将无法搜索到终点；2）当空间环境中障碍物较为密集时，采用定步长可能出现无法绕开障碍物的情况，导致路径搜索失败，因此，本节采用变步长的策略对上述问题进行规避，提高算法的成功率和搜索效率，变步长策略通过引入步长因子λ对步长进行动态调节，如式（7）所示：

当出现以下两种情况需要对步长进行调节：

1）当前节点与终点间的距离小于设定的初始步长Stepsize；

2）当前节点NowPoint和新生成节点NewPoint连线与障碍物发生干涉。

假 设，当前节点NowPoint=(x0，y0，z0) 和下一节点NewPoint=(xn，yn，zn)连线的方向向量为a=(x0-xn，y0-yn，z0-zn)，当前节点NowPoint和发生干涉的障碍物距离为Dis，当前节点NowPoint和终点Goal的距离为dis，则步长因子λ的确定方式如式（8）所示：

当上述两种情况同时满足时，优先考虑绕开障碍物Ob，步长因子。变步长策略确保了在路径存在的前提下，算法能够搜索到从起点到达终点的路径，保证了算法的成功率。

上述路径搜索算法实现伪代码如下：

算法2 RRT路径搜索算法。

输入：管道起点和终点，布局空间C；

输出：RRTree路径节点矩阵。

2.2 路径优化算法设计

2.1 节利用RRT 算法进行了路径的搜索，RRT 算法的特点是能够快速、有效地搜索高维空间，通过增量式的不断生长，将搜索方向导向空白领域，但RRT 算法搜索得到的路径并不能保证最优，因此本文将其与蚁群算法进行结合，利用蚁群算法迭代寻优能力，不断对路径进行优化，最后得到最优路径。

2.2.1 选择概率的计算

设蚂蚁g当前所在位置坐标为(x，y，z)，结合船舶管路三维布局问题，RRT 生长的方向限定为6 个，因此，每只蚂蚁可选择的方向有6 个，在步长一定的前提下，蚂蚁g下一步可选择的节点一共有6 个，如式（9）为下一步可选节点集合，Stepsize为步长大小：

每一个节点的概率大小计算如式（10）所示：

2.2.2 信息素更新

信息素的更新对于整个算法的成功率和收敛速度至关重要，本节信息素的更新采用局部信息素更新和全局信息素更新相结合的方式，各条路径的更新信息素的更新方式如下式所示：

1）局部信息素更新。

假设蚂蚁从节点i到节点j，节点i和j两点之间路径的信息素更新公式如式（11）所示：

其中：ξ为局部信息素更新的挥发率，τ0为信息素的初始值。局部信息素更新可以保证其他路径被选择的概率，不至于使某一条路径上的信息素浓度太大。

2）全局信息素更新。

当算法完成一次迭代，按照公式，对最优路径信息素浓度进行更新：

2.2.3 停止准则

由于采用的使蚁群和RRT 的混合算法进行最优布管路径搜索，因此，管路路径搜索的停止条件包括两层：1）第一层是由RRT 路径搜索的停止，当某只蚂蚁到达设定的管道连接点时，则完成一次路径的寻找，停止条件如下式所示；2）第二层是蚁群算法路径优化的停止，通过设定最大迭代次数使算法停止，当迭代次数大于设定最大迭代次数时，蚁群路径优化算法停止，停止条件如式（14）～（15）所示：

其中：Nowpoint(i，j，k)为蚂蚁实时的位置坐标，goal(m，n，p)为设定的目标连接点坐标，b_number为当前迭代次数，max_number为最大迭代次数。

算法3 蚁群路径优化算法。

输入：RRTree路径节点矩阵；

输出：最优路径Bestpath、适应度值Fit。

3 仿真实验

仿真实验是在Windows10 系统环境下，采用Matlab R2016a，对上述船舶管路自动敷设方法进行仿真实验。实验构建一个对角坐标为(0，0，0)和(100，100，100)的管路布局空间，并将空间离散成100 ×100 ×100 个点，将障碍物简化成长方体形状，如图5 所示为空间及障碍物的三维布局显示图，障碍物信息如表1所示。

图5 空间及障碍物布局Fig.5 Space and obstacle layout

表1 障碍物对角坐标Tab.1 Obstacle diagonal coordinates

初始化管道起点Start(1，1，1)和终点Goal(81，81，81)，对布管空间100 ×100 ×100 个空间点进行信息浓度初始化，按照对敷管规则R4 的处理方法，对空间各点赋予能量值，利用评价函数对可行解集中路径的适应度值进行计算，在本次实验尽可能满足工程约束，并根据约束的重要程度来确定式（2）中的权重因子，以所有权重总和为1 的原则对权重因子进行分配，根据多次仿真的结果，以及综合实际船舶管路敷设工程经 验，式（2）中各权重因子分配情 况：w1=0.05，w2=0.52，w3=0.43，通常蚁群算法中信息素启发因子α∈[0，5]、期望启发因子β∈[0，5]、局部信息素挥发率ξ∈[0.1，0.99]、全局信息素挥发率ρ∈[0.1，0.99]，关键参数设置如表2所示。

表2 算法参数Tab.2 Algorithm parameters

如图6 所示，黑色点为管道连接起始点，图6（a）为采用RRT 搜索的初始路径，从图6（a）可以看出RRT 较强的路径搜索能力，能够让初始种群搜索的路径涵盖空间内的大部分区域，为后续蚁群算法路径优化奠定基础；图6（b）为采用蚁群算法优化之后的路径，从图6（b）可以看出优化之后的路径较为符合管路敷设工程规则，因此，该算法能够得到在复杂约束条件下最优敷管路径方案。

图6 路径优化前后Fig.6 Paths before and after optimization

图7（a）为ACO与RRT混合算法生成的管道路径，图7（b）采用对比文献［21］的ACO+PSO 方法算法生成的路径，7（c）采用对比文献［22］的改进ACO 方法算法生成的路径，通过两种算法生成的路径进行对比，可以看出ACO 与RRT 混合算法生成的路径更优，且较为符合管路敷设工程规则，

图7 管路自动布局结果Fig.7 Results of automatic pipeline layout

图8 为三种方法的适应度值的变化曲线，由于实验结果存在随机性，适应度值为多次仿真结果的平均值，采用ACO和RRT结合的算法迭代次数平均在11代，对比文献［21］中的方法平均迭代次数为27 代，对比文献［22］中的方法平均迭代次数为18代。

图8 适应度值变化Fig.8 Changes in fitness values

算法详细对比分析表如表3所示。

表3 实验结果对比分析Tab.3 Comparison and analysis of experimental results

从表3中可以看出，在同一布局空间中，ACO和RRT混合算法均能有效搜索到当前最优路径，且平均迭代次数最小，搜索时间最短：相较于ACO+PSO 算法，本文方法的成功率提升了35 个百分点，平均运行时间减少94.1%；相较于改进ACO算法，本文方法平均运行时间减少78.8%。因此，从实验结果来看，基于ACO 和RRT 的混合算法比其他两种方法具有良好的优越性。

图9 为ACO 和RRT 三维实体管路布局结果，在含有多个障碍物、布管空间有限的情况下，算法能够搜索到多个约束条件下的综合最优解，并且算法具有良好的收敛速度和搜索效率，基于ACO 和RRT 的混合算法，能够很好地求解在多目标、多约束下的管路路径规划问题，在实际工程布管上具有一定的参考作用，但由于仿真建模环境无法真实地还原实际环境，因此，管路布局结果与实际情况仍存在一定偏差。

图9 三维实体管路布局Fig.9 3D solid pipeline layout

4 结语

本文将蚁群算法与快速扩展随机树算法进行了结合，提出一种新的船舶管路自动敷设方法，利用快速扩展随机树算法在复杂、多维空间的路径搜索能力，很好地解决了蚁群算法在多障碍物环境下，易出现无法搜索到路径以及容易陷入局部最优解等问题，并利用该方法对单管路自动敷设问题进行了仿真实验，从仿真实验结果来看，将两种算法结合后，能够很好地求解多目标、多约束的船舶管路路径规划问题，并且算法的收敛速度和成功率有大幅提升。管路敷设方法同时考虑了船舶管路敷设主要的工程规则，管路自动布局结果能够为设计人员提供多种可行的管路敷设方案，很好地辅助管路设计人员设计管路，省去了设计人员前期重复、复杂的工作步骤。管道布局的理论研究和实际工程设计的主要区别在于：实际工程设计中，会给出具体的输入信息，例如空间大小和障碍物的具体位置，设计者会根据相关设计手册的要求来完成对应管路部分的布局设计，通常有约定俗成的设计风格。但是在理论研究中，由于没有具体的工程背景，很难实现量化的真实案例，且有很多工程约束无法量化成具体形式，因此，仿真环境中管路自动布局结果与实际工程要求仍存在偏差，还需要人工经验对布局结果进行修正。后期在此基础上，可加入专家系统知识，对布局结果进行二次评价，将专家经验知识融入到管路布局评价中，从而实现船舶管路全智能化布局。该方法也为后续分支管路和多管路敷设问题奠定了基础，同时，本文方法具有普适性，同样适应于解决类似的路径规划问题，为其提供可供借鉴的思路和方法。