基于改进粒子群算法的车间物料配送方法研究

杨 倩，陈再良

（苏州大学机电工程学院，江苏 苏州 215137）

1 引言

物料配送作为车间这一生产单元的重要活动，选择合适的搬运设备将正确的物料以所需的数量在正确的时间送至目标工位将成为首要考虑问题，对此进行研究对提高生产效率与控制成本具有重要意义。

目前，国内外不少学者对车间物料配送问题展开了相关研究，研究内容主要集中在两方面：单个物料搬运设备的物料配送问题和单种多个物料搬运设备的物料配送问题。如文献［1］考虑了机器人（Mobile robot）的配送能力约束，研究了单个移动机器人物料配送方法；文献［2-4］则对单个可移动机器人的物料配送顺序进行决策；文献［5］以线边库存最低为优化目标研究了装配线中单个Tow Train的准时制送料问题；文献［6］研究了含时间窗和容量约束的多ATV（Automated Transport Vehicles）运输调度问题；文献［7］则考虑了带线边缓存容量约束的多个搬运车准时化物料供应调度问题；文献［8］研究了以能耗和加权延迟时间为目标函数的多AGV混流装配线送料问题，并提出禁忌粒子群算法对其进行求解。

综上，现有文献多集中于研究单个物料搬运设备或同种多个物料搬运设备的物料配送问题，暂未发现考虑多种多个物料搬运设备协同调度的车间物料配送情况；而在实际生产中因物料规格、型号、重量不一，车间物料搬运设备是多种多样的［9］。基此，在分析上述文献的基础上，以搬运成本和线边库存成本最小化、平均装载率最大化为优化目标建立物料配送模型，并设计改进粒子群算法对其优化求解，在保证高效、准时送料的同时最小化投入成本和最大化搬运设备利用率。

2 数学建模

2.1 问题描述

一个采用物料超市的装配单元，物料超市暂存来自中心仓库的不同规格大小的料箱，因料箱体积、重量各不相同，本单元采用多种物料搬运设备，并根据装配物料清单（Bill of Material，BOM）和装配计划对目标工位进行物料配送，如图1所示。

图1 装配单元布局图Fig.1 The Layout of Assembly Part

为了有效描述该物料配送问题，作如下假设：

（1）装配单元采用装配线节拍作为基本时间单位；

（2）车间依装配计划进行装配，且装配BOM事先已确定；

（3）各料箱的物料类型和数量已知；

（4）由于物料装卸时间较短，故运输过程中不予考虑；

（5）物料的搬运成本与其搬运量成正比；

（6）各工位物料的消耗量与节拍时间线性相关。

2.2 数学模型

（1）问题参数：i为搬运设备类型；j为搬运物料种类；k为配送批次；n为搬运设备编号；w工位索引；τ为装配线生产节拍；qin为第i类搬运设备索引；αi为第i类单个搬运设备的固定成本；βi为第i类搬运设备的搬运成本系数；γjw为w工位储存j类物料的成本系数；Fjw为单位生产节拍工位w需要消耗物料j数量；sk为第k批物料出发时间；为初始时刻工位w物料j初始库存；为在第k次配送中运到工位w的物料j数量；Vij为第i类运输设备对物料j的运量；Sjw为工位w对物料j的最大线边缓存能力；TD为运输成本；TI为线边库存成本；η为平均装载率。

（2）决策变量：tk为第k批物料到达时间为第k次搬运中是否用到搬运设备为在第k次搬运中是否用搬运设备qin搬运物料j；在第k次配送中搬运设备qin运输到工位w的物料j数量；Qki第k次运输中第i种运输设备数量。

（3）数学模型：目标函数为：

其中，式（1）为目标函数，式（2）和式（3）分别为物料搬运成本和线边库存成本；式（4）为平均装载率；式（5）为运量约束，即每次运输的总物料量不能超过该批次所使用的运输设备总运量；式（6）为生产需求约束和缓存约束，即到达前k批物料应满足第k+1批物料消耗需求，且当第k批物料到达时，总物料应小于最大线边缓存量；式（7）表示单批次各运输设备运力之和应至少大于一个节拍内各工位零件所需数量；式（8）和式（9）分别表示第1批或第k批物料到达时间应小于或等于物料消耗最快的工位的要料时间；式（10）为变量约束。

3 算法构建

由问题描述可知多种搬运设备协同调度问题属于多目标多约束优化问题，目前PSO（Particle Swarm Optimization）算法已广泛应用于求解TSP［10］、VRP［11-12］、物料配送［13］等多目标多约束优化问题，然而经典PSO算法虽然易于实现，却容易陷入局部最优；文献［14］提出的综合学习粒子群算法（Comprehensive Learning Particle Optimization，CLPSO）虽在一定程度上解决这个问题，但仍很难摆脱局部最优；故参考文献［15-16］，构建了改进粒子群算法，即在CLPSO算法的基础上增加转移算子，设计粒子转移策略，使搜索粒子能更有效跳出局部收敛区域，进而搜索全局最优，其算法流程，如图2所示。

