考慮支撐面約束的三維裝箱問題快速求解方法

張 瑩，劉二超，戚銘堯

（清華大學(xué) 深圳研究生院，現(xiàn)代物流研究中心，廣東 深圳 518055）

1 引言

集裝箱是現(xiàn)代重要的運(yùn)輸工具，在市場競爭日趨激烈的當(dāng)今社會(huì)，如何在貨物運(yùn)輸這一重要環(huán)節(jié)減低成本與費(fèi)用，是進(jìn)出口和運(yùn)輸?shù)刃袠I(yè)企業(yè)普遍關(guān)心的問題.事實(shí)上，集裝箱的裝箱問題在大部分企業(yè)中一直得不到很好解決，往往是憑經(jīng)驗(yàn)作業(yè)，造成空間利用率低，計(jì)算耗時(shí)費(fèi)力，作業(yè)缺乏標(biāo)準(zhǔn)，貨物擺放混亂.在解決具有規(guī)則形狀的貨物在貨柜集裝箱、廂式貨車、包裝箱、托盤中的優(yōu)化裝箱問題中，如果通過三維裝箱算法，快速設(shè)計(jì)裝箱方案，可以優(yōu)化空間效率，節(jié)約運(yùn)費(fèi)，規(guī)范作業(yè)，提高車輛配載率.

三維裝箱(three-dimensional bin packing,3DBP)問題指如何用最少的車廂將一系列數(shù)目為n的三維貨物全部裝載，同時(shí)滿足給定的約束條件，如任意兩個(gè)貨物不能有空間重疊，每個(gè)貨物底部的支撐面積必須達(dá)到其底面面積的一定比例.根據(jù)W?scher,G等[1]對“切割和裝載”問題所進(jìn)行的分類，三維裝箱(3D-BP)問題屬于單箱尺寸裝箱問題(SBSBPP).

三維裝箱問題最早由Martello等[2]于2000年提出.該文中，作者首先給出三維裝箱問題下界的求解方法，并提出基于基本點(diǎn)的構(gòu)造啟發(fā)式算法求解3D-BP問題，最后設(shè)計(jì)了九種算例來驗(yàn)證算法，2000年以后求解三維裝箱問題的算法大多基于該算例進(jìn)行驗(yàn)證和比較.Faroe等[3]提出了引導(dǎo)鄰域搜索(GLS)啟發(fā)式方法，該算法把求解過程分為兩步，構(gòu)造階段和鄰域搜索階段，通過迭代以逐步減少車廂的方法來達(dá)到最優(yōu).Grainic T G等[4]提出關(guān)鍵點(diǎn)(Extreme Points)的概念來確定貨物擺放位置，對Martello等提出的基本點(diǎn)做了改進(jìn)，增加了貨物擺放位置，并且裝箱前將貨物按照一定規(guī)則進(jìn)行排序，結(jié)果表明，該措施顯著減少了車廂使用數(shù)目.陳實(shí)[5]、王磊[6]提出了一種新的裝箱啟發(fā)式算法，這種裝箱啟發(fā)式算法考慮了更多的關(guān)鍵點(diǎn)，所以使裝箱檢驗(yàn)的效果提高從而使求解結(jié)果取得了改進(jìn)，同時(shí)，該算法也使求解時(shí)間變得更長.Grainic T G等[7]提出了兩階段禁忌搜索方法，構(gòu)造階段采用基于關(guān)鍵點(diǎn)的裝箱方法得到初始解，然后采用兩階段禁忌搜索對初始解進(jìn)行改進(jìn)，第一階段給每個(gè)車廂分配貨物，第二階段對分配結(jié)果進(jìn)行裝箱測試.Parre?o,F等[8]將貪婪搜索算法(GRSAP)應(yīng)用于三維裝箱問題，并首次提出裝載空間的概念.Mack D等[9]結(jié)合裝箱(Container Loading)問題和一維裝箱(1D-BP)問題提出一種組合啟發(fā)式算法求解三維裝箱問題.該算法求解速度快，可用于求解貨物數(shù)量大的三維裝箱問題.

根據(jù)貨物是否可以翻轉(zhuǎn)90°，Boschetti[10]將3DBP分成3BPOF和3BPMF，并分別針對3BPOF和3BPMF設(shè)計(jì)了更好的下界函數(shù).

本文將基于帶支撐面的裝載空間來解決帶有支撐限制的三維裝箱問題.

2 帶支撐面的裝載空間

