船舶维修备件供应调度路径优化研究

侯朵莉，姚玉南

(武汉理工大学 能源与动力工程学院，湖北 武汉 430063)

船舶装备维修的高效性对保证船舶安全航行至关重要，同时是缩短装备维修周期和提高航运企业经济效益的保证。如果装备维修费用过高或维修时间过长，会增加航运企业的经营成本，致使企业经济效益降低。而保证船舶装备高效维修的关键之一是维修备件能够及时供应，维修备件是船舶装备临时抢修、计划修理、状态维修的保障性物资，是开展船舶装备维修作业的物质基础。随着船舶装备技术发展的智能化、系统功能的集成化、任务的多样化、运行环境的复杂化，维修备件供应调度规划往往面临着装备部组件故障的突发性高、备件消耗的不确定性增加、备件需求应急性突出等情况，因此，维修备件能否合理调度与及时供应成为制约船舶装备维修保障能力提高的瓶颈。

在维修备件供应调度规划中，一个重要问题便是对维修备件供应路径的优化。国内外学者对供应路径优化展开了研究，吕游等[1]提出一种改进的蚁群算法用于解决作战物资的车辆运输路径规划问题，并考虑不同作战单元对物资需求的可能变化,用排队策略对算法进行求解,得出适应需求变化的路径,最后通过仿真实验验证了规划路径的合理性。文献[2]介绍了一个涉及大型集装箱的滚动式滚装废物收集运输路径问题，并提出了一种基于大邻域搜索的迭代启发式解决方法。Lin Zhu[3]开发了一个配对的协同再优化(PCR)策略来解决随机需求(VRPSD)的运输路径问题，提出了一种启发式算法，可以根据更新的信息动态地改变访问顺序和运输车辆分配，比较分析结果，显示PCR策略表现更好。马祥丽等[4]在VRPTW问题的求解中引进蝙蝠算法，为了克服基本蝙蝠算法的不足之处,将惯性权重引入蝙蝠速度更新公式中对其进行改进，并采用惩罚函数的方式对目标函数进行了简化求解。郭森[5]提出了一种基于动态学习和突变因子的粒子群算法(DSPSO)来解决粒子群算法(PSO)及其变种在约束多目标等复杂问题优化过程中所遇到的易陷入局部最优和收敛性问题,并在多目标路径问题实例优化中取得了较好的效果。

目前，针对船舶装备维修备件供应路径优化方面的研究较少，且仍采用类比、依靠经验的传统方法。这种传统方法确定的维修备件供应路径规划方式在维修任务多样化时就会显得不适用，在极大程度上影响维修活动的及时展开。

1 船舶维修备件两级保障模式

随着船舶装备数量不断增多，维修工作量日益增大，装备对维修备件的需求量也越来越多，因此，合理的储备维修备件十分重要[6]。同时，维修备件供应路径的合理选取也影响着装备维修保障能力的提高。采用合理的供应路径能够有效满足自主式装备维修备件调度所需求的时间响应、供应成本等方面要求。为此，本文在自主式维修保障[7]基础上提出两级维修保障(基层级和基地级)下的船舶备件供应路径优化策略。

从20世纪90年代开始，美国军方最先认识到三级维修保障模式的局限性，随后对装备采用两级维修保障模式，并取得了成功。实行两级维修保障模式后，保证了基层级和基地级的维修能力。相较传统的三级维修保障模式，其优势和特点主要表现在以下几个方面：减少了中间运转机构，信息流动更加顺畅；减少了由于路径原因使信息丢失或者发生偏差的概率；基地级可以更好的执行总领调度协调的作用，而基层级的要求也可以更加及时准确的得到反馈；缩短了供应保障的周期，维修备件供应直接从基地级到达基层级，提高了故障件的修复效率并提高了维修保障资源的利用率。两级维修保障下备件供应调度模式如图1所示(实线为物流，虚线为信息流)。

图1 两级维修保障下的备件供应调度模式

随着联供联储概念的提出，基于配送中心模式的供应保障已成为备件供应保障研究的热点[8]。为实现船舶维修备件从基地级仓库到各基层级仓库准确、高效的供应，借助配送中心模式构建供应地或配送中心(基地级仓库)—多需求地(基层级仓库)的船舶维修备件供应保障模式，以提高供应配送能力。

2 船舶维修备件供应调度路径优化模型

2.1 参数定义

模型参数及定义如表1所示。

表1 模型参数及定义

2.2 构建惩罚函数

