摘  要： 針對梯形箱子的三維裝箱問題，提出了一種基于空間分割的構(gòu)造性啟發(fā)式算法，根據(jù)梯形箱子三維裝箱問題的特點，設(shè)計了相應(yīng)的空間分割策略、空間合并策略與空間重組策略，在此基礎(chǔ)上加入遺傳算法，提高算法局部與全局搜索能力。實驗結(jié)果表明，該算法能有效處理梯形箱子三維裝箱問題。

　　關(guān)鍵詞： 三維裝箱問題；啟發(fā)式算法；遺傳算法

0 引言

　　裝箱問題（Bin Packing Problem）在現(xiàn)實生活中具有廣泛的應(yīng)用。計算機(jī)領(lǐng)域中有內(nèi)存分配、信息存儲等一維裝箱問題；二維裝箱問題應(yīng)用于服裝裁剪、新聞排版、矩形裝箱[1]等；在貨運碼頭、物流、倉儲等領(lǐng)域則涉及三維裝箱問題。

　　裝箱問題是NP難問題，需要考慮維數(shù)、形狀、約束、目標(biāo)等不同因素，因此理論研究與實際工程應(yīng)用中一般采用近似算法。近年來，國內(nèi)外學(xué)者對三維裝箱問題進(jìn)行了廣泛而深入的研究。三維裝箱問題存在禁忌搜索算法[2]、遺傳算法[3-4]、模擬退火算法[5]等研究和應(yīng)用。參考文獻(xiàn)[6]采用動態(tài)空間分解方法進(jìn)行啟發(fā)式裝載，其對剩余空間進(jìn)行重組優(yōu)化存在不足；參考文獻(xiàn)[5]提出了混合模擬退火算法，從一個初始貨物裝載序列采用模擬退火搜索一個好的貨物裝載序列，作為問題的近似解；參考文獻(xiàn)[7]通過組織裝填樹把大空間分成小空間進(jìn)行裝填，最后再對剩余空間進(jìn)行處理，其通過搜索局部最優(yōu)解進(jìn)行裝填，全局搜索能力需要提高；另外還有一些基于“塊”的啟發(fā)式算法[8-10]與運用“墻”的建立與穴度方法相組合的啟發(fā)式算法[11]，這些啟發(fā)式算法是面向長方體箱子三維裝箱問題算法研究應(yīng)用，而沒有涉及到梯形箱子的三維裝箱問題。

　　在實際工程應(yīng)用中存在非長方體箱子三維裝箱問題，例如，箱子幾何形狀為上下底面為直角梯形的直四棱柱等特殊類型的箱子。這需要根據(jù)具體裝箱問題的特點與實際工程應(yīng)用要求，研究相應(yīng)的裝箱算法來完成貨物裝箱。

　　本文研究的梯形箱子三維裝箱問題的具體描述為：給定無限數(shù)量相同規(guī)格的梯形箱子，給定有限數(shù)量的待裝長方體貨物，在滿足裝載約束的條件下把這些長方體貨物全部裝入梯形箱子中，目標(biāo)是梯形箱子使用數(shù)目最少，使空間利用率最高。

　　定義1（梯形箱子） 梯形箱子的幾何形狀是上下底面為直角梯形的直四棱柱，在圖1中，其幾何形狀可以通過底面直角梯形的高度L、底面直角梯形的下底邊W、底面直角梯形的銳角θ以及直四棱柱高度H來描述。

　　裝載約束條件如下：

　?。?）每個裝載的貨物不能與其他裝載貨物或者梯形箱子互相重疊；

　　（2）每個裝入梯形箱子的貨物的每一個面必須與梯形箱子的某一個面平行；

　?。?）每個裝入梯形箱子的貨物必須滿足方向約束。

1 基于空間分割的構(gòu)造性啟發(fā)式算法

　　針對梯形箱子三維裝箱問題，本文提出了一種基于空間分割的構(gòu)造性啟發(fā)式算法。該算法思想借鑒了Bortfeld和Gehring[2]中提到的基礎(chǔ)啟發(fā)式算法。

　　1.1 空間分割

　　在裝箱問題中，所有裝入的貨物都是與坐標(biāo)軸平行的長方體，對它們的裝載位置描述是通過參考點與各個維度上的邊長來確定的。圖2中空間直角坐標(biāo)系的X軸、Y軸、Z軸分別與梯形箱子長度L、寬度W、高度H方向平行，梯形箱子左后下角為原點O。