帶有支撐底面的裝載空間如圖1所示，該空間外觀是一個(gè)長方體，其底面陰影部分表示已知的提供支撐的部分，該陰影部分由車廂底面或者放入車廂的貨物的上表面提供，陰影部分向長方體的各個(gè)側(cè)面有一定的可拓展的空間，這部分空間不確定是否有支撐.

該空間可由以下7個(gè)屬性來表示：location(x,y,z)，shape(x,y,z)，back，left，front，right和 fragility.其中l(wèi)ocation(x,y,z)表示圖1中所示的點(diǎn)在三維坐標(biāo)系中的坐標(biāo)；shape(x,y,z)表示支撐空間的大小，x代表陰影部分的寬，z代表陰影部分的長，y代表該空間結(jié)構(gòu)的高；back表示從陰影部分向長方體的背面可以拓展的可能無支撐空間的長；left表示從陰影部分向長方體的左側(cè)可以拓展的可能無支撐空間的寬；front表示從陰影部分向長方體的前面可以拓展的可能無支撐空間的長；right表示從陰影部分向長方體的右側(cè)可以拓展的可能無支撐的空間的寬；fragility表示提供陰影部分支撐面所對應(yīng)的貨物的易碎性.對于沒有擺放貨物的一個(gè)長、寬、高分別為100、100、100的車廂而言，它構(gòu)成了一個(gè)帶支撐底面的裝載空間，其屬性為：location=(0,0,0)，shape=(100,100,100)，back=0，left=0，front=0，right=0，fragility=0.

圖1 帶支撐面的裝載空間Fig.1 Loading space with support surface

2.1 判斷兩立方體之間是否有空間重疊

圖2 兩個(gè)物體在車廂底面投影關(guān)系Fig.2 Projection of two items on the bottom

2.2 裝載空間更新算法

開始（輸入：空間集合subBins，當(dāng)前裝載貨物item，貨物裝載位置location）.

Step 1 新建一個(gè)空的空間集合newsubBins.

Step 2 依次考察subBins中的每一個(gè)空間結(jié)構(gòu)subBin.

如果subBin與item有空間重疊，將該subBin標(biāo)記為可刪除狀態(tài)，對subBin進(jìn)行切割更新：如果貨物的后表面（左側(cè)面、前表面、右側(cè)面、上表面、下表面）所在的平面切割subBin會(huì)形成新的空間結(jié)構(gòu)newsubBin，則將newsubBin增加到newsubBins中.

Step 3 從subBins中刪除掉標(biāo)記為可刪除狀態(tài)的subBin.

Step 4 將newsubBins中的每一個(gè)subBin增加到subBins中.

Step 5 合并subBins中可以進(jìn)行合并的裝載空間.結(jié)束.

3 基于帶支撐面的裝載空間求解三維裝箱問題

3.1 貨物排序

不同的貨物排序方法，對最終的裝箱結(jié)果影響很大.借鑒參考文獻(xiàn)[4]，本文采用如表1所示的四種貨物排序方法，為了對比，本文還考慮不排序的情況.

表1 貨物排序方法Table 1 Sorting Method

表中，“主原則”是主要的排序依據(jù)，當(dāng)兩個(gè)貨物在“主原則”列中的屬性相等時(shí)，則依據(jù)“次原則”進(jìn)行排序，并且均按降序排列.如“體積-高”排序方法：根據(jù)貨物體積大小進(jìn)行排列，體積大的貨物排在前面，體積小的排在后面；如果兩個(gè)貨物體積相等，則根據(jù)貨物高進(jìn)行排序，較高的貨物排在前面，較矮的貨物排在后面.

高-體積、面積-高、高-面積排序方法類推即可.

3.2 裝載空間選擇

[4，5]選擇關(guān)鍵點(diǎn)的思想，運(yùn)用于裝載空間的選擇并在它們的基礎(chǔ)上進(jìn)行拓展，形成更多的選擇策略，分別如下：

ZXY：檢驗(yàn)?zāi)硞€(gè)貨物能否裝載時(shí)，如果當(dāng)前空間集合中有多個(gè)空間結(jié)構(gòu)能夠容納該貨物，則將該貨物裝載在這些可以容納該貨物的裝載空間中屬性location的z值最小的裝載空間中，如果仍存在多個(gè)這樣的裝載空間，則考慮這些裝載空間中x值最小的，如果還存在多個(gè)，則考慮y值最小的.