为提高船舶维修备件需求地的维修效率，本文引入软时间窗[9]概念。由于软时间窗路径优化问题考虑时间约束，因此这里引进惩罚函数[10]。假设备件需求地i要求供应时间范围为[bi，ci]，允许的最大服务时间范围为[ai，di]，如果供应车辆在[ai，bi]和[ci，di]时间范围内到达受到的惩罚分别为：f1(bi-ti)和f2(ti-ci)，惩罚值设为一个很大的正数M；而在[bi，ci]时间范围内就不会有损失的惩罚，如图2所示。

图2 惩罚函数定义图

现构建惩罚函数f(ti)如下：

(1)

2.3 基本假设

在软时间窗约束下，结合船舶维修备件供应的特点，可对问题做以下假设：只考虑一种备件供应方式，假设为公路运输；备件供应地和需求地的地理位置已知，且供应地无缺货问题；备件供应地车辆数一定，且为同类型车辆，供应车辆每次完成供应后返回供应地；已知需求地备件需求量和时间窗，且无临时变动；各供应车辆只允许走一条线路，且线路上备件总载量不超过供应车辆的最大装载量，备件供应地到需求地供应的线路始终可行；不考虑供应备件的型号和数量，仅以备件的质量作为需求量的计算单位，单位假设为kg。

2.4 模型建立

决策变量如下：

(2)

运输成本Z1：

(3)

惩罚成本Z2：

(4)

目标函数：

minZ=min(Z1+Z2)，

(5)

s.t.：

(6)

(7)

(8)

(9)

(10)

公式(6)为每台供应车辆上船舶维修备件总需求量不超过车载量；公式(7)、(8)为每个需求地的船舶备件需求量只能由一辆供应车辆配送，且每个需求地只能被供应一次；公式(9)为供应车辆从供应地出发，完成供应任务后全部返回到备件供应地；公式(10)为软时间窗约束。

3 算法设计

由于带软时间窗的路径规划问题具有多个条件约束，传统的遗传算法在解决此类问题时采用随机化搜索，很容易得到劣质解。通过添加算子优化等操作来改进遗传算法，可以有效改善算法的局限性，在多条件约束下得到优质解。算法流程示意图如图3所示。

图3 算法流程示意图

4 仿真实验结果及分析

4.1 适应度函数的设计

算法适应度定为成本的倒数：

fi=1/Zi，

(11)

式中：fi表示第i个个体适应度；Zi表示种群中第i个个体对应的成本。

算法终止条件：迭代次数为500次。

4.2 仿真实验

某沿海城市10个基层级仓库(编号1～10)提出需求，1个基地级仓库(编号0)对其进行维修备件供应，算例可以描述为：由1个配送中心为10个需求地进行维修备件供应。参数f1，f2，α，K，mk值分别设定为1元、2元、15元、9辆、8 kg，求解目标为维修备件供应调度总成本最小化。维修备件需求地信息如表2所示(将某一地点的坐标定为(0,0)，单位距离为1 km)。

表2 维修备件需求地信息

运用MATLAB 2016a软件对目标函数进行优化，结果如表3所示。

表3 优化结果 元

从表3可知，配送中心向需求地供应维修备件的路径规划有4条。当车辆按照规划路径中所对应的需求地供应顺序配送维修备件时，此时供应调度总成本最低为4 342.55 元。MATLAB 2016a软件绘制的维修备件供应最优路径示意图如图4所示。

图4 维修备件供应最优路径示意图

传统遗传算法求得的维修备件供应调度总成本为5 420.65元。图5和图6分别为遗传算法改进前后的迭代示意图。

图5 遗传算法改进前迭代示意图

图6 遗传算法改进后迭代示意图

由图5可知，算法改进前在迭代次数为100次之后寻得目标最优值，而图6中遗传算法改进后在迭代次数为100次之前就已寻得目标最优值。

5 结束语

本文以船舶维修备件为研究对象，针对其供应调度总成本较高的问题建立了路径优化模型。以供应调度总成本最小为优化目标，用改进前后的遗传算法对模型求解。本文所建模型有效实现了船舶维修备件供应路径的优化，对于维修备件及时到达维修地点，提高船舶装备维修效率，降低维修费用具有重要意义；带软时间窗的维修备件供应路径优化模型使路径规划更加科学有效；改进后的遗传算法较传统遗传算法收敛速度更快，维修备件供应调度总成本下降了19.9%，大幅度降低了备件供应调度的总成本。