林云鵬，宋 爽，江志斌，張大力

(上海交通大學(xué) 1.機(jī)械與動(dòng)力工程學(xué)院，上海 200240；2.中美物流研究院，上海 200030；3.安泰經(jīng)濟(jì)與管理學(xué)院，上海 200030)

裝箱問題是一種具有復(fù)雜約束條件的離散組合優(yōu)化問題，具有很強(qiáng)的應(yīng)用背景。到目前為止，有大量關(guān)于裝箱問題的研究，并有很多文獻(xiàn)對(duì)此進(jìn)行解決方法闡述。這些裝箱算法大部分都是關(guān)于品類少、單項(xiàng)數(shù)量多、弱異構(gòu)性的裝箱問題。隨著電子商務(wù)應(yīng)用與供給需求不斷改善發(fā)展，個(gè)性化程度高的電商領(lǐng)域裝箱訂單越來越多，強(qiáng)異構(gòu)性裝箱問題成為其中重要部分，對(duì)傳統(tǒng)的裝箱算法提出新的要求。本文的研究對(duì)象為電商領(lǐng)域中的多箱型三維裝箱問題 (three-dimensional multiple bin-size bin packing problem, 3D-MBSBPP)。

近些年來，3D-MBSBPP已經(jīng)有了一定的研究，主要集中在結(jié)構(gòu)假定方式和啟發(fā)式算法的優(yōu)化上。在結(jié)構(gòu)假定方式優(yōu)化方面，大致可分為關(guān)鍵點(diǎn)法[1]、分層法[2]以及空間分割法[3]，主要關(guān)注如何確定物品在箱子內(nèi)的可擺放位置以及有多個(gè)可擺放位置時(shí)如何進(jìn)行選擇。在啟發(fā)式算法優(yōu)化方面，大量學(xué)者從不同方面進(jìn)行深入研究。Eley[4]首次提出集合覆蓋模型，以模型的每一列對(duì)應(yīng)一種裝箱方案，并提出相應(yīng)的基于樹搜索啟發(fā)式算法的列生成算法。隨著該模型的提出，各種列生成算法不斷涌現(xiàn)，其中啟發(fā)式算法為首選。例如，Sulaiman等[5]提出一種基于隨機(jī)交叉和動(dòng)態(tài)變異的遺傳算法，以克服早熟收斂。Fu等[6]基于優(yōu)先級(jí)隊(duì)列分支的思想和約束方法，提出一種分支定界算法。Dell'Amico等[7]在研究了多項(xiàng)式大小公式、指數(shù)大小公式以及若干下界上界的基礎(chǔ)上，提出一種求解指數(shù)型公式的分支價(jià)格算法。Li等[8]提出一種基于差分進(jìn)化算子的入侵雜草優(yōu)化算法。Fan等[9]根據(jù)算法編碼的特點(diǎn)，設(shè)計(jì)一種替換插入的方法并更新了交叉算子，從而提出一種改進(jìn)的分組遺傳算法。此外，國(guó)內(nèi)學(xué)者在啟發(fā)式算法優(yōu)化方面也取得很好的結(jié)果，如在遺傳算法[10]、模擬退火算法[11]、蟻群算法[12]等方面。

以上這些算法都假定裝填結(jié)果滿足一定的結(jié)構(gòu)，雖然簡(jiǎn)化了裝填過程，但造成搜索解空間變小，從而導(dǎo)致解的質(zhì)量不高。而且，電商物流訂單具有高度個(gè)性化特點(diǎn)，主要體現(xiàn)在由于電商訂單均為客戶定制訂單，訂單個(gè)體呈現(xiàn)出各品類間物品數(shù)量波動(dòng)大的特點(diǎn)。因此，傳統(tǒng)裝箱問題的結(jié)構(gòu)假定方式，如砌墻、建堆、立方體排列、切割等，不適用于電商物流。同時(shí)，大規(guī)模鄰域搜索算法是作為一種高效尋優(yōu)算法，既能保持大規(guī)模鄰域的尋優(yōu)能力，又能克服低效耗時(shí)的弱點(diǎn)，如在TSP問題研究中，賈瑞玉等[13]就通過引入大規(guī)模鄰域搜索算法優(yōu)化傳統(tǒng)啟發(fā)式算法的搜索路徑并取得良好效果。而在三維裝箱問題中，由于大規(guī)模鄰域搜索算法的關(guān)鍵元素較難選擇，該算法之前并未用于裝箱算法的搜索路徑優(yōu)化。因此，為了適用新的問題背景、改進(jìn)解的質(zhì)量，本文一方面提出新的假定結(jié)構(gòu)方式，通過采用空間矩陣表征方式和新型算法編碼控制裝箱過程；另一方面提出三維裝箱問題中大規(guī)模鄰域搜索的關(guān)鍵元素選取方式，并以此優(yōu)化傳統(tǒng)啟發(fā)式算法對(duì)裝箱方案的搜索過程，避免陷入局部最優(yōu)，從而快速有效地解決電商物流領(lǐng)域的3D-MBSBPP。

