有限緩存區(qū)自動化分揀車間調(diào)度混合人工蜂群算法

宋志蘭++張壯++徐七龍

摘 要：自動化訂單分揀效率低下的問題普遍存在于各個(gè)生產(chǎn)銷售企業(yè)的配送中心。針對以提高分揀效率、降低整個(gè)物流過程的成本為最終目標(biāo)的有限緩存區(qū)自動化分揀車間調(diào)度問題，通過融合可操作性強(qiáng)并且合理有效的混合人工蜂群算法加以改善。在引領(lǐng)蜂階段引入并使用遺傳算法，設(shè)計(jì)了4種混合結(jié)構(gòu)的調(diào)度算法。并且進(jìn)一步利用插入和交換鄰域的鄰域搜索算法提升了混合算法的局部改良能力。通過仿真實(shí)驗(yàn)驗(yàn)證了所提混合調(diào)度算法的高效率和優(yōu)越性。

關(guān)鍵詞：自動化分揀車間調(diào)度；有限緩存區(qū)；人工蜂群算法；混合算法；鄰域搜索算法

中圖分類號：F273 文獻(xiàn)標(biāo)識碼：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 引 言

傳統(tǒng)的流水車間調(diào)度問題（Flow Shop Scheduling Problem，F(xiàn)SSP）的描述為：有n個(gè)元件在m個(gè)機(jī)器上進(jìn)行加工，并且每個(gè)工件的加工順序相同，假設(shè)各個(gè)機(jī)器之間存在無限大的緩沖區(qū)，當(dāng)后面的機(jī)器正在進(jìn)行加工作業(yè)時(shí)，前面一個(gè)機(jī)器加工后的工件可以存放在緩存區(qū)內(nèi)直到后面的機(jī)器可以對其進(jìn)行加工。然而在許多實(shí)際的生產(chǎn)加工活動中，由于儲存空間或儲存設(shè)備的約束限制，中間緩存區(qū)往往十分有限或者根本不存在。為了提高自動化分揀設(shè)備之間的分揀效率，減少單個(gè)訂單在一個(gè)分揀設(shè)備上的滯留時(shí)間，降低分揀作業(yè)的成本，合理設(shè)置分揀設(shè)備間的緩存區(qū)是不可忽視的一個(gè)環(huán)節(jié)。因此，研究配送中心或其他物流車間的帶有限緩存區(qū)的自動化分揀車間調(diào)度（Automatic Sorting Shop Schedule，ASSS）問題具有一定的研究意義。

Johnson（1954）[1]最早提出了關(guān)于兩臺機(jī)器設(shè)備之間的流水調(diào)度問題，之后國內(nèi)外各領(lǐng)域的學(xué)者對這一問題進(jìn)行了深入而廣泛的研究與分析，并取得了豐富的研究成果。Hsu（2005）[2]和Tsai（2008）[3]將遺傳算法引入到訂單分批問題中，并運(yùn)用遺傳算法解決訂單分批和路徑優(yōu)化的問題。Mostafa Akhshab（2012）[4]采用一種并行遺傳算法來解決流水車間調(diào)度問題，最終證實(shí)使用并行遺傳算法可以大大提高調(diào)度效率，節(jié)約處理時(shí)間。G.M. Komaki和Vahid Kayvanfar（2015）[5]等將流水車間調(diào)度分為兩個(gè)階段：制造階段和組裝階段。利用狼群算法（Grey Wolf Optimizer，GWO）解決流水車間調(diào)度的效率問題，實(shí)驗(yàn)結(jié)果表明該算法明顯優(yōu)于其他常用的啟發(fā)式算法。

近年來學(xué)者們發(fā)現(xiàn)利用混合算法可以改善單一算法的搜索能力和搜索效率，這對解決流水車間調(diào)度問題有著重要的意義。Sana Abdollahpour和Javad Rezaeian（2015）[6]將最小化最大完工時(shí)間視為目標(biāo)函數(shù)，來解決流水車間調(diào)度問題。Alkin Yurtkuran和Erdal Emel（2015）[7]提出原始的人工蜂群算法搜索性能不佳，并開發(fā)出一種自適應(yīng)人工蜂群算法（AABC），通過對比試驗(yàn)證明AABC的搜索能力優(yōu)于原始算法。Shams k Nseef（2016）等[8]對傳統(tǒng)的人工蜂群算法進(jìn)行了動態(tài)優(yōu)化，加強(qiáng)了不同階段蜂群的動態(tài)配合，通過實(shí)驗(yàn)證明優(yōu)化后的人工蜂群算法在搜索能力上得到提升。Dunbing Tang（2015）等[9]采用基于一種改進(jìn)的粒子群優(yōu)化搜索的帕累托最優(yōu)解來解決動態(tài)調(diào)度問題降低能耗和極小化柔性流水車間調(diào)度問題。李坤（2015）[10]等建立了針對中間儲存能力有限的混合流水車間調(diào)度問題的混合整數(shù)規(guī)劃模型，并且提出了一個(gè)自適應(yīng)的變鄰域搜索算法。而且通過實(shí)驗(yàn)證實(shí)了該算法具有較好的全局和局部搜索能力。

