面向船舶制造企业车间作业过程物料配送优化方法

段金健，王美清，王泽宇

（北京航空航天大学 机械工程及自动化学院，北京 100191）

0 引言

在市场经济环境下，制造企业增加利润的主要方式有两种，获得更多的订单和降低自身的成本。近年来，国际船舶行业需求低迷，船舶行业迎来持续寒冬，订单量持续减少，这使得降低制造成本成为企业获得利润的主要途径。船舶制造过程具有制造场所地理位置分散、物料存放点多，制造过程物料运输环节多等特点，物料配送的效率成为影响企业提高生产效率、降低生产成本的瓶颈之一。因此研究面向车间作业的船舶制造企业物料配送优化问题既可以减少运输成本，又可以提高生产效率，减少空间资源浪费，从而降低船舶生产成本，为企业赢得市场竞争力。

船舶制造企业的物料配送优化问题，主要研究如何在资源约束条件下将正确的物料运送到正确的地点，并且保证成本最低，已有人证明这是一个NP问题[1]。NP问题是完全多项式非确定性问题，所以用启发式算法解决该类问题是一个研究热点。常见的启发式算法有禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法、神经网络算法、粒子群算法等。利用启发式算法解决此类问题，国内外学者进行了大量研究。物料配送过程中主要有能力约束和时间约束。针对能力约束，张涛等[2]利用遗传算法提出了在容量和重量限制下重复使用车辆的物流优化模型，不过其假设所有车辆载重、容量都一致；陈宏程等[3]提出了多车辆多车型的物流配载优化模型，将物流的路径优化模型和多车辆配载相结合，提出了具有装载关系的配送模型，并利用遗传算法对其进行验证，取得了一定的效果。针对时间约束，侯占亭等[4]利用多目标分解的进化算法对带有时间窗的物流优化问题进行了详细研究，提出了一种搜索效果更好的交换算子；Olli Bräysy[5]提出了一种层次化的解决方法，首先通过进化算法找到最短路径，再通过相同路线比较各车辆的花费差异，最后确定最优的路径和车辆搭配；Phuong Khanh Nguyen[6]提出了一个等待区模型，当在时间窗外达到目的地时进入等待区，此时计算路径时加入前往等待区的花费，从而寻找最优路径，这为解决物流配送问题提供了新思路；其他相关研究也为物料配送优化提供了值得借鉴的思路，李冰[7]解决了有顺序约束指派问题；叶炜[8]建立了交通管制下的物流优化模型，分析了交通管制对路径选择的影响；罗梓瑄[9]通过蚁群算法建立了成本最小化和碳排放量最少化的多目标优化模型。

综上所述，前人的研究多集中在寻找物流最短路径方面，但实际船舶制造过程不仅仅要求物料配送路径最短，还需要考虑多车辆下的派工问题，本文根据船舶制造过程物料配送特点，提出了一种面向船舶制造过程车间作业的物料配送优化方法，建立了船舶制造过程的物料配送优化模型，提出了考虑道路约束、工序约束和容量约束的成本最低配送方案，基于蚁群算法进行了工作地间路径寻优，融合图论和退火算法进行任务分配，最终实现了在车间作业约束下搜寻最优派工和最短路径的目标，并通过MATLAB仿真验证了所提方法的有效性。

1 面向车间作业的物料配送优化模型建立

面向船舶制造企业车间作业的物料配送模型十分复杂，完全对其进行建模和求解有一定难度。因此本研究取其中适用性高、影响大的因素为优化目标。物料配送优化本质上是搜寻成本最低的配送方案。船舶制造过程中的物流配送特点是：1）各工作地点间的道路并非直线需要考虑工作地间的实际道路，为了方便问题研究，本文将两目标点间的直线路径模型称为“路径”，将两目标点间实际存在可达路径的折线路径模型称为“道路”；2）物料的配送有顺序，需要按照工序将物料依次送达目的地，因此建立模型时必须引入工序约束；3）船厂配送的物料较多，一般不能由一辆车全部配送完成，因此必须研究车辆的任务分配问题。基于上述特点可以建立如下数学模型。

1.1 研究假设

为了更好的优化目标，假设物料配送过程满足以下条件：

1）物料运输方向满足工序间顺序要求，不存在因反向作业，导致的车辆需要多次经过同一工作地的情况；

2）各作业地点间道路通断情况已知；

3）车辆载重已知，运载时只考虑载重要求，且一个任务地的需求可由一辆车配送。在实际生产中，如果一个工作地需求大于一辆车载重，可以先派出车辆满载，直至需求减为一辆车载重以下后，再进行任务分配；

