基于改进蚁群算法的邮船舱室模块移运路径规划

王炬成, 赵学涛

(江苏科技大学 船舶与海洋工程学院，江苏 镇江 212100)

0 引 言

研究邮船舱室模块从舷侧开孔进入至主竖区指定安装位置的路径规划问题，对于减少邮船舱室模块运输所需时间、提高邮船舱室模块的安装效率具有重要的意义。传统的路径规划算法为遗传算法[1]、人工势场法等[2-3]，当前比较主流的算法为A*算法、蚁群算法、神经网络算法等[4-6]，其中，蚁群算法具有稳健性佳、全局搜索能力强、环境约束表达简便等优势。

学者们将蚁群算法用于各领域中。孙功武等[7]提出一种新的启发式函数，用于水面无人舰艇的路径规划。濮明月等[8]提出结合遗传算法的蚁群算法，用于物流配送车辆的路径规划。游晓明等[9]提出一种动态搜索策略，用于机器人路径规划。吴雨婷等[10]将蚁群算法用于安徽某公司的速冻蔬菜配送，并在实际应用中取得较好的效果。

针对在大型邮船舱室模块运输过程中的移运路线长、路线混乱、舱室模块易与障碍物发生碰撞等问题，通过应用加入动态搜索模型的蚁群算法、模拟退火算法对邮船舱室模块的移运路线进行规划加以解决，并根据实际情况进行进一步改进。对同一主竖区的舱室模块同时进行路径规划，分析区域内的障碍物，限制蚁群的搜索方向；对每个舱室模块所要行走的栅格地图进行动态调整；对主竖区内不能通过的区域进行优化；在确定每个舱室模块较优路径后，通过离散数据分析，确定主通道与各舱室模块行走的支路。蚁群算法参数[11]是影响蚁群算法性能的重要因素，可采用模拟退火算法[12-13]获得。通过试验仿真，对改进蚁群算法在舱室模块移运过程中缩短舱室模块运输路线、移运路线清晰化、避免舱室模块与障碍物碰撞等方面进行验证。

1 算法研究

1.1 加入动态搜索模型的蚁群算法

蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法[5]。蚁群算法主要步骤如下：

步骤1：初始化。对蚁群算法所需的各项参数(信息素启发式因子、期望启发因子、信息素蒸发系数、信息素强度、初始信息素质量分数、蚁群数量和迭代次数等)进行初始化。

步骤2：进行路径更新、禁忌表更新。

(1)根据蚁群算法概率公式[6]采用“轮盘赌”的方式选择下一个行走城市(栅格)。概率公式(城市i至城市j的概率)为

(1)

式中：τij为城市i至城市j的信息素强度；ηij为城市i与城市j之间距离的倒数；α、β分别为信息素启发式因子和期望启发因子，均为常数。

(2)更新禁忌表。将走过的城市进行记录、删除，保证接下来的路径不会再次选择该城市。

(3)记录路径。包括到达终点和未到达终点的行走路径，完成一次路径游历。

(4)信息素增强。每只蚂蚁在行走路径到达终点时会在该路径上的城市残留信息素，对路径上的城市起到信息素增强的作用，未到达终点的路径不进行信息素增强。信息素增强公式为

Δτij=Q/L

(2)

式中：Δτij为城市i至城市j的信息素增强；Q为信息素强度，为常数；L为需进行信息素增强路径的总长度。

步骤3：更新信息素。在所有蚂蚁均完成一次路径更新后进行全局信息素更新，包括信息素挥发与信息素增强。

信息素更新公式为

Tau=(1-ρ)Tau+Δτ

(3)

式中：Tau为全局信息素质量分数，用于指导下一代蚁群路径的选择；ρ为信息素蒸发系数，为常数；Δτ为某一代中所有到达终点的路径的信息素质量分数增强之和。

步骤4：重复上述3步，完成迭代，输出最优路径。通过加入动态搜索模型对蚁群算法收敛速度慢、易陷入局部最优等问题进行改进。

(1)根据初始位置与终止位置的相对位置，对蚁群的斜格移动进行限制。

(2)信息素质量分数更新过程设置惩罚系数，通过动态搜索模型控制信息素质量分数的更新。

动态搜索模型为

(4)

式中：Δτkr为到达终点的第k代、第r只蚂蚁在完成一次路径游历后在路径上的残留信息素；Lkr为第k代、第r只蚂蚁在完成一次路径游历后的路径长度；Lmin为迭代至某一代前所有代中的最小值。

(3)由于算法本身的特点，在迭代至20次以后会出现相对较优路径所在栅格的信息素质量分数远大于其他栅格，使蚁群算法丧失活跃性，向局部最优进行迭代，因此设置最低质量分数下限，使算法不仅可依照信息素质量分数差寻优，而且可保留一定的活跃性，增强算法的纠错能力。设置全局信息素质量分数下限为10-3。