ZYX，XZY，XYZ三種選擇策略和上述策略類似，只是在選擇裝載空間時(shí)，考慮屬性location的x、y、z順序不一樣.

TouchX：檢驗(yàn)?zāi)硞€(gè)貨物能否裝載時(shí)如果當(dāng)前空間集合中有多個(gè)裝載空間能夠容納該貨物，則計(jì)算該貨物與車廂中已經(jīng)裝載的其它貨物和車廂側(cè)面的接觸面積之和（不包括與車廂底面的接觸面積），選擇接觸面積之和最小的裝載空間來擺放該貨物，但如有多個(gè)這樣裝載空間，則選擇屬性lo-cation中x值最小的一個(gè).

TouchNX，TouchZ，TouchNZ三種選擇策略和上述策略類似，在計(jì)算接觸面積時(shí)，TouchNX不考慮與車型側(cè)面的接觸面積；存在多個(gè)接觸面積最小的裝載空間時(shí)，TouchZ選擇location屬性中z值最小的一個(gè)；TouchNZ不考慮與車型側(cè)面的接觸面積.

MaxFit：假設(shè)貨物的長、寬、高分別為l、w、h，裝載空間屬性shape的長寬高分別為L、W、H，則貨物形狀與裝載空間形狀的匹配值fitness=min(l/L,L/l)·min(w/W,W/w)·min(h/H,H/h).當(dāng)存在多個(gè)裝載空間可以裝載某個(gè)貨物時(shí)，選擇fitness值最大的來裝載該貨物.

3.3 裝載位置選擇

檢驗(yàn)一空間能否裝載某貨物時(shí)，分四種情況，考慮如圖3所示關(guān)鍵點(diǎn)，圖中3、5關(guān)鍵點(diǎn)位置根據(jù)支撐系數(shù)來確定.

圖3 不同情況下的裝載位置Fig.3 Loading position under different occasions

3.4 裝載算法流程

開始（輸入：物品裝載列表itemlist）.

Step 1 按照某一物品排序策略對itemlist進(jìn)行排序.

Step 2 初始化空間集合列表subBinsList（空間集合數(shù)目為n，n為貨物數(shù)目），所有sub-Bins的num屬性均為0.

Step 3 給subBinsList中每個(gè)空間集合加入一個(gè)由車廂本身所構(gòu)成的subBin.

Step 4 依次裝載itemlist中的每一個(gè)物品item.

Step 4.1 依次檢驗(yàn)subBinsList中的每一個(gè)subBins.

Step 4.1.1 將subBins中的subBin按照某一裝載空間選擇策略進(jìn)行排序.

Step 4.1.2 依次檢驗(yàn)subBins中的每一個(gè)subBin

如果當(dāng)前subBin不能裝載當(dāng)前物品item，檢驗(yàn)下一個(gè)subBin.

如果能夠裝載，根據(jù)當(dāng)前物品的擺放位置和當(dāng)前的空間集合對裝載空間進(jìn)行更新；如果當(dāng)前subBins第一次裝載貨物，則將該subBins的num屬性設(shè)為1；轉(zhuǎn)Step 4.

Step 4.2 如果該subBins不能裝載，則檢驗(yàn)下一個(gè)subBins；否則轉(zhuǎn)Step 4.

Step 5 返回subBins中，屬性num為1的空間集合數(shù)量，表示全部裝載完貨物所需車廂數(shù).結(jié)束.

4 算例分析

本文所提出的算法用C#語言在Visual Studio 2008開發(fā)平臺下實(shí)現(xiàn)，算法執(zhí)行的平臺環(huán)境如下：CPU是酷睿2雙核T6500處理器，主頻為2.1GHz，內(nèi)存為2GB，操作系統(tǒng)是Windows7系統(tǒng).

4.1 測試數(shù)據(jù)

本文所使用測試數(shù)據(jù)由Martello等人于2000年提出，下載網(wǎng)址：http://www.diku.dk/～pisinger/codes.html.

該測試數(shù)據(jù)分為八組，先列舉五種數(shù)據(jù)類型（表2中，w、l和h分別表示單個(gè)貨物的寬、長、高，W、L、H分別表示車廂的寬、長、高）.八組數(shù)據(jù)分別如下：

表2 五種數(shù)據(jù)類型Table 2 Five data types

第一組：60%來自類型一，10%分別來自類型二、三、四、五，W=L=H=100；

第二組：60%來自類型二，10%分別來自類型一、三、四、五，W=L=H=100；

