基于新型线边集成超市的周期性物料配送优化

周炳海,徐佳惠,彭 涛

(同济大学 机械与能源工程学院,上海201804)

0 引 言

物料配送(Part feeding)占车辆生产成本的20%～50%[1]。如何设计高效、合理的物料配送系统,对降低混流装配线的生产成本具有重要意义。

许多国内外学者对传统送料机制,即线边储料(Line stocking)和成套供料(Kitting)进行了广泛的对比和研究[2,3],并指出不存在绝对的最优机制,应根据物料特性和实际生产环境选用不同送料机制才可有效降低系统配送总成本。近年来,研究焦点逐渐转移为准时化配送策略[4,5],即采用物料超市(Supermarket)替代传统的中心仓库存放物料,通过对多载量小车等送料设备的调度[6]实现物料的小批量多频次配送。为充分结合传统线边储料、成套供料以及准时化配送策略的优势,降低系统总运作成本,Boysen等[7]结合某德国汽车制造商的实际运营情况,提出并介绍了“线边集成超市”(Line-integrated supermarkets)的概念,但未对具体的物料配送调度问题进行深入研究。Battini等[8]对厂内物流进行研究时也简单提及了“鱼骨型物流超市”(Fish bone supermarkets),即线边集成超市,并说明了其可行性和潜在价值。

虽然基于线边集成超市的物料配送有效利用当前送料机制的优势、降低系统成本,但是目前尚未发现其他相关研究。为此,本文引入线边集成超市的概念,研究送料工人与工位之间的合理配置问题,并对物料配送进行调度决策,以最小化包括工人固定成本和物料配送成本的系统总运作成本。对于小规模问题,结合问题的引理、定理建立嵌套启发式动态规划方法获取精确解,并构建改进型和声搜索算法(Modified harmony search algorithm,MHSA)求中大规模问题的满意解。

1 问题描述

如图1所示,为有效降低物料的线边库存,送料工人采用准时化顺序供应(Just-in-sequence,JIS),即根据实际生产计划和装配情况准备并配送物料到对应工位,并按需按序放置于JIS料箱,以满足装配需求。为明确物料配送任务、有效管理送料工人,本文将物料配送调度分解成两个子问题:①送料工人与工位的分配问题P1,即确定各送料工人负责工位;②周期性配送问题P2,即确定送料工人的周期性配送时间间隔。

图1 线边集成超市物料配送系统Fig.1 Part feeding system with line-integrated supermarkets

为有效描述该配送系统,作如下假设:①采用节拍时间作为基本时间单位;②装配线不允许发生缺料;③一个送料工人负责一个或多个连续工位;④送料工人对所负责的工位进行周期性配送;⑤送料工人搬运能力有限;⑥送料工人一旦从线边超市出发送料,必须配送完所有物料后返回;⑦每个工位设一个JIS料箱,存放物料,其容量有限;⑧送料工人拣料、卸料时间,以及从线边超市到工位的行走时间均为定值;⑨每个工位仅装配一类物料,且仅考虑每个生产节拍内的物料需求量;⑩生产系统为一个相对稳定的系统,不考虑不确定因素。

结合以上描述和假设,定义如下问题参数和决策变量,并建立数学模型。

(1)参数与变量

设S为装配工位集合,s＝1,2,…,;W为送料工人集合,w＝1,2,…,;P为待装配车辆总数,p＝1,2,…,P;T为系统生产节拍总数,t＝1,2,…,T;ct为系统节拍时间;B s为工位s处JIS料箱的容量;为工位s在第t个生产节拍所需物料量;wt为送料工人从线边超市到工位的行走时间;st为送料工人在两连续工位间的行走时间;at w为送料工人w每次的分拣、装卸物料时间;C w为第w个送料工人的搬运能力;δw为第w个送料工人负责的最左边工位编号;T w为第w个送料工人的周期性配送时间间隔,且T w≥1;D w为第w个送料工人的单次送料时长,且D w＝at w＋2·[wt＋st·(δw＋1－1－δw)];R w为第w个送料工人的送料次数,r＝1,2,…,R w;为第w个送料工人第r次配送的物料量;F w为第w个送料工人的固定成本;u为单位物料单位时间的搬运成本。

