面向紙板三維裝箱問(wèn)題的剩余空間最優(yōu)算法

王 程,陳正鳴,呂 嘉

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

0 引 言

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

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

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

1 問(wèn)題描述

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

圖1 裝箱示意圖

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

1)C1：?jiǎn)蝹€(gè)紙板約束。紙板為規(guī)則的長(zhǎng)方體，且它的長(zhǎng)、寬、高和重量都在容器所提供的范圍內(nèi)。

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

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

4)C4：紙板的先進(jìn)后出約束?？紤]紙板的卸載順序，后卸載的紙板先進(jìn)行裝箱，先卸載的紙板后裝箱。

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

6)C6：紙板的堆放約束。在堆放紙板時(shí)，考慮紙板的承重級(jí)別，承重級(jí)別弱的紙板不能堆放在承重級(jí)別強(qiáng)的紙板之下。

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

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

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

2 模型建立

設(shè)置相關(guān)的變量和符號(hào)如下：

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

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

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

約束條件：

(1)

(2)

(3)

(4)

或

其中:

i>0,j>0

(5)

(6)

(7)

(8)

(9)

(10)

(11)

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

目標(biāo)函數(shù)：

(12)

(13)

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

3 算法設(shè)計(jì)

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

在進(jìn)行裝箱之前，對(duì)紙板進(jìn)行組合和排序，確定裝箱序列。

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

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

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

圖2 復(fù)合塊示意圖

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

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

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

圖3 紙板和空間的投影

3.2.1 分割方法

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

(a)分割方式1

3.2.2 放置規(guī)則

在放置紙板時(shí)，紙板的底面積與放置空間的底面積越接近，該空間則越先被進(jìn)行放置，且紙板選擇能生成較大子空間的放置方式。設(shè)置放置方式的評(píng)價(jià)公式為：

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

(14)

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

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

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

3.2.3 空間合并

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

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

滿足S1.y1==S2.y2,S1.x1==S2.x2,S1.z1+S1.w1==S2.z2,則可以進(jìn)行合并，如圖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輸入基本信息，包括容器的尺寸和載重量、客戶的位置坐標(biāo)、編號(hào)和所需的紙板編號(hào)；紙板的尺寸、數(shù)量、重量、承重級(jí)別和最大堆碼數(shù)。

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

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

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

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

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

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

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

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

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

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

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

圖7 算法流程

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

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

表1 隨機(jī)算例的設(shè)置

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

表2 計(jì)算結(jié)果

由表2可以發(fā)現(xiàn)：容器在裝載B類物品時(shí)，其體積利用率明顯高于裝載A類物品，因?yàn)锽類物品擁有的體積比較小，較小的空間也能夠得到更好的利用，容器的空間利用率也得到了提高；容器裝載種類數(shù)在較多的A10、B10時(shí)，體積利用率高于裝載種類數(shù)較少的A5、B5，因?yàn)槲锲奉愋偷脑龆嗄芴岣哐b載的靈活性。B類物品的裝載時(shí)間明顯多于A類，在種類數(shù)較多的A10、B10的裝載時(shí)間多于種類數(shù)較少的A5、B5，說(shuō)明裝載時(shí)間受紙板總數(shù)及紙板種類數(shù)的影響，當(dāng)裝載體積小、數(shù)目多的紙板時(shí)，較大的問(wèn)題規(guī)模導(dǎo)致產(chǎn)生較多運(yùn)算時(shí)間，但由于算法運(yùn)算效率高，所有算例的平均耗時(shí)均在30 s以內(nèi)。

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

表3 算法比較結(jié)果

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

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

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

表6 計(jì)算結(jié)果

(a)容器1

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

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

5 結(jié)束語(yǔ)

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