王 程,陳正鳴,呂 嘉

(河海大學物聯(lián)網(wǎng)工程學院,江蘇 常州 213022)

0 引 言

瓦楞紙板由于綠色環(huán)保、可再生以及具備較好的緩沖功能等優(yōu)勢，被廣泛用于包裝領域，是現(xiàn)代包裝領域中用的最多的包裝材料，中國也是瓦楞紙板的最大產(chǎn)量國。紙板生產(chǎn)企業(yè)除了在生產(chǎn)工藝上進行改善優(yōu)化，還要在配送環(huán)節(jié)中避免產(chǎn)品損失。如果裝載利用率過低，會使企業(yè)的運輸成本大大增加。同時，因為不合理的裝配或者擠壓，容易發(fā)生變形和損壞，從而會影響瓦楞紙板的質量，造成浪費和經(jīng)濟損失。所以在保證最大容積裝載的同時，減少在物流運輸過程的損失也是紙板生產(chǎn)企業(yè)所面臨的重要挑戰(zhàn)之一。

三維裝箱問題是研究多種多樣的紙板在滿足約束的情況下，被裝入到某個容器中去，以達到容器的空間利用率最大或使用數(shù)目最小等目的，是廣泛地存在于實際生活中的復雜組合優(yōu)化問題。針對不同的情況和需求，學者們提出了不同的求解算法。Huang等[1]提出了一種應用在三維裝箱領域上的擬人穴度算法；Eley[2]提出了同構塊的概念，實現(xiàn)了一種啟發(fā)式樹搜索的算法；那日薩等[3]通過空間切割實現(xiàn)裝箱體積利用率最大，提出了一種啟發(fā)式搜索法；尚正陽等[4]將三維問題轉化為帶有高度約束的二維問題，不需要預處理和最優(yōu)解的搜索，提出了一種高效的啟發(fā)式剩余空間最優(yōu)化算法；李孫寸等[5]通過隨機放置和局部調整逼近最優(yōu)解，提出了一種多元優(yōu)化的算法；張德富等[6]基于塊裝載的思想，生成復合塊，提出了一個高效求解三維裝箱問題的多層啟發(fā)式搜索算法；何鯤等[7]對求解三維裝箱問題的穴度算法的基礎進行了改進，提出了基于動作空間的確定性高效率求解算法。在求解考慮基本約束的三維裝箱問題上，以上的研究都實現(xiàn)了很好的裝載效果。但是針對于實際應用上的約束考慮較少，且部分算法求解速度較慢，計算復雜度較高。

因此，本文以容器空間利用率最高和使用數(shù)目最少為目標，考慮紙板裝箱過程中遇到的多個實際約束，建立一個三維裝箱問題的多目標模型，提出一種基于剩余空間最優(yōu)和實際約束的快速算法對其進行求解。

1 問題描述

本文將裝箱問題定義為，把n種數(shù)量有限的規(guī)則的紙板完全裝入一種尺寸為L×W×H的長方體容器A中，M和V分別作為容器A的額定載重量和容積，ni、li×wi×hi、mi分別作為第i種紙板的數(shù)量、尺寸和重量。求將所有紙板都裝入容器中，并實現(xiàn)容器的空間利用率最大和使用數(shù)目最小的目標，并滿足多種多樣的現(xiàn)實約束，并建立如圖1所示的空間直角坐標系。

圖1 裝箱示意圖

在裝載紙板之前，為方便計數(shù)和打包，先將同類紙板按照一定的張數(shù)打包成捆。本文在裝載紙板時，考慮的瓦楞紙板實際上是一捆紙板形成的紙板集合塊，且紙板在實際的裝箱中約束條件如下：

1)C1：單個紙板約束。紙板為規(guī)則的長方體，且它的長、寬、高和重量都在容器所提供的范圍內。

2)C2：紙板的擺放方向約束。放置紙板時，保持與容器邊緣平行，擺放方向采用水平方向上的2種。

