有限缓存区自动化分拣车间调度混合人工蜂群算法

宋志兰++张壮++徐七龙

摘 要：自动化订单分拣效率低下的问题普遍存在于各个生产销售企业的配送中心。针对以提高分拣效率、降低整个物流过程的成本为最终目标的有限缓存区自动化分拣车间调度问题，通过融合可操作性强并且合理有效的混合人工蜂群算法加以改善。在引领蜂阶段引入并使用遗传算法，设计了4种混合结构的调度算法。并且进一步利用插入和交换邻域的邻域搜索算法提升了混合算法的局部改良能力。通过仿真实验验证了所提混合调度算法的高效率和优越性。

关键词：自动化分拣车间调度；有限缓存区；人工蜂群算法；混合算法；邻域搜索算法

中图分类号：F273 文献标识码：A

Abstract： The poor efficiency of order picking are widespread in the distribution center of each production and sales enterprises. In order to improve the sorting efficiency， reduce the cost of the whole logistics process as the ultimate goal of limited buffer automatic sorting shop scheduling problem， a strong operability and effective hybrid artificial bee colony（HABC）algorithm is improved. Four scheduling algorithms for hybrid structures are designed by introducing and using genetic algorithm in the lead bee phase. To improved the hybrid algorithm of local improvement ability further use of insert and swap neighborhood search algorithm in HABC. The simulation results show that the proposed hybrid scheduling algorithm has high efficiency and superiority.

Key words： automatic sorting shop schedule； limited buffer； artificial bee colony； genetic algorithm； neighborhood search algorithm

0 引 言

传统的流水车间调度问题（Flow Shop Scheduling Problem，FSSP）的描述为：有n个元件在m个机器上进行加工，并且每个工件的加工顺序相同，假设各个机器之间存在无限大的缓冲区，当后面的机器正在进行加工作业时，前面一个机器加工后的工件可以存放在缓存区内直到后面的机器可以对其进行加工。然而在许多实际的生产加工活动中，由于储存空间或储存设备的约束限制，中间缓存区往往十分有限或者根本不存在。为了提高自动化分拣设备之间的分拣效率，减少单个订单在一个分拣设备上的滞留时间，降低分拣作业的成本，合理设置分拣设备间的缓存区是不可忽视的一个环节。因此，研究配送中心或其他物流车间的带有限缓存区的自动化分拣车间调度（Automatic Sorting Shop Schedule，ASSS）问题具有一定的研究意义。

Johnson（1954）[1]最早提出了关于两台机器设备之间的流水调度问题，之后国内外各领域的学者对这一问题进行了深入而广泛的研究与分析，并取得了丰富的研究成果。Hsu（2005）[2]和Tsai（2008）[3]将遗传算法引入到订单分批问题中，并运用遗传算法解决订单分批和路径优化的问题。Mostafa Akhshab（2012）[4]采用一种并行遗传算法来解决流水车间调度问题，最终证实使用并行遗传算法可以大大提高调度效率，节约处理时间。G.M. Komaki和Vahid Kayvanfar（2015）[5]等将流水车间调度分为两个阶段：制造阶段和组装阶段。利用狼群算法（Grey Wolf Optimizer，GWO）解决流水车间调度的效率问题，实验结果表明该算法明显优于其他常用的启发式算法。

近年来学者们发现利用混合算法可以改善单一算法的搜索能力和搜索效率，这对解决流水车间调度问题有着重要的意义。Sana Abdollahpour和Javad Rezaeian（2015）[6]将最小化最大完工时间视为目标函数，来解决流水车间调度问题。Alkin Yurtkuran和Erdal Emel（2015）[7]提出原始的人工蜂群算法搜索性能不佳，并开发出一种自适应人工蜂群算法（AABC），通过对比试验证明AABC的搜索能力优于原始算法。Shams k Nseef（2016）等[8]对传统的人工蜂群算法进行了动态优化，加强了不同阶段蜂群的动态配合，通过实验证明优化后的人工蜂群算法在搜索能力上得到提升。Dunbing Tang（2015）等[9]采用基于一种改进的粒子群优化搜索的帕累托最优解来解决动态调度问题降低能耗和极小化柔性流水车间调度问题。李坤（2015）[10]等建立了针对中间储存能力有限的混合流水车间调度问题的混合整数规划模型，并且提出了一个自适应的变邻域搜索算法。而且通过实验证实了该算法具有较好的全局和局部搜索能力。

