范霽月,高 尚,張曉慶
(江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 鎮(zhèn)江 212003)
針對(duì)集裝箱裝載問(wèn)題(container loading problem,CLP)[1-3],現(xiàn)在研究者多使用數(shù)學(xué)規(guī)劃法、圖論法、啟發(fā)式算法[4]、遺傳算法[5]、蟻群算法[6]等來(lái)解決集裝箱問(wèn)題,但考慮到裝載中存在的約束條件不全面,裝載率仍有較大提升空間。細(xì)菌覓食算法是近年來(lái)新起的一種群智能優(yōu)化算法,它模擬大腸桿菌的覓食行為,對(duì)原始數(shù)據(jù)進(jìn)行趨化、復(fù)制、消亡操作,進(jìn)而得到最優(yōu)解[7-9]。該算法并行性高、處理效率高、魯棒性強(qiáng),能以較小的代價(jià)通過(guò)算法性能獲得較大的收益,因此是一種很有價(jià)值的解決方法。
本文就集裝箱裝載問(wèn)題,提出基于余弦的自適應(yīng)步長(zhǎng)細(xì)菌覓食優(yōu)化算法的求解新方法,在三空間分割裝載策略[10]的基礎(chǔ)上,使用基于順序表示的遺傳基因編碼方式將不同的裝載方式編碼為適應(yīng)度函數(shù)的解,再通過(guò)改進(jìn)的自適應(yīng)步長(zhǎng)的細(xì)菌覓食優(yōu)化算法[11]得出最優(yōu)解。相比之前采用的遺傳算法、啟發(fā)式算法、蟻群算法等各種優(yōu)化算法,實(shí)驗(yàn)結(jié)果表明,本文中采用的自適應(yīng)步長(zhǎng)的細(xì)菌覓食優(yōu)化算法可以在相對(duì)較短的時(shí)間內(nèi)獲得一個(gè)合理的裝載方案,并且有較高的裝載率和空間利用率,對(duì)實(shí)際的裝載過(guò)程有一定的指導(dǎo)意義。
大腸桿菌在覓食過(guò)程中逐步向目標(biāo)移動(dòng)并且遠(yuǎn)離有毒物質(zhì),這在生物學(xué)中被稱作覓食方法。細(xì)菌在初始位置考量食物的豐富程度后,通過(guò)翻滾選擇一個(gè)隨機(jī)方向并移動(dòng)固定的距離,隨后再次考量新位置食物的豐富度。一次翻滾和前進(jìn)過(guò)程形成一步趨化。趨化過(guò)程中如果下一位置食物更密集,細(xì)菌會(huì)在同樣方向再次游動(dòng),直到達(dá)到最大游動(dòng)次數(shù);反之,細(xì)菌會(huì)翻滾產(chǎn)生新的方向并前進(jìn)。最大游動(dòng)次數(shù)代表著細(xì)菌的生命周期。在細(xì)菌生命周期結(jié)束時(shí),一半具有較優(yōu)健康值的細(xì)菌在各自的置將被復(fù)制,另一半會(huì)死亡,復(fù)制的執(zhí)行次數(shù)也固定。在尋優(yōu)過(guò)程中我們可以把待優(yōu)變量和細(xì)菌所在位置匹配。細(xì)菌復(fù)制次數(shù)、趨化步數(shù)、前進(jìn)步長(zhǎng)、特定方向上的游動(dòng)次數(shù)要根據(jù)特定問(wèn)題初始化,利用BFOA實(shí)現(xiàn)變量的最優(yōu)化。
細(xì)菌覓食優(yōu)化算法是模擬大腸桿菌在我們食道中的吞噬食物行為而產(chǎn)生的新型群體智能優(yōu)化算法。概括起來(lái)主要有4種行為:趨化行為、聚集行為、復(fù)制行為和驅(qū)散行為。
趨化過(guò)程是由翻滾和前進(jìn)實(shí)現(xiàn)的,是細(xì)菌覓食算法的核心。其設(shè)計(jì)好壞與否直接影響著算法在解決集裝箱裝載問(wèn)題上的性能與效果。假設(shè)θi(j+1,k,l)表示第i個(gè)細(xì)菌在第l次驅(qū)散、第k次復(fù)制、第j+1次趨化的位置,則有
θi(j+1,k,l)=θi(j,k,l)+C(i)φ(j)
(1)
式中:C(i)為翻滾過(guò)程中設(shè)定的隨機(jī)方向上的步長(zhǎng),φ(j)為隨機(jī)方向單位向量。
通常問(wèn)題期望細(xì)菌尋找到食物最優(yōu)的路徑后能夠快速地吸引其它細(xì)菌到目標(biāo)位置。群游(swarming)能夠讓細(xì)菌緊密靠攏,使得細(xì)菌在群組中集體移動(dòng)。群游是所有細(xì)菌共同作用的結(jié)果,該結(jié)果添加到實(shí)際目標(biāo)函數(shù)后,表現(xiàn)為變化的目標(biāo)函數(shù)。群游結(jié)果的目標(biāo)函數(shù)數(shù)學(xué)上可表示為
(2)
式中:S是細(xì)菌總數(shù)量,p是每個(gè)細(xì)菌需優(yōu)化的參數(shù)個(gè)數(shù)。吸引劑數(shù)值dattract,排斥劑數(shù)值hrepellent,吸引劑釋放速度ωattract和排斥劑釋放速度ωrepellent是待調(diào)系數(shù)。
為了在優(yōu)勝劣汰,種群進(jìn)化的同時(shí),保證種群規(guī)模的相對(duì)穩(wěn)定,一部分覓食能力強(qiáng)、健康狀況好的細(xì)菌,在同樣的位置分裂為兩個(gè)相同個(gè)體;健康狀況最差的細(xì)菌被淘汰。通過(guò)復(fù)制操作,種群中的優(yōu)良個(gè)體得以保留并得到保護(hù),這樣大大提高了尋找最優(yōu)解的速度,且保持了種群的完整性。
細(xì)菌在局部環(huán)境下常受到養(yǎng)料消耗或是環(huán)境突變的影響,導(dǎo)致其消亡或者被驅(qū)散到別處。這種現(xiàn)象可能破壞趨化過(guò)程,但細(xì)菌也可能被驅(qū)散到好的食物源附近。驅(qū)散行為加強(qiáng)BFOA全局尋優(yōu)能力,降低細(xì)菌陷入局部極小現(xiàn)象的可能性。
基于BFOA具有容易陷入局部極值、收斂速度慢等缺點(diǎn),所以本文采用自適應(yīng)細(xì)菌覓食優(yōu)化算法(ABFOA)解決集裝箱裝在問(wèn)題,使用改進(jìn)的基于余弦的自適應(yīng)規(guī)則的步長(zhǎng)替代固定步長(zhǎng),自適應(yīng)步長(zhǎng)隨著迭代次數(shù)的降低而減小,更好地對(duì)細(xì)菌進(jìn)行趨化操作,顯著提升算法的尋優(yōu)質(zhì)量,在求解CLP上取得滿意的效果。
設(shè)定集裝箱的長(zhǎng)、寬、高分別為L(zhǎng)j,Wj,Hj,質(zhì)量為Mj,容積為Vj待裝的n類貨物的長(zhǎng)、寬、高分別為li,wi,hi,質(zhì)量為mj。ki為每類貨物的總數(shù)量。則問(wèn)題的目標(biāo)函數(shù)為
(3)
即:k1*所有裝載的貨物體積總和占集裝箱體積的比例+k2*所有裝載物品的質(zhì)量總和占集裝箱最多可承受的質(zhì)量比例,其中k1,k2為比例系數(shù),一般取值k1+k2=1,參見2.4章節(jié)。
式(3)中,F為目標(biāo)函數(shù);φi為第i類已裝貨物件數(shù),0≤φi≤ki,為第i類貨物總件數(shù),k1和k2為比例系數(shù),兩者范圍在0-1之間。
裝載貨物時(shí)的約束條件為:
(1)貨物的裝載容積約束:所有裝載的貨物體積之和小于集裝箱可容納的最大體積;
(2)貨物的裝載質(zhì)量約束:所有裝載的貨物質(zhì)量之和小于集裝箱可承受的最大質(zhì)量,公式表示如下
(4)
2.1.1 待裝載貨物擺放方式
假定待擺放物品是規(guī)則的六面體,并且重心在六面體幾何中心位置,因此貨物在集裝箱中產(chǎn)生6種不同的擺放方式。每種待裝貨物擺放方式的編號(hào)分別對(duì)應(yīng)的該貨物在集裝箱中某種特定的旋轉(zhuǎn)方向,表1是兩者之間關(guān)系的說(shuō)明。
表1 待裝貨物擺放方式編號(hào)和集裝箱位置對(duì)應(yīng)的關(guān)系
2.1.2 空間劃分和歸并策略
從每個(gè)長(zhǎng)方體平行但不與HL重合的面裝入貨物,每當(dāng)一個(gè)貨物進(jìn)入集裝箱放置好之后,該貨物將整個(gè)空間分為除自身以外的3個(gè)子空間:上空間、前空間、右空間,如圖1所示。而后已放置貨物的空間被去除,剩余3個(gè)形狀為長(zhǎng)方體的新的空間。放入下一個(gè)的貨物時(shí),按照上空間、前空間、右空間的順序?qū)ψ涌臻g進(jìn)行填充。每放入新的貨物,則其又產(chǎn)生3個(gè)新的子空間。
圖1 集裝箱三維分割
2.1.3 定位規(guī)則和定序規(guī)則
定位規(guī)則中占角策略是指將貨物首先擺放在集裝箱空間的某一角,通過(guò)分析,占角策略是大多集裝箱裝載問(wèn)題選擇的較好的策略。在定序過(guò)程中充分考慮體積和重量綜合因素的影響,參照式(3)中k1,k2值,按體積和質(zhì)量由大到小的定序規(guī)則裝載貨物。
通常,BFOA對(duì)解的編碼方案大多采用二維或三維空間坐標(biāo)編碼形式,但是對(duì)于集裝箱裝載排序問(wèn)題顯然不采能用該編碼方式。原因有二個(gè):①空間坐標(biāo)可以用于排列質(zhì)點(diǎn),但是對(duì)于待裝載的三維物品很容易在空間上產(chǎn)生交叉現(xiàn)象,為避免該現(xiàn)象不能不引入復(fù)雜的計(jì)算;②細(xì)菌的空間坐標(biāo)在空間維度上有具體的坐標(biāo)值,但是不能很好地將其和適應(yīng)度函數(shù)相配,導(dǎo)致算法不宜執(zhí)行。為此,本文采用基于順序表示的遺傳基因編碼方式。將n種待裝載物品按照體積和質(zhì)量由大到小的原則、按自然數(shù)由小到大的方式排序編號(hào),并且按照種類編號(hào)依次排列編碼,則第i個(gè)細(xì)菌編碼形式
Pi=(p1,p2,…,pn,pn+1,pn+2,…,p2n)
(5)其中,i=1,2,…,S,S為細(xì)菌種群規(guī)模,p1,p2,…,pn為待裝貨物種類編號(hào),pn+1,pn+2,…,p2n為前n個(gè)種類編號(hào)對(duì)應(yīng)貨物的旋轉(zhuǎn)方向,其值取1,2,…,6。含義見上文。
式(5)中pi和pn+i值相互對(duì)應(yīng),即第pi種貨物以pn+i表示的旋轉(zhuǎn)方向放入集裝箱中。利用該解碼方式,原有的初始解Pi可以被轉(zhuǎn)化為一個(gè)與之相對(duì)應(yīng)的可行解
Qi={q1,q2,…qm,qm+1,qm+2,…,q2m}
(6)
式中:m為待裝貨物總數(shù)量,qi表示等待裝載的第i個(gè)貨物。所有貨物根據(jù)當(dāng)前裝載狀態(tài)選擇性裝入集裝箱,貨物的編碼在可行解中記為1表示其被裝入,可行解中為0時(shí)表示不裝入集裝箱。
前進(jìn)步長(zhǎng)C(i)對(duì)收斂速度和輸出誤差起著決定性作用。研究發(fā)現(xiàn),BFOA中固定的C(i)會(huì)帶來(lái)兩個(gè)問(wèn)題:①若前進(jìn)步長(zhǎng)過(guò)大,細(xì)菌到達(dá)優(yōu)質(zhì)點(diǎn)區(qū)域的速度雖有所增加,但是會(huì)導(dǎo)致尋優(yōu)精度降低,使得細(xì)菌在之后趨化過(guò)程中的極值附近來(lái)回移動(dòng);②若前進(jìn)步長(zhǎng)過(guò)小,就會(huì)導(dǎo)致細(xì)菌到達(dá)優(yōu)質(zhì)點(diǎn)區(qū)域的趨化步數(shù)增加。此時(shí)收斂速度會(huì)降低,迭代步數(shù)較少可能使得細(xì)菌不能到達(dá)最優(yōu)位置。本文采用特殊的編碼和解碼方式,將細(xì)菌前、后兩步趨化坐標(biāo)Pi中每一維度之差視為前進(jìn)步長(zhǎng),因此前進(jìn)步長(zhǎng)必須為整數(shù)。所以本文改進(jìn)了文獻(xiàn)[11]中的趨向性步長(zhǎng)的計(jì)算方法,提出新的基于余弦規(guī)則的自適應(yīng)步長(zhǎng),其具有以下特點(diǎn):
(7)
式中:C(i)和Pi維度一致,C(i)是下取整函數(shù);Cimax為最小步長(zhǎng),Cimax為最大步長(zhǎng),則Cimin≤C(i)≤Cimax;gen為當(dāng)前迭代次數(shù),genm為最大迭代次數(shù)。
適應(yīng)度函數(shù)是考量個(gè)體在目標(biāo)問(wèn)題中適應(yīng)度的函數(shù),它對(duì)ABFOA效果起著至關(guān)重要的作用。ABFOA中使用適應(yīng)度這個(gè)概念來(lái)度量群體中每個(gè)細(xì)菌所代表裝箱方案的優(yōu)良程度。適應(yīng)度較高時(shí),代表細(xì)菌生命力越強(qiáng),即種群中的優(yōu)良細(xì)菌,利于存活和復(fù)制;而適應(yīng)度較低的細(xì)菌生命力弱,存活概率大大降低。根據(jù)2.1節(jié),ABFOA在求解CLP過(guò)程中主要考慮到容積率和承載效率,適應(yīng)度函數(shù)形式
(8)
式中:λ為集裝箱裝載容積率和承載效率的權(quán)衡因子,取值范圍為[0,1]。
從待裝集合Q中取出編號(hào)為qi的貨物,記錄該貨物標(biāo)記,為1表示可以裝入集裝箱中,無(wú)法裝入標(biāo)0:
(1)貨物裝入時(shí),集裝箱空間被分割為上、右、前子空間(如圖1所示),放置貨物的空間被標(biāo)記為已用,從空余空間隊(duì)列中刪除,空余空間隊(duì)列中為3個(gè)形狀為長(zhǎng)方體的新空間。
(2)直到第i個(gè)的貨物放置時(shí),發(fā)現(xiàn)最大的空間仍無(wú)法放入,則在貨物隊(duì)列中取i+1貨物進(jìn)行放置,直到可以放入空間內(nèi),重復(fù)(1)。
(3)當(dāng)空閑隊(duì)列中每一個(gè)子空間的體積都小于貨物隊(duì)列中體積最小的貨物時(shí),則程序停止,跳出。
自適應(yīng)細(xì)菌覓食優(yōu)化算法求解集裝箱貨物裝載問(wèn)題流程如下:
步驟1 對(duì)每種裝載貨物按照體積和重量由大到小原則排序并編號(hào),輸入每種貨物的參數(shù)li,wi,hi,mi。
步驟2 初始化權(quán)衡因子λ,ABFOA細(xì)菌規(guī)模S,細(xì)菌i的初始位置Pi,驅(qū)散次數(shù)lmax、復(fù)制次數(shù)kmax、趨化步
數(shù)jmax、特定方向上的游動(dòng)次數(shù)和長(zhǎng)度,方向概率PC,吸引劑數(shù)值dattract、排斥劑數(shù)值hrepellent、吸引劑釋放速度ωattract和排斥劑釋放速度ωrepellent,j=k=l=0。
步驟3 執(zhí)行驅(qū)散操作,l=l+1,若驅(qū)散次數(shù)l>lmax,則執(zhí)行步驟6。
步驟4 執(zhí)行復(fù)制操作,k=k+1,若復(fù)制次數(shù)k>kmax,則執(zhí)行步驟3。
步驟5 使用式(1)進(jìn)行趨化操作,j=j+1,更新并保存適應(yīng)度函數(shù)值。若趨化次數(shù)j>jmax,則執(zhí)行步驟4。
步驟6 選取具有最大適應(yīng)度函數(shù)值的細(xì)菌,對(duì)其對(duì)應(yīng)的編碼進(jìn)行解碼,輸出結(jié)果,結(jié)束。
實(shí)驗(yàn)中算例采用國(guó)際上通常使用的標(biāo)準(zhǔn)20尺貨柜,尺寸大小為232*92.5*94cm。實(shí)驗(yàn)比較了在相同集裝箱大小,對(duì)相同的貨物批次進(jìn)行裝載。待裝貨物種類20種,每種貨物各3-10件不等,貨物參數(shù)由某物流公司裝箱貨物尺寸中隨機(jī)抽取,如表2所示,其長(zhǎng)、深、高分別為li,wi,hi,單位為mm,質(zhì)量為m。
表2 待裝貨品參數(shù)
為評(píng)價(jià)算法的性能及優(yōu)越性,采用啟發(fā)式算法[4]、多目標(biāo)多種群的隨機(jī)遺傳算法[5]、混合二元蟻群算法[6]和本文中提出的文中提出的基于自適應(yīng)細(xì)菌覓食算法相比較。其中,文獻(xiàn)[4]中提出來(lái)包含樹型搜索子算法和貪心子算法的啟發(fā)式算法進(jìn)行空間布局,但是未考慮到裝載的約束條件;文獻(xiàn)[5]中提出了三維空間切割模型,但為考慮到重量,承載等約束條件;文獻(xiàn)[6]中提出了混合二元蟻群算法求解,先用二元蟻群算法確定預(yù)備裝入貨物集,再用啟發(fā)式算法決定裝入優(yōu)先級(jí)順序,雖大大提升裝載率,但算法復(fù)雜,時(shí)間復(fù)雜度較高。實(shí)驗(yàn)對(duì)3個(gè)不同的裝箱訂單進(jìn)行裝箱實(shí)驗(yàn)三維仿真,圖2~圖4為3次裝箱效果,表3為3次裝箱的平均計(jì)算結(jié)果,且各對(duì)比算法中的參數(shù)設(shè)置與原文一致。
裝箱訂單1中,每種貨物取20件,最后共裝入貨物190件,裝載率達(dá)到94.76%,結(jié)果如圖2所示。
圖2 訂單1三維裝箱結(jié)果
裝箱訂單2中,每種貨物隨機(jī)取1-30件不等,結(jié)果共裝入貨物105件,裝載率達(dá)到93.69%,結(jié)果如圖3所示。
圖3 訂單2三維裝箱結(jié)果
裝箱訂單3中,每種貨物隨機(jī)取1-10件不等,結(jié)果共裝入貨物68件,裝載率達(dá)到91.76%,結(jié)果如圖4所示。
實(shí)例表明,在細(xì)菌趨化過(guò)程中極大地降低了細(xì)菌游動(dòng)的復(fù)雜性,提升了算法性能,降低了時(shí)間復(fù)雜度,說(shuō)明該算法在解決此類三維空間復(fù)雜問(wèn)題上具有優(yōu)勢(shì)。與此同時(shí),自適應(yīng)步長(zhǎng)的設(shè)置,改善了傳統(tǒng)細(xì)菌覓食優(yōu)化算法行進(jìn)過(guò)程中易陷入局部極值的缺陷。在收斂時(shí)間上相較啟發(fā)式算法和蟻群算法也有優(yōu)勢(shì)。實(shí)驗(yàn)結(jié)果中的平均空間利用率為92.07%,和其它3種算法相比較,有了較明顯的提升。
圖4 訂單3三維裝箱結(jié)果
平均空間利用率/%算法平均收斂時(shí)間/s質(zhì)量/kg標(biāo)準(zhǔn)差啟發(fā)式算法90.2014.90163.550.170蟻群算法91.0915.68166.300.162遺傳算法92.1613.47173.260.168自適應(yīng)細(xì)菌覓食算法93.0713.53175.960.161
本文采用了基于順序表示的遺傳基因編碼方式,將動(dòng)態(tài)裝載問(wèn)題的各參數(shù)與及細(xì)菌覓食算法相結(jié)合,很好地規(guī)避了空間坐標(biāo)編碼的缺陷,在集裝箱這類復(fù)雜度較高的問(wèn)題上應(yīng)用結(jié)果良好。改變細(xì)菌覓食算法中的固定步長(zhǎng),采用改進(jìn)了的基于余弦的自適應(yīng)步長(zhǎng)算法,在前期步長(zhǎng)大,區(qū)域搜索速度快,后期步長(zhǎng)小利于局部尋優(yōu)。在考慮裝箱過(guò)程中的其它因素,本文對(duì)于更復(fù)雜的多種類和多約束條件,這也是后續(xù)研究的一個(gè)方向。
[1]Ramos AG,Oliveira JF,Gon?alves JF,et al.Dynamic stabi-lity metrics for the container loading problem[J].Transportation Research Part C:Emerging Technologies,2015,60(6):480-497.
[2]CHENG Zhongwen.Solving three dimension container loading problem based on space-dividing genetic algorithm[J].Microcomputer Information,2012,54(10):286-287(in Chinese).[程中文.基于空間分割的遺傳算法解決三維裝載問(wèn)題[J].微計(jì)算機(jī)信息,2012,54(10):286-287.]
[3]Liu S,Tan W,Xu Z,et al.A tree search algorithm for the container loading problem[J].Computers & Industrial Engineering,2014,75(2):20-30.
[4]Sheng L,Hongxia Z,Xisong D,et al.A heuristic algorithm for container loading of pallets with infill boxes[J].European Journal of Operational Research,2016,252(3):728-736.
[5]Zheng JN,Chien CF,Gen M.Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem[J].Computers & Industrial Engineering,2015,89(9):80-87.
[6]DU Lining,ZHANG Dezhen,CHEN Shifeng.Solution to complex container loading problem based on ant colony algorithm[J].Journal of Computer Application,2011,31(8):2275-2278(in Chinese).[杜立寧,張德珍,陳世峰.蟻群算法求解復(fù)雜集裝箱裝載問(wèn)題[J].計(jì)算機(jī)應(yīng)用,2011,31(8):2275-2278.]
[7]Peng J,El-Latif AAA,Li Q,et al.Multimodal biometric authentication based on score level fusion of finger biometrics[J].Optik-International Journal for Light and Electron Optics,2014,125(23):6891-6897.
[8]Reddy CHV,Siddaiah P.Bacterial foraging optimization algorithm(BFOA) optimized adaptive hybrid DWT-SVD watermarking with encryption[J].International Journal of Applied Engineering Research,2014,9(24):30911-30933.
[9]Huang YH,Hwang FJ,Lu HC.An effective placement method for the single container loading problem[J].Compu-ters & Industrial Engineering,2016,97(5):212-221.
[10]ZUO Xianliang,GUO Lili,GAO Shang.Improved estimation of distribution algorithm for solving multi-constrained container loading problem[J].Science Technology and Enginee-ring,2014,14(11):216-220(in Chinese).[左先亮,郭莉莉,高尚.改進(jìn)分布估計(jì)算法解決多約束集裝箱裝載問(wèn)題[J].科學(xué)技術(shù)與工程,2014,14(11):216-220.]
[11]LIU Zhen,SUN Jinghao.An improved bacterial foraging optimization algorithm[J].Journal of East China University of Science and Technology(Natural Science Edition),2016,42(2):225-232(in Chinese).[劉珍,孫京誥.一種改進(jìn)的細(xì)菌覓食優(yōu)化算法[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,42(2):225-232.]