對國內(nèi)外研究的回顧分析表明，大多數(shù)現(xiàn)有的算法都是運(yùn)用在計(jì)算機(jī)領(lǐng)域或是用來解決流水車間調(diào)度問題，運(yùn)用到物流方面還比較少。利用人工蜂群算法（ABC）來研究分揀車間調(diào)度問題的還比較少。隨著電子商務(wù)浪潮的推進(jìn)和“互聯(lián)網(wǎng)+”的發(fā)展以及產(chǎn)品的生命周期縮短，以爆發(fā)式的大批量訂單為形式的市場逐漸朝著細(xì)化和個(gè)性化發(fā)展，零散、多種類、高時(shí)效的貨物搭配需求不斷增加。因此利用人工蜂群算法來研究自動分揀車間的調(diào)度問題有著實(shí)際意義，可以為提高企業(yè)物流效率和收益提供理論指導(dǎo)。

1 問題描述

有限緩存區(qū)ASSS描述如下：研究x個(gè)訂單N=1，2，3…，x在y個(gè)自動分揀設(shè)備M=1，2，3…，y上的分揀過程，所有x個(gè)訂單依次在y個(gè)自動分揀設(shè)備上進(jìn)行分揀，并規(guī)定一個(gè)訂單在某一時(shí)刻只能在一臺自動分揀設(shè)備上進(jìn)行分揀，一臺自動分揀設(shè)備在某一時(shí)刻只能對一個(gè)訂單進(jìn)行分揀；在每臺分揀設(shè)備上，x個(gè)訂單的分揀次序都相同；每兩臺相鄰的分揀設(shè)備u和u+1之間存在大小為Q的緩存區(qū)，即訂單v在分揀設(shè)備u上分揀完成后，如果下一臺分揀設(shè)備u+1的分揀任務(wù)沒有完成，則訂單v將進(jìn)入緩存區(qū)，如果緩存區(qū)已滿，則訂單v滯留在當(dāng)前分揀設(shè)備上；訂單在緩存區(qū)中都服從按次序分揀的原則。已知訂單v在自動分揀設(shè)備u上的分揀時(shí)間為g，其中v∈1，2，…，x，u∈1，2，…，y。需要解決的問題是尋找一個(gè)滿足上述約束條件的可行調(diào)度，求出最小化最大分揀時(shí)間。

設(shè)有訂單序列c=c1，c2，…，cx，令a表示訂單c在自動化分揀設(shè)備u上分揀完成并離開的時(shí)刻，T為分揀設(shè)備u上第cv個(gè)訂單分揀完成的時(shí)刻，v∈1，2，…，x；用Tc表示訂單序列c對應(yīng)的最大訂單分揀時(shí)間，則有限緩存區(qū)ASSS的數(shù)學(xué)模型為minT

c=minmaxT， v∈1，2，…，x。a的計(jì)算如下：

上面7個(gè)公式表明，如果Q≥x-1，那么緩存區(qū)將對分揀完成的最大時(shí)間指標(biāo)沒有影響，上述調(diào)度問題可以簡化為傳統(tǒng)置換調(diào)度問題。各個(gè)訂單c=c1，c2，…，cx的最大分揀完成時(shí)間公式為：

在帶有限緩存區(qū)的自動分揀設(shè)備N=y

上ASSS的甘特圖如圖1所示，其中有限緩存區(qū)容量為1，Q=Q=1。與圖2的置換FSS相比，訂單c的開始分揀時(shí)間有所滯后。

2 求解有限緩存區(qū)的混合離散人工蜂群算法

2.1 種群編碼及初始化

本文采用基于訂單排序作為離散的編碼，種群中的個(gè)體都可以描述為1個(gè)訂單的分揀序列：c=c1，c2，…，cm。