1 問題描述及數(shù)學(xué)建模

本節(jié)對(duì)本文研究的3D-MBSBPP進(jìn)行數(shù)學(xué)描述，并結(jié)合實(shí)際背景，對(duì)目標(biāo)和約束進(jìn)行介紹。

1.1 問題背景

多箱型三維裝箱問題是指有多種不同的箱型，每種箱型有一個(gè)尺寸和成本，每種箱型的箱子可使用數(shù)量無限制，求能將給定三維物品集合內(nèi)的所有物品全部裝下且不存在物品空間重疊或超出箱子范圍的總成本最小的箱子使用方案。而在本文研究的電商領(lǐng)域中，隨著客戶對(duì)便捷性需求的提高和企業(yè)對(duì)客戶滿意度的關(guān)注，單箱裝載(將單個(gè)客戶訂單中所有物品裝載至單個(gè)箱子中)逐漸成為物流企業(yè)在裝箱中非常關(guān)注的一點(diǎn)。因此，本文所研究的問題，是一種以單箱裝載為目標(biāo)的3D-MBSBPP，具體是指基于客戶訂單和給定的多種可選箱型，確定一種箱型及其相應(yīng)裝箱方案，在盡可能單箱裝載客戶訂單所有物品的基礎(chǔ)上實(shí)現(xiàn)裝載率最大；若出現(xiàn)無法單箱裝載情況，則等效為多個(gè)在單箱裝載更多物品的基礎(chǔ)上實(shí)現(xiàn)裝載率最大的多箱型三維裝箱問題復(fù)合，其本質(zhì)上與前文所述的在盡可能單箱裝載所有物品的基礎(chǔ)上實(shí)現(xiàn)裝載率最大的要求相同，因此對(duì)于該情況本文不作過多贅述。

1.2 模型建立

1.2.1 相關(guān)參數(shù)

假設(shè)有N種給定的可選箱型，以有序集合(按箱子體積升序)B={b1,b2,···,bN}表示，某客戶訂單中有n個(gè)待裝載物品，以有序集合(按物品體積降序)集合T={t1,t2,···,tn}表 示。其中，箱子bI的長(zhǎng)LI、寬WI、高HI；物 品ti的 長(zhǎng)li、寬wi、高h(yuǎn)i， 且LI≥WI≥HI，lI≥wI≥hI。I為被選箱型的編號(hào)，I=1,2,···,N，i=1,2,···,n。同時(shí)，由于物品無擺放朝向約束，物品ti在X、Y、Z軸上長(zhǎng)度與長(zhǎng)li、寬wi、高h(yuǎn)i的對(duì)應(yīng)關(guān)系會(huì)因其不同朝向而變化，因此，定義lXi、lYi、lZi分別表示其沿X、Y、Z軸上長(zhǎng)度。

問題目標(biāo)是在滿足給定裝載約束的條件下，確定最優(yōu)箱型及其相應(yīng)的最優(yōu)裝箱方案。其中，最優(yōu)箱型編號(hào)記為I*；最優(yōu)裝箱方案記為P*。因此，本文數(shù)學(xué)模型的決策變量為選用箱型編號(hào)I和對(duì)應(yīng)裝箱方案P。

1.2.2 目標(biāo)函數(shù)

由問題背景和求解目標(biāo)可得本文所研究問題為多重優(yōu)化問題，其中多重優(yōu)化如下。

第1重優(yōu)化 (所裝物品數(shù)量最多)。

由于第1重優(yōu)化為主優(yōu)化目標(biāo)，上述兩重優(yōu)化目標(biāo)函數(shù)可整合為單目標(biāo)權(quán)重優(yōu)化函數(shù)。

1.2.3 數(shù)學(xué)模型

本文可行裝箱方案必須滿足如下兩個(gè)條件：1) 任一裝載的物品不能與其他裝載物品或者箱子互相重疊；2) 所有裝載的物品以與箱子平行的方式裝載。