　　定義2（方形空間）方形空間i由其幾何形狀長度Li、寬度Wi和高度Hi，以及空間坐標(biāo)參考點（xi，yi，zi）構(gòu)成，數(shù)學(xué)表達(dá)方式：

　　cspacei={（Li，Wi，Hi），（xi，yi，zi）}（1）

　　定義3（梯形空間）梯形空間i由其幾何形狀長度Li、寬度Wi、高度Hi和底面直角梯形的銳角θ，以及空間坐標(biāo)參考點（xi，yi，zi）構(gòu)成，數(shù)學(xué)表達(dá)方式：

　　tspacei={（Li，Wi，Hi，θi），（xi，yi，zi）}（2）

　　把梯形箱子作為一個梯形空間tspacei，當(dāng)某個長寬高為（lj，wj，hj）的貨物j滿足梯形空間約束時，該貨物裝入梯形空間的空間坐標(biāo)參考點（xi，yi，zi）即原點O，剩余空間被分割成3個子空間：

　　方形上空間

　　cspacea={（lj，wj，Hi-hj），（xi，yi，zi+hj）}（3）

　　梯形邊空間

　　tspaceb={（lj，Wi-wj，Hi，θi），（xi，yi+wj，zi）}（4）

　　梯形前空間

　　tspacec={（Li-lj，Wi-lj/tanθi，Hi，θi），（xi+lj，yi，zi）}（5）

　　梯形空間約束：

　　當(dāng)貨物j裝入梯形空間tspacei時需滿足：

　　lj≤Li且hj≤Hi且（wj+lj/tanθi）≤Wi（6）

　　由所有子空間構(gòu)成一個空間集合S，從空間集合中選擇一個子空間，若是梯形空間則分割方法如上，若是方形子空間則采用方法如下：

　　選擇一個方形空間cspacei，當(dāng)某個長、寬、高為（lj，wj，hj）的貨物j滿足方形空間約束時，該貨物裝入方形空間的空間坐標(biāo)參考點（xi，yi，zi），剩余空間被分割成3個子空間：

　　方形上空間

　　cspaced={（lj，wj，Hi-hj），（xi，yi，zi+hj）}（7）

　　方形邊空間

　　cspacee={（lj，Wi-wj，Hi），（xi，yi+wj，zi）}（8）

　　方形前空間

　　cspacef={（Li-lj，Wi，Hi），（xi+lj，yi，zi）}（9）

　　方形空間約束：

　　當(dāng)貨物j裝入方形空間cspacei時需滿足：

　　lj≤Li且hj≤Hi且wj≤Wi（10）

　　1.2 啟發(fā)式算法

　　基于空間分割的啟發(fā)式算法基本步驟表述如下：

　　（1）算法開始，初始化待裝貨物序列C與梯形箱子信息。

　?。?）判斷待裝貨物是否裝載完成，裝載完成跳轉(zhuǎn)（7）；反之，未完成裝載則跳轉(zhuǎn)到（3）。

　?。?）選擇一個待裝貨物并開啟一個新的梯形箱子，待裝貨物裝入梯形箱子后剩余空間被分割成3個子空間，分別為方形上空間、梯形邊空間與梯形前空間，這3個子空間組成新的空間序列S，把裝入的貨物從待裝貨物序列C中移除，完成待裝貨物序列C更新。

　?。?）判斷待裝貨物序列C中是否存在一個貨物滿足裝載約束并能裝入空間序列S中某個空間，存在該貨物則跳轉(zhuǎn)（5）；反之，則跳轉(zhuǎn)到（6）。

　?。?）若該空間為梯形子空間，裝入選擇的貨物后，剩余空間被分割為方形上空間、梯形邊空間與梯形前空間這3個子空間；若該空間為方形子空間，則裝入選擇的貨物后，剩余空間被分割為方形上空間、方形邊空間與方形前空間這3個子空間；該空間裝入貨物后從空間序列S中移除，新生成的3個子空間添加到空間序列S中，同時通過空間合并策略更新空間序列S，裝入的貨物從待裝貨物序列C中移除，完成待裝貨物序列C更新。

　?。?）判斷是否進(jìn)行過重組策略操作，沒有則對空間序列S進(jìn)行重組策略操作，跳轉(zhuǎn)（4）；若進(jìn)行過重組策略操作則跳轉(zhuǎn)到（2）。