人工蜂群算法中，蜂群主要由以下三部分組成：雇傭蜂、觀察蜂和偵查蜂。由上述式（1）～式（7）可以看出對于有限緩存區(qū)自動化分揀車間調(diào)度問題，排序靠前的訂單造成的分揀設(shè)備阻塞時(shí)間和空閑時(shí)間大于排序靠后的訂單造成的阻塞時(shí)間和空閑時(shí)間。為了使所有訂單在分揀設(shè)備上的阻塞時(shí)間之和最小以及分揀設(shè)備空閑時(shí)間最小并且保證初始種群的質(zhì)量，本文采用NEH來初始化種群，并建立基于WPFE和隨機(jī)方法的混合方法來生成初始種群。在WPFE算法中，首先采用帶權(quán)重的曲線擬合（WPF）算法得到一個(gè)訂單序列α，然后基于NEH對α進(jìn)行插入操作進(jìn)而得到一個(gè)可行解，將雇傭蜂中插入上述得到的解，然后采用隨機(jī)方式生成蜂群中的其他個(gè)體。

2.2 雇傭蜂階段

在離散人工蜂群（DABC）算法中，雇傭蜂階段引入離散差分進(jìn)化策略來生成鄰域個(gè)體，差分進(jìn)化策略包括變異、交叉和選擇。為使雇傭蜂搜索過程中的鄰域結(jié)構(gòu)和種群多樣性更加豐富，采用以下基于Insert和Swap操作的4種方法（隨機(jī)插入交換操作，RIS來生成新的解）。

雇傭蜂采用以上4種方法的一種后得到新的訂單分揀序列c，如果c優(yōu)于c，則取c來代替c。

2.3 觀察蜂階段

為了避免算法陷入局部最優(yōu)，并且增加算法的全局搜索能力，本文采用錦標(biāo)賽選舉法為觀察蜂選擇初始訂單序列，過程如下：（1）在雇傭蜂搜索到的初始訂單序列中，隨機(jī)挑選并比較兩個(gè)不同的訂單序列c和c，選出兩個(gè)解中耗時(shí)最小的作為進(jìn)行鄰域搜索的候選解。（2）第一步中的候選解使用RIS得到一個(gè)新訂單序列c，如果c的目標(biāo)函數(shù)值優(yōu)于第一步中的候選解，則將候選解替換為c。

2.4 偵查蜂階段

在DABC算法中，偵察蜂對當(dāng)前種群中的最優(yōu)解執(zhí)行3次Insert操作，并生成一個(gè)新的解，使用這個(gè)新的解來替換連續(xù)NC次迭代沒有更新的解。

綜上，本文提出的DABC調(diào)度算法步驟如下：

第一步 對參數(shù)PS，NC初始化。利用WPFE算法對種群X=x

x，計(jì)算x對應(yīng)的訂單序列c的符合值f

c。

第二步 雇傭蜂階段。對于j=1，2，…，PS，重復(fù)以下操作：

（1）利用RIS方法對每個(gè)c產(chǎn)生新訂單序列c。

（2）如果有f

c≤f

c，則令c=c。

第三步 觀察蜂階段。j=1，2，…，PS，重復(fù)以下操作：

（1）利用錦標(biāo)賽選舉法為觀察蜂選取候選解。

（2）對候選解使用RIS方法產(chǎn)生新解，如果新解優(yōu)于原始解，則將原始解替換為新解。

第四步 偵查蜂階段。如果一個(gè)解在連續(xù)NC次迭代后沒有優(yōu)化，則對當(dāng)前的最優(yōu)解進(jìn)行三次Insert操作，生成新解。

第五步 得到的解如果滿足要求，則終止操作。否則返回第二步。

3 DABC與GA結(jié)合的混合調(diào)度算法

3.1 嵌入GA的混合算法

GA算法的特點(diǎn)是進(jìn)化初期的收斂速度非?？?。在DABC的雇傭蜂階段用GA代替RIS進(jìn)行對初始食物源的搜索，可以提高算法的全局搜索能力，這種混合算法記為G-DABC1。這種混合算法中，交叉操作和變異操作可以分別提高個(gè)體繼承的程度和個(gè)體的多樣性。雇傭蜂階段嵌入GA使得算法的全局搜索能力得到提升。

3.2 GA與RIS串行的混合算法