(2)数学模型

式(1)～(4)以最小化送料工人数为目标求解问题P1。其中,式(2)(3)表示各送料工人至少负责1个工位,且负责的工位不重复。式(4)为终止条件,均为虚拟值,不计入目标函数。此外,为有效应对问题P2,即减少物料配送等非增值活动的成本,建立以最小化单位物料配送的最大时间为目标的数学模型,如式(5)所示。式(6)(7)为配送量约束,即应满足装配过程不发生缺料。式(8)(9)分别为送料工人能力和JIS料箱容量约束。式(10)表明送料工人周期性配送时间间隔不得小于其固定的送料时长。

显然,两个子问题相互关联:工位分配问题确定送料工人数和负责工位(W,δw),其作为问题P2的已知参数;相应地,只有求出每个工人的周期性配送时间才可明确工人数是否满足要求,工位分配问题是否合理、可行。基于两者的关联性,结合式(1)(5)建立总目标函数(11)进行求解,其代表最小化包括工人固定成本和物料配送成本的系统总成本,式中“∗”表示相应目标函数的最优解。函数(11)应满足约束(2)(3)(4)、(6)～(10)。

2 算法构建

2.1 引理和定理

引理1 若送料工人w负责工位m,…,n的物料配送,且周期性配送时间和次数分别为T w和R w,则当时,Z2(T w)取最小值。

证明 若工人w负责工位m,…,n,则D w为定值。取最小值时,则Z(T)取得最小值。根据2w数学不等式性质可得:

定理2 送料工人w负责工位m,…,n,若存在可行周期性配送时间,对应配送次数X、Y,且a i、b j(i＝1,2,…,X;j＝1,2,…,Y)分别表示每次配送的量,则当,即X＜Y时,。

证明 根据引理1可得:

2.2 嵌套启发式动态规划算法

根据模型P1,需决策每个工人w负责的最左边工位,继而可知其负责的所有工位。故将决策过程划分为个阶段,每阶段表示一个工位,i＝1,2,…,为终止阶段。每阶段的状态亦为i,表示工人负责的最左边工位,从状态i到状态j,即表示w负责工位i,…,(j－1),从1到依次进行前向递归,并计算状态转移对应目标函数值的变化:

式中:“∗”为i,…,(j－1)工位周期性配送问题最优解。

用H(i)表示从工位1到i的最优目标函数值,则:

Step1 计算工位s(s＝i,…,j－1)最少配送次数:,取。

Step2 计算该子区域i,…,(j－1)最少配送次数:。

Step3 根据Step1和Step2确定w最少配送次数。

Step4 计算w配送次数,相应周期时间。

2.3 改进型和声搜索算法

为了有效求解中、大规模问题,引入和声搜索算法(Harmony search,HS),该算法原理简单、控制参数少、收敛速度快,且文献[9]证明了其解决离散问题时的全局收敛性,已成功应用于各类非线性优化问题[10]。然而,HS算法仍存在搜索后期收敛较慢、局部探索能力差、易陷入局部最优等缺陷。因此,提出了一种改进型和声搜索算法MHSA,基本流程如下。

Step1 参数初始化。给定和声记忆库大小HMS、精度ε、最大迭代次数SNI及参数HMCR,PAR。

Step2 初始化和声记忆库。结合约束(2)(3)(4),随机产生H MS个和声,存入记忆库。

Step3 按照和声长度(即所需工人数)将和声记忆库分解成为若干个子和声记忆库。

Step4 对于每个子和声记忆库,基于HMCR、PAR进行即兴创作,产生新的和声向量。

Step5 更新子和声记忆库,即判断新和声向量是否优于当前子和声记忆库中最差和声。

Step6 判断子和声记忆库终止准则,若当前迭代次数sk大于最大迭代次数SNI,则合并所有子和声记忆库构成新的和声记忆库,否则重复Step4、Step5。

