基于聚類和網(wǎng)格覆蓋的三維裝箱算法

李少港 張宇輝 魏文紅

(東莞理工學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523808)

2021年10月，習(xí)近平總書記在第二屆聯(lián)合國全球可持續(xù)交通大會上強(qiáng)調(diào)要大力發(fā)展智慧交通和智慧物流，使人享其行、物享其流。裝箱作為物流中的重要環(huán)節(jié)，研究高效的裝箱算法有助于降低物流成本。20世紀(jì)60年代以來[1-2]，裝箱問題一直為廣大學(xué)者所關(guān)注。從最開始的一維、二維擴(kuò)展到三維，問題的復(fù)雜度越來越高，需要考慮的影響因素越來越多，研究的難度也越來越大。1980年后，隨著低維裝箱問題研究成果的逐漸累積，人們開始將研究目標(biāo)轉(zhuǎn)向三維裝箱問題。崔會芬等提出了改進(jìn)遺傳算法解決三維裝箱問題[3]，劉勝等人提出了一種解決三維裝箱問題的多層樹搜索算法[4]，Xueping Li等人在使用遺傳算法的基礎(chǔ)上提出了啟發(fā)式裝載策略，在合理的時間內(nèi)得到了很好的效果[5]，F(xiàn)aroe等人提出了基于導(dǎo)向局部搜索的啟發(fā)式算法用于解決三維裝箱問題[6]，Yaru Su等人使用改進(jìn)的化學(xué)反應(yīng)算法既融入了模擬退火算法的特點(diǎn)又保證了較快的收斂速度[7]，但這些算法都專注于解決三維裝箱問題效率問題，較少關(guān)注算法在大規(guī)模問題上的運(yùn)行時間問題，而正是運(yùn)行時間的問題，使現(xiàn)今問題規(guī)模普遍較大且要求時間的相關(guān)工業(yè)自動化領(lǐng)域難以將這些算法應(yīng)用于實(shí)際。另一方面，張長勇等人使用K-Means算法將飛機(jī)上旅客行李分成大體積大質(zhì)量、大體積小質(zhì)量、小體積大質(zhì)量、小體積小質(zhì)量4類，再通過關(guān)鍵點(diǎn)[8]的思想進(jìn)行裝箱，能夠得到較大的剩余空間[9]。Seda Erbayrak等人提出了使用相同訂單或相同目的地的方式將不同物體聚集在一起，提高了裝箱效率[10]。這些算法雖然在不同領(lǐng)域取得不錯的效果，但是通用性差，所以筆者提出一種新的聚類方式，能夠應(yīng)用于大多數(shù)的裝箱問題，且將此更細(xì)粒度的聚類應(yīng)用于大規(guī)模裝箱問題時，能夠保證裝箱效率的同時，大大減少算法運(yùn)行所需的時間。

三維裝箱問題作為一個經(jīng)典的NP-hard問題，“組合爆炸”的現(xiàn)象限制了人們使用常規(guī)算法來解決此問題，無法在多項式時間內(nèi)得到它的精確解。由于傳統(tǒng)算法不能在合理的時間內(nèi)得到較好的解，智能優(yōu)化算法逐漸成為了解決裝箱問題的主流方法，它能夠在可接受的時間內(nèi)盡可能地去搜尋最優(yōu)解。但在處理大規(guī)模三維裝箱問題時，智能優(yōu)化算法解決問題運(yùn)行時間較長，效率較低。另一方面，使用智能優(yōu)化算法解決問題，其解決方案和問題之間缺乏確定性的聯(lián)系，若稍微改變一下裝箱問題的參數(shù)，所得解決方案就會產(chǎn)生較大變化。所以，在每次求解都要重新運(yùn)行算法的前提下，如何減少運(yùn)行時間是智能優(yōu)化算法能否應(yīng)用于大規(guī)模裝箱問題的關(guān)鍵。