3)C3：紙板的穩(wěn)定性約束。在放置紙板時，不能將其懸空。

4)C4：紙板的先進后出約束。考慮紙板的卸載順序，后卸載的紙板先進行裝箱，先卸載的紙板后裝箱。

5)C5：紙板的合并裝載約束。同一客戶的紙板要進行合并裝載，并放置在容器中的相鄰位置。

6)C6：紙板的堆放約束。在堆放紙板時，考慮紙板的承重級別，承重級別弱的紙板不能堆放在承重級別強的紙板之下。

7)C7：紙板的最大堆放層數(shù)約束。紙板在堆放時，為了防止其變形和擠壓，限制紙板不超過最大堆放層數(shù)進行堆放。

8)C8：容器約束。裝載在容器內的紙板的總體積和總重量必須不大于容器的額定容積和載重量。

本文根據(jù)上述約束條件建立模型并設計裝箱規(guī)則。

2 模型建立

設置相關的變量和符號如下：

1)Lk,Wk,Hk,Mk,Vk分別表示容器k的長、寬、高、載重量和體積；(Xk,Yk,Zk)表示k的重心坐標；k為容器的編號(k=1,2,3,…,k)；(a′k,a″k),(b′k,b″k),(c′k,c″k)表示k的重心范圍。

2)(pt,qt)表示客戶t的坐標，可計算得到客戶與配送中心的距離dt；t為客戶的編號(t=1,2,3,…,t)。

基于多種實際約束的三維裝箱模型見式(1)～式(13)。

約束條件：

(1)

(2)

(3)

(4)

或

其中:

i>0,j>0

(5)

(6)

(7)

(8)

(9)

(10)

(11)

其中，式(1)～式(4)表示單個紙板約束C1，紙板的尺寸和重量不能超過容器允許的范圍；式(5)和式(6)表示紙板的擺放方向約束C2，即紙板的擺放方式只有水平方向的2種；式(7)表示紙板的穩(wěn)定性約束C3，當紙板b放在紙板i上時，其底面積要不大于紙板i的底面積，放置時不懸空；式(8)表示紙板堆放約束C6，當紙板b放在紙板i上時，紙板i的承重級別不小于紙板b；式(9)表示紙板的最大堆放層數(shù)約束C7，表示紙板的堆放層數(shù)不能超過紙板本身的最大堆放層數(shù)；式(10)和式(11)表示容器約束C8，紙板的總體積和總重量不能超過容器的容積和載重量。

目標函數(shù)：

(12)

(13)

式(12)表示容器的容積利用率最大；式(13)表示容器的裝箱率函數(shù)，N為使用容器的個數(shù)，F(xiàn)k為容器k所裝載紙板的總體積，Vk為容器的額定體積。

3 算法設計

3.1 裝箱序列的確定規(guī)則

在進行裝箱之前，對紙板進行組合和排序，確定裝箱序列。

1)考慮紙板先進后出約束(C5)，根據(jù)客戶所在位置計算出客戶與公司的距離，根據(jù)距離遠近確定裝載順序，距離遠的優(yōu)先級高于距離近的優(yōu)先級，則先進行裝載。屬于同一客戶的紙板，考慮其底面積和承重級別，對紙板進行從大到小的排序，這樣能有效地提高一定的空間利用率。

2)考慮紙板組合裝載約束(C4)，并滿足紙板最大堆放層數(shù)約束(C7)，按照相同的擺放方向將同類紙板進行堆放組合，同時紙板在裝載前，生產(chǎn)企業(yè)會將紙板以一定的張數(shù)打包成捆，以捆為單位，生成復合塊，將其視為一種新的待裝載物品；客戶的不同類紙板裝載在相同的容器，并保持裝載位置相鄰。

根據(jù)以上規(guī)則，對待裝載的紙板貨物序列進行處理優(yōu)化，生成符合規(guī)則的裝箱序列。復合塊示意圖如圖2所示。