对国内外研究的回顾分析表明，大多数现有的算法都是运用在计算机领域或是用来解决流水车间调度问题，运用到物流方面还比较少。利用人工蜂群算法（ABC）來研究分拣车间调度问题的还比较少。随着电子商务浪潮的推进和“互联网+”的发展以及产品的生命周期缩短，以爆发式的大批量订单为形式的市场逐渐朝着细化和个性化发展，零散、多种类、高时效的货物搭配需求不断增加。因此利用人工蜂群算法来研究自动分拣车间的调度问题有着实际意义，可以为提高企业物流效率和收益提供理论指导。

1 问题描述

有限缓存区ASSS描述如下：研究x个订单N=1，2，3…，x在y个自动分拣设备M=1，2，3…，y上的分拣过程，所有x个订单依次在y个自动分拣设备上进行分拣，并规定一个订单在某一时刻只能在一台自动分拣设备上进行分拣，一台自动分拣设备在某一时刻只能对一个订单进行分拣；在每台分拣设备上，x个订单的分拣次序都相同；每两台相邻的分拣设备u和u+1之间存在大小为Q的缓存区，即订单v在分拣设备u上分拣完成后，如果下一台分拣设备u+1的分拣任务没有完成，则订单v将进入缓存区，如果缓存区已满，则订单v滞留在当前分拣设备上；订单在缓存区中都服从按次序分拣的原则。已知订单v在自动分拣设备u上的分拣时间为g，其中v∈1，2，…，x，u∈1，2，…，y。需要解决的问题是寻找一个满足上述约束条件的可行调度，求出最小化最大分拣时间。

设有订单序列c=c1，c2，…，cx，令a表示订单c在自动化分拣设备u上分拣完成并离开的时刻，T为分拣设备u上第cv个订单分拣完成的时刻，v∈1，2，…，x；用Tc表示订单序列c对应的最大订单分拣时间，则有限缓存区ASSS的数学模型为minT

c=minmaxT， v∈1，2，…，x。a的计算如下：

上面7个公式表明，如果Q≥x-1，那么缓存区将对分拣完成的最大时间指标没有影响，上述调度问题可以简化为传统置换调度问题。各个订单c=c1，c2，…，cx的最大分拣完成时间公式为：

在带有限缓存区的自动分拣设备N=y

上ASSS的甘特图如图1所示，其中有限缓存区容量为1，Q=Q=1。与图2的置换FSS相比，订单c的开始分拣时间有所滞后。

2 求解有限缓存区的混合离散人工蜂群算法

2.1 种群编码及初始化

本文采用基于订单排序作为离散的编码，种群中的个体都可以描述为1个订单的分拣序列：c=c1，c2，…，cm。

人工蜂群算法中，蜂群主要由以下三部分组成：雇佣蜂、观察蜂和侦查蜂。由上述式（1）～式（7）可以看出对于有限缓存区自动化分拣车间调度问题，排序靠前的订单造成的分拣设备阻塞时间和空闲时间大于排序靠后的订单造成的阻塞时间和空闲时间。为了使所有订单在分拣设备上的阻塞时间之和最小以及分拣设备空闲时间最小并且保证初始种群的质量，本文采用NEH来初始化种群，并建立基于WPFE和随机方法的混合方法来生成初始种群。在WPFE算法中，首先采用带权重的曲线拟合（WPF）算法得到一个订单序列α，然后基于NEH对α进行插入操作进而得到一个可行解，将雇佣蜂中插入上述得到的解，然后采用随机方式生成蜂群中的其他个体。

2.2 雇佣蜂阶段

在离散人工蜂群（DABC）算法中，雇佣蜂阶段引入离散差分进化策略来生成邻域个体，差分进化策略包括变异、交叉和选择。为使雇傭蜂搜索过程中的邻域结构和种群多样性更加丰富，采用以下基于Insert和Swap操作的4种方法（随机插入交换操作，RIS来生成新的解）。

雇佣蜂采用以上4种方法的一种后得到新的订单分拣序列c，如果c优于c，则取c来代替c。

2.3 观察蜂阶段