筆者在傳統(tǒng)的三維最優(yōu)適配算法(3DBF)[11]基礎(chǔ)上，提出網(wǎng)格覆蓋選優(yōu)的方法，并針對三維裝箱問題對K-Means進(jìn)行了調(diào)整優(yōu)化，提出基于聚類和網(wǎng)格覆蓋選優(yōu)的三維最優(yōu)適配算法(3DBFBCGC)，在提高算法準(zhǔn)確性的情況下，盡可能地減少算法運(yùn)行的時間。

本研究的目的是尋找一種能夠減少算法運(yùn)行時間且使結(jié)果更準(zhǔn)確的方法，提高裝箱算法的效率并減少算法運(yùn)行時間，使裝箱算法在工業(yè)自動化領(lǐng)域有較好的理論支撐和解決方案。

1 三維裝箱問題建模過程

1.1 前提假設(shè)

針對規(guī)則物體離線裝箱問題，相關(guān)假設(shè)如下：

a)待裝箱的物體和箱子的形狀都是長方體；

b)待裝箱的物體是無彈性的，不可壓縮的；

c)待裝箱的物體在箱內(nèi)的任意位置都是可以的，即物體沒有更偏向于裝在箱子的邊緣位置或者中間位置，任意位置的權(quán)重都是相等的；

d)待裝箱的物體的邊框與箱子或已裝箱物體邊框平行或正交；

e)每個物體都是密封且不可穿透的；

f)裝箱的物體不能超過箱子容器的邊界;

g)裝箱過程中不能出現(xiàn)被裝箱的物體懸空的情況；

h)每個箱子都有一定的載重，每個物體都有自己的重量，箱子中的物體總重不能大于箱子的載重；

1.2 裝箱過程建模

在以上前提假設(shè)下，假設(shè)裝箱過程在有x、y、z坐標(biāo)的三維空間下，箱子擺放位置，每條邊均與x軸、y軸或z軸平行或正交。同時，所裝的物體是長方體的，每條邊均與x軸、y軸或者z軸平行或正交。對一個長方體物體裝箱時，由于它跟箱子的邊是平行或正交，所以裝箱總共有六種裝載方式，用旋轉(zhuǎn)的方式來表明這六種裝載方式如表1。

表1 待裝箱物體擺放方式

1.3 優(yōu)化目標(biāo)

研究的優(yōu)化目標(biāo)是在有限容量容器中裝入盡可能多的物體，即最小化剩余未裝物體體積的比，算法最終給出找到的最優(yōu)解決方案。當(dāng)剩余未裝物體體積比相同時，利用剩余未裝物體重量比來衡量哪一個解決方案更優(yōu)。所以，要處理的數(shù)據(jù)中每個物體有4個屬性：長l、寬wd、高h(yuǎn)和重量wg。假設(shè)有N個物體要裝入B個容器，通過某種裝載方式，最后剩下m個物體在限定條件下無法裝入容器，即容器中裝下了N-m個物體，此時，優(yōu)化目標(biāo)的公式如式(1)：

(1)

其中l(wèi)i表示第i個物體的長，wdi表示第i個物體的寬，hi表示第i個物體的高。

當(dāng)?shù)趕1個解決方案與第s2個解決方案最小剩余未裝物體體積比相同時，從中選擇剩余未裝物體重量比最小的解決方案作為最優(yōu)解決方案，如式(2)。

(2)

其中wgs1,i和wgs2,i分別表示s1解決方案和s2解決方案中第i個物體的重量。同理，ls1,i、wds1,i以及hs1,i分別表示s1解決方案中第i個物體的長寬高。

2 混合式裝箱算法

在前人基礎(chǔ)上提出了一種新的“先打包再裝箱”的方法。算法先使用改進(jìn)的K-Means聚類方法將相似形狀(物體在長寬高三個維度上某一維度相等或相近)的物體“打包”，將每一個打好的“包”看作一個個體，使用遺傳算法[12]對這些“包”進(jìn)行計算，找到最好的“包”裝入順序，按照順序?qū)ⅰ鞍苯忾_即為最終的裝箱順序。在遺傳算法計算過程中，使用改進(jìn)的啟發(fā)式裝箱算法進(jìn)行裝箱，返回的剩余未裝箱物體體積比和重量比作為遺傳算法中對應(yīng)個體的適應(yīng)值。

