摘 要： 針對(duì)梯形箱子的三維裝箱問(wèn)題，提出了一種基于空間分割的構(gòu)造性啟發(fā)式算法，根據(jù)梯形箱子三維裝箱問(wèn)題的特點(diǎn)，設(shè)計(jì)了相應(yīng)的空間分割策略、空間合并策略與空間重組策略，在此基礎(chǔ)上加入遺傳算法，提高算法局部與全局搜索能力。實(shí)驗(yàn)結(jié)果表明，該算法能有效處理梯形箱子三維裝箱問(wèn)題。
關(guā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ò)組織裝填樹(shù)把大空間分成小空間進(jìn)行裝填，最后再對(duì)剩余空間進(jìn)行處理，其通過(guò)搜索局部最優(yōu)解進(jìn)行裝填，全局搜索能力需要提高；另外還有一些基于“塊”的啟發(fā)式算法[8-10]與運(yùn)用“墻”的建立與穴度方法相組合的啟發(fā)式算法[11]，這些啟發(fā)式算法是面向長(zhǎng)方體箱子三維裝箱問(wèn)題算法研究應(yīng)用，而沒(méi)有涉及到梯形箱子的三維裝箱問(wèn)題。
在實(shí)際工程應(yīng)用中存在非長(zhǎng)方體箱子三維裝箱問(wèn)題，例如，箱子幾何形狀為上下底面為直角梯形的直四棱柱等特殊類(lèi)型的箱子。這需要根據(jù)具體裝箱問(wèn)題的特點(diǎn)與實(shí)際工程應(yīng)用要求，研究相應(yīng)的裝箱算法來(lái)完成貨物裝箱。
本文研究的梯形箱子三維裝箱問(wèn)題的具體描述為：給定無(wú)限數(shù)量相同規(guī)格的梯形箱子，給定有限數(shù)量的待裝長(zhǎng)方體貨物，在滿(mǎn)足裝載約束的條件下把這些長(zhǎng)方體貨物全部裝入梯形箱子中，目標(biāo)是梯形箱子使用數(shù)目最少，使空間利用率最高。
定義1（梯形箱子） 梯形箱子的幾何形狀是上下底面為直角梯形的直四棱柱，在圖1中，其幾何形狀可以通過(guò)底面直角梯形的高度L、底面直角梯形的下底邊W、底面直角梯形的銳角θ以及直四棱柱高度H來(lái)描述。
裝載約束條件如下：
?。?）每個(gè)裝載的貨物不能與其他裝載貨物或者梯形箱子互相重疊；
?。?）每個(gè)裝入梯形箱子的貨物的每一個(gè)面必須與梯形箱子的某一個(gè)面平行；
（3）每個(gè)裝入梯形箱子的貨物必須滿(mǎn)足方向約束。
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（方形空間）方形空間i由其幾何形狀長(zhǎng)度Li、寬度Wi和高度Hi，以及空間坐標(biāo)參考點(diǎn)（xi，yi，zi）構(gòu)成，數(shù)學(xué)表達(dá)方式：
cspacei={（Li，Wi，Hi），（xi，yi，zi）}（1）
定義3（梯形空間）梯形空間i由其幾何形狀長(zhǎng)度Li、寬度Wi、高度Hi和底面直角梯形的銳角θ，以及空間坐標(biāo)參考點(diǎn)（xi，yi，zi）構(gòu)成，數(shù)學(xué)表達(dá)方式：
tspacei={（Li，Wi，Hi，θi），（xi，yi，zi）}（2）
把梯形箱子作為一個(gè)梯形空間tspacei，當(dāng)某個(gè)長(zhǎng)寬高為（lj，wj，hj）的貨物j滿(mǎn)足梯形空間約束時(shí)，該貨物裝入梯形空間的空間坐標(biāo)參考點(diǎn)（xi，yi，zi）即原點(diǎn)O，剩余空間被分割成3個(gè)子空間：
方形上空間
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時(shí)需滿(mǎn)足：
lj≤Li且hj≤Hi且（wj+lj/tanθi）≤Wi（6）
由所有子空間構(gòu)成一個(gè)空間集合S，從空間集合中選擇一個(gè)子空間，若是梯形空間則分割方法如上，若是方形子空間則采用方法如下：
選擇一個(gè)方形空間cspacei，當(dāng)某個(gè)長(zhǎng)、寬、高為（lj，wj，hj）的貨物j滿(mǎn)足方形空間約束時(shí)，該貨物裝入方形空間的空間坐標(biāo)參考點(diǎn)（xi，yi，zi），剩余空間被分割成3個(gè)子空間：
方形上空間
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時(shí)需滿(mǎn)足：
lj≤Li且hj≤Hi且wj≤Wi（10）
1.2 啟發(fā)式算法
基于空間分割的啟發(fā)式算法基本步驟表述如下：
?。?）算法開(kāi)始，初始化待裝貨物序列C與梯形箱子信息。
?。?）判斷待裝貨物是否裝載完成，裝載完成跳轉(zhuǎn)（7）；反之，未完成裝載則跳轉(zhuǎn)到（3）。
?。?）選擇一個(gè)待裝貨物并開(kāi)啟一個(gè)新的梯形箱子，待裝貨物裝入梯形箱子后剩余空間被分割成3個(gè)子空間，分別為方形上空間、梯形邊空間與梯形前空間，這3個(gè)子空間組成新的空間序列S，把裝入的貨物從待裝貨物序列C中移除，完成待裝貨物序列C更新。
?。?）判斷待裝貨物序列C中是否存在一個(gè)貨物滿(mǎn)足裝載約束并能裝入空間序列S中某個(gè)空間，存在該貨物則跳轉(zhuǎn)（5）；反之，則跳轉(zhuǎn)到（6）。
?。?）若該空間為梯形子空間，裝入選擇的貨物后，剩余空間被分割為方形上空間、梯形邊空間與梯形前空間這3個(gè)子空間；若該空間為方形子空間，則裝入選擇的貨物后，剩余空間被分割為方形上空間、方形邊空間與方形前空間這3個(gè)子空間；該空間裝入貨物后從空間序列S中移除，新生成的3個(gè)子空間添加到空間序列S中，同時(shí)通過(guò)空間合并策略更新空間序列S，裝入的貨物從待裝貨物序列C中移除，完成待裝貨物序列C更新。
?。?）判斷是否進(jìn)行過(guò)重組策略操作，沒(méi)有則對(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）}能夠滿(mǎn)足以下條件中的一個(gè)：
條件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個(gè)方形子空間合并為新的方形子空間cspace3。
若滿(mǎn)足條件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）
若滿(mǎn)足條件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個(gè)能合并的子空間合并成一個(gè)更大的子空間，提高箱子的空間利用率。
圖3（a）為滿(mǎn)足條件1的空間合并示意圖，圖3（b）為滿(mǎn)足條件2的空間合并示意圖。
定義5（空間重組策略）若2個(gè)方形子空間cspace4={（L4，W4，H4），（x4，y4，z4）}、cspace5={（L5，W5，H5），（x5，y5，z5）}能夠滿(mǎn)足以下條件中的一個(gè)：
條件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個(gè)方形子空間重組為新的方形子空間cspace6。
令H6=min（H4，H5），z6=max（z4，z5）；（19）
若滿(mǎn)足條件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）
若滿(mǎn)足條件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 面向梯形箱子三維裝箱的混合遺傳算法
針對(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 遺傳操作
采用輪盤(pán)賭選擇方法作為選擇算子，在輪盤(pán)賭選擇中，各個(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為面向梯形箱子三維裝箱的混合遺傳算法流程圖。
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)題。
圖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ì)三角形箱子、楔形箱子等特定類(lèi)型箱子三維裝箱問(wèn)題的研究提供一些幫助和借鑒。
參考文獻(xià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]. 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] 張德富，彭煜，朱文興，等.求解三維裝箱問(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.