根據(jù)上述裝箱約束條件和目標(biāo)函數(shù)，建立如下數(shù)學(xué)模型。

上述約束中，式(1)為目標(biāo)函數(shù)，目標(biāo)為裝載物品數(shù)量最多的基礎(chǔ)上裝載率最大；式(2)表示箱子最大容積約束；式(3) ～ (5)表示每個(gè)物品平行或正交裝載于箱子內(nèi)，由于當(dāng)且僅當(dāng)式(6)中6個(gè)符號(hào)函數(shù)之和為6時(shí)，物品ti近原點(diǎn)坐標(biāo) (xi,yi,zi)被另一物品包含；同理，式(7)是對(duì)物品ti遠(yuǎn)原點(diǎn)坐標(biāo)的約束，因此兩式共同表示物品間不互相重疊；式(8) ～ (9)表示物品裝載于箱子內(nèi)。

2 算法設(shè)計(jì)

本文針對(duì)上述問題和數(shù)學(xué)模型，提出一種基于空間矩陣的大規(guī)模鄰域搜索裝箱算法，以便快速有效地求解問題。

在之前的三維裝箱問題研究中，相關(guān)算法大多由基于結(jié)構(gòu)假定方式的裝箱檢驗(yàn)算法和基于啟發(fā)式規(guī)則的裝箱方案路徑搜索算法組成，并通過編碼譯碼規(guī)則實(shí)現(xiàn)前者所得的解空間轉(zhuǎn)化成后者所能處理的搜索空間。而本文則對(duì)上述算法進(jìn)行創(chuàng)新，提出一種新的結(jié)構(gòu)假定方式空間矩陣表征方式用于快速裝箱檢驗(yàn)，并提出基于物品朝向的編碼譯碼規(guī)則以控制算法的迭代次數(shù)，最后通過定義關(guān)鍵元素選取方式，首次引入大規(guī)模鄰域搜索算法以優(yōu)化傳統(tǒng)啟發(fā)式算法對(duì)裝箱序列的路徑搜索過程。

2.1 空間矩陣表征方式

由于電商領(lǐng)域裝箱訂單具有個(gè)性化程度高特點(diǎn)，傳統(tǒng)的結(jié)構(gòu)假定方式不適用于電商問題背景；且由于三維裝箱在空間布局中，干涉計(jì)算量較多，簡(jiǎn)單的坐標(biāo)表示不利于問題求解。因此，本文首先提出空間矩陣表征方式用于裝箱問題中的結(jié)構(gòu)假定。Ngoi等[14]在夾具設(shè)計(jì)應(yīng)用中提出一種基于可變正交單元的細(xì)胞分解、實(shí)體模型表征方式，本文則在其基礎(chǔ)上提出應(yīng)用于三維裝箱問題中的空間矩陣表征方式，從而快速更新箱內(nèi)空間使用情況，查找可用空間，便于裝箱檢驗(yàn)的模擬進(jìn)行。空間矩陣外框架如圖1所示。

圖1 空間矩陣外框架Figure 1 Spatial matrix's outer frame

2.1.1 相關(guān)介紹

空間矩陣將根據(jù)內(nèi)部物品裝箱情況分解成多個(gè)二維矩陣，每個(gè)二維矩陣表示某個(gè)高度范圍內(nèi)的箱內(nèi)空間占用情況，具體表征方式如下。同時(shí)，由于空間矩陣中可用空間可視為由多個(gè)長(zhǎng)方體組成，因此采用同上文物品ti空間信息一樣的表述方式描述可用空間位置。

步驟1 構(gòu)建當(dāng)前空間矩陣外框架。

1) 整理匯總X、Y、Z軸參考量。根據(jù)所選箱子bI及其當(dāng)前已裝載物品ti， 將LI及各物品的xi、xi+lXi匯 總成X軸參考量，將WI及各物品的yi、yi+lYi匯總成Y軸參考量，將HI及各物品的zi、zi+lZi匯總成Z軸參考量。

3) 根據(jù)X、Y、Z軸參考量生成如圖1所示空間矩陣外框架，并填充0表示空間均無占用。

步驟2 確定每一層平面矩陣所包含物品。

1)Z軸參考量分別對(duì)應(yīng)各層平面矩陣層高。

2) 物品ti如滿足條件zi＜ZM≤zi+lZi，則其被第M層平面矩陣包含。

步驟3 填充各層平面矩陣以表示空間占用情況。