2.1 改進(jìn)的K-Means聚類算法

K-Means聚類算法是最為著名的聚類算法之一，由于簡單且易于實(shí)現(xiàn)，目前該算法極其相關(guān)改進(jìn)的算法被廣泛應(yīng)用于科學(xué)研究和工業(yè)領(lǐng)域[13]。

K-Means聚類算法首先選取初始化k個聚類中心，然后對所有數(shù)據(jù)點(diǎn)進(jìn)行分類，最后計算每個簇的平均值來調(diào)整聚類中心，通過不斷循環(huán)迭代，最終使類內(nèi)對象相似性最大，類間相似性最小。具體算法步驟如下。

輸入：需要聚類的數(shù)據(jù)以及聚類的數(shù)目k。

輸出：k個聚類簇。

方法：

1)隨機(jī)從需要聚類的數(shù)據(jù)中挑選k個對象作為初始的聚類中心點(diǎn)；

2)計算每個對象到各個中心點(diǎn)的歐氏距離，選取距離最近的聚類簇作為其分類；

3)對每個聚類簇計算所含有對象的平均值，作為新的聚類中心；

4)重復(fù)2)3)步驟，直到聚類結(jié)果不再變化時退出循環(huán)，返回最終聚類結(jié)果。

K-Means聚類算法因其簡單快捷、對大數(shù)據(jù)集處理較快而被廣泛應(yīng)用于學(xué)術(shù)研究及工業(yè)領(lǐng)域中。正常情況下，它的時間復(fù)雜度為O(nkt)，其中n為數(shù)據(jù)集大小，k為聚類簇個數(shù)，t為迭代次數(shù)。但是它的缺點(diǎn)明顯，如在未知數(shù)據(jù)究竟有多少類的時候k的設(shè)置對最終結(jié)果影響很大，k個聚類中心初始化的位置對最終結(jié)果有影響，算法對于噪聲點(diǎn)和孤立點(diǎn)很敏感等問題。

對本文研究的三維裝箱問題，處理的數(shù)據(jù)集內(nèi)對象相對較少，屬于小數(shù)據(jù)集的聚類，使用傳統(tǒng)K-Means聚類算法，不能發(fā)揮它的優(yōu)勢，且k個聚類中心初始化的位置對結(jié)果影響更大。為解決這問題，采用了Vassilvitskii S等人提出的K-Means++算法，從而保證在聚類中心初始化過程中選擇較好的聚類中心[14]。

K-Means++算法的主要思路是在聚類中心初始化過程中盡可能地使初始的聚類中心相隔較遠(yuǎn)，它對于傳統(tǒng)K-Means的改進(jìn)主要體現(xiàn)在聚類中心初始化過程中，具體步驟如下。

1)從數(shù)據(jù)集X隨機(jī)選擇一個樣本點(diǎn)作為第一個初始聚類中心c1；

2)計算所有其它樣本點(diǎn)到c1的最短距離，記為D(x)；

3)選出D(x)最大的點(diǎn)作為第二個初始聚類中心；

4)計算所有其它點(diǎn)到當(dāng)前所有聚類中心的最短距離D′(x)，選取最短距離D′(x)最大的樣本點(diǎn)作為新的聚類中心；

5)循環(huán)迭代直到聚類中心的個數(shù)達(dá)到k個，初始化聚類中心結(jié)束。

根據(jù)裝箱問題的具體特征，區(qū)別于之前K-Means使用歐氏距離計算兩個點(diǎn)之間的距離，提出了使用兩個樣本點(diǎn)(待裝箱物體)相似度來作為其距離的方式。待裝箱物體相似度的值由兩個待裝箱物體的長寬高中最為相近的兩條邊決定，具體相似度計算式(3)。

(3)

其中，i和j分別表示待裝箱物體的長寬高三條邊的某兩條的編號，x1,i表示第一個待裝箱物體的第i條邊的長度。