4）配送任务和工序作业清单已知。

1.2 数学模型

针对物料配送优化问题约束多、优化层次复杂的特点，建立了面向道路、任务和容量约束的多层次多目标优化数学模型。

1）面向道路约束的最优道路搜索模型

模型的道路约束由式(1)表示，其中Z1(i,j)表示两工作地间运输的最小花费，cp表示经过第p条道路时的费用，opij表示在从工作地i到工作地j是否经过道路p，是为1，否为0。通过式(2)将从工作地i到工作地j的最短距离集传递，Cij表示由工作地i到j的最小花费，通过这个模型寻找各工作地间的最短道路。

2）面向工序和容量约束的最优任务分配模型

其中式(3)表示第k辆车分配的任务重量小于其载重，形成了容量约束，式(4)表示一个工作地的任务只由一辆车配送，并且所有任务由m辆车完成，式(5)限制到达某工作地的只有一辆车，式(6)表示限制某工作地只有一辆车。表示第k辆车是否经过i、j间的道路，是为1，否为0，表示第i个工作地需要资源重量，表示第k辆车是否经过第i个工作地。式(7)表示工序对路径选择的影响，到达每个工作地前必须考虑是否已经经过其前序工序，表示第k辆车分配的任务中是否有i、j工作地，表示第k辆车在到达第j个工作地前是否到达过其前序工序。式(8)表示每辆车交接时工作地间的路程最长，表示第k辆车和第k+1辆车的交接路程。

3）各车辆运输成本最低模型

其中式(9)表示各车辆运输成本，其中Zk指第k辆车的运输成本最小，cij是满足道路约束时从工作地i到工作地j的最短距离，xijk是满足工序约束、容量约束最优任务分配模型的工作地i到工作地j间的可行道路。

2 面向车间作业的物料配送优化方法

2.1 面向车间作业的物料配送优化过程模型

根据建立的数学模型将优化流程分为以下三步：

1）搜寻工作地间的最优道路。在实际制造过程中，各个作业地间的距离并不能以直线判定，所以在进行最优的工作地到达顺序搜寻时，首先要对各个工作地间的道路进行选择，从而找到各个工作地间的最短道路和距离，形成最优道路集，由于有道路约束，随机生成新解和交叉较为困难，采用蚁群算法可以较好地解决这一问题。

2）搜寻最优的车辆任务分配。在配送过程中，由于每个车辆的载重有限，当需要配送的物料总重大于单车辆载重时，需要通过多车辆配送。但是，整个配送任务需要满足工序要求，因此需要研究在不改变工序要求的目的地到达顺序的前提下，寻找分配方案使得多车辆协作时成本最低，通过有向图可将问题简化，配合退火算法有利于解决模糊问题。

3）搜寻当前任务下单车辆的最优路径。形成最优任务分配集后，虽然有工序约束，但是一辆车可能会执行多个产品物料配送，它们的工序是并行的，因此还是会出现多种路径安排，需要对路径进行进一步优化，以实现配送成本最低。面向车间作业的物料配送优化过程模型如图1所示。

图1 面向车间作业的船厂物料配送优化流程

2.2 基于蚁群算法的工作地间最优路径搜索

蚁群算法是Marco Dorigo 1992年提出的，用于解决组合寻优问题的启发式寻优算法。基础的蚁群算法具有良好的搜索速度，但是也存在容易陷入局部最优解的不足，本文将遗传变异思想与蚁群算法相结合，提出了面向船舶制造过程中工作地间最优路径的搜索方法。具体过程方法如下：

第1步：参数初始化，导入工作地位置、道路关键节点、节点间的联通情况、各个道路的长度、设置变异概率、设置当前迭代次数NC=0、设置最大迭代次数NC_MAX、设置蚂蚁数、设置初始信息素浓度、信息素挥发率及诱导因子等。

第2步：进入循环，NC NC+1，将所有的蚂蚁放置到起点，将起点加入禁忌表。

第3步：逐个蚂蚁开始寻找下一个节点，下一个节点是从除去禁忌表中已走过的节点，若没有可选节点，则代表其进入死区，这时需要终止这只蚂蚁循环，并对其在后期释放信息素时给予相应惩罚。每只蚂蚁寻找节点由转移概率公式决定，即：

其中τij代表节点i到节点j间的信息素浓度；是启发函数，这里用节点i到节点j间的距离倒数表示，j表示所有可行节点。获得转移概率后，将所有可行节点的概率转化成轮盘赌中可行域的大小，从而随机决定蚂蚁爬向的下一个节点。