1) 根據(jù)每層矩陣所包含的相應(yīng)物品ti，確定其在相應(yīng)平面矩陣的行起點(diǎn)、列起點(diǎn)、行終點(diǎn)、列終點(diǎn)，并填充1表示空間被占用。

2) 確定行起點(diǎn)，若xi=Xr,Xr∈X′，則其行起點(diǎn)為第r+ 1行；確定列起點(diǎn)，若yi=Yr,Yr∈Y′，則其列起點(diǎn)為第r+ 1列。

3) 確定行終點(diǎn)，若xi+lXi=Xs,Xs∈X′，則其行終點(diǎn)為第s行；確定列終點(diǎn)，若yi+lYi=Ys,Ys∈Y′，則其行終點(diǎn)為第s列。

步驟4 尋找空間矩陣內(nèi)可用空間。

1) 記空間矩陣第x行 、第y列、第z層元素為Fxyz， 其中，x=1,···,x′；y=1,···,y′；z=1,...,z′。

2) ?x∈{1,···,x′}，y∈{1,···,y′}，z∈{1,···,z′}，若Fxyz=0， 則有單位長(zhǎng)方體子空間(Xx-1,Yy-1,Zz-1,Xx,Yy,Zz)， 并記為sxyz。

3) 匯總可用單位長(zhǎng)方體子空間，并基于預(yù)設(shè)規(guī)則將其合并為若干個(gè)較大的長(zhǎng)方體子空間，組成可用空間集合S，其所含元素表示為S[p]，p表示裝箱檢驗(yàn)時(shí)，該子空間在集合中被選擇的順序，并定義其長(zhǎng)寬高S[p]l≥S[p]w≥S[p]z，在X、Y、Z軸上長(zhǎng)度S[p]X、S[p]Y、S[p]Z。裝箱檢驗(yàn)中，物品將按照集合中的順序與可用空間逐一進(jìn)行檢驗(yàn)。

2.1.2 使用示例

空間矩陣表征方式運(yùn)用示例如下。當(dāng)前空間矩陣內(nèi)裝箱情況如圖2所示。已知X′={0,20,30,50}，Y′={0,10,20,40}，Z′={0,5,10,30}。構(gòu)建空間矩陣外框架，并填充各層平面矩陣空間占用情況，得空間矩陣如圖3所示。

圖2 三維裝箱示例Figure 2 3D packing example

圖3 空間矩陣示例Figure 3 Space matrix example

2.2 算法優(yōu)化設(shè)計(jì)

2.2.1 編碼規(guī)則

啟發(fā)式算法在三維裝箱問題中運(yùn)用成功的關(guān)鍵在于通過編碼規(guī)則將問題的可行解從其解空間轉(zhuǎn)化到算法能處理的搜索空間[15]。在之前的三維裝箱問題研究中，大多以有序物品集合作為編碼方式，實(shí)現(xiàn)啟發(fā)式算法的搜索空間和裝箱方案可行解空間的相互轉(zhuǎn)化。而本文為簡(jiǎn)化模型，便于搜索，提出一種新的算法編碼，以有朝向約束的物品(簡(jiǎn)稱物品(朝向))作為搜索空間，以有序的物品(朝向)集合作為可行解。

由于物品ti的可旋轉(zhuǎn)性，lXi、lYi、lZi會(huì)因擺放朝向的變化而改變。根據(jù)物品需平行或正交裝載于箱子內(nèi)的約束條件，物品有6種擺放朝向，故lXi、lYi、lZi也有6種組合。因此，基于物品集合T={t1,t2,···,tn}建立集合T′={1,2,···,6n}，其中，T′的元素表示物品(朝向)，ti的6種朝向分別對(duì)應(yīng)集合T′中的 6i-5至 6i，從而避免在后續(xù)算法中考慮物品的可旋轉(zhuǎn)性。同時(shí)，構(gòu)造函數(shù)i(t′)=(t′-1)//6+1，其中，//為整除符號(hào)；t′∈T′，i(t′)表 示物品(朝向)編號(hào)t′對(duì)應(yīng)的物品編號(hào)。并定義物品每種擺放朝向下X、Y、Z軸上長(zhǎng)度與長(zhǎng)寬高的對(duì)應(yīng)關(guān)系，如式(10)所示，其中，%為取余符號(hào)。