图2 改进粒子群算法流程图Fig.2 Flowchart of the Improved PSO

3.1 适应度函数

由上述可知，该模型为多目标函数模型（运输成本、线边库存成本、平均装载率），因此为了使目标函数同质化，现将适应度函数调整为：

式中：个体x—一个可行解（即被选方案）。

3.2 粒子编码设计

物料搬运设备的协同调度问题，其实质是确定物料运输次数、搬运设备类型及数量、搬运物料种类及数量、所至工位等，故对优化算法的粒子采取三层变长编码方式，即x={K，X，P} ，式中K为物料运输次数；X={n，i，k} ，表示使用索引为qin的搬运设备；P={k，i} {n，j，w} ，表示使用索引为qin的搬运设备送至w工位的物料j数量。

3.3 初始种群生成设计

改进粒子群算法是对群体进行进化的操作，需要初始化群体数据构造初始解，其步骤为：

（1）根据约束式（5）和式（6）中的缓存约束确定最少运输次数Kmin，定义：

（2）根据约束式（8）和式（9）确定下一批次物料到达时间，定义：

式中：i—消耗最快的物料种类编号；Δt1—与times1对应的物料运送时间间隔；Δt2—与times2对应的物料运送时间间隔。

（3）初始化运送物料量，根据需要运送的物料量确定搬运设备类型、数量及运量，若满足约束（6）中的需求约束，则输出配送结果，否则返回（2）。

3.4 粒子转移策略

当Tu＞0 时，随机选择一个较差的粒子，使其以Pm的概率跳出局部收敛区域并将其转移到较优的位置；定义局部收敛区[μj-σj，μj+σj]N，而粒子转移的概率由粒子位置上的方差、粒子速度以及粒子与gbest的距离等动态因素决定［13］，计算的公式如下：

式中：μj和σj—所有粒子在第j维的位置均值和标准差；vji—第i个粒子在第j维的速度；gbestj—所有粒子在第j维上的最优位置；σj，|vji|和|μj-gbestj|越小，则Pmji越大，即粒子越有可能在第j维跳出局部收敛区。

4 仿真分析

这里算法和实验均在内存为8GB、处理器为Intel（R）Core（TM）i7-865U CPU @1.80GHz 2.00 GHz 的计算机上进行，采用MATLAB（2018a）编程实现。

4.1 参数设置

以某公司助力器装配车间中的某四个工位为例，验证多种物料设备调度模型，产品-物料BOM、工位-初始库存、工位-最大线边缓存以及工位-物料储存系数，如表1 所示。某日生产计划2000件，生产节拍为15s。车间有3种物料搬运设备，分别为脚轮车、手推车和平台车，每种运输设备各有3辆，每种搬运设备的固定成本分为3、4、5，其搬运成本系数分别为0.01、0.01、0.015；其中脚轮和平台车仅运输小料和大料，运量（按物料箱计算）分别为10和5；手推车可运输小料和中料，运量分别为15和10；小料、中料、大料料箱容量分别为100、50、25；优化参数分别为：初始粒子群数30，循环迭代次数100。

表1 工位-物料BOM/初始库存/最大线边缓存/储存系数Tab.1 Station-Bill of Material/initial Inventory/Maximum Line-Side Buffer/Storage Coefficient

4.2 仿真结果

算法运行时间对比图，如图3所示。根据以上数据，利用改进PSO算法计算的总成本为547.875，平均装载率55.4%；每次配送的搬运设备类型与数量、搬运物料种类和运量、所至工位到达时间具体，如表2所示。限于篇幅，仅列出前三次物料搬运方案。

表2 物料搬运设备协同调度方案Tab.2 Scheme of Co-Scheduling of Material Handling Equipment

图3 算法运行时间对比图Fig.3 Comparison Chart of Runtime

为验证改进PSO 算法的适应性以及效率性，将其与自适应PSO 算法进行对比，利用自适应PSO 算法计算的总成本为569.530，平均装载率为53.6%；同时更改粒子群数目与迭代次数大小，对比其算法运行时间，其中，实验组别1，3，5，7粒子群数目为30，迭代次数为100、200、500、800；实验组别2，4，6，8的粒子群数目为50，迭代次数同上。

从图3可知，改进PSO算法的运行时间总是低于自适应PSO算法，当粒子群数目和迭代次数都比较大时，这一差别尤为明显。结果表明，改进PSO算法的解优于自适应PSO算法，且计算时间短。

5 结论

针对含多种物料搬运设备的车间送料问题，提出多种物料搬运设备协同调度物料配送模型，并设计改进粒子群算法寻求最优解，得到具体物料配送方法。所得研究成果可帮助企业合理安排物料搬运设备，为企业提供一种准时化物料供应方法，避免企业为防止缺货而频繁送货，可有效降低企业成本。然而，文总在研究多种搬运设备协同调度物料配送模型时未考虑多种搬运设备在车间的并行可能性以及车间突发性因素，如搬运设备故障、装配计划变更等；后续将进一步研究并行可能性以及不确定因素对模型的影响。