第三組：60%來自類型三，10%分別來自類型一、二、四、五，W=L=H=100；

第四組：60%來自類型四，10%分別來自類型一、二、三、五，W=L=H=100；

第五組：60%來自類型五，10%分別來自類型一、二、三、四，W=L=H=100；

第六組 ：w、l和 h隨機(jī) 在[1,10]選 取 ，W=L=H=10；

第七組 ：w、l和 h隨機(jī) 在[1,40]選 取 ，W=L=H=40；

第八組：w、l和h隨機(jī)在[1,100]選取，W=L=H=100.

由于第二、三組數(shù)據(jù)和第一組數(shù)據(jù)類似，這里不再考慮第二、三組數(shù)據(jù).針對其它六組數(shù)據(jù)，貨物數(shù)量分為 50、100、150、200四種情況，共24種組合，每種組合又隨機(jī)產(chǎn)生10組數(shù)據(jù)，一共240套數(shù)據(jù).

4.2 實(shí)驗(yàn)結(jié)果及分析

支撐系數(shù)設(shè)為0.75，即要求每個(gè)貨物的底面至少有75%的面積處于被支撐狀態(tài)，不考慮轉(zhuǎn)向，裝載策略為ZXY時(shí)，各種組合使用車廂數(shù)及車廂總數(shù)如表3所示.

表3 支撐系數(shù)設(shè)為0.75、不考慮轉(zhuǎn)向、裝載策略為ZXYZXY時(shí)計(jì)算結(jié)果Table 3 Loading coefficient=0.75,loading strategy=ZXYZXY,forbid rotation

表3中第一到三列的組、車廂尺寸、貨物數(shù)分別表示第幾組數(shù)據(jù)、車廂長寬高尺寸、貨物數(shù)量；第四到第八列表示高-體積、體積-高、面積-高、高-面積、無排序五種貨物排序策略所使用的車廂數(shù)目平均值（對應(yīng)每一組數(shù)據(jù)，當(dāng)貨物數(shù)量為50、100、150、200四種情況時(shí)，取10套數(shù)據(jù)的平均值）.由表3可知，在不考慮轉(zhuǎn)向，支撐系數(shù)為0.75，裝載策略為ZXY時(shí)，采用體積-高的排序策略結(jié)果最好.

其它幾種裝載策略所使用車廂總數(shù)如表4所示.

表4 支撐系數(shù)設(shè)為0.75、不考慮轉(zhuǎn)向、幾種裝載策略計(jì)算結(jié)果Table 4 Loading coefficient=0.75,forbid rotation,different loading strategies

表4中只列出了各種裝載策略所對應(yīng)的幾種貨物排序策略時(shí)使用車廂數(shù)目總值.由表4可看出，幾種策略均是采用體積-高的貨物排序策略結(jié)果最好，但采用面積-高的貨物排序策略結(jié)果與前者差別不大.同時(shí)由表4還可知道當(dāng)裝載策略為XYZ，貨物排序策略為體積-高時(shí)，所使用車廂總數(shù)為763.4，使用車廂數(shù)目最少.

支撐系數(shù)設(shè)為0.75，考慮轉(zhuǎn)向，裝載策略為ZXY時(shí)，各種組合使用車廂數(shù)及車廂總數(shù)如表5所示.

表5 支撐系數(shù)設(shè)為0.75、考慮轉(zhuǎn)向、裝載策略為ZXYZXY時(shí)計(jì)算結(jié)果Table 5 Loading coefficient=0.75,loading strategy=ZXYZXY,allow rotation

表5中各列的含義和表3相同.由表5可知，在考慮轉(zhuǎn)向，支撐系數(shù)為0.75，裝載策略為ZXY時(shí)，采用體積-高的貨物排序策略結(jié)果最好，但采用面積-高的貨物排序策略結(jié)果與前者差別不大.

考慮轉(zhuǎn)向，裝載策略為ZXY，不同支撐率情況下所使用車廂總數(shù)如表6所示.

表6 考慮轉(zhuǎn)向、裝載策略為ZXYZXY、不同支撐率計(jì)算結(jié)果Table 6 Loading Strategy=ZXYZXY,Allow Rotation,different Loading Coefficient

由表6可知，在考慮轉(zhuǎn)向，裝載策略為ZXY時(shí)，支撐系數(shù)為0.6、0.75時(shí)，采用體積-高的貨物排序策略結(jié)果最好；但支撐系數(shù)為0.9、1時(shí)采用面積-高的貨物排序策略結(jié)果最好.由此可知，當(dāng)對支撐要求越高，采用面積-高的貨物排序策略計(jì)算結(jié)果更加經(jīng)濟(jì).