1.2 模拟退火算法

模拟退火算法以统计物理为基础。算法的核心是以一定的概率拒绝局部极小值问题解，从而跳出局部极值点继续开采状态空间的其他状态解，进而得到全局最优解[11-13]。

模拟退火算法主要步骤如下：

(1)初始化参数。将初始温度、温度下降速率、温度下限、解空间(迭代次数)进行初始化。

(2)产生一组初始解。获得一组参数，输入改进蚁群算法获得一组最短距离，作为初始解Ibest，用于后续与新解进行对比。

(3)产生一组新解。获得一组新的参数，获得一组新解Ibest1，将新解与初始解进行对比。

(4)初始解与新解进行对比。若新解比初始解更优秀，即ΔI<0，则记录该组新解并将其更新为初始解，为后续与新的新解进行对比。

若新解不如初始解优秀，即ΔI≥0，则按照模拟退火概率公式进行概率跳跃，选择是否更新初始解。一开始温度很高，选择更新初始解的概率就会很高，算法在解空间中活跃地寻找优势解；随着温度降低，选择更新初始解的概率降低，算法的活跃程度下降，趋于稳定。

模拟退火概率更新公式[13]为

(5)

ΔI=Ibest-Ibest 1

(6)

式中：ΔI为新解与初始解之差；T为当前温度。

(5)更新温度。重复步骤(3)和(4)，直至达到迭代次数，随即更新温度。

(6)重复步骤(3)～步骤(5)，直至达到最低温度，输出符合条件的参数组合。

2 舱室模块移运路径优化

舱室模块移运是舱室模块完成吊装与舱室模块安装的中间操作。重点解决舱室模块在移运过程中遇到的问题，并使用算法进行移运路径规划。

改进蚁群算法虽在处理复杂环境下的路径寻优与旅行商问题(Traveling Salesman Problem，TSP)同样表现不错，但其并未将舱室模块大小、主竖区面积、障碍物的相对位置等因素考虑进去，因此需在该算法基础上对栅格地图、蚁群移动规则、障碍之间相对距离和不同舱室位置行走的栅格地图进行优化。

2.1 建立栅格地图

以某一中型邮船的主竖区为例，分析其中障碍物，包括不可移动的立柱、安装舱室模块的三角区和一些角钢等。布局主要为有楼梯间和无楼梯间。

大型邮船的主竖区中间可供游客行走、游玩的区域更大，因此在两种船舱布局的基础上进一步扩展使其适用于更多的邮船舱室模块运输。根据两种布局主竖区类型分别对其进行栅格地图建模，尺寸分别为15 m×30 m与21 m×30 m。在15 m×30 m的主竖区，可搭载10个舱室，每个号位代表舱室模块6 m×3 m的安装区域和安装顺序，每一小格表示主竖区内0.5 m×0.5 m的方形区域，用于计算移运路径和表示障碍物区域，入口位置一般位于10号位与14号位处。主竖区布局与栅格地图如图1所示，其中，栅格地图的横、纵坐标表示栅格的数量。

图1 主竖区布局与栅格地图建模

2.2 蚁群的移动规则

由于一层甲板的主竖区内并不会有太多障碍物，因此可对蚁群的前进方向进一步限制。

舱室的入口与安装位置的相对位置一般包括正右方、正下方和右下方等3种。在舱室位置处于前两种情况时，蚁群只进行上、下和右的转移，即在较为空旷的地图上，舱室模块只能前进不能后退。

在舱室位置位于安装位置右下方时，可进行斜格移动，通常分为4种情况，如图2所示，其余情况不发生斜格移动。

图2 舱室位置位于右下方蚁群的移动规则

在前进路上遇到障碍物，为避免刮擦、碰撞等情况发生，无法采取斜向移动方式(见图3中的①)通过，可采取绕行方式躲开障碍物(见图3中的②)。

图3 前进方向遇到障碍物示例

2.3 障碍物优化

在两个障碍物的间距不足以通过舱室模块时，需对栅格地图进行优化。根据舱室模块体积，在两个障碍物的行间距≤6行且列间距≤6列时，将栅格地图上两个障碍物所围成的矩形内的栅格均设为障碍物。

例如：在行间距为2、列间距为5计算栅格间距时，将3行6列范围内的栅格全部设为障碍物，即舱室模块不会通过该区域，如图4所示。

图4 障碍物优化规则

2.4 栅格地图和蚁群数量动态调整

在同一主竖区，不同的舱室模块所处的位置不同，按照安装顺序，在寻得上一个舱室模块的最短路线后，表示该位置已安装舱室模块，然而蚁群算法在计算栅格间距时依然会包含该位置，因此该位置需进行优化。

