基于PSC-IGA算法的数字化车间仓配一体化研究

胡小建, 刘婷婷

(1.合肥工业大学 管理学院,安徽 合肥 230009; 2.过程优化与智能决策教育部重点实验室,安徽 合肥 230009)

数字化车间(digital workshop,DS)建设是制造企业走向智能制造的起点。《中国制造2025》中明确指出:“推进制造过程智能化,在重点领域试点建设智能工厂/数字化车间。”物料的仓储和配送是数字化车间保证生产的重要环节,两者密不可分,仓配一体化就是建立一种协同机制,以仓辅配,以配定仓,优化制造流程,降本增效。

现有文献对物料仓储与配送问题的研究颇多。在物料配送方面,物料配送路径优化问题是车辆路径问题(vehiacle routing problem,VRP)[1]的一个经典变种问题,文献[2]考虑车辆负载均衡,用混合多目标进化算法有效减少了总行驶距离;文献[3]以配送时间和作业人数为优化目标对该问题进行研究。带时间窗的车辆路径优化问题(vehicle routing problem with time window,VRPTW)由文献[4]提出,学者们在此基础上构建了很多不同的VRPTW优化模型,如带混合时间窗[5]、带软时间窗[6]和带时间窗的同时取送货的车辆路径优化模型[7]等。针对物料的仓储问题,数字化车间一般配备的都是自动化立体仓库(automated storage and retrieval system,AS/RS),文献[8]对立库系统进行了综述分析；文献[9]用遗传算法求解多目标货位优化问题;文献[10]和文献[11]建立了多目标优化模型,前者考虑出入库效率和货架稳定性,在算法上使用了病毒协同遗传算法,后者考虑物料周转率和相关性,在算法上使用了基于Pareto保持和模拟退火算法。而在仓配一体化问题上,现有文献大多针对电商领域,对于制造业中的生产物流仓配一体化问题的研究相对较少。

本文以安徽博一流体传动股份有限公司(以下简称为BY)的数字化车间为例,研究生产物料的配送和仓储一体化问题,结合生产物流的特性提出仓配整体解决方案,先求解数字化车间工位的配送问题,确定出配送效率最高的配送方案,再基于确定出的配送方案以及数字化车间的库位、工位的分布特点建立2层布尔围道矩阵进行约束,最后采用改进遗传算法进行求解,得到仓配一体化方案,具有一定的创新性和实际应用价值。

1 数字化车间仓配一体化方案

本文从配送效率和仓储效率出发,提出在生产车间内部的仓配一体化物流方案。该方案主要分为2个阶段：

(1) 配送路径优化。根据生产订单要求,采用倒排的方法明确各工位的需求时间窗和需求数量,保证在时间窗允许的范围内寻找小车配送各工位物料的最优方案和最佳配送路径,确保生产效率不受影响。

(2) 立库的货位分配优化。根据配送需求信息,建立物料出库的时间和顺序等约束,在满足配送需求的情况下以堆垛机运行功率和时间最小为目标寻找物料的最优存储货位和拣选路径。该方案将生产物流中的仓储、配送问题进行关联,互相约束,使生产物流达到整体最优。

1.1 生产物料配送路径规划模型

本文首先建立物料配送路径规划模型,考虑物料配送所需小车数量和需求时间窗,以此达到配送时间最短的要求,获取物料出库的准确时间和顺序,此为方案的第1层。

1.1.1 配送路径规划问题描述

数字化生产车间有缓存物料的立库1个、小车k辆和装配工位m个。立库存储来自零件库的齐套物料,物料均以工装板/周转箱为单位。在一个配送周期内,每个工位都有齐套物料配送需求。任意工位的配送任务可以由任一配送工具执行且只能配送1次,在配送过程中,通过生产排程可知第i个工位最早接收物料的时间为Ai和最晚接收物料的时间为Bi,即存在1个服务时间窗[Ai,Bi],物料到达工位i的时间必须在时间窗内,早于或晚于时间窗要求都会给生产进度带来影响。要求车间在满足上述约束条件的前提下,将生产物料配送至各个工位,目标是用最短的运行时间满足生产车间的物料需求,最终形成一条最优的物料配送方案。由于实际情况的复杂性和不确定因素,为有效描述该问题,现做如下假设:

(1) 物料配送前明确配送路线和行驶时间,不考虑因漏装物料导致的往返情况。

(2) 生产计划是己知的,立库的物料完全能够满足生产现场的生产需求,车间能够平稳连续地生产。

(3) 各个物料需求点已知且需求量均为齐套物料,且物料需求点的时间窗和初始位置到各工位的移动时间已知,由上文建模计算得出。

(4) 用于配送的小车类型和承载能力相同,保持匀速运动,且一定能承载所有物料。

(5) 物料出库位置固定,小车初始位置记为S0,为加工车间的工位进行物料配送作业,当小车完成该次配送作业中的全部任务,会回到初始位置,等待执行下一次配送作业。

1.1.2 配送路径规划模型构建

假设小车匀速运动,速度记为V,清洗时间固定,记为Tw,有k辆配送工具,T为配送工具从立库初始位置S0到各工位的时间矩阵,si为小车卸货时间,装车时间忽略不计,共有q辆配送工具,d为小车k从初始位置的出发时刻。

目标为最小化物料配送总时间，表示为:

(1)

其中:从左至右依次表示物料从仓储区初始位置到工位i的总配送时间、需要清洗的物料的总清洗时间、小车k从工位i到工位j的总配送时间、物料卸货时间以及配送时间点不在服务时间窗内的惩罚时间;yik、xijk、zi为决策变量。当工位i由小车k进行配送时,yik取值为1,否则为0;当小车k由工位i配送到工位j时,xijk取值为1,否则为0;当物料需要清洗时,zi取值为1,否则为0。物料配送到第j个工位的时间点为:

(2)

约束条件如下:

(3)

(4)

(5)

C≪D

(6)

Ai≤ti≤Bi

(7)

其中,i=1,2,…,m。

(3)式表示工位i对应的物料且只能由1辆运输工具运输;(4)式、(5)式表示运输工具从起始位置出发最后回到起始位置;(6)式表示若不能在规定时间窗内配送,则惩罚,C、D分别为早到和迟到的惩罚因子;(7)式表示物料到达工位时间点需在时间窗内。

1.2 基于物料配送需求的货位分配优化模型

通过上述物料配送路径优化,即可确定每种物料出库的顺序及时间要求等,以此为基础利用多色集合理论对货位分配进行约束,再通过目标函数优化确定货位分配方案,此为仓配一体化方案的第2层。

1.2.1 物料货位分配优化问题描述

在数字化生产车间内部,立库往往起到缓存物料的作用。根据当前生产周期内的订单需求,物料事先齐套完成,进行入库,并根据方案第1层产生的物料配送顺序和产线实时需求生成出库任务,堆垛机按照顺序进行拣选并送至立库出口,即上文小车的起始位置S0。单排货架示意图如图1所示。

图1 单排货架示意图

1.2.2 物料货位分配优化模型构建

根据分巷道存放原则,同类型的货物均匀分布到每个巷道的2排货架上,因此,这里只考虑单排货架,货架共有S列Q层。立库中堆垛机水平及竖直方向均保持匀速运动,移动速度分别为V1、V2,水平及竖直方向的移动时间记为T1、T2。每个库位大小相同,宽为L,高为H。将距离近似为横纵坐标值,则第a层b列的库位坐标记为(bL,aH)。g为重力加速度,P为堆垛机牵引功率,堆垛机水平及竖直方向做功分别记为W1、W2,M为物料质量。为了提高立库运行效率,本文以堆垛机运行时间和能耗为优化目标,建立优化模型。

最小化堆垛机能耗F1为:

(8)

最小化物料出库时间F2为:

(9)

约束条件为:

1≤i≤n,i为编号为i的货位,n为任务单上待拣选的货位数;

2≤i≤PQ,PQ为货架上总的货位数量。

综上所述,针对不同的优化目标分别建立目标函数,形成了多目标优化问题模型。综合考虑所得的均衡解即为全局最优解。

2 求解数字化车间仓配一体化问题

2.1 算法流程

本文设计了求解数字化车间仓配一体化问题的两阶段遗传算法。

第1阶段根据一个生产订单的需求,通过配送路径规划确定所需小车数量和物料需求时间窗。