綜上，本文針對裝箱問題的特點(diǎn)，使用K-Means++聚類算法進(jìn)行聚類，在此基礎(chǔ)上提出了待裝箱物體的分類標(biāo)準(zhǔn)及二次聚類方法，使該聚類算法更適合于處理裝箱問題。

2.2 改進(jìn)的啟發(fā)式裝箱算法

啟發(fā)式裝箱算法也是整個算法中非常重要的一環(huán)，一個好的裝箱算法能夠很大程度地節(jié)省裝箱的時間，并能提高裝箱算法的效率?；贓rick Dube等人提出的三維最優(yōu)適配算法(3D Best Fit，3DBF)[11]，筆者提出基于網(wǎng)格覆蓋的三維最優(yōu)適配算法。相比于三維最優(yōu)適配算法沒有限制所使用的箱子的數(shù)量，本文根據(jù)所研究問題具有確定數(shù)量箱子的情況對算法進(jìn)行改進(jìn)。改進(jìn)的基于網(wǎng)格覆蓋的三維最優(yōu)適配算法增加了每個箱子可裝載物體重量限制、每個物體底面被覆蓋必須超過80%才足以支撐其在當(dāng)前位置放置的限制，并提出了基于網(wǎng)格覆蓋率選最優(yōu)放置方式的方法，具體如下。

輸入

1)所使用的箱子Boxes={b1,b2,…,bB-1,bB}；

2)箱子的載重Weight={w1,w2,…,wB-1,wB}；

3)需要被裝箱的物體及其序列X={x1,x2,…,xN-1,xN}；

4)物體的重量wg={wg1,wg2,…,wgN-1,wgN}；

準(zhǔn)備

1)當(dāng)前持有的箱子編號i=1；

2)當(dāng)前箱子已有物體的重量Wsum=0；

3)當(dāng)前待裝箱物體編號j；

算法步驟

1： while 終止條件未滿足時 do

2： sign=false

3： forxj∈ X do

4： ifWsum+wgj

5： ifWsum==0 then

6： 選擇覆蓋面大的方式裝入箱子左下角

7： else

8： 遍歷箱子bi中所有物體，分別嘗試在各個物體后左上、前左下、右下位置放置當(dāng)前物體，得到可放置位置列表；

9： 從可放置位置列表中計算并選擇網(wǎng)格覆蓋率最大的位置放置當(dāng)前物體；

10：Wsum+=wgj

11： end if

12： ifsign==falsethen

13：i=i+1

14：Wsum=0

15： end if

16： end if

17： end for

18：end while

終止條件

所有物體已被裝箱，或箱子已被用完。

輸出

根據(jù)最終裝箱結(jié)果返回剩余未裝箱物體體積比以及剩余未裝箱物體重量比。

該算法使用網(wǎng)格覆蓋率的方式來選擇放置的方式，是為了盡可能地讓當(dāng)前的待裝箱物體能夠緊挨已經(jīng)放置好的物體或者箱子的內(nèi)壁，從而提高箱子的空間利用率，減少不必要的空間浪費(fèi)。網(wǎng)格覆蓋率的計算方式如下。

取最小邊長minL為長寬高三條邊的最短的邊的邊長，將最小邊長minL被分割為Ks份，每份的長度為一個網(wǎng)格的邊長ls，根據(jù)這個長度將剩余長邊進(jìn)行分割，最終物體的每個面都被分割成很多個邊為ls的正方形的組合。之后，對被覆蓋的面，通過式(4)計算該面的網(wǎng)格覆蓋率。

(4)

其中，x和y分別代表當(dāng)前這個面的長和寬，C(gi,j)代表當(dāng)前面的第i行第j個的網(wǎng)格gi,j是否被覆蓋。

2.3 遺傳算法2.3.1 編碼及種群初始化