圖2 復合塊示意圖

3.2 剩余空間最優(yōu)化算法(RSO算法)

本文將三維裝箱問題看作是一種帶有高度約束的二維裝箱問題進行求解。當紙板進行裝載放置時，首先要考慮紙板在容器中如何擺放，得到一個合適的放置位置；其次，要考慮放置紙板后，所在空間如何進行分割并被劃分為子空間。

當紙板被放入某一個空間中，為提高空間的利用率，需要空間分割后生成的較大子空間越大越好。在放置紙板時，觀察其底面所在的平面，將分割后的子空間投影到二維平面上，分割方式有圖3(a)～圖3(d)這4種。由圖3可知，當紙板以圖3(d)放置和空間以圖3(d)分割時，所產(chǎn)生子空間S3的底面積最大，從而所在的空間體積也最大。所以如圖3(d)所示的紙板放置位置和空間分割方式最佳，這樣既可以提高后面較大紙板的放置幾率，也可以減少由于空間太小造成的浪費。

圖3 紙板和空間的投影

3.2.1 分割方法

按照上文的裝載布局方法，空間的分割方式采用能生成較大子空間的方式。當紙板放入容器后，其車廂的容器將會被劃分為如圖4所示的剩余空間，如圖4(a)和圖4(b)所示的3個子空間S1、S2、S3，計算比較圖4(a)和圖4(b)中最大子空間S3的底面積大小，選擇底面積較大的分割方式。

(a)分割方式1

3.2.2 放置規(guī)則

在放置紙板時，紙板的底面積與放置空間的底面積越接近，該空間則越先被進行放置，且紙板選擇能生成較大子空間的放置方式。設置放置方式的評價公式為：

f(bi,Sj)=-(l(Sj)-l(bi)+α)?(w(Sj)-w(bi)+α)

(14)

其中，l(Sj)、w(Sj)分別表示放置空間的長和寬，l(bi)、w(bi)分別表示紙板放入時底面積的長和寬，α是被賦值為0.1的修正參數(shù)。放置紙板時，選擇評價度高的放置方式。

根據(jù)公式(14)，如圖5所示，圖5(b)和圖5(c)的放置是優(yōu)于圖5(a)的，因為紙板的底面積和空間的底面積更加接近。由于圖5(c)中紙板的擺放方式能夠產(chǎn)生較大的子空間，f(bi,Sj)的值更高，所以選為紙板的放置方式。當l(Sj)-l(bi)或者w(Sj)-w(bi)為0時，加入修正參數(shù)α能保證按評價規(guī)則仍能夠選出更好的紙板放置方式。

(a)規(guī)則1 (b)規(guī)則2 (c)規(guī)則3

3.2.3 空間合并

在分割空間時，會出現(xiàn)有剩余子空間相鄰的情況，將其合并后實際上能夠裝下一個體積較大的紙板，但因為這2個子空間被分割開，算法將會認為無法裝下。為解決這一問題，引入了相鄰剩余空間合并的方法：將2個相鄰且相鄰邊分別相等的子空間合并為一個更大的子空間，或是將2個相鄰但僅有一條相鄰邊相等的子空間進行重新分割，判斷重新分割后得到的2個空間是否相對原子空間更滿足剩余空間最優(yōu)化策略。若滿足這一策略，則接受重新分割后得到的子空間，否則保留原子空間。

若空間S1,S2滿足S1.y1==S2.y2，S1.z1==S2.z2，S1.x1+S1.l1==S2.x2，則可以進行合并，如圖6(a)所示。

滿足S1.y1==S2.y2,S1.x1==S2.x2,S1.z1+S1.w1==S2.z2,則可以進行合并，如圖6(b)所示。