GA算法的全局搜索能力雖然很強(qiáng)，但在經(jīng)過若干次迭代后會使種群失去多樣性，從而陷入局部最優(yōu)也就是造成算法的早熟。為了解決DABC1雇傭蜂階段算法的早熟問題，雇傭蜂階段先利用GA搜索時(shí)間短的優(yōu)點(diǎn)在初始種群中選出一個(gè)性狀比較好的新種群，然后利用RIS對新種群中的個(gè)體分別進(jìn)行求解來得到新的解。這種算法將GA和RIS結(jié)合，兼?zhèn)鋬煞N算法的優(yōu)點(diǎn)，提高了算法收斂到最優(yōu)解的速度，記為G-DABC2。

3.3 交替型的混合算法

在雇傭蜂階段交替使用GA和RIS兩種算法的交替型混合算法記為G-DABC3。G-DABC3的算法流程如圖3所示：

在不斷重復(fù)上述搜索過程后，算法會較為快速地鎖定比較好的解的鄰域，之后的迭代又可以找到在現(xiàn)有鄰域的范圍內(nèi)更好的鄰域。在GA算法和RIS算法交替使用的基礎(chǔ)上，G-DABC3的全局搜索和局部搜索能力都得到了改進(jìn)和平衡，有利于最后得到最優(yōu)解。

3.4 并行結(jié)構(gòu)的混合算法

并行結(jié)構(gòu)的混合算法（G-DABC4）結(jié)合了兩種算法的優(yōu)化操作，增強(qiáng)了算法的探索能力。G-DABC4算法流程如圖4所示：

在G-DABC4中，雇傭蜂通過交叉操作將搜索到的優(yōu)良模式遺傳給后代并且使其搜索范圍進(jìn)一步擴(kuò)大。在獲得較好信息的基礎(chǔ)上，觀察蜂的鄰域探索也更加順利。同時(shí)，變異操作和偵查蜂使得算法能夠避免局部最優(yōu)的誤區(qū)。

4 融合VNS算法

上述混合算法的全局優(yōu)化能力雖然得到了加強(qiáng)，但是局部搜索能力還比較弱。為了平衡算法的全局搜索和局部改良能力，將VNS算法嵌入上述混合算法內(nèi)。

在調(diào)度問題中，在一個(gè)鄰域內(nèi)的局部最優(yōu)解周圍往往存在其他鄰域的局部最優(yōu)解。VNS算法所獲得的全局最優(yōu)解的概率大于只對單一鄰域進(jìn)行搜索的算法，因?yàn)閂NS算法是對多個(gè)不同鄰域進(jìn)行搜索。所以本文采用基于插入鄰域和交換鄰域的VNS算法，有效引導(dǎo)整個(gè)搜索在較優(yōu)解附近的進(jìn)一步搜索，從而使局部搜索能力得到提高。算法的最大迭代次數(shù)為z=5n。算法流程如圖5所示。

通過將本文提出的4種混合算法和VNS進(jìn)行結(jié)合后進(jìn)行仿真實(shí)驗(yàn)后，我們知道將VNS于并行結(jié)構(gòu)的混合算法結(jié)合后是最有效的。將這種最有效的算法記為G-DABCVNS。

5 仿真實(shí)驗(yàn)

5.1 仿真試驗(yàn)設(shè)置

本文仿真硬件環(huán)境為Windows 7（32位）系統(tǒng)，PIV 3.0GHz，內(nèi)存4G，使用VC++編碼。Juyeon Kim[11]指出，如果緩存區(qū)容量不斷加大，那么緩存區(qū)的容量大小對最大訂單分揀完成時(shí)間的影響會越來越小，在緩存區(qū)的容量大于4時(shí)，最大訂單分揀完成的時(shí)間約等于緩存區(qū)為無限大時(shí)的最大訂單分揀完成的時(shí)間。所以本文主要研究緩存區(qū)容量為1，2，4Q=1，2，4時(shí)的情況。

根據(jù)對大量文獻(xiàn)的研究和大量實(shí)驗(yàn)，本文仿真實(shí)驗(yàn)的參數(shù)設(shè)置如下：PS=20， NC=20， pm=0.2， gr=0.7，T為算法的最大運(yùn)行時(shí)間，T=5×x×yms。在仿真實(shí)驗(yàn)中，采用Taillard Benchmark問題驗(yàn)證算法有效性，并且與其他算法所得的結(jié)果進(jìn)行對比驗(yàn)證本算法的優(yōu)越性。

5.2 DABC、GA與混合算法的對比