Step7 对记忆库最差和声向量X w1、X w2进行交叉、变异形成新和声X′、X″,并更新和声记忆库。

Step8 判断终止准则。若任两个和声对应目标值之差均小于精度ε,终止算法,否则重复Step3～Step7。

2.3.1和声编码方式

和声向量X i采用变长双层编码方式[11],i＝1,2,…,HMS。由编码长度可得所需送料工人数,即。第一层为工位层,代表各工人负责的最左边工位δw。根据约束(2)(3)(4)可知其以1开始,以结束,且升序排列。第二层为时间层,代表工人配送时间间隔T w。图2所示为以上算例的两个和声编码示意图。其中,X1即为最优解,可行解X2表示由5个工人分别负责1个工位,且其对应配送时间间隔分别为5、5、2、2、5个周期。

图2 和声编码示意图Fig.2 Diagram of encoded mode for harmony vector

2.3.2 初始化和声记忆库

给定S,则和声的最大长度;根据定理1计算最少送料工人数,则。因此,和声X i(i＝1,2,…,H MS)的长度范围为[Lenmin,Lenmax]。分别用1,2表示和声X i第一、二层编码的第j列,。为生成初始可行解,结合约束(2)(3)(4)随机生成HMS个和声,∀i＝1,2,…,H MS,和声X i满足:

根据和声X i计算对应函数值f(X i),一并存入和声记忆库HM,即实现和声记忆库的初始化。

2.3.3 子和声记忆库操作

Chen等[12]指出,对于中等规模的问题,通常采用较小的HM优于较大的HM,即应该设置较小的H MS。因此,本文将HM按照和声长度Len i划分成大小不同的若干子和声记忆库Sub-HM。对于每个Sub-HM,为防止算法过早收敛、陷入局部最优,结合参数H MCR、PAR等创作新和声,并不断更新Sub-HM。

对于每个Sub-HM,新和声Xnew以HMCR概率继承现有Sub-HM中和声,并以PAR概率进行微调。由于编码的特殊性,结合定理3,对Xnew进行邻域搜索。新和声Xnew以(1－HMCR)的概率进行创作,不同于HS中按定义域随机生成,本文采用轮盘赌算法从Sub-HM中选取两个和声X a、X b,并引入比例系数α生成新和声元素1。为进一步加快算法收敛速度,求得较优解,沿用2.2中的启发式算法求2。最后,计算新和声Xnew和最差和声Xworst对应目标函数值f(Xnew)和f(Xworst),并比较、更新Sub-HM。

2.3.4 更新和声记忆库

为进一步增加和声多样性并改善解质量,对于重组后HM中的和声进行交叉、变异操作,具体流程如下。

(1)交叉操作

给定交叉概率P c,根据

选取两个和声X w1,X w2,若rand(0,1)＜P c,则:

Step1 随机选取X w1、X w2的交叉点C1、C2,记,则新和声X′、X″长度分别为L′＝C1＋L2－C2,L″＝C2＋L1－C1。

Step2 若1,转Step3,否则转Step4。

Step3对X w1、X w2在C1、C2处交叉,结合2.2节中Step1～Step 5求相应2X′j、2X″j,形成新和声X′、X″,并求f(X′),f(X″)。

Step4 重新生成交叉点C2,并转Step3。

Step5 和声X w1、X w2交叉结束。

如图3所示,分别选取X1、X2(L1＝3,L2＝6)的交叉点C1＝2,C2＝4,按照Step2和Step3进行交叉,并重新计算周期性配送时间,得到两个长度分别为L′1＝4,L′2＝5的新和声X1′、X2′。

图3 交叉操作示意图Fig.3 Diagram of crossover operation

(2)变异操作

和声X w1、X w2经交叉后变为X′、X″,若f(X′)＜f(X w1)f(X″)＜f(X w2),则X w1←X′,X w2←X″;否则记Xchng为待变异和声,引入变异概率P m,若rand(0,1)＜P m,进行如下操作:

Step2 结合约束(3)进行随机变异:1,并根据2.3.3节中Step1～Step5求相应2,形成邻域解Xchng。

Step3 计算f(Xchng),若f(Xchng)＜f(X w1),则X w1←Xchng,否则转Step1。

Step4 和声Xchng变异结束。

3 仿真实验与分析

为评价该线边集成超市物料配送系统及MHSA算法,结合文献[5]生成如下实验参数。该混流装配线生产多种车型,工位s(s∈S)在周期t＝1,2,…,T所需物料,即采用(0,3)的均匀分布,表示就近取整,同理。系统节拍时间ct＝100s,且st＝0.1ct,wt＝0.2ct,at w＝0.3ct。分别取不同的和T组合,每种组合运行20次并进行统计分析。

3.1 有效性验证

为验证MHSA的有效性,将其与嵌套启发式动态规划算法进行比较,其计算机运行时限设置为1800 s,若求解超过时限,即视为中大规模问题,无法求得最优解。表1为小规模问题参数和实验结果。其中,MHSA方法的相关参数如HMCR、PAR参见文献[9]推荐值,初始和声记忆库大小为HMS＝2·|S|。动态规划方法求得最优解,MHSA运行20次后取平均值,由表1可知,其与最优解的偏差Gap均小于5%,即可得到满意解,验证了该算法的有效性。同时,随着问题规模扩大,偏差减小,表明随着问题规模扩大,MHSA的记忆库扩大,和声多样性增加,避免局部最优,因此,MHSA适用于求解中大规模的问题。

表1 小规模问题的实验参数和结果Table 1 Parameters and results of small scale problems

3.2 算法比较

3.2.1 比较MHSA、ACO和SA

MHSA模拟音乐家创作优美和声的过程,将其与其他模拟自然现象的优化算法进行比较,包括蚁群算法(Ant colony optimization,ACO)和模拟退火算法(Simulated annealing,SA)。问题规模和结果如表2所示。

表2 MHSA、ACO和SA的结果比较Table 2 Experimental results of MHSA,ACO&SA

由表2可知,随着问题规模T和的扩大,MHSA算法的寻优能力优于ACO和SA等优化算法。尤其在较大规模情况下(T≥100,),ACO和SA与MHSA的目标函数值Gap均超过5%,MHSA算法深度的搜索能力更为突出,一定程度上验证了MHSA算法处理中大规模问题时的有效性。

图4 算法收敛性能比较Fig.4 Convergence performance of algorithms

图4(a)(b)分别为MHSA、ACO和SA算法在T＝20,时的收敛曲线。由图4(a)可知,在问题规模较小时,MHSA、ACO均能快速收敛;而随着问题规模的扩大,本文提出的子和声记忆库操作加快算法的收敛速度,结合交叉变异等操作扩大邻域搜索范围,避免陷入局部最优,使MHSA明显优于ACO和SA算法,如图4(b)所示。

3.2.2 比较MHSA、IHS、GHS和NGHS

为进一步说明MHSA算法可有效避免或减少HS算法早熟收敛、易陷入局部最优的缺点,如图5所示,将其与目前引用较广泛的IHS[13]、GHS[14]和NGHS[15]进行对比。

图5 MHSA、IHS、GHS和NGHS结果比较Fig.5 Experimental results of MHSA,IHS,GHSand NGHS

3.2.3 参数分析

为最小化线边超市供料系统的运行成本,必须找到一个平衡点,使送料工人的雇佣成本与物料配送成本之和最小,根据式(11)可知,其受参数F w和u影响。令问题规模T＝20,,参数u＝1保持不变,F w分别取0,100,200,…,1000,则F w/u对目标函数值的影响如图6所示。由图可知,随着F w/u线性递增,对应目标函数值也基本呈线性递增,斜率约为7.54,即所需的平均送料工人数;截距约为6028.54,即物料配送成本。

图6 F w/u对目标函数值的影响Fig.6 Effect of F w/u on objectives