滿足S1.z1==S2.z2，S1.x1+S1.l1==S2.x2，S1.y1≠S2.y2，則將空間重新分割為S1(x1+x2,y1,z1)和S2(x2,y2-y1,z2)，如圖6(c)所示。

(a)合并方式1

3.3 算法流程

本文算法步驟如下：

Step1輸入基本信息，包括容器的尺寸和載重量、客戶的位置坐標、編號和所需的紙板編號；紙板的尺寸、數(shù)量、重量、承重級別和最大堆碼數(shù)。

Step2根據(jù)3.1節(jié)設定的裝箱序列確定規(guī)則，先對客戶的紙板進行組合和排序，根據(jù)優(yōu)先級排序，生成裝箱序列。

Step3選取容器，初始化容器的空間列表，未裝載之前，空間列表里只有一個空間，且數(shù)量為1。

Step4判斷容器里的紙板數(shù)和紙板總數(shù)是否相等，若相等，則執(zhí)行下一步。

Step5按照裝箱序列，依次取出一個紙板，按照以下策略裝載到容器中去。

Step5.1對紙板的尺寸、質量進行判斷，是否超出容器的范圍，若超出，將紙板加入Errors列表中，并返回Step4中選擇下一紙板，否則執(zhí)行下一步。

Step5.2計算當前紙板在所有放置狀態(tài)下的評價度，形成評價度集合。

Step5.3判斷容器中是否存在某個剩余空間可以放入該紙板，若能放入，則以評價度最高的狀態(tài)進行放置，并將該紙板加入到該容器的裝載紙板列表中；若不能放入，判斷裝箱序列的個數(shù)和容器個數(shù)是否相等，若相等則新建一個裝箱序列，將紙板加入，否則直接將紙板加入新的紙板序列中。

Step5.4對裝入紙板的該空間按照分割方法進行分割，生成新的子空間，并刪除原空間，把子空間加入到空間列表中去，更新容器空間列表。

Step5.5對相鄰的剩余空間進行合并或重新分割，按照空間的高度和體積大小進行排序，更新容器空間列表；跳轉到Step5，繼續(xù)選擇下一紙板。

Step6當遍歷完裝箱序列中的紙板后，若容器中裝載的紙板數(shù)和紙板總數(shù)不相等時，說明還有紙板未裝載，取Step5.3中新生成的裝箱序列，繼續(xù)執(zhí)行Step3，直至當所有容器里的紙板數(shù)和紙板總數(shù)相等的時，完成所有裝載，并返回裝箱結果。

本文算法流程如圖7所示。

圖7 算法流程

4 實驗與結果

本文基于Eclipse開發(fā)平臺，采用Java語言實現(xiàn)算法，采用Three.js三維可視化工具進行裝箱結果的可視化展示。由于針對實際約束的三維裝箱問題沒有統(tǒng)一的標準數(shù)據(jù)進行對比實驗，故本文先采用隨機生成算例方式在驗證模型與算法時，其參數(shù)設置同文獻[3]一致，具體如表1所示。

表1 隨機算例的設置

表1中的L、W、H表示容器的尺寸，取L=W=H，尺寸為1000 mm和2000 mm這2種，容器的最大載重量分別為1000 kg和2000 kg。對A類物品，生成種類數(shù)為5和10 的算例A5和A10，B類物品同理，每種類型各10組，物品的尺寸根據(jù)表1中的選取區(qū)間產(chǎn)生，共計80組算例。每種物品的數(shù)量在區(qū)間[1,?L/l×?W/w×?H/h]內隨機產(chǎn)生(紙板的長、寬、高分別為l，w，h)，每個物品的重量為5 kg。設定隨機算例組不考慮先進后出約束(C4)和組合裝載約束(C5)，計算結果如表2所示。其中Vol，Time，BoxNum，CgNum依次表示容器的平均空間利用率、算法的平均計算時間、使用的平均容器數(shù)和每個容器裝載的平均物品數(shù)。

表2 計算結果