從提出的4種混合算法和DABC和GA算法的最優(yōu)值、最差值、均值、方差4個(gè)指標(biāo)數(shù)值的比較中可以得出以下結(jié)論：

（1）DABC和GA的最優(yōu)值、最差值和均值都不如4種混合算法的數(shù)值，證明了混合算法分別繼承了兩種算法的優(yōu)點(diǎn)，提高了算法的求解質(zhì)量和效率。

（2）G-DABC1的最優(yōu)值和最差值是在4種算法中最差的。G-DABC2的均值和方差都不如其他算法，但G-DABC2的最優(yōu)值明顯優(yōu)于G-DABC1和G-DABC4。

（3）G-DABC4的方差值在4種算法中是最好的，但其最優(yōu)值和均值僅優(yōu)于G-DABC1和G-DABC2，這說明并行結(jié)構(gòu)的混合算法所得到的結(jié)果魯棒性最好。這是因?yàn)镚-DABC4結(jié)合了GA和RIS算法的優(yōu)點(diǎn)，使雇傭蜂在全局搜索和局部搜索方面都得到了提升，從而提升了解的質(zhì)量。

由于4種算法的表現(xiàn)相似，所以，以G-DABC4為例，在緩存區(qū)容量不同時(shí)，對不同算例進(jìn)行優(yōu)化，進(jìn)行多次仿真實(shí)驗(yàn)所得出的結(jié)果表明，G-DABC4無論相對于GA還是DABC都具有較短的最大完工時(shí)間，其優(yōu)化效率和收斂速度都比其他單一算法更加優(yōu)秀。

5.3 G-DABC4VNS的進(jìn)一步比較分析

將G-DABC4VNS與混合微粒群優(yōu)化算法（HPSO）及G-DABC4得出的優(yōu)化結(jié)果進(jìn)行對比，在分別在Q=2，4時(shí)計(jì)算相對于NEH算法其所得解的相對百分偏差（RPI）和標(biāo)準(zhǔn)差（SD），如表1、表2所示，3種算法的RPI和SD走勢如圖6～圖9所示。

由上述表和對比圖像可知：

（1）在Q=2，4的時(shí)候G-DABC4VNS的平均相對百分偏差（ARPI）分別為-5.881%，-5.703%，而HPSO算法的ARPI分別為-5.428%，-5.322%，遠(yuǎn)小于G-DABC4VNS的ARPI。這說明G-DABC4VNS相對于一般智能算法來說具有更好的求解能力。

（2）G-DABC4VNSQ=2時(shí)最好RPI個(gè)數(shù)為10，Q=3時(shí)最好RPI個(gè)數(shù)為9，Q=4時(shí)最好RPI個(gè)數(shù)為8。由此可見，以上3個(gè)算法在不同規(guī)模問題的處理上也好于其他算法。

（3）在Q=2，4時(shí)，G-DABC4VNS均能取到平均標(biāo)準(zhǔn)房差（ASD），說明G-DABC4VNS對初始種群具有更好的魯棒性。

（4）對比G-DABC4和G-DABC4VNS的數(shù)據(jù)結(jié)果和圖像可知VNS算法使得原G-DABC4算法的局部搜索能力顯著增強(qiáng)，使得改進(jìn)后的算法能獲得更高質(zhì)量的解。GA和VNS的加入，使得DABC的各方面搜索能力得到優(yōu)化，使得G-DABC4VNS具有較快的收斂速度以及極好的搜索能力和求解能力。

6 結(jié)束語

物流活動的訂單分揀成本占一個(gè)配送中心總成本的60%～80%，因此有必要對訂單分揀過程進(jìn)行研究和優(yōu)化。通過設(shè)計(jì)基于訂單編碼的混合人工蜂群算法，用來解決有限緩存區(qū)的流水車間調(diào)度問題。在初始化階段使用了GA和RIS兩種方法。所設(shè)計(jì)的混合人工蜂群算法在雇傭蜂階段引入遺傳操作使得雇傭蜂的全局搜索能力和收斂速度得到提升，為了防止算法陷入局部最優(yōu)，在觀察蜂階段使用錦標(biāo)賽選舉法，并且為了平衡對解空間探索的效率和改良，在算法中采用基于插入和交換鄰域搜索算法。在文中給出了典型的算例仿真和算法的比較分析，以此驗(yàn)證了所提的算法具有較強(qiáng)的魯棒性和優(yōu)越性。希望為大中型企業(yè)的自動