預(yù)設(shè)裝箱序列Q是一個(gè)過渡量，既是裝箱方案路徑搜索算法的輸出量，也是裝箱檢驗(yàn)算法的輸入量，表示算法根據(jù)啟發(fā)式規(guī)則路徑搜索出的未經(jīng)過實(shí)際檢驗(yàn)的預(yù)設(shè)裝箱方案。Q為一個(gè)包含n個(gè)元素的有序集合，其第k個(gè)元素表示為Q[k]，表示在后續(xù)裝箱檢驗(yàn)的第k階段被檢驗(yàn)?zāi)芊裱b入箱子的物品(朝向)編號(hào)。為避免迭代次數(shù)超過裝箱序列長(zhǎng)度，預(yù)設(shè)序列Q基于上述規(guī)則進(jìn)行編碼，Q[k]∈t，從而通過避免在裝箱過程中考慮物品旋轉(zhuǎn)性以控制迭代次數(shù)，其中裝箱檢驗(yàn)由裝箱算法實(shí)現(xiàn)。

2.2.2 譯碼規(guī)則

在裝箱方案路徑搜索算法中，編碼規(guī)則實(shí)現(xiàn)了問題的可行解從其解空間到算法能處理的搜索空間的轉(zhuǎn)化，從而得出基于啟發(fā)式規(guī)則搜索出的預(yù)設(shè)裝箱序列Q。而在裝箱檢驗(yàn)算法中，則需要通過譯碼規(guī)則將Q轉(zhuǎn)化成空間矩陣可以模擬裝載的各物品裝箱順序和朝向信息。

譯碼規(guī)則如式(11)所示，首先將Q[k]譯碼成物品ti(Q[k])的lXi(Q[k])、lYi(Q[k])、lZi(Q[k])信息，再和當(dāng)前空間矩陣Space的 可用空間 SUB進(jìn) 行裝箱檢驗(yàn)，并生成ti(Q[k])的xi(Q[k])、yi(Q[k])、zi(Q[k])信息，從而實(shí)現(xiàn)從預(yù)設(shè)裝箱序列Q到各物品實(shí)際空間信息的轉(zhuǎn)換。

Q中各元素逐一譯碼并裝箱檢驗(yàn)后，求得該預(yù)設(shè)序列所對(duì)應(yīng)的各物品空間信息。為便于后續(xù)啟發(fā)式算法對(duì)裝箱方案的迭代優(yōu)化，對(duì)上述各物品空間信息再逐一編碼生成實(shí)際裝箱方案P。P是與Q對(duì)應(yīng)的包含n個(gè)元素的有序集合，表示一種可行的裝箱方案，其第k個(gè)元素表示為P[k]。P[k]為實(shí)際裝箱的第k階段中，實(shí)際裝入箱子的物品(朝向)編號(hào)，其值可能會(huì)因?yàn)檠b箱檢驗(yàn)的調(diào)整與Q[k]不一致。

2.2.3 大規(guī)模鄰域搜索算法優(yōu)化設(shè)計(jì)

本文在傳統(tǒng)啟發(fā)式算法搜索裝箱方案的過程中，通過對(duì)關(guān)鍵元素選取和相關(guān)度函數(shù)定義，引入大規(guī)模鄰域搜索算法。

1) 大規(guī)模鄰域搜索算法關(guān)鍵元素選取和相關(guān)度函數(shù)定義。

分析目標(biāo)函數(shù) m axU(I,P)=A+E，其中，E∈[0,1]，故A的取值即箱子所裝物品數(shù)對(duì)目標(biāo)函數(shù)值起關(guān)鍵影響。因此，P中無法成功裝箱的元素即為關(guān)鍵元素，關(guān)鍵元素集合表示為R={P[k]|P[k]＜0,P[k]∈P}，其第d個(gè)元素記為R[d]，R中元素?cái)?shù)量記為D。

2) 相關(guān)度函數(shù)定義。

2.3 算法流程描述

2.3.1 子算法裝箱檢驗(yàn)算法

步驟1 初始化k=1， 輸入預(yù)設(shè)裝箱方案Q和被選箱型I。

步驟2 根據(jù)所選箱子bI構(gòu)建空間矩陣。

步驟3 根據(jù)當(dāng)前所裝物品信息及空間矩陣表征方式規(guī)則，更新空間矩陣及其可用空間集合S。

步 驟4 將Q[k]解 碼 成 物 品ti(Q[k])的lXi(Q[k])、lYi(Q[k])、lZi(Q[k])， 并將其解碼信息與S進(jìn)行裝箱檢驗(yàn)，根據(jù)檢驗(yàn)情況調(diào)整Q[k]生 成相應(yīng)P[k]， 并確定ti(Q[k])的xi(Q[k])、yi(Q[k])、zi(Q[k])。