第4步：判断蚂蚁爬向的节点是否是终点，如果是终点则终止，记录这只蚂蚁的总花费和路线，如果不是则将这一节点加入禁忌表，返回第3步，直到所有的蚂蚁爬到终点。

第5步：设置变异概率，每只蚂蚁的爬行路线按一定概率进行变异。

第6步：计算本次迭代的最优解，记录其路径，并且依据每只蚂蚁的路线更新信息素，更新信息素时采用分级蒸发策略，路程越长的路径蒸发越快，爬进死区的蚂蚁进行惩罚释放信息素为0。

第7步：判断NC=NC_MAX，若不等则返回第2步，清空禁忌表，若等于则停止迭代，寻找记录的各代最优解中的最优的，输出最优路径和最少花费。

本算法将遗传算法中的变异原理融入蚁群算法中以增加算法的随机性，减少陷入局部最优的可能性。

2.3 基于转化模型和退火算法的任务分配

2.3.1 基于图论的问题转化

船舶制造过程中的物料运输任务可以描述为有n个工作地，m个运输车辆，k个产品，每个产品有nk道加工工序，将其排列出来，对工作地进行编号，编号满足先序任务的工作地编号必须小于后序任务的工作地编号。取一个工作地任务分配实例如图2所示，其中有14个工作地，3辆运输车辆，2个产品，产品1有11道工序，产品2有10道工序，将工作地编号形成点，并将工序连接起来形成有向边。此时便将加工任务转化为一张有向无环路图，顶点集为，边集为，在本实例中n=14，l=16。

图2 作业任务工作地分配示例

通过以下概念可以将加工任务分配问题转化为求割通过的边权值最大问题。

1）划分：集合{V1，V2，...，VN}是图G(V，E)的划分，则应当满足

2）割：若{V1，V2}是V的划分总有，v1i＜v2j则称{V1，V2}是V的割，在本问题中V中所有元素满足上述编号要求。

3）割点：若{V1，V2}是V的割，取v1i=min(V1)，取v2j=min(V2)，称{v1i，v2j}是V的割点。

4）连续点集：如果V中的所有的点都是连通的，则称V为连续点集。

5）连续划分：集合{V1，V2，...，VN}是图G(V，E)的割，且满足V1，V2，...，Vn都是连续点集，则称{V1，V2，...，VN}是图G(V，E)的连续划分。

根据以上概念对给出的任务分配进行连续划分，在图3中{V1，V2，V3}就是有向无环图G(V，E)的一个连续划分。

满足上述要求后，1）取工作地需要的资源为点的权重W(i)；2）取工作场地间运送花费为边的权重，记为c(i，j)。这样分配问题就转化为求取最佳划分问题，取划分{V1，V2，...，VN}为V连续划分，则显然每个Vi是连续点集，这保证每个划分内部都是连通的。这时最佳分配问题转化为在满足划分内点集的权重总和小于车辆载重时，分割所经过的边的权重值之和最大，在保证车辆装卸次数最小的情况下，交换车辆节约的路程最大。

2.3.2 基于图模型的最优任务分配方法

在将任务分配问题转化为图论问题后，将图论知识与退火算法相融合，设计了最优任务分配搜索算法，具体步骤如下：

第1步：参数初始化，首先任意给出一个工序排列，再对其进行任意连续划分，这里不需要满足容量条件，记初始排列为O0，初始划分为Cut0。设定退火算法初始参数，初始温度T0=100，温度衰减系数α=0.95，初始温度下的搜索次数L=0，最大搜索次数，L_MAX=20迭代次数为NC=0，最大迭代次数NC_MAX=100。

第2步：令NC=NC+1，L=+1，进入循环迭代，首先产生新解，将当前工序按照分割进行左右长移，计算过左右长移使Σc(i，j)增加的成本，记为Pv，则接受这次新解的概率为：

左右长移是在不改变工序顺序的情况下进行的排序移动，本文仅介绍右长移的步骤，左长移同理。{V1，V2，...，VN}是图G(V，E)的一个划分定义：

即当i，j 之间有边时f(i，j)=1，当i，j 之间无边时f(i，j)=0。若f(vp，vp+1)=f(vp，vp+2)=f(vp，vp+n)=0，且f(vp，vp+n+1)≠0，则将点vp移动至vp+n到vp+n+1之间，称为点的右长移，右长移并不会改变工序顺序约束。

第3步：获得新的排列后，求解其满足容量约束的最优划分。设H(v)指图的最后一个割点为v时的最大成本，S(u，v)是在割点u后增加一个割点v所增加的最大成本，则可以通过以下步骤寻找最佳分割：

1）令v=1，U={1}，u∈U，即u=1，H(v)=0。

