任岳淼，陳賢富，劉斌

（中國(guó)科學(xué)技術(shù)大學(xué)電子科學(xué)與技術(shù)系，安徽合肥230027）

面向梯形箱子的三維裝箱問(wèn)題算法研究

任岳淼，陳賢富，劉斌

（中國(guó)科學(xué)技術(shù)大學(xué)電子科學(xué)與技術(shù)系，安徽合肥230027）

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

三維裝箱問(wèn)題；啟發(fā)式算法；遺傳算法

0 引言

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

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

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

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

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

裝載約束條件如下：

（1）每個(gè)裝載的貨物不能與其他裝載貨物或者梯形箱子互相重疊；

圖1 梯形箱子

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

（3）每個(gè)裝入梯形箱子的貨物必須滿足方向約束。

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

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

1.1 空間分割

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

圖2 梯形箱子空間分割

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

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

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

方形上空間

梯形邊空間

梯形前空間

梯形空間約束：

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

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

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

方形上空間

方形邊空間

方形前空間

方形空間約束：

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

1.2 啟發(fā)式算法

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

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

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

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

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

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

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

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

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

條件1：（L1+x1==x2||L2+x2==x1）&&（y1==y2）&&

條件2：（W1+y1==y2||W2+y2==y1）&&（x1==x2）&&

則2個(gè)方形子空間合并為新的方形子空間cspace3。

若滿足條件1，則：

若滿足條件2，則：

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

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

圖3 空間合并

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

則2個(gè)方形子空間重組為新的方形子空間cspace6。

若滿足條件3，則：

若滿足條件4，則：

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

圖4 空間重組

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

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

2.1 編碼方案

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

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

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

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

2.3 遺傳操作

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

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

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

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

圖5 混合遺傳算法流程圖

3 實(shí)驗(yàn)結(jié)果

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

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

表1 混合模擬退火算法與混合遺傳算法的填充率比較

圖6梯形箱子三維裝箱實(shí)例

圖6 中，（a）是測(cè)試用例5的一個(gè)空間填充率為87. 24%的梯形箱子三維裝箱布局方案實(shí)例，（b）是測(cè)試用例12的一個(gè)空間填充率為92.11%的梯形箱子三維裝箱布局方案實(shí)例。

4 結(jié)論

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

[1]陳勝達(dá)，張德富，劉艷娟.求解矩形裝箱問(wèn)題的一種近似算法[J].計(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].Eu ropean 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]張德富，彭煜，朱文興，等.求解三維裝箱問(wèn)題的混合模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，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]張德富，彭煜，張麗麗.求解三維裝箱問(wèn)題的多層啟發(fā)式搜索算法[J].計(jì)算機(jī)學(xué)報(bào)，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]陳國(guó)良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

Study on algorithm of three-dimensional bin packing problem for trapezoidal bin

Ren Yuemiao，Chen Xianfu，Liu Bin
（School of Information Science and Technology，University of Science and Technology of China，Hefei 230027，China）

To solve three-dimensional bin packing problem for trapezoidal bin，we proposed a constructive heuristic algorithm based on the space decomposition approach.Concerning on the feature of this problem，we designed three corresponding strategies，they are space decomposition strategy，space consolidation strategy and space reconstruction strategy.To improve capabilities of the local and global search of the algorithm，we integrated the proposed algorithm into the genetic algorithm.The experimental results show that the hybrid genetic algorithm is efficient to address three-dimensional bin packing problem for trapezoidal bin.

three-dimensional bin packing problem；heuristic algorithm；genetic algorithm

TP391

A

1674-7720（2015）09-0018-04

2015-01-03）

任岳淼（1990-），通信作者，男，碩士研究生，主要研究方向：智能信息處理。E-mail：renym@mail.ustc.edu.cn。

陳賢富（1963-），男，博士，副教授，主要研究方向：復(fù)雜系統(tǒng)與計(jì)算智能。

劉斌（1992-），男，碩士研究生，主要研究方向：智能信息處理。