對提出的混合式裝箱算法，遺傳算法在其中的作用主要是找到較好的裝箱順序。所以，在前面使用聚類算法對待裝箱物體“打包”后，再將每一個“包”看做一個整體，按照聚類的順序?qū)⑺邪鼜?開始編號，遺傳算法將這些包隨機(jī)排序，找到較好的序列，之后將“包”拆開，按照“包”的順序?qū)⑺写b箱物體裝入箱內(nèi)。遺傳算法中種群POP的pop_size個個體保存的是pop_size個所有包編號的隨機(jī)排列。因為前面已經(jīng)通過聚類算法將N個物體聚類成k個“包”，所以在種群POP中，每個個體的大小是k，其中存儲的信息是[1,2,3,…,k]，這k個數(shù)的隨機(jī)組合。種群初始化時為每一個個體賦值1到k，這k個數(shù)隨機(jī)排列組合即可。

2.3.2 適應(yīng)度計算

適應(yīng)度是用來評判種群內(nèi)每一個個體性能好壞的標(biāo)準(zhǔn)之一，實(shí)際解決的問題的個體適應(yīng)度有可能越大越好，也有可能越小越好，在種群迭代過程中，根據(jù)“優(yōu)勝劣汰”原則，種群整體向好的方向發(fā)展，最終找到較優(yōu)的解。根據(jù)前面建模過程中所定的優(yōu)化目標(biāo)可知，剩余未裝物體體積比越小越好，在剩余未裝物體體積比相同情況下，剩余未裝箱物體重量比越小越好，如式(2)、式(3)。所以，本文使用的適應(yīng)度包含剩余未裝物體體積比和剩余未裝箱物體重量比兩項，如式(5)。

(5)

其中，popj代表種群中第j個個體，N是待裝箱物體的個數(shù)，m是未裝箱物體的個數(shù)，l、wd、h分別表示待裝箱物體的長寬高，wg表示待裝箱物體的重量。

2.3.3 選擇

選擇是從當(dāng)前種群中按照某種方法選出指定個數(shù)的個體進(jìn)入下一代。使用傳統(tǒng)經(jīng)典的輪盤賭方法來進(jìn)行選擇操作，它類似于自然界的“自然選擇”，每一個個體都有幾率存活，但是較優(yōu)的個體會有較大的生存幾率，而較差的個體則存活幾率較小。

不考慮剩余未裝物體體積比相同再去比較剩余未裝物體重量比的情況，而是直接使用剩余未裝物體體積比作為個體在執(zhí)行選擇操作時的適應(yīng)度fitness。由于在輪盤賭時，個體fitness越大被選擇的概率越大，而此處需要的適應(yīng)度fitness是越小越好，所以設(shè)計了一個轉(zhuǎn)換函數(shù)，如式(6)。

(6)

其中PI代表圓周率。此轉(zhuǎn)換函數(shù)在實(shí)現(xiàn)實(shí)際適應(yīng)值越小，轉(zhuǎn)換后適應(yīng)值越大的同時，利用正弦函數(shù)在x接近0時y變化較大的特點(diǎn)，使原適應(yīng)值中相互接近的值更具區(qū)分度，使算法更容易向更優(yōu)的方向發(fā)展。

2.3.4 交叉

交叉操作是遺傳算法中非常重要的部分，它通過交換附帶個體中的部分值產(chǎn)生新的子代個體，是維持種群多樣性的重要因素。通過合理的交叉操作，能夠大大提高算法的探索效率。本文使用的交叉算子如下：

對于父代個體pop1，隨機(jī)從種群中選擇另一個個體pop2進(jìn)行交叉，其中：

(7)

(8)

之后分別從[1,k]區(qū)間內(nèi)隨機(jī)選取bl、br作為父代個體交叉的左邊界和右邊界，其中bl≤br。父代交叉產(chǎn)生的子代個體s的bl到br的元素使用pop2中bl到br的元素，再將pop1中未加入到子代個體s的元素按照在pop1中的順序加到bl到br之外的位置，從而產(chǎn)生最終的子代個體s。

(9)

其中使用下標(biāo)other表示剩余未加入到子代個體的元素。

2.3.5 變異

變異是通過將個體中某個或某些元素值換成其它的值來實(shí)現(xiàn)。為了增大探索的范圍、維持種群的多樣性，可以通過變異產(chǎn)生一個不同于之前父代的個體，這樣防止了算法陷入某個局部最優(yōu)當(dāng)中。