　?。?）輸出梯形箱子三維裝箱方案，算法結(jié)束。

　　定義4（空間合并策略）若2個方形子空間cspace1={（L1，W1，H1），（x1，y1，z1）}、cspace2={（L2，W2，H2），（x2，y2，z2）}能夠滿足以下條件中的一個：

　　條件1：（L1+x1==x2||L2+x2==x1）&&（y1==y2）&&（W1==W2）&&（z1==z2）&&（H1==H2）（11）

　　條件2：（W1+y1==y2||W2+y2==y1）&&（x1==x2）&&（L1==L2）&&（z1==z2）&&（H1==H2）（12）

　　則2個方形子空間合并為新的方形子空間cspace3。

　　若滿足條件1，則：

　　if x1<x2 cspace3={（L1+L2，W1，H1），（x1，y1，z1）}；（13）

　　if x2<x1 cspace3={（L1+L2，W2，H2），（x2，y2，z2）}；（14）

　　若滿足條件2，則：

　　if y1<y2 cspace3={（L1，W1+W2，H1），（x1，y1，z1）}；（15）

　　if y2<y1 cspace3={（L2，W1+W2，H2），（x2，y2，z2）}；（16）

　　空間合并策略是把2個能合并的子空間合并成一個更大的子空間，提高箱子的空間利用率。

　　圖3（a）為滿足條件1的空間合并示意圖，圖3（b）為滿足條件2的空間合并示意圖。

　　定義5（空間重組策略）若2個方形子空間cspace4={（L4，W4，H4），（x4，y4，z4）}、cspace5={（L5，W5，H5），（x5，y5，z5）}能夠滿足以下條件中的一個：

　　條件3：（L4+x4==x5||L5+x5==x4）&&（y4==y5）&&（W4==W5）&&（z4+H4==z5+H5）（17）

　　條件4：（W4+y4==y5||W5+y5==y4）&&（x4==x5）&&（L4==L5）&&（z4+H4==z5+H5）（18）

　　則2個方形子空間重組為新的方形子空間cspace6。

　　令H6=min（H4，H5），z6=max（z4，z5）；（19）

　　若滿足條件3，則：

　　if x4<x5 cspace6={（L4+L5，W4，H6），（x4，y4，z6）}；（20）

　　if x5<x4 cspace6={（L4+L5，W5，H6），（x5，y5，z6）}；（21）

　　若滿足條件4，則：

　　if y4<y5 cspace6={（L4，W4+W5，H6），（x4，y4，z6）}；（22）

　　if y5<y4 cspace6={（L5，W4+W5，H6），（x5，y5，z6）}；（23）

　　空間重組策略是充分利用剩余的子空間，有利于提高箱子的空間利用率。圖4為空間重組示意圖。

2 面向梯形箱子三維裝箱的混合遺傳算法

　　針對梯形箱子三維裝箱問題這一NP難問題，結(jié)合啟發(fā)式算法局部搜索能力與遺傳算法全局搜索能力，混合遺傳算法不僅局部搜索能力得到加強(qiáng)，而且兼具全局搜索能力。

　　2.1 編碼方案

　　根據(jù)梯形箱子三維裝箱問題的具體情況，采用順序編碼，每個個體由待裝貨物編號序列PN以及其對應(yīng)的擺放方向序列PD組成。貨物的擺放方向有6種，對應(yīng)編號1為（l，w，h）、編號2為（w，l，h）、編號3為（w，h，l）、編號4為（h，w，l）、編號5為（l，h，w）、編號6為（h，l，w）。

　　2.2 適應(yīng)度函數(shù)

　　通過個體適應(yīng)度的大小來評價群體中個體所對應(yīng)裝載方案的優(yōu)劣。這里選擇整體梯形箱子三維裝箱空間利用率作為適應(yīng)度函數(shù)：

　　其中，M表示裝載了M個貨物，lj，wj，hj表示第j件貨物的長度、寬度和高度；N表示使用了N個梯形箱子，Vi表示第i個梯形箱子的體積。

　　2.3 遺傳操作

　　采用輪盤賭選擇方法作為選擇算子，在輪盤賭選擇中，各個個體的選擇概率與其適應(yīng)度值成正比例。