由表2可以發(fā)現(xiàn)：容器在裝載B類物品時，其體積利用率明顯高于裝載A類物品，因為B類物品擁有的體積比較小，較小的空間也能夠得到更好的利用，容器的空間利用率也得到了提高；容器裝載種類數(shù)在較多的A10、B10時，體積利用率高于裝載種類數(shù)較少的A5、B5，因為物品類型的增多能提高裝載的靈活性。B類物品的裝載時間明顯多于A類，在種類數(shù)較多的A10、B10的裝載時間多于種類數(shù)較少的A5、B5，說明裝載時間受紙板總數(shù)及紙板種類數(shù)的影響，當裝載體積小、數(shù)目多的紙板時，較大的問題規(guī)模導致產(chǎn)生較多運算時間，但由于算法運算效率高，所有算例的平均耗時均在30 s以內。

對比文獻[3]算法中不考慮優(yōu)先級約束，考慮承重級別約束的實驗結果，由表3可以看出，整體上，本算法在容器的空間利用率要優(yōu)于文獻[3]算法，但由于使用的隨機算例具有不確定性，所以也存在空間利用率低于文獻[3]算法的情況；并且在運算效率方面，本文提出的算法更優(yōu)，其計算復雜度遠小于O(2n2)。

表3 算法比較結果

為進一步驗證本文算法的有效性，取某公司的實際客戶需求數(shù)據(jù)和紙板的基礎信息數(shù)據(jù)進行分析。實際算例中，采用的容器為集裝箱的國際標準尺寸5870 mm×2330 mm×2200 mm，額定載重量為1500 kg?？蛻魯?shù)據(jù)信息如表4所示，x軸和y軸分別表示客戶所在的地區(qū)與公司在x軸和y軸上的距離，可計算得到客戶到公司的距離，從遠到近依次為(2，1，5，3，4)；紙板數(shù)據(jù)信息如表5所示，紙板以捆計數(shù)，每一捆紙板的張數(shù)為50張，表5紙板的高為每捆紙板的高度；計算結果如表6所示，紙板的放置結果如圖8所示。

表4 客戶需求數(shù)據(jù)

表5 紙板的基礎數(shù)據(jù)信息

表6 計算結果

(a)容器1

由表6可以看出，241捆紙板均全部裝入了2個容器中去，且容器的空間利用率均達到了91%以上；容器1裝載了客戶(2，1)，其紙板裝載順序為(1，4，3，6，2)，如圖8(a)所示；容器2裝載了客戶(5，3，4)，其紙板裝載順序為(8，9，5，6，2，7，10)，如圖8(b)所示。滿足距離遠的客戶優(yōu)先級相對較高，則先進行裝載，距離近的客戶優(yōu)先級相對較少，則后進行裝載；同一客戶中底面積大且承重級別大的紙板優(yōu)先級高，先裝載，客戶的所有紙板保持相鄰位置裝載，紙板的堆放層數(shù)均不超過最大堆放層數(shù)。

從計算結果可以看出，該算法不僅實現(xiàn)了多種實際約束，而且能快速進行求解，實現(xiàn)了容器空間利用率最高和使用數(shù)目最少的目標。

5 結束語

為滿足紙板三維裝箱中遇到的多種實際約束，本文建立了一個求解該裝箱問題的多目標規(guī)劃模型，提出了基于剩余空間最優(yōu)和實際約束的算法。隨機算例數(shù)據(jù)和實際數(shù)據(jù)都驗證了模型的準確性和算法的有效性，而且實現(xiàn)了容器空間利用率最高和使用數(shù)目最少的目標，并且能在較短的時間內完成求解得到裝箱方案，滿足紙板生產(chǎn)企業(yè)的需求。未來研究中，將算法運用到實際裝箱系統(tǒng)的開發(fā)中去，建立一個三維裝箱可視化的系統(tǒng)以供相關企業(yè)進行應用。