1) 初始化p=1， 當(dāng)前S中所含子空間元素?cái)?shù)量為s。

2) 根據(jù)物品ti(Q[k])的 尺寸信息，若S[p]l≥li(Q[k])、S[p]w≥wi(Q[k])、S[p]h≥hi(Q[k])， 則ti(Q[k])可裝載于可用空間S[p]中 ，否則p=p+1，跳至4)。

3) 根據(jù)物品ti(Q[k])的朝向信息，若物品可直接裝箱，則P[k]=Q[k]， 若物品旋轉(zhuǎn)后可裝箱，則P[k]∈{6i(Q[k])-5,6i(Q[k])-4,···,6i(Q[k])}。步驟4結(jié)束。

4) 若p≤s，返回2)。

5) 物品ti(Q[k])始 終無法裝箱，P[k]=-Q[k]，負(fù)值表示物品ti(Q[k])在 方案P中無法裝箱。步驟4結(jié)束。

步驟5 如果k＜n，n為待裝載物品數(shù)量，即未完成所有物品裝箱檢驗(yàn)，k=k+1，返回步驟3。

步驟6 根據(jù)空間矩陣表征方式規(guī)則，獲得空間矩陣當(dāng)前所裝物品信息，并輸出實(shí)際裝箱方案P和目標(biāo)函數(shù)值U(I,P)，算法結(jié)束。

2.3.2 基于三維矩陣的大規(guī)模鄰域搜索算法

步驟1 確定最小可用箱型編號(hào)I。

步驟2 啟發(fā)式算法初始化，啟發(fā)式迭代次數(shù)m=0。

步驟3 根據(jù)蟻群算法信息素濃度規(guī)則生成e種預(yù)設(shè)裝箱序列{Q1,Q2,···,Qe}。

步驟4 根據(jù)輸入被選箱型I和預(yù)設(shè)裝箱序列{Q1,Q2,···,Qe}，調(diào)用裝箱檢驗(yàn)算法輸出實(shí)際裝箱方案{P1,P2,···,Pe} 和 目標(biāo)函數(shù)值 {U1,U2,···,Ue}，并確定該次迭代最優(yōu)目標(biāo)函數(shù)值U*。

U*=max{U1,U2,···,Ue}。

步驟5 由于最優(yōu)裝箱方案可能并不唯一，根據(jù)U*生 成最優(yōu)裝箱方案集合Pˉ*和其對(duì)應(yīng)目標(biāo)函數(shù)值集合Uˉ*，Pˉ*[j]、Uˉ*[j]分 別表示其第j個(gè)元素，J為其所含元素?cái)?shù)量。如果U*＞n，則完成單箱裝載所有物品，算法結(jié)束。

1) 初始化p=1，j=1。

2) 若Up=U*， 則Pˉ*[j]=Pp，Uˉ*[j]=U*。

3) 若p＜e， 則p=p+1，返回2)，否則，確定集合Pˉ*和Uˉ*。

4) 如 果U*＞n， 則I*=I，P*∈Pˉ*， 輸出I*和P*，算法結(jié)束，否則步驟5結(jié)束，算法繼續(xù)。

步驟6 通過大規(guī)模鄰域搜索算法優(yōu)化集合Pˉ*和相應(yīng)目標(biāo)函數(shù)值集合Uˉ*。

1) 初始化j=1。

2) 通過大規(guī)模鄰域搜索算法優(yōu)化裝箱方案Pˉ*[j]，并初始化大規(guī)模鄰域搜索迭代次數(shù)r=0。

3) 根據(jù)前文所述關(guān)鍵元素選取規(guī)則和相關(guān)度函數(shù)定義，確定并選取Pˉ*[j]中若干關(guān)鍵元素并計(jì)算各關(guān)鍵元素相關(guān)度，并保留部分相關(guān)度較高元素生成關(guān)鍵元素集合R。根據(jù)R中所保留關(guān)鍵元素，Pˉ*[j]中相應(yīng)元素依次與非關(guān)鍵元素隨機(jī)置換重組。如果U(I,Pˉ*[j])＞Uˉ*[j]， 則更新優(yōu)化Pˉ*[j]、Uˉ*[j]，并轉(zhuǎn)至4)，否則，Pˉ*[j]保持不變，跳至5)。

