“RMFS”拣选系统的订单分批优化.pdf

第 卷第期陕西科技大学学报V o l N o 年 月J o u r n a l o fS h a a n x iU n i v e r s i t yo fS c i e n c e&T e c h n o l o g y D e c 文章编号:X()“RM F S”拣选系统的订单分批优化杨玮,郑传辉,李然,徐丹(陕西科技大学 机电工程学院,陕西 西安 )摘要:在全球零售额和当天交货量不断增长的时代,实现订单的快速交付和优质分批是影响移动机器人履行系统(R o b o t i cM o b i l eF u l f i l l m e n tS y s t e m s,RMF S)拣选效率的关键因素为构造高质量订单分配批次、提升RMF S系统拣选效率,提出融合大邻域搜索的改进差分进化算法(L N S_D E),引入大邻域搜索的破坏与修复思想及一批基于随机、基于最大代价贡献和基于集中批次的移除算子以及新的插入算子组件,以最小化订单总延迟时间为目标建立订单分批优化模型,并针对不同订单规模算例进行实验仿真仿真结果表明,所提出的订单分批优化算法较差分进化算法(D E)相比求解质量更优,性能更稳定、收敛速度更快,尤其当订单数量增大时,L N S_D E算法解的平均值优化比例不断扩大,这为提高RMF S系统拣选效率,实现订单快速响应提供有效决策指导关键词:RMF S拣选系统;货到人;订单分批;融合大邻域搜索的改进差分进化算法中图分类号:T P ;T P ;F 文献标志码:AO r d e rb a t c ho p t i m i z a t i o no f RMF S p i c k i n gs y s t e mYANG W e i,Z HE NGC h u a n h u i,L IR a n,XUD a n(C o l l e g eo f M e c h a n i c a la n d E l e c t r i c a lE n g i n e e r i n g,S h a a n x iU n i v e r s i t yo fS c i e n c e&T e c h n o l o g y,X i a n ,C h i n a)A b s t r a c t:I na ne r ao f i n c r e a s i n gg l o b a lr e t a i ls a l e sa n ds a m e d a yd e l i v e r y,f a s td e l i v e r ya n dq u a l i t yb a t c h i n go fo r d e r sa r et h ek e yf a c t o r sa f f e c t i n gt h ep i c k i n ge f f i c i e n c yo fRMF Ss y s t e m I no r d e r t oc o n s t r u c t h i g h q u a l i t yo r d e r a l l o c a t i o nb a t c h e s a n d i m p r o v e t h eo r d e r p i c k i n ge f f i c i e n c yo fRMF S,a ni m p r o v e dd i f f e r e n t i a le v o l u t i o na l g o r i t h m(L N S_D E)i sp r o p o s e d,w h i c h i n t e g r a t e s t h e i d e ao fd e s t r u c t i o na n dr e p a i ro f l a r g en e i g h b o r h o o ds e a r c h,ab a t c ho fr e m o v a l o p e r a t o r sb a s e do nr a n d o m,m a x i m u mc o s tc o n t r i b u t i o na n dc e n t r a l i z e db a t c h e s,a n dan e wi n s e r t i o no p e r a t o rc o m p o n e n t T h eo r d e rb a t c h i n go p t i m i z a t i o n m o d e l i se s t a b l i s h e dw i t ht h eo b j e c t i v eo fm i n i m i z i n gt h et o t a ld e l a yt i m eo fo r d e r s,a n dt h es i m u l a t i o ne x p e r i m e n t sa r e c a r r i e do u t f o rd i f f e r e n t o r d e r s i z e s T h e s i m u l a t i o nr e s u l t s s h o wt h a t t h ep r o p o s e do r d e rb a t c h i n go p t i m i z a t i o na l g o r i t h mh a sb e t t e rs o l u t i o nq u a l i t y,m o r es t a b l ep e r f o r m a n c ea n df a s t e rc o n v e r g e n c es p e e dt h a nt h ed i f f e r e n t i a le v o l u t i o na l g o r i t h m E s p e c i a l l yw h e nt h en u m b e ro f o r d e r s i n c r e a s e s,t h e a v e r a g eo p t i m i z a t i o np r o p o r t i o no f t h eL N S_D Ea l g o r i t h ms o 收稿日期:基金项目:“十四五”国家重点研发计划项目(Y F D );陕西省西安市未央区科技计划项目()作者简介:杨玮(),女,山西运城人,教授,博士,研究方向:智能物流技术陕西科技大学学报第 卷l u t i o ne x p a n d s,w h i c hp r o v i d e s e f f e c t i v ed e c i s i o ng u i d a n c e f o r i m p r o v i n g t h eo r d e r p i c k i n ge f f i c i e n c yo fRMF Ss y s t e ma n da c h i e v i n gr a p i dr e s p o n s e t oo r d e r s K e yw o r d s:RMF Sp i c k i n gs y s t e m;g o o d s t op e r s o n;o r d e rb a t c h i n g;i m p r o v e dd i f f e r e n t i a l e v o l u t i o na l g o r i t h mi n t e g r a t i n g l a r g ed o m a i ns e a r c h引言随着互联网技术的迅猛提升,电商行业发展愈发繁荣,订单拣选效率备受关注,如何在紧凑的交货期内处理海量客户订单实现“快速交付”,不断提高客户满意度,已然成为企业巩固自身核心竞争力的关键所在 B a h r a m iB等将订单分拣(O r d e rP i c k i n g,O P)定义为涉及从指定的储存位置检索产品以满足客户需求的过程,并被认为是仓库中最劳动密集型的作业,约占为仓库作业成本的 此外虽人到货拣选系统(P i c k e r s t o G o o d s,P T G)所需的投资相当低,但缺点是拣货人员行走时间占总订单分拣时间的 以上,“货到人”拣选系统(G o o d s t o P i c k e r s,G T P)是为适应配送中心完成多品种、高频率、小批量的海量客户需求而提出的新模式,由储存系统、输送系统、拣选系统三部分组成相对于传统的人到货拣选系统(P i c k e r s t o G o o d s,P T G),可有效避免拣货人员行走于货架之间的冗余时间,降低劳动强度、提高拣选效率,近些年来被广泛应用于电商、服装、医药等行业而移动机器人履行系统(R o b o t i cM o b i l eF u l f i l l m e n tS y s t e m s,RMF S)是“货到人”拣选系统的主流拣选形式该系统可根据订单波峰波谷调整移动机器人及货架的数量,使系统对拣选量变化较大的配送中心能够作出迅速的调整及重规划,这使RMF S拣选系统具备柔性强、成本低等优点,有利于提高系统的整体生产率和效率在G T P系统订单分批研究中,已有文献研究各种情况下的订单拣选问题李珍萍等建立了订单分批拣选联合优化问题的混合整数规划模型,目标是最小化货箱出库总次数李珍萍等以订单分批拣选总成本极小化为目标,给出了基于商品品项信息和货架信息的类中心的定义,提出了K m a x聚类算法求解订单分批问题陈广锋等以最佳货位的最大完工时间为目标建立了数学模型,利用拉格朗日差值方法优化了差分进化算法局部搜索的能力胡金昌等以最小化料箱出入库数量为目标,来解决订单排序优化客户分批问题,提出种子算法和遗传算法进行求解,实验表明不同的方法可以依据不同的规模场景提高系统效率万明重等设计订单分批算法和智能果蝇优化算法,实验表明考虑拆分策略能够明显减小订单拣选的总延迟时间刘凯等 提出求解订单分批问题的启发式聚类算法,并设计了仿真实验将所提策略与随机分批方式进行对比吴仁超等 针对订单分批问题,提出了一种混合元启发式算法,实验表明,所提分批算法在求解质量上要优于多重变邻域搜索、禁忌搜索等算法 N i c o l a sL等 以最小化总完成时间为目标构建了订单批处理模型,提出了一种元启发式方法求解模型,并将其拓展到仓库中具有多个分区的情况 C a vA等 以最小化拣货距离为目标建立了订单分批模型,提出了一种启发式算法求解整数规划模型 C h e n等 提出了混合粒子群优化(P S O)和A C O算法,求解以最小化行驶总距离为目标的订单分批问题在处理限时订单的拣选配送问题中,保障订单及时到达客户,提高客户满意度这一目标对于处理限时客户订单是至关重要的因素只有少数学者将总延迟时间作为优化目标融入至订单分批问题中赵金龙等 建立以最小化总延迟时间的整数规划模型,利用改进的智能果蝇优化算法确定订单分配和排序决策;C h e n等 在考虑客户订单总延迟最小的情况下,提出了混合遗传和蚁群优化算法,提出的混合算法在求解质量上优于多遗传算法和到期日期优先算法此外在上述研究中,强调了对融入启发式搜索的混合算法的性能和改进效果;因此本文结合RMF S系统的特点,提出一种融合大邻域搜索的改进差分进化算法,引入大邻域搜索的破坏、修复思想与一批基于随机、基于最大代价贡献和基于集中批次的移除算子以及新的插入算子组件,以最小化订单总延迟时间为目标对不同规模的限时客户订单分配高质量批次,提高拣选效率RMF S拣选系统RMF S拣选系统由调度系统、移动机器人、拣选台、拣货员、可移动货架、巷道和充电站组成,整体布局如图所示 RMF S拣选系统订单拣选作业流程如下:()系统依据库存信息以及任务信息对第期杨玮等:“RMF S”拣选系统的订单分批优化已接收的订单分配给目标货架及拣选台;()系统确定需要执行的机器人,并判断机器人自身电量是否有足够的时间移动至目标货架,若有则由该机器人执行拣货任务,若无则需前往充电区域充电,直至电量达到 后继续完成任务;()移动机器人按照规划好的最优拣选路径移动至目标货架;()到达目标货架后,移动机器人顶升、抬起可移动货架并将其运送至目标拣选台;()到达拣选台后,按照如图所示进行排队拣选,直至拣货员开始执行该任务;()待拣货员拣货完成后向系统进行反馈,系统规划好移动机器人的路径,命令其将货架放回存储区;()移动机器人将货架放回存储区,即完成当前任务的拣选,系统将释放移动机器人并命令其返回待命位置;()若移动机器人任务密集时,则需就地待命,若否,移动机器人需返回停车区拣选流程如图所示图RMF S拣选系统图RMF S系统中的拣选台在RMF S拣选系统中,往往同一批次的订单需要移动机器人多次搬运以及拣货员在可移动货架上多次拣选才能完成而传统的订单分批方法比如随机分批或低质量的订单分配批次会使得移动机器人和拣货员频繁操作,从而增加设备及人力损耗,同时也会使移动机器人进行多次运输作业增加订单拣选时间、降低拣选效率为解决这一难题,本文首先针对RMF S拣选系统,建立以最小化订单总延迟时间为目标的订单分批优化模型,提出了融合大邻域搜索的改进差分进化算法,引入移除、插入算子组件,优化客户订单分配,构造高质量批次,避免设备损耗,减少订单拣选时间及资源闲置,从而提高客户满意度及仓库拣选效率订单分批优化模型 条件与假设本文所有假设如下:()同一订单的S KU不能拆分为不同批次()任何单个存储位置都有足够的S KU用于批量订单,不会出现缺货现象()同一批次中不同订单的同一S KU是从同一可移动货架上拣选的()可移动货架上的存储S KU的货位固定、货架位置固定()若两个订单中包含同一S KU,将其合并拣选能减少拣货员拣选操作一次的时间()若两个订单中包含的S KU位于同一货架,将其合并拣选可以减少一次移动机器人搬运的时间()已知移动机器人每搬运一次货架的时间简化为t及拣货员拣选一次S KU的时间为t()同一移动机器人,单周期内仅需处理某一陕西科技大学学报第 卷批次订单,且必须完成当前周期的当前批次所有拣选任务后,方可开启下一周期内某一批次的拣选任务图RMF S系统订单拣选流程 模型建立假设系统某一时刻的订单池中,共有N张具有不同截止时间的订单O,O,O,Oi等待处理,每条订单有M种S KU且货位信息已知,用ai m表示订单i中包含商品m,否则ai m,此外每个可移动货架s,s,s,se上可摆放种S KU,用bm e表示商品m在货架e上,否则bm e同时设置移动机器人搬运一次货架的时间t及拣货员拣选一次S KU的时间t其次考虑到电商行业订单需要快速响应,从而保障订单及时到达客户这一现状,本文定义了订单i的延迟时间为订单结束时间与截止时间差,如式()所示:im a xte n ditd u ei,iI()式()中:td u ei是订单i的截止时间;te n di是订单i完成拣选的时间,即批次j中最晚完成的订单i的结束时间如式()所示:te n dim a xse n djxi jzj m,iI,jJ,mM()式()中:se n dj是批次j完成拣选的时间;xi j、zj m均为为变量,xi j表示订单i被分配到批次j中,否则xi j;zj m表示批次j中包括商品m,zj m表示不包括;其中定义C为一个批次中最大的订单量,约束()为可行批次集合中的批次容量约束:Iixi jC,jI()综合考虑以上的订单延迟时间、拣选时间和批次容量约束,可建立以最小化订单总延迟时间为目标的订单分批优化模型m i nNii()s t Jjxi j,iI()Iiai mxi jIzj m,jJ,mM()zj mEebm eyj e,jJ,mM()se n djss t a r tjss e r v i c ej()ss t a r tjm i nta r r i v eixi jzj m,iI,jJ,mM()ss e r v i c ejtyj etzj m()xi j,iI,jJ()yj e,jJ,eE()zj m,jJ,mM()目标函数()表示以最小化订单总延迟时间;式()表示每个订单只能被分到一个批次;式()表示批次j中任意订单i中包含商品m,则批次j包含商品m;式()表示如果批次j中包含商品m,则移动机器人需要搬运商品m所在的货架e,其中yj e为变量,若拣选批次j需要搬运货架e,则yj e,否则yj e;式()表示批次j的完成拣选的时间,为批次j开始拣选的时间与批次j的服务时间的和;式()表示批次j的开始时间,为该批次内订单i的最早到达时间;式()表示批次j的服务时间,为移动机器人搬运货架的时间与拣货员的拣货时间和;式()至式()表示决策变量取值约束一种融合大邻域搜索的改进差分进化算法设计差分进化算法(D i f f e r e n t i a lE v o l u t i o n,D E)是第期杨玮等:“RMF S”拣选系统的订单分批优化从仿生 智 能 计 算(B i o n i cI n t e l l i g e n tC o m p u t i n g,B I C)出现以来,优化算法结构中的又一大进步,其保留了一对一的竞争策略和基于种群的搜索方式 由于该算法具有优越的全局收敛能力,求解过程和方法较为简单等优点,因此D E算法更适用于求解较为复杂的大规模全局问题但是传统D E算法因其单一的变异策略、固定不变的邻域值和缓慢的静态邻域拓扑交换速率,导致其全局与局部之间的搜索能力无法达到均衡等问题而大邻域搜索算法(L a r g eN e i g h b o r h o o dS e a r c h,L N S)可通过一组移除和插入算子进行动态邻域搜索,使算法具备了良好的适应能力 同时移除算子和插入算子能够针对问题特性灵活设计,可扩展度高本文在传统D E算 法 的 基 础 上 融 入 大 邻 域 搜 索 算 法(L a r g eN e i g h b o r h o o dS e a r c h,L N S),设计了个移除算子和个插入算子,提出了应用于RMF S系统离散型订单分批问题的融合大邻域搜索的改进差分进化算法 移除算子()基于随机的移除算子:从当前解中随机移除批次Bj中的ni笔订单()基于最大代价贡献的移除算子:优先移除延迟时间代价贡献最大的批次Bj中的订单Oi某个订单Oi的代价贡献由式()计算,采用轮盘赌的方式,从当前解中选择ni笔订单进行移除操作,定义订单Oi的权重Qii()基于集中批次的移除算子:集中移除一个批次上的订单从当前解中找到某个代价最大的批次,随机移除该批次上的所有订单若无符合条件的批次,则退化为随机移除算子随机移除算子为纯随机算子,具有随机性强、跳出局部最优的能力较强的优点,但也容易移除在正确位置上的订单,从而产生无效操作;最大代价贡献移除算子会将延迟时间贡献最大的订单优先考虑,而这些订单往往正是需要优化的订单,缺点是容易陷入局部最优;集中批次移除算子会集中移除一个批次上的所有订单,策略简单且具有良好的局部收敛能力,这两种移除算子均需要遍历一遍当前解中各个订单的属性,故以上三种移除算子的时间复杂度分别为O()、O(n)、O(n)插入算子()贪婪顺序插入算子:每个订单i由贪婪策略得到插入位置,也就是选择使本次插入增加的总延迟时间最小的位置插入,将待插入订单随机乱序后依次贪婪插入()遍历插入算子:随机选择两个移除的订单,将其它订单顺序打乱后依次以贪婪法插入,然后选择两个订单中的第一个订单,分别固定到使延迟时间增加最小的前kyn 个批次中对另一订单遍历所有批次即位置,以概率p直接选择其中最优的邻域解,但仍有 p的概率以赌盘方式选择一个邻域解,每个邻域解的权重为其适应值其中ky为(,)之间的常数根据待插入订单需要尝试的批次数和,贪婪顺序插入算子与遍历插入算子的时间复杂度均为O(n),是算法的主要耗时部分之一因移除算子的时间复杂度均小于O(n),故每次选择一个移除算子和一个插入算子执行的时间复杂度仍为O(n)此外贪婪顺序插入算子存在易陷入局部最优的缺点,而遍历插入算子在很大程度上弥补了这种局限 L N S_D E算法步骤本文提出的L N S_D E算法进行优化的步骤如下,算法流程图如图所示图L N S_D E算法流程图陕西科技大学学报第 卷()种群初始化首先采用随机初始化的方法,在满足约束条件的前提下,生成初始种群,种群规模与个体的维数D有关,一般设在区间 D,D内,种群的初始化应在符合边界约束的条件下尽可能均匀覆盖全部区域,假设每个个体的第j维的上下界分别为xjm i n和xjm a x,那么个体将按以下的方式进行初始化:xj,i,xjm i nr a n d,(xjm a xxjm i n)()并设定算法相关参数,包括种群数量N P、缩放因子F、交叉概率C R、最大迭代次数g e nm a x等参数()计算适应度值在算法迭代过程中,设置保留为适应度最小的个体,以f m i nnii为适应度函数,根据适应度函数计算种群中个体的适应度值()记录当前个体最优值以及全局最优值()经过步骤()后进入迭代循环,当迭代循环小于次数g e nm a x,执行如下操作:变异针对每个个体向量,执行差分变异操作会产生变异向量在D E中共有常用的种变异策略产生变异个体Vi,G,以D E/b e s t/策略进行变异操作,如下所示:Vi,Gxb e s t,GF(xr,Gxr,G)()式()中:xr m,G是m,M 中随机选择的不同的个体,与目标个体xi,G不相同;xb e s t,G是种群中适应度最好的个体;缩放因子F是,中的一个实常数因数,起到对控制偏差变量的放大作用交叉在变异操作后,需将目标向量xi,G与变异向量Vi,G进行二项式交叉生成最终的试验向量Ui,GUi,G,Ui,G,Ui M,G,依下式进行交叉操作,以增加干扰参数向量的多样性:UVi j,G,i f r a n d,C Ro r j jr a n dxi j,G,o t h e r w i s e()式()中:jr a n d是集合,M 内随机选择的一个整数,以保证变异向量至少有一维信息被保留下来;交叉概率C R是区间,之间的常数判断当前解是否为较优解,若是,则在较优解的移除算子集中以轮盘赌的方式选择一个算子;若不是,则在非较优解的移除算子集中以轮盘赌的方式选择一个算子;对当前解应用选择的移除算子,得到移除的订单集和其待插入的位置,以轮盘赌的方式选择插入算子,并计算邻域解;计算原解与新解的适应度;选择适应度更优的个体,转至步骤进入下一次迭代循环()当迭代次数等于g e nm a x时,迭代停止,并输出最终的全局最优值数值算例为了评估L N S_D E算法的性能,本研究使用的算例大小从 到 个订单(N订单数量)、个货架(E货架数量)和s k u商品总数为、(M s k u数量)在这些问题算例中包含的订单长度范围集,订单分批容量b a t c h s i z e,到达时间ta r r i v eir a n d,的订单为同一周期,且这些订单的截止时间td u eir a n d,所有算例使用MAT L A BR a程序设计 平 台 执 行 计 算,计 算 硬 件 配 置 为w i n d o w 、AMD R y z e n X C o r eP r o c e s s o r GH z处理器、GH z内存 参数校准该算法框架主要有个参数,为每种算例类型寻找最佳参数设置非常耗时相反,更希望在广泛的算例类型上提供良好结果的参数设置因此,必须校准所涉及的个参数本研究基于C o y等 中提出的系统参数校准过程,为这些问题算例查找高质量的参数设置因此整个参数设计实验包括四个步骤:选择问题子集,确定每个参数变化的设计中心和范围,组合参数设置并进行算例验证,最后确定每个问题集良好的参数设置在参数校准中,选择代表整个问题集特征的个不同算例作为实验子集确定实验子集后,依据各参数本身的性质设置设计中心和变化区域,如表所示最小值和最大值代表实验区域的外边缘,根据步长可计算参数的不同水平值表参数校准初始实验区域最小值设计中心最大值步长种群规模N Pn n nn 缩放因子F 交叉概率C R 由于必须校准个参数,利用田口方法论为个因子和个水平进行析因设计,以确定实验结果稳定、波动性小的参数组合,如表所示,从正交表中选择L 正交阵列,对于 种配置中的每种配置,在算例类型为 个订单、个货架上执行次运行以获得算法最优解平均值A b s_O b j 第期杨玮等:“RMF S”拣选系统的订单分批优化并通过方差分析法可以找到重要参数,从表可以看出,对于算例来说因子F(缩放因子)对算法的影响最大,其次是因子N P(种群规模),因子C R(交叉概率)对算法的影响最小算例中每个因子的最佳水平为N P、F 和C R 接下来,为每个算例选择最优解平均值最低的参数设置结果设置如表所示,通过取实验子集的参数设置的平均值,可以获得最终参数设置,该参数设置将用于进一步的实验,并在广泛的问题类型上可提供高质量的解决方案,以显示所提出的算法框架的计算性能表正交表及方差分析T r i a lN PFC R算例A b s_O b j R R ANKB E S TN P F C R d fM S S S F 表参数校准结果算例类型(N E M)种群规模N P缩放因子F交叉概率C R、实验结果上述研究的参数设置用于下面讨论的所有实验第一部分实验在基于每个算例类型上比较使用D E算法、L N S_D E算法,每组实验分别重复 次,累计 x x 组试验并统计了两种订单分批算法的最优解平均值A b s_O b j、平均偏差值D e v、平均目标值优化比例MP I及平均运行时间T其中D e v表示在一类算例中,当前算法最优解平均值A b s_O b j与已知最优解之间的平均百分比偏差值,已知最优解是D E、L N S_D E中发现的最优解的平均值;MP I表示L N S_D E求解结果对比D E的改进程度表比较了在个算例类型中,D E算法、L N S_D E算法的性能在求解质量上,L N S_D E算法在所有算例类型上均优于D E算法具体表现为,所有算例上,L N S_D E算法解的平均值优化比例随着订单数量的增大而增大,优势在不断扩大,平均缩短了 的延迟时间,在N/E/M /时最大可减少 的延迟时间此外L N S_D E算法平均偏差值D e v小于D E算法,这表示在每个算例类型中,L N S_D E算法都发现了最多的已知最优解,尤其在N 后平均偏差值D e v均为,说明每次实验已知最优解全部来源于L N S_D E算法;在求解时间上,L N S_D E算法并未优于D E算法,但计算时间差率大小控制在合理范围内:,这是由于任何混合算法性能的提高都是以牺牲算法搜索时间为代价;且随着客户订单数量增 大时,两种算 法执行时间 均呈一定幅 度下降表两种分批算法在不同算例中的计算结果算例类型D EL N S_D E仓库配置(E M)订单结构N(M、订单长度)A b s_O b jD e vT(S)A b s_O b jD e vMP IT(S)/(s k u、,)/(s k u、,)/(s k u、,)/(s k u、,)/(s k u、,)/(s k u、,)企业促销活动时,客户反映表现为两方面,一方面是购买订单增加带来的订单行增加,另一方面陕西科技大学学报第 卷是客户一起购买的商品增加,即订单长度增加因此第二部分实验探究订单长度对分批效果的影响基于算例类型N/E/M /,在不同的订单长度(,、,、,)上统计了L N S_D E算法和D E算法的订单总延迟时间,累计 组试验图呈现了D E算法、L N S_D E算法在种订单长度下的订单总延迟时间数值虽然随着单个订单所包含的的商品种类扩增时,两种算法所求解的订单延迟时间均进一步延长,但延迟时间也在合理范围之内另外L N S_D E算法分批效果明显优于D E,且在订单行长度为,时,优化效果达到最大,说明在订单分批流程时,管理者可选择L N S_D E算法缓解延迟时间所带来的经济损失,得出的方案对企业面临大型促销活动时,可实现快速响应客户这一点图两种算法在不同订单长度下的总延迟时间图记录了D E算法、L N S_D E算法在不同规模算例下的计算迭代过程可以发现D E算法的收敛速度较快,但易陷入局部最优,而本文所提出的L N S_D E算法通过扩大邻域搜索范围,能够有效提高算法精度;同样L N S_D E算法得到的最优解适应度值均优于D E算法,且随着订单规模的增大,适应度值的优化效果愈加明显第期杨玮等:“RMF S”拣选系统的订单分批优化图D E算法、L N S_D E算法收敛图结论()以最小化订单总延迟时间为目标,建立基于“RMF S”拣选系统的订单分批优化模型()引入大邻域搜索的破坏与修复思想及一批基于随机、基于最大代价贡献和基于集中批次的移除算子以及新的插入算子组件,设计出融合大邻域搜索的改进差分进化算法对模型进行求解()对于不同规模的限时客户订单结构,L N S_D E算法通过扩大邻域搜索范围,能够有效提高算法精度,平均缩短 的延迟时间,与差分进化算法(D E)相比,求解质量更优、性能更稳定、收敛速度更快()面对大型促销活动所带来的订单长度增加、高订单数量时,本文算法解的优化比例不断扩大,主要体现在L N S_D E算法平均偏差值D e v均小于D E算法,且在N 后均为,说明每次实验已知最优解全部来源于L N S_D E算法,故该方法所求解高质量的订单批次可有效缩短拣选时间,提高拣选效率()此外,L N S_D E算法与D E算法计算时间差率大小始终保持在合理范围内:参考文献B a h r a m iB,A g h e z z a fEH,VL i m r e E n h a n c i n gt h eo r d e rp i c k i n gp r o c e s st h r o u g han e ws t o r a g ea s s i g n m e n ts t r a t e g y i nf o r w a r dr e s e r v ea r e aJ I n t e r n a t i o n a lJ o u r n a lo fP r o d u c t i o nR e s e a r c h,(/):D eK o s t e rR,L eD u cT,R o o d b e r g e nKJ D e s i g na n dc o n t r o lo fw a r e h o u s eo r d e rp i c k i n g:Al i t e r a t u r er e v i e wJE u r o p e a nJ o u r n a l o fO p e r a t i o n a lR e s e a r c h,():T o m p k i n sJA,Wh i t eJA,B o z e rY A,e ta l F a c i l i t i e sP l a n n i n gM t he d i t i o n N e wY o r k:W i l e y,C e r g i b o z a n,T a s a nAS O r d e rb a t c h i n go p e r a t i o n s:A no v e r v i e wo fc l a s s i f i c a t i o n,s o l u t i o nt e c h n i q u e s,a n df u t u r er e s e a r c hJ J o u r n a lo fI n t e l l i g e n tM a n u f a c t u r i n g,():李珍萍,韩倩倩,仪明超设置货箱缓存区的自动小车存储及取货系统订单分批拣选问题J计算机集成制造系统,():李珍萍,田宇璇,卜晓奇,等无人仓系统订单分批问题及K m a x聚类算法J计算机集成制造系统,():陈广锋,余立潮基于级联的改进差分进化算法的仓储多订单分批 优 化 J上 海 交 通 大 学 学 报,():胡金昌,马文凯,杨栋,等考虑客户收货顺序的“货到人”分拣系统的订单排序和客户分批优化J机械工程学报,():万明重,蒋忠中,秦绪伟,等考虑拆分策略的智能仓库订单拣选优化问题J计算机集成制造系统,():刘凯,彭玲玲基于智能仓储拣选系统的订单分批问题研究J中国储运,():吴仁超,贺建军,李欣,等基于混合元启发式算法的订单分批问题J控制与决策,():N i c o l a sL,Y a n n i c kF,R a m z iH O r d e rb a t c h i n g i na na u t o m a t e dw a r e h o u s e w i t hs e v e r a lv e r t i c a ll i f t m o d u l e s:O p t i m i z a t i o na n de x p e r i m e n t sw i t hr e a l d a t aJ E u r o p e a nJ o u r n a lo f O p e r a t i o n a l R e s e a r c h,():C a vA,J e bB O r d e rb a t c h i n gu s i n ga na p p r o x i m a t i o nf o rt h ed i s t a n c e t r a v e l l e db yp i c k e r sJ E u r o p e a nJ o u r n a l o fO p e r a t i o n a lR e s e a r c h,():C h e nCY,C h e nYY,C h e nTL,e t a l U s i n gah y b r i da p p r o a c hb a s e do nt h ep a r t i c l es w a r mo p t i m i z a t i o na n da n tc o l o n yo p t i m i z a t i o nt os o l v eaj o i n to r d e rb a t c h i n ga n dp i c k e r r o u t i n gp r o b l e mJ I n t e r n a t i o n a l J o u r n a lo fP r o d u c t i o nE c o n o m i c s,:赵金龙,蒋忠中,万明重,等考虑配送截止时间的“货到人”订单拣选优化问题研究J/O L中国管理科学:D O I:/j c n k i i s s n x 陕西科技大学学报第 卷 C h e nCY,C h e nYY,C h e nTL,e t a l A ne f f i c i e n t h y b r i da l g o r i t h mf o ri n t e g r a t e do r d e rb a t c h i n g,s e q u e n c i n ga n dr o u t i n gp r o b l e mJ I n t e r n a t i o n a lJ o u r n a lo fP r o d u c t i o nE c o n o m i c s,:B o y s e nN,W e i d i n g e rF W a r e h o u s i n gi nt h ee c o mm e r c ee r a:As u r v e yJ E u r o p e a nJ o u r n a lo fO