第2阶段根据路径优化结果对立库作业进行规划,以此优化整个生产车间内部的仓配问题。算法流程如图2所示。

图2 算法流程

2.2 算法设计

2.2.1 第1阶段配送路径遗传算法

(1) 编码设计。采用自然数编码的方式。假设该生产车间一共有8个工位,分别用0～8来表示物料配送初始位置和各个工位。假设要使用3辆配送工具才能完成配送任务,根据规则可知,其中一条染色体可以表示为(0,3,5,0,8,7,2,0,1,4,6,0),子路径如图3所示。

图3 第1阶段遗传算法中的染色体

(2) 初始种群。随机生成包含1～8且不重复的自然数排列组合,即是一个基因段,开头和末尾为0,再把k-1个0随机加入该数列中,且0不连续。这样就构成1个满足约束条件的染色体,重复上述步骤直到产生足够多的染色体。

(3) 适应度函数设计。将(1)式加1后再取倒,防止正向溢出,即

(10)

(4) 选择。采用轮盘赌法,每个个体被选择的概率与其适应度值成正比,然后每次从父代种群中选择2个个体进入交叉变异操作。

(5) 交叉。本阶段采用换位交叉的操作方式。换位交叉可以加速算法的收敛,根据交叉概率替换群体中的一些染色体,可以避免随机交叉可能带来的不良影响,提高群体整体的性能。

(6) 变异。为了提高变异后染色体的多样性,本文采用旋转变异的操作方式,在求解过程中克服早熟,避免陷入局部最优。

(7) 结束。将得到的子代与父代个体的适应度值进行大小比较并替代。根据设置的最大迭代次数直到输出最优解或近似最优解为止。

2.2.2 第2阶段基于多色集合约束的遗传算法

(1) 基于约束模型进行染色体编码。仓配一体化问题的解包含工位所需物料的出库顺序及库区的选择2部分内容。为了反映这2个部分,采用基于工位和库区的2层编码方式。

第1层采用基于优先权规则的自然编码方法。各基因对应的工位按照矩阵M1的行对应的工位的排序依次放置,基因值为优先权随机数。若有10种物料,则在{1,…,10}中产生不同的随机数作为基因，即

(11)

第2层采用实数编码,为第1层编码对应各物料存储的库区。通过搜索矩阵M2获得基因,各物料的基因从矩阵M2中对应的统一颜色中为1的个人颜色所对应的库区编号中随机获取,以保证每个基因是有效的。

(12)

(2) 初始种群。按照上面编码规则,利用计算机随机产生初始种群,每个染色体由长度各不重复的基因值组成。这个初始种群经过选择、交叉和变异操作,循环若干代后得到一个最优解。采用以上编码方式解决上述问题的一种编码方案见表1所列，即一条染色体。

表1 物料编码方案示例

(3) 计算适应度。目标函数分别是求最短时间和最低能耗,均求最小值。选用权重系数法给各目标函数赋权将其转换为单目标问题,先采用极差法去量纲，即

(13)

其中:f为目标函数;fmin、fmax分别为目标函数的最小值和最大值。2个目标函数通过转换后分别记为f1′、f2′,完成去量纲操作;再主观赋权,系数均为0.5,因此,组合后的单目标函数为:

minF3=0.5f1′+0.5f2′

(14)

为防止正向溢出对目标函数加1后再取倒作为适应度函数。本文的加权重系数后的单目标适应度函数为:

(15)

(4)选择、交叉、变异。根据适应度值大小在父种群中选择特定数量的个体遗传到下一代子种群进行交叉和变异操作。交叉和变异算子分别采用循环交叉算法和换序变异算法,自适应交叉概率c及变异概率d计算公式如下:

(16)

(17)

其中,c1、c2、d1、d2为常数。

(5) 结束。设置遗传代数,当达到设置的遗传代数则终止算法。

3 算例与结果分析

3.1 配送路径规划算例求解