根据主竖区的栅格地图，在寻得下方的舱室模块最优路径后，会影响上方舱室模块的最优路径寻找。由于上一个舱室模块所在行对应的栅格对于其上方的舱室模块寻优是一个较大干扰，因此对这一部分需进行优化。

栅格地图的动态调整主要分为两个方面：

(1)在寻得一个舱室模块的最优路径后将该位置栅格全部变为障碍物(将该部分的0变为1)，保证后续最优路径不会通过该位置，该变化只用于后续其他舱室模块路径规划的计算，并不会显示在最终的栅格地图上。以一个3行6列的舱室模块为例，在该模块寻得最优路径后将其设置为障碍物，如图5所示。

图5 某舱室模块寻得最优路径后的地图优化

(2)根据需进行路径规划的舱室模块的终点位置，对栅格地图可行走区域进行限制。栅格地图动态调整如图6所示。

图6 栅格地图动态调整示例

随栅格地图变化的还有蚁群数量，对于一个主竖区的两列舱室模块采用不同的蚁群数量计算公式。在地图调整后，靠近舷侧开孔的舱室模块由于栅格数量远小于远离开孔处的舱室模块，因此蚁群数量为其舱室模块中心位置所在行的10倍；而远离舷侧开孔的舱室模块，蚁群数量为其舱室模块中心位置所在行的20倍，同时设置下限为300。

舱室模块蚁群数量更新公式为

(7)

式中：d为蚁群数量；Ei、Ej分别为舱室模块中心位置栅格所在的行和列。

2.5 蚁群算法的初始参数

每个主竖区在寻找不同舱室模块的最优路径时，栅格地图会动态变化，每个舱室模块所需的参数会不同，且后期舱室模块数量较多，单个舱室模块寻找参数不仅困难而且消耗时间。为方便计算，采用模拟退火算法寻找一组相对通用的参数组合。

参数组合计算过程：①参照以往文献给出的蚁群算法，参数范围适当扩大，作为模拟退火算法的参数范围；②模拟退火算法在给出的范围中随机生成参数组合并输入舱室模块移运算法，该参数组将用于所有舱室模块的路径寻优；③记录所有生成路径和作为模拟退火算法的解，待退火完成，生成较为稳定、通用、适用于多舱室模块路径规划的蚁群算法参数组合。

2.6 改进蚁群算法和模拟退火算法流程

用于计算多舱室模块移运路径的改进蚁群算法和用于计算蚁群算法参数的模拟退火算法的流程如图7所示。

图7 改进蚁群算法和模拟退火算法流程

2.7 主、支通道设置与优化

为方便运输舱室模块，需最大限度地减少转向、掉头等操作，通过改进蚁群算法完成主竖区每个舱室模块的最优路径计算。虽是最优路径，但转向过多，不同的运输路径混杂在一起，若按照该计算结果进行舱室模块运输，即使实际运输距离缩短，但易导致运输过程更加繁琐、运输效率低下，不符合实际需求。

为避免上述问题，在确定主竖区每个舱室模块最优路径后，需要对所有的路径(一般是远离入口一侧的路径)进行二次优化，即对离散的数据进行分析，将一些斜向移动集中在一起，确定一条直线，使该直线通过较多移运路径，使其作为该主竖区舱室模块运输的主通道，将不同舱室模块移运路径的支路顺序连接在主通道上，并对支路上的转向位置进行优化，使每个舱室模块尽可能地减少转向次数，并用信号带对主通道和支路进行标记，可沿标记带运输舱室模块。以两条移运路径为例，展示不同移运路径调整前后的优化，主、支通道随之确定，如图8所示。

图8 不同移运路径优化

3 舱室模块移运路径优化

对主竖区地图Ⅰ、Ⅱ进行路径规划求解，测试算法性能，改进蚁群算法与模拟退火算法用MATLAB实现，通过与文献[1]算法和文献[9]算法的对比验证改进蚁群算法在提高算法效率和优化解质量、缩短时间等方面的优越性。通过与船厂安装同一主竖区舱室模块的行走距离对比验证改进蚁群算法在提升舱室模块移运效率、缩短移运时间等方面的优势。

测试结果在CPU为Intel Core i5 7300HQ、内存为8 GB的便携式计算机平台上运行得到。

3.1 算法性能

由于文献[12]验证合理的参数组合所得到的结果优于随机的参数组合，因此在进行算法对比时采用的参数均由模拟退火算法计算得到。在仿真试验中不再进行退火算法获得参数与随机参数的对比试验。分别将改进蚁群算法、文献[1]算法和文献[9]算法代入模拟退火算法，得出各自的参数组合，分别选取其中较为优秀的一组参数组合用于后续路径计算。

采用搭载10个舱室模块的主竖区建立栅格地图，共进行3组测试：1号位和3号位舱室模块单独移运和远离入口一侧的舱室模块全部移运，计算完成舱室模块移运所需时间和得到的优势解。