为了避免算法陷入局部最优，并且增加算法的全局搜索能力，本文采用锦标赛选举法为观察蜂选择初始订单序列，过程如下：（1）在雇佣蜂搜索到的初始订单序列中，随机挑选并比较两个不同的订单序列c和c，选出两个解中耗时最小的作为进行邻域搜索的候选解。（2）第一步中的候选解使用RIS得到一个新订单序列c，如果c的目标函数值优于第一步中的候选解，则将候选解替换为c。

2.4 侦查蜂阶段

在DABC算法中，侦察蜂对当前种群中的最优解执行3次Insert操作，并生成一个新的解，使用这个新的解来替换连续NC次迭代没有更新的解。

综上，本文提出的DABC调度算法步骤如下：

第一步 对参数PS，NC初始化。利用WPFE算法对种群X=x

x，计算x对应的订单序列c的符合值f

c。

第二步 雇佣蜂阶段。对于j=1，2，…，PS，重复以下操作：

（1）利用RIS方法对每个c产生新订单序列c。

（2）如果有f

c≤f

c，则令c=c。

第三步 观察蜂阶段。j=1，2，…，PS，重复以下操作：

（1）利用锦标赛选举法为观察蜂选取候选解。

（2）对候选解使用RIS方法产生新解，如果新解优于原始解，则将原始解替换为新解。

第四步 侦查蜂阶段。如果一个解在连续NC次迭代后没有优化，则对当前的最优解进行三次Insert操作，生成新解。

第五步 得到的解如果满足要求，则终止操作。否则返回第二步。

3 DABC与GA结合的混合调度算法

3.1 嵌入GA的混合算法

GA算法的特点是进化初期的收敛速度非常快。在DABC的雇佣蜂阶段用GA代替RIS进行对初始食物源的搜索，可以提高算法的全局搜索能力，这种混合算法记为G-DABC1。这种混合算法中，交叉操作和变异操作可以分别提高个体继承的程度和个体的多样性。雇佣蜂阶段嵌入GA使得算法的全局搜索能力得到提升。

3.2 GA与RIS串行的混合算法

GA算法的全局搜索能力虽然很强，但在经过若干次迭代后会使种群失去多样性，从而陷入局部最优也就是造成算法的早熟。为了解决DABC1雇佣蜂阶段算法的早熟问题，雇佣蜂阶段先利用GA搜索时间短的优点在初始种群中选出一个性状比较好的新种群，然后利用RIS对新种群中的个体分别进行求解来得到新的解。这种算法将GA和RIS结合，兼备两种算法的优点，提高了算法收敛到最优解的速度，记为G-DABC2。

3.3 交替型的混合算法

在雇佣蜂阶段交替使用GA和RIS两种算法的交替型混合算法记为G-DABC3。G-DABC3的算法流程如图3所示：

在不断重复上述搜索过程后，算法会较为快速地锁定比较好的解的邻域，之后的迭代又可以找到在现有邻域的范围内更好的邻域。在GA算法和RIS算法交替使用的基础上，G-DABC3的全局搜索和局部搜索能力都得到了改进和平衡，有利于最后得到最优解。

3.4 并行结构的混合算法

并行结构的混合算法（G-DABC4）结合了两种算法的优化操作，增强了算法的探索能力。G-DABC4算法流程如图4所示：

在G-DABC4中，雇佣蜂通过交叉操作将搜索到的优良模式遗传给后代并且使其搜索范围进一步扩大。在获得较好信息的基础上，觀察蜂的邻域探索也更加顺利。同时，变异操作和侦查蜂使得算法能够避免局部最优的误区。

4 融合VNS算法

上述混合算法的全局优化能力虽然得到了加强，但是局部搜索能力还比较弱。为了平衡算法的全局搜索和局部改良能力，将VNS算法嵌入上述混合算法内。

在调度问题中，在一个邻域内的局部最优解周围往往存在其他邻域的局部最优解。VNS算法所获得的全局最优解的概率大于只对单一邻域进行搜索的算法，因为VNS算法是对多个不同邻域进行搜索。所以本文采用基于插入邻域和交换邻域的VNS算法，有效引导整个搜索在较优解附近的进一步搜索，从而使局部搜索能力得到提高。算法的最大迭代次数为z=5n。算法流程如图5所示。

通过将本文提出的4种混合算法和VNS进行结合后进行仿真实验后，我们知道将VNS于并行结构的混合算法结合后是最有效的。将这种最有效的算法记为G-DABCVNS。

5 仿真实验