考慮易碎性情況，假設(shè)0為非易碎，1為易碎，240套數(shù)據(jù)假設(shè)前20%為易碎貨物，后80%為非易碎貨物，考慮轉(zhuǎn)向、裝載策略為ZXY、支撐率為0.75時(shí)，五種貨物排序策略所使用車廂總數(shù)分別為825（高-體積）、785.2（體積-高）、766.1（面積-高）、825（高-面積）、853.4（無排序）.由此可知，在考慮易碎性時(shí)，面積-高的貨物排序策略明顯好于體積-高的貨物排序策略.

4.3 計(jì)算效率及對比分析

在對所有算例進(jìn)行計(jì)算時(shí)，采用不同策略進(jìn)行組合，每套數(shù)據(jù)的平均計(jì)算時(shí)間均不會(huì)超過0.1秒，因此該算法計(jì)算效率較高.

Martello[2]提出基于基本點(diǎn)的構(gòu)造啟發(fā)式算法，且該算法未考慮轉(zhuǎn)向，對其設(shè)計(jì)的標(biāo)桿數(shù)據(jù)進(jìn)行求解，所使用車廂總數(shù)為769.9.由表3和表4可知，對同樣的數(shù)據(jù)集，本文所提出的算法即便考慮了支撐面積的限制，在采用體積-高和面積-高兩種貨物排序方法時(shí)，幾種裝載策略所使用車廂總數(shù)依然比Martello得到的結(jié)果優(yōu).因此可認(rèn)為本文算法計(jì)算結(jié)果達(dá)到較好效果.

5 研究結(jié)論

本文提出了帶支撐面的裝載空間這一概念，并應(yīng)用于三維裝箱問題，結(jié)果表明，相比關(guān)鍵點(diǎn)等思想，本文提出的方法計(jì)算結(jié)果質(zhì)量更高，而且計(jì)算速度快，對于實(shí)際應(yīng)用及后續(xù)的研究有很大的借鑒意義.下一步可以考慮在本文結(jié)果的基礎(chǔ)上用啟發(fā)式算法再進(jìn)行優(yōu)化改進(jìn)，然后集成開發(fā)裝箱軟件，并進(jìn)行三維顯示、報(bào)表輸出，方便物流計(jì)劃.

參考文獻(xiàn):

[1]W?scher G,Hau?ner H,Schumann H.An improved ty?pology of cutting and packing problems[J].European Journal of Operational Research,2007,183(3):1109-1130.

[2]Martello S,Pisinger D,Vigo D.The three-dimensional bin packing problem[J].Operations Research,2000,48(2):256-267.

[3]Faroe O,Pisinger D,Zachariasen M.Guided local search for the three-dimensional bin-packing problem[J].IN?FORMS Journal on Computing,2003,15(3):267-283.

[4]Crainic T G,Perboli G,Tadei R.Extreme point-based heuristics for three-dimensional bin packing[J].Informs Journal on Computing,2008,20(3):368-384.

[5]陳實(shí).帶有三維裝箱能力約束的車輛路徑問題的算法研究[D].中山大學(xué),2008.[CHEN S.Research on algo?rithm for three-dimensional loading capacitated vehicle routing problem[D].Sun Yat-Sen University,2008.]

[6]王磊.車輛路徑與三維裝箱混合問題(3L-CVRP)的研究[D].中山大學(xué),2009.[WANG L.An integrated re?search for the capacitated vehicle routing problem with container loading[D].Sun Yat-Sen University,2009.]

[7]Crainic T G,Perboli G,Tadei R.TS2PACK:A two-level tabu search for the three-dimensional bin packing prob?lem[J].European Journal of Operational Research,2009,195(3):744-760.

[8]Parre?o F,Alvarez-Valdés R,Oliveira J F,et al.A hy?brid GRASP/VND algorithm for two-and three-dimen?sional bin packing[J].Annals of Operations Research,2010,179(1):203-220.

[9]Mack D,Bortfeldt A.A heuristic for solving large bin packing problems in two and three dimensions[J].Cen?tral European Journal of Operations Research,2012,20(2):337-354.

[10]Boschetti M A.New lower bounds for the three-dimen?sional finite bin packing problem[J].Discrete Applied Mathematics,2004,140(1):241-258.