　　采用部分匹配交叉（Partally Matched Crossover，PMX）算子，在PMX操作中，先依據(jù)均勻隨機(jī)分布產(chǎn)生兩個位串交叉點，這兩點之間的區(qū)域為一匹配區(qū)域，并使用位置交換操作交換兩個父串的匹配區(qū)域。

　　對進(jìn)行變異操作的個體，隨機(jī)產(chǎn)生2個位置i、j，交換處在位置i與位置j上的貨物編號信息n及對應(yīng)的貨物方向信息；存在一定變異概率使得貨物擺放方向變異。變異算子的作用是維持群體的多樣性，避免算法早熟收斂。

　　圖5為面向梯形箱子三維裝箱的混合遺傳算法流程圖。

3 實驗結(jié)果

　　表1中測試用例1~4，使用梯形箱子參數(shù)為L=400、W=800、H=400、tanθ=1；測試用例5~8，使用梯形箱子參數(shù)為L=400、W=600、H=400、tanθ=2；測試用例9~12，使用梯形箱子參數(shù)為L=400、W=900、H=400、tanθ=0.8；混合遺傳算法參數(shù)設(shè)置：種群大小20、進(jìn)化代數(shù)100、交叉概率0.5、變異概率0.05；每個測試用例進(jìn)行100次實驗。本文混合遺傳算法與混合模擬退火算法[5]進(jìn)行比較。

　　表1的實驗結(jié)果顯示，在面向梯形箱子三維裝箱問題上，通過與混合模擬退火算法比較，混合遺傳算法的解不僅平均空間填充率較高，而且平均運行時間較短?；旌线z傳算法能有效處理梯形箱子三維裝箱問題。

　　圖6中，（a）是測試用例5的一個空間填充率為87.24%的梯形箱子三維裝箱布局方案實例，（b）是測試用例12的一個空間填充率為92.11%的梯形箱子三維裝箱布局方案實例。

4 結(jié)論

　　借鑒Bortfeld和Gehring[2]的長方體空間基礎(chǔ)啟發(fā)式算法思想，根據(jù)梯形箱子的空間約束條件，研究設(shè)計了面向梯形空間的構(gòu)造性啟發(fā)式算法。采用空間分割策略、空間合并策略與空間重組策略提高局部搜索能力。其與遺傳算法全局搜索能力相結(jié)合，設(shè)計了面向梯形箱子三維裝箱問題的混合遺傳算法。理論分析與實驗結(jié)果顯示，針對梯形箱子三維裝箱問題，混合遺傳算法具有良好的優(yōu)化效果。希望本文的研究對三角形箱子、楔形箱子等特定類型箱子三維裝箱問題的研究提供一些幫助和借鑒。

　　參考文獻(xiàn)

　　[1] 陳勝達(dá)，張德富，劉艷娟.求解矩形裝箱問題的一種近似算法[J].計算機(jī)工程，2007，33（9）：189-193.

　　[2] BORTFELDT A， GEHRING H， MACK D. A parallel tabu search algorithm for solving the container loading problem[J]. Parallel Computing，2003，29（5）：641-662.

　　[3] BORTFELDT A， GEHRING H. A hybrid genetic algorithm for the container loading problem[J]. European Journal of Operational Research，2001，131（1）：143-161.

　　[4] GEHRING H， BORTFELDT A. A parallel genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research，2002，9（4）：497-511.

　　[5] 張德富，彭煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法[J].計算機(jī)學(xué)報，2009，32（11）：2148-2156.

　　[6] WANG Z， LI K W， LEVY J K. A heuristic for the container loading problem： a tertiary-tree-based dynamic space decomposition approach[J]. European Journal of Operational Research，2008，191（1）：86-99.

　　[7] LIM A， RODRIGUES B， YANG Y. 3-D container packing heuristics[J]． Applied Intelligence，2005，22（2）：125-134.

　　[8] 張德富，彭煜，張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法[J].計算機(jī)學(xué)報，2012，35（12）：2554-2561.

　　[9] MIYAZAWA F K，.WAKABAYASHI Y. Three-dimensional packings with rotations[J]. Computers & Operations Research，2009，36（10）：2801-2815.

　　[10] ELEY M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research，2002，141（2）：393-409.

　　[11] Wu Xiuli， Du Yanhua， Li Sujian. A new approach for the three-dimensional single container loading problem[C]. Intelligent Human-Machine Systems and Cybernetics （IHMSC）， 2013 5th International Conference on， 2013：155-158.

　　[12] 陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.