5.1 仿真试验设置

本文仿真硬件环境为Windows 7（32位）系统，PIV 3.0GHz，内存4G，使用VC++编码。Juyeon Kim[11]指出，如果缓存区容量不断加大，那么缓存区的容量大小对最大订单分拣完成时间的影响会越来越小，在缓存区的容量大于4时，最大订单分拣完成的时间约等于缓存区为无限大时的最大订单分拣完成的时间。所以本文主要研究缓存区容量为1，2，4Q=1，2，4时的情况。

根据对大量文献的研究和大量实验，本文仿真实验的参数设置如下：PS=20， NC=20， pm=0.2， gr=0.7，T为算法的最大运行时间，T=5×x×yms。在仿真实验中，采用Taillard Benchmark问题验证算法有效性，并且与其他算法所得的结果进行对比验证本算法的优越性。

5.2 DABC、GA与混合算法的对比

从提出的4种混合算法和DABC和GA算法的最优值、最差值、均值、方差4个指标数值的比较中可以得出以下结论：

（1）DABC和GA的最优值、最差值和均值都不如4种混合算法的数值，证明了混合算法分别继承了两种算法的优点，提高了算法的求解质量和效率。

（2）G-DABC1的最优值和最差值是在4种算法中最差的。G-DABC2的均值和方差都不如其他算法，但G-DABC2的最优值明显优于G-DABC1和G-DABC4。

（3）G-DABC4的方差值在4种算法中是最好的，但其最优值和均值仅优于G-DABC1和G-DABC2，这说明并行结构的混合算法所得到的结果鲁棒性最好。这是因为G-DABC4结合了GA和RIS算法的优点，使雇佣蜂在全局搜索和局部搜索方面都得到了提升，从而提升了解的质量。

由于4种算法的表现相似，所以，以G-DABC4为例，在缓存区容量不同时，对不同算例进行优化，进行多次仿真实验所得出的结果表明，G-DABC4无论相对于GA还是DABC都具有较短的最大完工时间，其优化效率和收敛速度都比其他单一算法更加优秀。

5.3 G-DABC4VNS的进一步比较分析

将G-DABC4VNS与混合微粒群优化算法（HPSO）及G-DABC4得出的优化结果进行对比，在分别在Q=2，4时计算相对于NEH算法其所得解的相对百分偏差（RPI）和标准差（SD），如表1、表2所示，3种算法的RPI和SD走势如图6～图9所示。

由上述表和对比图像可知：

（1）在Q=2，4的时候G-DABC4VNS的平均相对百分偏差（ARPI）分别为-5.881%，-5.703%，而HPSO算法的ARPI分别为-5.428%，-5.322%，远小于G-DABC4VNS的ARPI。这说明G-DABC4VNS相对于一般智能算法来说具有更好的求解能力。

（2）G-DABC4VNSQ=2时最好RPI个数为10，Q=3时最好RPI个数为9，Q=4时最好RPI个数为8。由此可见，以上3个算法在不同规模问题的处理上也好于其他算法。

（3）在Q=2，4时，G-DABC4VNS均能取到平均标准房差（ASD），说明G-DABC4VNS对初始种群具有更好的鲁棒性。

（4）对比G-DABC4和G-DABC4VNS的数据结果和图像可知VNS算法使得原G-DABC4算法的局部搜索能力显著增强，使得改进后的算法能获得更高质量的解。GA和VNS的加入，使得DABC的各方面搜索能力得到优化，使得G-DABC4VNS具有较快的收敛速度以及极好的搜索能力和求解能力。

6 结束语

物流活动的订单分拣成本占一个配送中心总成本的60%～80%，因此有必要对订单分拣过程进行研究和优化。通过设计基于订单编码的混合人工蜂群算法，用来解决有限缓存区的流水车间调度问题。在初始化阶段使用了GA和RIS两种方法。所设计的混合人工蜂群算法在雇佣蜂阶段引入遗传操作使得雇佣蜂的全局搜索能力和收敛速度得到提升，为了防止算法陷入局部最优，在观察蜂阶段使用锦标赛选举法，并且为了平衡对解空间探索的效率和改良，在算法中采用基于插入和交换邻域搜索算法。在文中给出了典型的算例仿真和算法的比较分析，以此验证了所提的算法具有较强的鲁棒性和优越性。希望为大中型企业的自动