4) 如 果Uˉ*[j]＞n， 則I*=I，P*=Pˉ*[j]，輸 出I*和P*，算法結(jié)束，否則，算法繼續(xù)。

5) 如果r超過給定值或多次迭代沒有新的Uˉ*[j]產(chǎn)生，則當(dāng)前裝箱方案無大規(guī)模鄰域搜索算法優(yōu)化可能，轉(zhuǎn)至6)，否則，返回3)，r=r+1。

6) 若j＜J，則j=j+1，返回2)，否則，更新最優(yōu)目標(biāo)函數(shù)值U*=maxUˉ*及其對(duì)應(yīng)最優(yōu)裝箱方案Pˉ*，步驟6結(jié)束。

步驟7 根據(jù)啟發(fā)式規(guī)則，強(qiáng)化最優(yōu)裝箱方案集合Pˉ*對(duì)應(yīng)路徑信息素濃度。

步驟8 如果m超過給定值或多次迭代沒有新的U*產(chǎn)生，則當(dāng)前箱型限制下無更優(yōu)方案，否則，返回步驟2，m=m+1。

步驟9 如果I＞N，無更大箱型可以選擇，則I*=I，輸出I*和P*，算法結(jié)束，否則，返回步驟2，I=I+1。

3 數(shù)值實(shí)驗(yàn)

本文的組合啟發(fā)式算法以Python實(shí)現(xiàn)，程序試驗(yàn)運(yùn)行在Intel Core i7-8750H 2.20 GHZ的處理器上。本文針對(duì)電商領(lǐng)域所提出的組合啟發(fā)式算法，在電商領(lǐng)域3D-MBSBPP中具有良好表現(xiàn)。在實(shí)驗(yàn)中，為便于檢驗(yàn)算法性能，本文組合啟發(fā)算法的路徑搜索算法部分?jǐn)M采用蟻群算法作為大規(guī)模鄰域搜索算法的優(yōu)化對(duì)象，同時(shí)將基于電商領(lǐng)域物流裝箱訂單數(shù)據(jù)，與之前學(xué)者所提出的三維裝箱算法、當(dāng)前電商物流企業(yè)常用裝箱軟件進(jìn)行性能比較。

3.1 算例說明

實(shí)驗(yàn)采用的標(biāo)準(zhǔn)算例集來自電商物流企業(yè)，共計(jì)49 591個(gè)客戶訂單和17種可選箱型，每個(gè)訂單均可看作有17種箱型可選的3D-MBSBPP算例。此外，由于每個(gè)訂單所含物品總體積小于最大箱型體積，且問題背景以單箱裝載盡可能多物品為目標(biāo)，因此裝箱問題將以訂單所含物品全部單箱裝載成功作為達(dá)標(biāo)情況并統(tǒng)計(jì)，從而簡(jiǎn)單直觀地比較算法性能。

訂單來自于電商物流企業(yè)實(shí)際訂單，訂單樣本具有高度個(gè)性化特點(diǎn)，訂單間品類數(shù)量波動(dòng)大，訂單所含品類最多達(dá)44種，所含物品數(shù)量最多達(dá)208個(gè)，品類數(shù)量概率分布如圖4所示，物品數(shù)量概率分布如圖5所示。箱型選擇較多、長(zhǎng)寬高比例特點(diǎn)明顯，詳細(xì)情況如表1所示。

表1 箱型詳細(xì)數(shù)據(jù)Table 1 Box type details

同時(shí)，為了便于比較本文算法和同類型裝箱算法、商用軟件在求解不同復(fù)雜程度的多箱型三維裝箱問題時(shí)的性能，基于圖4和圖5，將算例集按照品類數(shù)量分成7組，詳細(xì)情況如表2所示，按照物品數(shù)量分成9組，詳細(xì)情況如表3所示。

表2 標(biāo)準(zhǔn)算例集(按品類數(shù)量分組)Table 2 Standard example set (group by category quantity)

表3 標(biāo)準(zhǔn)算例集(按物品數(shù)量分組)Table 3 Standard example set (group by item quantity)

圖4 訂單品類數(shù)量概率分布Figure 4 Category quantity probability distribution of order

圖5 訂單物品數(shù)量概率分布Figure 5 Items quantity probability distribution of orders