改进蚁群算法通过模拟退火算法计算选取的参数组合α、β、ρ、Q、Tau分别为[1.1、9.8、0.5、25、2]。文献[1]算法选取的参数组合为[3.4、9.4、0.6、27、1]。文献[9]算法选取的参数为[2.2、7.3、0.6、16、1]。在迭代次数为50次时，无论蚁群算法还是改进蚁群算法均可达到收敛，因此迭代次数均设为50。蚁群数量在改进蚁群算法中随栅格地图变化而动态调整，蚁群算法统一设置为400。每组测试计算10次，取最优解。

为验证改进蚁群算法在复杂环境下的寻优能力，先在一组复杂环境下进行单条路径寻优，3种算法参数与上文相同，3种算法仿真结果对比如图9所示。

图9 3种算法的结果对比

在复杂环境的仿真计算中，改进蚁群算法寻得路径的距离更短，寻得最优路径即为收敛路径，收敛质量更高，且计算所需时间更短。在1号位和3号位舱室模块的移运路线规划中，改进蚁群算法与另外两种算法的对比如图10和图11所示。

图10 1号位舱室模块移运路径和收敛曲线

图11 3号位舱室模块移运路径和收敛曲线

通过单条移运路径运算可确定改进蚁群算法在运算时间、收敛结果的质量和效率方面明显优于文献[1]算法和文献[9]算法，但仍需要进行多路径同时运算验证改进蚁群算法是否比另外两种算法更适合于舱室模块的路径规划。

使用3种算法分别完成主竖区内远离入口一侧的舱室模块移运路线规划，通过仿真，改进蚁群算法在运算总时间、每条路径收敛质量、转向次数等方面均高于另外两种算法。通过改进蚁群算法获得的各舱室模块移运路径，可较为方便地进行下一步的主、支通道的确定，如图12和表1所示。

表1 不同算法获得的移运路径对比

图12 1～5号位舱室模块移运路径和收敛曲线

3.2 算法应用

在第3.1节中验证改进蚁群算法在计算时间、获得优势解的质量和效率等方面均优于蚁群算法、文献[1]算法和文献[9]算法。对邮船上主要的两种主竖区(分别搭载10个和14个舱室模块)进行路径规划。由于主竖区安装区域外的一段区域是走廊(阳台)，因此可获得足够的空间方便刚进入主竖区的舱室模块掉头，可使舱室模块沿主竖区边缘运输靠近入口一侧的舱室模块。

通过上述路径规划得到的舱室模块移运路线并不足以用于现场施工，需要进行离散数据分析，确定主、支通道，以减少舱室模块的转向与通道的标记工作，方便识别运输。主通道需尽可能成为主移运路径，通过调整支通道减少过多的转向，如图13和图14所示。

图13 主竖区地图Ⅰ调整前后的移运路线

图14 主竖区地图Ⅱ调整前后的移运路线

调整后的路径总体长度与调整前的差距虽不明显，但每个舱室模块在移运过程中的转向次数却大幅减少，可将每个舱室模块的转向次数控制在4次以内，避免因转向造成磕碰和因操作不当造成舱室模块损坏。根据调整后的路径设置信号带或标签，并在主、支通道交接处标记编号。远离舷侧的舱室模块可在条件允许的情况下同时运输，近入口处需按编号顺序运输。

通过调研某极地邮船某主竖区内舱室模块的运输时间，得到单独舱室模块运输的平均时间或全部舱室模块的运输时间。该邮船在建造过程中，在不受外界影响的情况下，平均20 d需完成运输、安装60个舱室模块，每天平均工作时间取9 h，即平均每3 h完成1个舱室模块的运输与安装任务，其中，运输时间约0.4～0.6 h，平均运输速度约30～50 m/h。10个舱室模块主竖区的运输时间约5 h，14个舱室模块主竖区的运输时间约8.4 h。越大的主竖区越易出现过多转弯与碰撞等情况，且杂乱无章的路径会使运输距离的计算变得困难。改进前后的路径规划移运效率对比如表2所示。

表2 改进前后的路径规划移运效率对比

4 结 语

通过改进蚁群算法、模拟退火算法对邮船舱室模块移运过程中的移运路线混乱、移运无方向、易发生碰撞等问题加以解决，提出大型邮船舱室模块移运路径规划问题的一种新的解决方案。

通过改进蚁群算法获得的移运路线没有过多的转向且具有足够的通道间距用于运输舱室模块。路线信号带与标签的设置可有目的性地运输舱室模块。通过仿真试验对比，经路径规划确定主、支通道后的舱室模块运输时间均少于未规划的路线，大幅提高舱室模块的运输效率与安全性，对于后续舱室模块的安装和邮船的按时完工发挥重要作用。