本文使用互換變異算子即從[1,k]序列中隨機(jī)選取兩個位置rand1、rand2，之后互換這兩個位置元素的值，從而產(chǎn)生一個新的個體。如對式(7)中pop1，假設(shè)rand1

(10)

3 實(shí)驗結(jié)果及其分析

3.1 復(fù)雜度分析3.1.1 聚類算法

3.1.2裝箱算法

在裝箱算法中，3DBF的時間復(fù)雜度為O(nlogn)，而本文提出的基于網(wǎng)格覆蓋率的3DBF每次選擇放置位置時都需要計算網(wǎng)格覆蓋率。筆者將計算網(wǎng)格覆蓋率的時間復(fù)雜度設(shè)置為d，則所提出的基于網(wǎng)格覆蓋選優(yōu)的裝箱算法的時間復(fù)雜度為O(18ndlogn)。

3.1.3遺傳算法

3.2 結(jié)果分析

選取了近兩年內(nèi)同樣使用遺傳算法求解三維裝箱問題的文獻(xiàn)[15]進(jìn)行對比，并在華為的裝箱數(shù)據(jù)集上對本文提出的基于聚類和網(wǎng)格覆蓋的三維最優(yōu)適配算法(3DBFBCGC)與3DBF[14]、基于網(wǎng)格覆蓋的三維最優(yōu)適配算法(3DBFBGC)以及文獻(xiàn)[15]提出的算法(GA-PRS)進(jìn)行對比實(shí)驗，結(jié)果如表2、表3。從結(jié)果中可以看出，加入網(wǎng)格覆蓋率選優(yōu)方法后的3DBF相比于原算法效果有所提升，說明本文提出的網(wǎng)格覆蓋率選優(yōu)方法對三維裝箱問題是有效的，而本文提出的3DBFBCGC效果要好于其它三種算法，且所有測試案例都能找到最優(yōu)解，這說明本文針對三維裝箱問題提出的聚類方式能夠提高裝箱效率。此外，文獻(xiàn)[15]提出的算法與本文的算法相比，兩者使用的交叉算子以及裝箱算法時間復(fù)雜度相似，但整體上由于聚類算法的引入，本文的3DBFBCGC在時間上要優(yōu)n/k倍，且在裝箱效率方面性能更優(yōu)。

圖1 兩種裝箱算法裝箱結(jié)果比較

另一方面，圖1是在數(shù)據(jù)集2上運(yùn)行算法得到的裝箱結(jié)果，其中圖2(a)代表未使用聚類算法的最終裝箱結(jié)果，圖2(b)代表使用聚類算法之后的裝箱結(jié)果，從圖中可以看出，通過聚類算法“打包”后的裝箱可以減少不必要的空間浪費(fèi)，在將所有物體裝箱后，圖2(b)箱中還剩余出很多空間。從結(jié)果可以看出，“先打包，后裝箱”的思路除了能減少時間消耗，還能夠減少空間上的浪費(fèi)。

表2 算法的剩余體積比

表3 算法的剩余重量比

4 結(jié)語

針對三維離線裝箱問題，在遺傳算法和三維最優(yōu)適配算法的基礎(chǔ)上，提出了一種基于聚類和網(wǎng)格覆蓋的三維裝箱算法，并對其進(jìn)行了復(fù)雜度分析。為驗證該算法的有效性，本文在華為的數(shù)據(jù)集上進(jìn)行了實(shí)驗。實(shí)驗結(jié)果表明，本文提出的算法能夠在有限時間內(nèi)得到較好的解，且使用本文提出的聚類方式能夠減少空間上的浪費(fèi)，提高容器的利用率。但遺傳算法結(jié)合啟發(fā)式裝箱算法進(jìn)行裝箱相對較慢，盡管使用聚類減小了時間復(fù)雜度，仍有改進(jìn)的空間。未來的研究工作將包括本文所提出算法與分布式技術(shù)結(jié)合，同時開發(fā)收斂速度更快的迭代算法，進(jìn)一步提升優(yōu)化結(jié)果與優(yōu)化效率。