此外，在上述的標(biāo)準(zhǔn)算例集中，雖然算例數(shù)量龐大，特點(diǎn)明顯，但是其僅能實(shí)現(xiàn)本文算法和同類型裝箱算法、商用軟件的性能比較，無法實(shí)現(xiàn)和精確解的比較。因此，本文根據(jù)該電商物流企業(yè)的實(shí)際檢驗(yàn)反饋，從49 591個(gè)標(biāo)準(zhǔn)算例中，遴選出其中58個(gè)算例作為特殊算例。這58個(gè)特殊算例雖然相較標(biāo)準(zhǔn)算例集，數(shù)量較少，但是經(jīng)由人工裝箱檢驗(yàn)后理論精確解為100%(即所有裝箱訂單均可實(shí)現(xiàn)單箱全部裝載)，且當(dāng)前該企業(yè)所有商用裝箱軟件均無法對(duì)其實(shí)現(xiàn)單箱全部裝載，具有較大的比較價(jià)值。

3.2 比較實(shí)驗(yàn)

首先將基于前文分組后的標(biāo)準(zhǔn)算例集，分別進(jìn)行本文算法和其他學(xué)者之前所提出的裝箱算法、裝箱軟件的比較實(shí)驗(yàn)和結(jié)果分析，從而充分檢驗(yàn)本文算法在求解不同品類數(shù)量復(fù)雜程度的3D-MBSBPP時(shí)的性能，比較結(jié)果如表4、表5所示。

表4 與其他算法的結(jié)果比較(標(biāo)準(zhǔn)算例集)Table 4 Results compared with other algorithms (standard example set)

表5 與商用軟件的達(dá)標(biāo)率比較(標(biāo)準(zhǔn)算例集)Table 5 Compliance rate compared with commercial softwares(standard example set) %

根據(jù)比較結(jié)果，在達(dá)標(biāo)率方面，本文算法求解電商物流領(lǐng)域裝箱問題時(shí)的性能優(yōu)于其他算法和裝箱軟件，而且隨著裝箱問題復(fù)雜程度的提升，性能優(yōu)勢(shì)越發(fā)明顯。此外，在求解速度方面，雖然本文算法慢于部分算法，但是同樣隨著裝箱問題復(fù)雜程度的提升，求解速度的差距也在逐漸縮小。因此，本文算法相比之前針對(duì)弱異構(gòu)性問題設(shè)計(jì)的算法、軟件，能更好地滿足高度個(gè)性化的電商物流鄰域訂單中強(qiáng)異構(gòu)性和弱異構(gòu)性兼有的要求。

最后，將基于特殊算例集對(duì)本文算法和其他裝箱算法進(jìn)行進(jìn)一步性能比較，比較結(jié)果如表6所示。根據(jù)比較結(jié)果，本文算法達(dá)標(biāo)率明顯超過其他算法，充分體現(xiàn)出其性能的優(yōu)越。而且，在求解商用軟件無法解決而實(shí)際可解的裝箱問題時(shí)，本文算法的達(dá)標(biāo)率非常接近理論精確解100%，進(jìn)一步證明本文算法對(duì)電商物流領(lǐng)域3D-MBSBPP的求解非常接近理論最優(yōu)解。

表6 與其他算法的結(jié)果比較(特殊算例集)Table 6 Results compared with other algorithms(special example set)

4 結(jié)論

本文提出一種針對(duì)個(gè)性化程度高的電商領(lǐng)域3D-MBSBPP的組合啟發(fā)式算法。首先，根據(jù)電商物流背景建立數(shù)學(xué)模型；其次，以物品(朝向)作為算法搜索空間，建立編碼譯碼規(guī)則及預(yù)設(shè)裝箱序列、實(shí)際裝箱方案等數(shù)據(jù)結(jié)構(gòu)，并提出基于空間矩陣表征方式的裝箱檢驗(yàn)算法，快速實(shí)現(xiàn)從預(yù)設(shè)序列到實(shí)際方案的轉(zhuǎn)換；最后，提出一種大規(guī)模鄰域搜索算法，用于優(yōu)化3D-MBSBPP中啟發(fā)式算法的路徑搜索過程。實(shí)驗(yàn)測(cè)試表明，本文所提出的組合啟發(fā)式算法在求解電商物流3D-MBSBPP中，精度超過傳統(tǒng)三維裝箱算法，且運(yùn)算速度較為理想。但是，本文所涉及的三維裝箱問題約束較少，且大規(guī)模鄰域搜索算法的重構(gòu)規(guī)則較為簡(jiǎn)單，還需要進(jìn)一步的調(diào)試參數(shù)、優(yōu)化算法。