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

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

在帶有限緩存區(qū)的自動(dòng)分揀設(shè)備N(xiāo)=y

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

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

2.1 種群編碼及初始化

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

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

2.2 雇傭蜂階段

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

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

2.3 觀察蜂階段

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

2.4 偵查蜂階段

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

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

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

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

c。

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

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

（2）如果有f

c≤f

c，則令c=c。

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

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

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

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

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

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

3.1 嵌入GA的混合算法

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

3.2 GA與RIS串行的混合算法

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

3.3 交替型的混合算法

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

在不斷重復(fù)上述搜索過(guò)程后，算法會(huì)較為快速地鎖定比較好的解的鄰域，之后的迭代又可以找到在現(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中，雇傭蜂通過(guò)交叉操作將搜索到的優(yōu)良模式遺傳給后代并且使其搜索范圍進(jìn)一步擴(kuò)大。在獲得較好信息的基礎(chǔ)上，觀察蜂的鄰域探索也更加順利。同時(shí)，變異操作和偵查蜂使得算法能夠避免局部最優(yōu)的誤區(qū)。

4 融合VNS算法

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

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

通過(guò)將本文提出的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ū)的容量大小對(duì)最大訂單分揀完成時(shí)間的影響會(huì)越來(lái)越小，在緩存區(qū)的容量大于4時(shí)，最大訂單分揀完成的時(shí)間約等于緩存區(qū)為無(wú)限大時(shí)的最大訂單分揀完成的時(shí)間。所以本文主要研究緩存區(qū)容量為1，2，4Q=1，2，4時(shí)的情況。

根據(jù)對(duì)大量文獻(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問(wèn)題驗(yàn)證算法有效性，并且與其他算法所得的結(jié)果進(jìn)行對(duì)比驗(yàn)證本算法的優(yōu)越性。

5.2 DABC、GA與混合算法的對(duì)比

從提出的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，這說(shuō)明并行結(jié)構(gòu)的混合算法所得到的結(jié)果魯棒性最好。這是因?yàn)镚-DABC4結(jié)合了GA和RIS算法的優(yōu)點(diǎn)，使雇傭蜂在全局搜索和局部搜索方面都得到了提升，從而提升了解的質(zhì)量。

由于4種算法的表現(xiàn)相似，所以，以G-DABC4為例，在緩存區(qū)容量不同時(shí)，對(duì)不同算例進(jìn)行優(yōu)化，進(jìn)行多次仿真實(shí)驗(yàn)所得出的結(jié)果表明，G-DABC4無(wú)論相對(duì)于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)行對(duì)比，在分別在Q=2，4時(shí)計(jì)算相對(duì)于NEH算法其所得解的相對(duì)百分偏差（RPI）和標(biāo)準(zhǔn)差（SD），如表1、表2所示，3種算法的RPI和SD走勢(shì)如圖6～圖9所示。

由上述表和對(duì)比圖像可知：

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

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

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

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

6 結(jié)束語(yǔ)

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