2）令v=v+1，U={1，2，...，v-1}，∀u∉U，同时点集{u,u+1，...，v-1}中点的权值小于车辆总载重，使得H(v)=max[H(u)+s(u,v)]，将此时的{u,v,H(v)}作为一个元素放入集合B中。

3）判断v=n+1，若不等于重复1），若等于进行4）。

4）在集合B的元素中寻找v=n+1时对应的u，记为um，接着寻找v=un+1时所对应的u，记为um-1，不断重复直到寻找到v=1时对应的u=1。

5）输出最佳划分的割点集合为{1，...，vm-1，vm}。

第4步：计算当前排列下最佳划分的割和经过边的总权值Σc(i，j)，并与最大权值比较，若大于最大权值则更新最大权值。

第5步：判断L≤L_MAX是否成立，成立则返回第2步，不成立到第6步。

第6步：判断NC≤NC_MAX是否成立，成立则输出最优排列和最优划分，如果不成立，则令T=T×α，进行降温。

2.4 基于蚁群算法的考虑任务分配的车辆最优路径搜索算法

基于所建立的工作地间最优路径搜索和基于图模型的最优任务分配方法，设计了如下的考虑工作地点间工序约束的，面向船舶制造企业生产过程中的物料配送问题的车辆最优路径搜索算法。

其算法流程与2.2节中所述算法相似。关键在于第3步，需要令一只蚂蚁爬向下一目标工作地点，下一目标工作地点的选择有两个约束，首先其不在禁忌表内，然后其前序工序的工作地在禁忌表内。如果没有可选目标工作点，判断是否爬行完所有目标工作点，若没有则取消这只蚂蚁的循环，并加入惩罚，若爬行完则终止。通过此步骤可以在蚂蚁选择道路时添加工序约束。对每个运送车辆执行算法，即可得到在工序约束、容量约束和道路约束下每辆车的最优路径。

3 试验仿真与结果分析

按照上述优化流程进行试验仿真分析，以一个包含10个任务地5个产品的运输优化任务为例，工作地的坐标和容量如表1所示。按照优化流程首先应当进行工作地间最短道路搜索，形成最短道路集，由于道路集较多，在这里仅展示工作地1，2，3之间的最短道路，仿真的工作地和路口信息如表2所示。

表1 10个工作地的任务基本信息

表2 工作地及路口坐标

利用MATLAB 2018 A 进行仿真，设定m=2 2，NC=300，α=3，β=4，Q=2 0，ρ=0.2，变异概率p=0.3，计算的结果如图3所示。

图3 蚁群算法搜索工作地间最短路径的算法结果

从图4由可以看出，工作地1到2之间的最短道路为工作地1→路口12→路口10→工作地2。在迭代20次左右算法趋于平稳，由于有0.3的变异概率仍然会有路径发生变异，本算法能较好的生成各工作地之间的最短路径集。

按照算法流程进行最优任务分配得到的结果如图4所示。其中可以看出在工作地6和7之间通过割的边的权重最大，形成任务分配集。

图4 10个工作地的最优任务分配

得到任务分配集和由最短道路集生成的最短路径距离集后对单车辆配送路径进行优化得到结果如图5所示。

图5 10个工作地分配后的最优路径

可以看出在本实例中车辆1 的运送路径为1→3→2→5→4→6，车辆2的运送路径为7→9→8→10，最短的运送距离为41.6454，本方法能完整的完成在工序约束、容量约束和道路约束下的物料配送最优路径搜索。

随机取10个、20个和30个工作地配送任务，工作地在相距为10的地图中随机生成。为了实现运输任务完全按照工序顺序约束执行，分别计算10次随机实验直接按照工序运送和分配优化后的平均路程，得到的结果如表3所示。

表3 按照工序运送和分配优化后的平均路程

由表3可以看出优化后的平均路程小于直接按工序顺序的平均路程，在保证各个工序连通性和车辆的容量要求下平均路程有效减少。

4 结语

船舶产品制造过程中物料配送占据了制造成本的很大一部分，本文设计了一种面向车间作业过程的船舶制造过程物料配送方案。通过改进蚁群算法寻找到了各工作地间的最短路径，采用图论将任务分配问题转化成求取连续划分的割所通过的边的权值最大问题，基于退火算法实现了车辆容量和工序约束下的任务分配，接着通过蚁群算法在工序约束下进一步优化了单个车辆的配送路径，并通过仿真对整个算法流程进行了验证，仿真结果表明该算法能有效减少任务分配后的平均路程，对减少船舶制造过程物料运输的成本、提高运送效率有重要意义。