本文以BY数字化生产车间为例,根据上文提出的第1层遗传算法解决路径最优问题。根据实地调研,已知该车间有1个立库、8个工位,清洗时间Tw固定为1 min,装货时间忽略不计,卸货时间si固定为1.5 min,早到惩罚因子的取值为60 min,迟到惩罚因子的取值为90 min,8个工位对应的时间窗分别为[0,6]、[3,6]、[5,8]、[2,6]、[3,9]、[6,9]、[6,12]、[5,13]。初始位置至工位及工位间配送时间见表2所列。

将表2中数据代入模型,设置如下遗传算法参数:初始种群大小为50,交叉概率为0.9,变异概率为0.1。将上述参数分别代入Matlab程序中,经多次实验,确定遗传迭代次数为200次。

表2 初始位置至工位及工位间配送时间 单位:min

为了确定运输工具数量k,本文在编程时分别考虑了1～3辆车的情况,优化及迭代过程如图4所示。

图4 物料配送路径优化及迭代过程

输出路径方案见表3所列。

表3 路径方案

由此可以看出,1辆车无法满足产线需求,3辆车不仅固定成本高,时间上也不是最优的,启用2辆小车的结果是最优的。最小配送时间为24.5 min,对应染色体为(0,2,8,7,6,5, 0,1,3,4,0), 经过解码,得到配送路径如下:

k1:m2→m8→m7→m6→m5;

k2:m1→m3→m4。

3.2 基于配送需求约束的货位分配算例求解

根据实地调研,BY数字化生产车间立库分为6个库区,共计140个库位,每个库区可存储的物料不同,实际的物料可存储库区情况及库区的出库时间，见表4所列。

表4 工位存储库区和出库时间

假设某批次的出库任务需要从6个库区中的16个货位(不包括I/O)里拣选货物。再根据第2阶段的数学模型求解结果,可知物料的出库顺序如下:21-81-71-61-51-11-31-41-22-82-72-62-52-12-32-42。

依据该顺序选择库区进行编码,建立约束并且基于该约束的模型进行求解算法的选择和设计。假设数字化车间立体仓库中堆垛机的水平行走速度为V1=60 m/min,垂直提升速度为V2=40 m/min,每个货位的宽度L=0.8 m,高度H=0.56 m,堆垛机能耗P=200 kW,g=9.8 m/s2,M=2 kg。以布尔围道矩阵中的约束为依据,对物料的货位分配及堆垛机的拣选路径进行规划,设I/O的编号为1,坐标为(0,1)。设置遗传算法的参数:初始种群大小为50,染色体长度为17;自适应交叉概率常量c1设为0.3,c2设为0.7,自适应变异概率常量d1设为0.01,d2为0.05。将上述参数分别带入Matlab程序中,经多次实验,确定遗传迭代次数为500次。

以多目标最优为目标,算法在搜索过程中每代的最优解以及种群均值的跟踪图如图5所示。

图5 目标最优解和种群均值跟踪图

可以看出,遗传算法对该目标结果有较好的优化结果,最优目标函数值从优化前的0.272 9,经过优化后降到0.131 0,下降了约52%,表明方法是有效的,保证配送需求的同时提高了立库作业效率和运行成本,优化后的货位分配和拣货路径情况，见表5所列。

表5 货位分配结果

本部分采用基于约束模型的遗传算法求解方式运行10次，与传统遗传算法对比结果见表6所列。由表6可知,本文基于多色集合约束的遗传算法有效加快了收敛速度。

表6 改进的遗传算法效果对比

4 结 论

本文提出了BY数字化生产车间仓配一体化方案,构建了针对配送路径和货位分配2个层次的模型,将生产车间内部仓储和配送作业联动,满足物料准时配送的要求且使得配送路径最短、货位分配最优。本文的主要贡献如下:① 设计了基于多色集合约束的两阶段遗传算法进行求解,通过多色集合理论将配送需求作为约束来影响货位分配,使仓储和配送有机融合,互相影响;② 通过Matlab仿真验证了模型和算法的有效性,并结合BY公司的实际算例给出了整体的优化方案,有效提高了配送和仓储效率,降低了生产物流成本。本文的方案不仅对BY公司适用,对其他制造业的生产车间物流优化也有一定的借鉴意义。

本文考虑的主要是流水线加工方式,对离散型生产车间的优化还需要进一步探索,且本文考虑的工位数及物料数量都很有限,对大规模仓配一体化的生产车间是否适用还需要进一步验证。