根据以上分析可知,F w/u的变化主要影响送料工人数量。取F w/u∈[0,3000],令T＝20,分别取为20,40,…,120,则相应的工人数随F w/u变化的情况如图7所示,其中,图7(b)为图7(a)在YOZ平面投影。由图7可知,当生产周期数T一定时,随着增加,所需工人数增加。对任意给定随F w/u的增加而减少,且减少到一定程度(约|S|/2,即平均1个工人负责2个工位)后保持不变,即得到该T、|S|情形下满足所有约束条件的最小工人数,此时增加F w/u仅对目标函数有影响,对无影响。

图7 F w/u对送料工人数量的影响Fig.7 Effect of F w/u on number of logistics operators

4 结束语

本文将新型线边集成超市物料配送分解为工位分配和周期性配送调度问题进行研究,并以最小化送料工人固定成本和物料的配送成本为目标建立数学模型进行求解。针对该关联问题,提出相应的引理、定理,并建立嵌套启发式动态规划方法以获取小规模问题的精确解;对于中大规模问题,构建了改进型和声搜索算法(MHSA)获取满意解。最后,通过仿真实验与其他模拟算法或改进算法进行对比,验证了MHSA的可行性和有效性。后续为提升工人的利用率,将对一组送料工人共同负责一个装配区域的情况进行研究。

[1]Lau H Y K,Woo S O.An agent-based dynamic routing strategy for automated material handling systems[J].International Journal of Computer Integrated Manufacturing,2008,21(3):269-288.

[2]Sali M,Sahin E,Patchong A.An empirical assessment of the performances of three line feeding modes used in the automotive sector:line stocking vs.kitting vs.sequencing[J].International Journal of Production Research,2015,53(5):1439-1459.

[3]Caputo A C,Pelagagge P M,Salini P.A decision model for selecting parts feeding policies in assembly lines[J].Industrial Management&Data Systems,2015,115(6):974-1003.

[4]Battini D,Boysen N,Emde S.Just-in-time supermarkets for part supply in the automobile industry[J].Journal of Management Control,2013,24(2):209-217.

[5]Boysen N,Emde S,Hoeck M,et al.Part logistics in the automotive industry:decision problems,literature review and research agenda[J].European Journal of Operational Research,2015,242(1):107-120.

[6]周炳海,徐佳惠.基于支持向量机的多载量小车实时调度[J].吉林大学学报:工学版,2016,46(6):2027-2033.Zhou Bing-hai,Xu Jia-hui.SVM-based real-time scheduling approach of multi-load carriers[J].Journal of Jilin University(Engineering and Technology Edition),2016,46(6):2027-2033.

[7]Boysen N,Emde S.Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets[J].European Journal of Operational Research,2014,239(3):820-829.

[8]Battini D,Gamberi M,Persona A,et al.Part-feeding with supermarket in assembly systems:transportation mode selection model and multi-scenario analysis[J].Assembly Automation,2015,35(1):149-159.

[9]赵玉新,Yang X S,刘利强.新兴元启发式优化方法[M].北京:科学出版社,2013:201,202,216-218.

[10]Manjarres D,Landa-Torres I,Gil-Lopez S,et al.A survey on applications of the harmony search algorithm[J].Engineering Applications of Artificial Intelligence,2013,26(8):1818-1831.

[11]Zhou B,Peng T.Scheduling the in-house logistics distribution for automotive assembly lines with justin-time principles[J].Assembly Automation,2017,37(1):51-63.

[12]Chen J,Pan Q K,Wang L,et al.A hybrid dynamic harmony search algorithm for identical parallel machines scheduling[J].Engineering Optimization,2012,44(2):209-224.

[13]Mahdavi M,Fesanghary M,Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation,2007,188(2):1567-1579.

[14]Omran M G H,Mahdavi M.Global-best harmony search[J].Applied Mathematics and Computation,2008,198(2):643-656.

[15]Zou D,Gao L,Li S,et al.Solving 0-1 knapsack problem by a novel global harmony search algorithm[J].Applied Soft Computing,2011,11(2):1556-1564.