面向梯形箱子的三維裝箱問題算法研究

任岳淼，陳賢富，劉斌

（中國科學技術大學電子科學與技術系，安徽合肥230027）

面向梯形箱子的三維裝箱問題算法研究

任岳淼，陳賢富，劉斌

（中國科學技術大學電子科學與技術系，安徽合肥230027）

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

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

0 引言

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

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

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

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

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

裝載約束條件如下：

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

圖1 梯形箱子

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

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

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

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

1.1 空間分割

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

圖2 梯形箱子空間分割

定義2（方形空間）方形空間i由其幾何形狀長度Li、寬度Wi和高度Hi，以及空間坐標參考點（xi，yi，zi）構成，數學表達方式：

定義3（梯形空間）梯形空間i由其幾何形狀長度Li、寬度Wi、高度Hi和底面直角梯形的銳角θ，以及空間坐標參考點（xi，yi，zi）構成，數學表達方式：

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

方形上空間

梯形邊空間

梯形前空間

梯形空間約束：

當貨物j裝入梯形空間tspacei時需滿足：

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

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

方形上空間

方形邊空間

方形前空間

方形空間約束：

當貨物j裝入方形空間cspacei時需滿足：

1.2 啟發(fā)式算法

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

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

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

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

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

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

（6）判斷是否進行過重組策略操作，沒有則對空間序列S進行重組策略操作，跳轉（4）；若進行過重組策略操作則跳轉到（2）。

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

定義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）&&

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

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

若滿足條件1，則：

若滿足條件2，則：

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

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

圖3 空間合并

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

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

若滿足條件3，則：

若滿足條件4，則：

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

圖4 空間重組

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

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

2.1 編碼方案

根據梯形箱子三維裝箱問題的具體情況，采用順序編碼，每個個體由待裝貨物編號序列PN以及其對應的擺放方向序列PD組成。貨物的擺放方向有6種，對應編號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ōu)劣。這里選擇整體梯形箱子三維裝箱空間利用率作為適應度函數：

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

2.3 遺傳操作

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

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

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

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

圖5 混合遺傳算法流程圖

3 實驗結果

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

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

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

圖6梯形箱子三維裝箱實例

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

4 結論

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

[1]陳勝達，張德富，劉艷娟.求解矩形裝箱問題的一種近似算法[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]張德富，彭煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法[J].計算機學報，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].計算機學報，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)泉，等.遺傳算法及其應用[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-），男，博士，副教授，主要研究方向：復雜系統(tǒng)與計算智能。

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