吳 蓓，丁文英，杜彥華，趙 寧

(北京科技大學(xué) 機械工程學(xué)院，北京 100083)

0 引言

多箱型三維裝箱問題(three-Dimensional Multiple Bin-Size Bin Packing Problem, 3D-MBSBPP)的定義為：已知一組數(shù)量有限且三維尺寸不同的待裝載貨物，有一組不同三維尺寸且價值不同的可選箱型，選擇單個或多個箱子在滿足裝載要求的情況下將貨物裝載完畢，使被選擇的箱子總價值最小。3D-MBSBPP比傳統(tǒng)三維裝箱問題更加貼合電商行業(yè)的實際應(yīng)用。隨著電商行業(yè)的發(fā)展，網(wǎng)絡(luò)購物產(chǎn)生的訂單量巨大，在裝載訂單商品的過程中，選擇經(jīng)濟合適的箱型裝載能夠有效減少紙箱成本，以及填充物和膠帶紙等物品的使用量，提高運輸效率。目前大多數(shù)企業(yè)在選箱操作時主要依靠員工經(jīng)驗，很難選到優(yōu)選組合箱型，導(dǎo)致快遞被簽收后，包裝材料大多難以回收，造成大量的包裝垃圾。

3D-MBSBPP是三維裝箱問題中研究較少的一類問題[1]，除了考慮傳統(tǒng)三維裝箱問題中的貨物擺放方式外，還要考慮箱型選擇和貨物分配等?？臻g劃分方法是擺放過程中的關(guān)鍵點之一，三維問題中常用的是三空間劃分法，該方法同時在3個維度上搜索可用空間，然而隨著搜索空間的增多，算法的復(fù)雜性在計算后期會大大增加[2]，通過動態(tài)改變領(lǐng)域可以改進求解結(jié)果[3]。另外，選擇裝載物前，可以通過構(gòu)造同質(zhì)塊或利用一些捆綁策略來有效提高箱子的空間利用率[4-5]。另一種常見的空間劃分方法是分層法，該方法操作簡單，特別適用于同類或相似貨物的裝載[6-7]，同層裝載可看作二維平面問題，二維問題中主要是優(yōu)化平面上的貨物排布[8-9]。然而，在貨物異構(gòu)型強、擺放方向各異的情況下，三維空間上明顯分層容易出現(xiàn)層間利用率低和底面無法支撐的問題，可以通過填充不平整層來提高層間利用率[10]。本文結(jié)合填充不平整的思想，提出重力式空間搜索策略來合理利用不平整空間，選擇裝載空間時需要考慮貨物的支撐問題[11-12]。

在多容器裝箱問題研究中，將對貨物和容器的操作分開，分別討論裝載規(guī)則和容器的選擇，幫助合理使用容器[13-15]，有研究將組合選箱問題看作為揀選和裝箱問題的結(jié)合，先將訂單拆分，分開揀選后裝入不同的箱型[16]。為了更加合理地進行選箱，本文同時考慮容器選擇和裝載規(guī)則。

在最優(yōu)解未知的情況下，與問題的下界比較可以證明算法的優(yōu)劣，合理的下界更具說服力[17-18]。本文以使用箱子總成本最小為目標(biāo)，考慮尺寸、穩(wěn)定性等約束，建立了3D-MBSBPP數(shù)學(xué)模型；同時提出一種模仿重力作用的新空間劃分方法，并針對3D-MBSBPP問題設(shè)計了一種自適應(yīng)隨機算法和一種粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法，通過求解三維裝箱問題算例詳細展示了求解過程及算法的強大功能，使整體空間利用率提高了2.16%，從而驗證了重力式空間搜索策略的有效性和正確性。按照已有文獻中的方法構(gòu)造了3D-MBSBPP算例并求解，證明了自適應(yīng)隨機算法的優(yōu)越性，該研究能夠提高訂單商品的選箱效率，降低電商企業(yè)的包裝使用成本。

1 選箱模型的建立

1.1 問題描述

本文研究3D-MBSBPP的多箱裝載問題，分為箱型選擇和貨物裝載兩個步驟，箱型選擇與貨物裝載有關(guān)，貨物裝載可以看作傳統(tǒng)的裝箱問題。在單箱裝載的情況下，箱型選擇只需要根據(jù)貨物的不同擺放方式用空間利用率來決定；在多箱裝載的情況下，箱型選擇需要考慮貨物的分箱，可以將箱型選擇和貨物裝載同步進行，也可以先將訂單拆分或貨物分類再進行單箱選箱。因此，本文主要解決選擇裝載箱型、貨物分箱、貨物箱內(nèi)擺放3個問題。

客戶訂購的商品一般有種類多、同種商品只有一件、總件數(shù)少的特點，從而導(dǎo)致貨物差異大，增加了人為估計的難度、增加了擺放的復(fù)雜性，難以采用簡單的分層裝載。為了研究方便，將貨物簡化為長方體。電商企業(yè)都有一系列大小規(guī)格不同的紙箱用于裝載訂單商品，其尺寸、載重能力等都不同，一般選箱操作時首要考慮的因素是三維尺寸。目前電商行業(yè)使用的箱型系列并未統(tǒng)一。

1.2 變量及符號說明

已知待裝載貨物和待選箱型，假設(shè)：①將待裝載貨物簡化為長方體，貨物質(zhì)量均勻，重心在幾何中心位置；②箱型已知，數(shù)量不限，不考慮箱子厚度和裝載間隙；③單個貨物的尺寸必須在最大箱型允許的范圍內(nèi)；④裝載的貨物的總體積不能超過箱子的最大容積；⑤貨物不能懸空擺放。

表1所示為本文使用的符號集。

表1 符號集

續(xù)表1

1.3 坐標(biāo)系及擺放方式

計算過程使用坐標(biāo)系，每一個使用的箱子都有單獨的坐標(biāo)系，坐標(biāo)原點為箱子的某一頂點，假設(shè)X，Y，Z分別為箱子的3個維度方向，如圖1所示，對角坐標(biāo)(px1，py1，pz1)(i，s，j(s))和(px2，py2，pz2)(i，s，j(s))分別表示貨物i在放入箱型s中序列號為j(s)的箱子后，在箱子坐標(biāo)系中靠近和遠離坐標(biāo)原點的對角頂點。貨物在箱內(nèi)有6種擺放方向，分別以長寬、長高、寬高平面為底，沿底面方向旋轉(zhuǎn)90°，分別得到另外一種擺放方向，如圖2所示。

每個箱子的的擺放結(jié)果用兩個矩陣表示，一個表達貨物裝入順序和擺放方向，由貨物號和擺放方向代號構(gòu)成，記為A(s，j(s))，j(s)為箱子編號；另一個確定貨物在箱內(nèi)的具體位置，由對角坐標(biāo)(px1，py1，pz1)(i，s，j(s))和(px2，py2，pz2)(i，s，j(s))構(gòu)成，記為B(s，j(s))，每一列對應(yīng)A(s，j(s))中的一行。綜合A(s，j(s))和B(s，j(s))兩個矩陣可以唯一確定每件貨物在不同箱內(nèi)的位置。

1.4 模型

以使用箱子的總價格最低為目標(biāo)，目標(biāo)函數(shù)表示為

(1)

(2)

aik+bik+cik≥1,aik，bik，cik∈{0,1},

i，k=1,2,…,n,i≠k。

(3)

(4)

i=1,2,…,n,j(s)=1,2,…,J(s),

s=1,2,…,S。

(5)

aik=0,bik=0,pz2(k,s,j(s))=pz1(i,s,j(s))；

i，k=1,2,…,n,i≠k,j(s)=1,2,…,J(s),

s=1,2,…,S。

(6)

其中：式(2)表示所有貨物擺放完成后在坐標(biāo)系3個維度方向都不超過箱子尺寸；式(3)表示貨物i和k的空間位置關(guān)系，aik=1表示貨物i在貨物k的左方，即貨物i在X軸方向的坐標(biāo)值小，bik=1表示貨物i在貨物k的后方，即貨物i在Y軸方向的坐標(biāo)值小，cik=1表示貨物i在貨物k的下方，即貨物i在Z軸方向的坐標(biāo)值小；式(4)表示坐標(biāo)在貨物不同擺放方向時，參數(shù)li(mi)，wi(mi)，hi(mi)的計算方式；式(5)表示貨物各邊與箱子各邊平行或正交擺放；式(6)表示保證貨物擺放的物理穩(wěn)定性，假設(shè)貨物k在貨物i下方且k頂面與i底面接觸，則貨物i的重心G必須受到貨物k的頂面支撐，如圖3所示。

2 算法介紹

2.1 自適應(yīng)隨機算法

異構(gòu)型強的貨物如果采用分層裝載，則將導(dǎo)致層間有很多剩余空間。本文提出一種新的重力式空間搜索策略，其弱化“層”的思想，不明顯區(qū)分每一層，通過模仿重力作用進行空間搜索，優(yōu)先選擇較低的支撐平面，以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮整體上各種可能的情況，不需要回溯，大大縮短了計算時間。裝載過程可以看作為從一維到二維再到三維的過程，重力式空間搜索主要在二維和三維方向。

自適應(yīng)隨機算法是建立在重力式空間搜索策略上的一種串行求解算法，在初始裝載過程上具有隨機性，包括初始箱型的選擇和首件裝入貨物的選擇，在已裝載貨物的基礎(chǔ)上選擇新的裝載空間，并動態(tài)更新可選空間集合，根據(jù)即時更新的裝載空間得到候選裝載貨物集合，再根據(jù)最佳貨物選擇規(guī)則得到裝載貨物，擺放時結(jié)合空間和貨物選擇擺放方向，空間與貨物之間相互反饋，自動調(diào)整。

定義集合D為已裝載的貨物集合，D′為剩余待裝載貨物集合，則D∪D′=N0。算法步驟如下：

步驟1輸入裝箱單。獲取待裝載貨物信息及可選箱型信息，初始化集合D=?，D′=N0。

步驟2確定擺放方向規(guī)則。根據(jù)不同規(guī)則確定貨物在箱內(nèi)的擺放方向，貨物共有3種擺放規(guī)則，設(shè)置其優(yōu)先級以應(yīng)對不同裝載情況。在制定貨物擺放方向規(guī)則之前先固定箱子各邊對應(yīng)坐標(biāo)軸的方向，本文規(guī)定箱子的長寬高分別對應(yīng)X，Y，Z軸方向。規(guī)定第一優(yōu)先級規(guī)則為貨物的最長邊擺放在X軸方向，次長邊擺放在Y軸方向，最短邊擺放在Z軸方向，即擺放在各個坐標(biāo)軸方向的貨物邊長為X>Y>Z。如果按照該規(guī)則不能在選擇的平面上擺放，則順延其他規(guī)則。第二優(yōu)先級規(guī)則為Y>X>Z，第三優(yōu)先規(guī)則為Z>X>Y。

步驟3隨機選擇初始箱型。從已有箱型中隨機選擇一種作為初始箱型，用s0表示。

步驟4隨機選擇首件裝入貨物。在未裝載貨物中隨機選定某一類型貨物i第一個裝入，若不能裝下，則轉(zhuǎn)步驟5；否則更新集合D=D+{i}和D′=D′-{i}，轉(zhuǎn)步驟6。

步驟5修復(fù)過程1。選用大一號的箱型s0=s0+1，轉(zhuǎn)步驟4。

步驟6搜索裝載空間。利用重力式空間搜索策略選擇下一個放置平面，轉(zhuǎn)步驟7；若P=?，則轉(zhuǎn)步驟9。

步驟7確定最佳貨物。計算選定裝載平面的剩余裝載空間，在D′中選擇最適應(yīng)當(dāng)前情況的放置貨物(具體見本節(jié)“裝載空間及最佳貨物搜索過程”)，將其編號為{ibest}，更新集合D=D+{ibest}和D′=D′-{ibest}，轉(zhuǎn)步驟8。若無可放置貨物，則轉(zhuǎn)步驟6。

步驟8試裝載。將最佳貨物放入選定的裝載空間，查看剩余貨物情況，D′=?時終止程序，輸出當(dāng)前的裝載方案作為所求解的最佳方案，轉(zhuǎn)步驟11；D′≠?時轉(zhuǎn)步驟7。

步驟9修復(fù)過程2。按照式(7)～式(9)檢查已裝入的貨物整體三個維度的坐標(biāo)，確定是否可以選用更小的箱型。循環(huán)該過程，確定可行的最小s0。

(7)

(8)

(9)

步驟10自動生成新裝箱單。保留s0及其中的擺放箱型作為多箱問題中第一個選用箱子的結(jié)果，剩余貨物集合D′即為新的裝箱單，轉(zhuǎn)步驟3選用下一個新的箱子。

步驟11輸出結(jié)果。

具體流程如圖4所示。

在最佳貨物搜索過程中引入貪婪思想，選擇符合當(dāng)前情況盡可能大的貨物。

(1)一維過程

一維方向的裝載過程沿著X軸方向裝載，按初始規(guī)則在箱型為s的箱子j(s)中裝入第一個貨物，貨物的一條邊與箱邊重合，此時py2(i,s,j(s))=0,i∈D。按照式(10)計算X軸方向箱子的剩余長度spx，如圖5所示。

(10)

在D′中找出滿足約束(11)～(13)的貨物組成候選貨物集合D0。

li(mi)≤spx,i∈D′；

(11)

wi(mi)≤Ws,i∈D′；

(12)

hi(mi)≤Hs,i∈D′。

(13)

集合D0中含有最長邊的貨物即為最佳貨物塊，將其編號為{ibest}，其長寬高分別為lbest，wbest，hbest，則

max{lbest,wbest,hbest}=max{li,wi,hi},

i∈D0。

(14)

按照擺放方向規(guī)則裝入，更新集合D和D′，直到X軸的剩余長度無法裝入任何剩余貨物，轉(zhuǎn)二維方向。二維方向初始候選支撐面Y的坐標(biāo)集合為P={py2(i,s,j(s)),i∈D}。

(2)二維過程

li(mi)≤width,i∈D′；

(15)

py2(a)+wi(mi)≤Ws,i∈D′；

(16)

hi(mi)≤Hs,i∈D′。

(17)

(3)三維過程

li(mi)≤widthx,i∈D′；

(18)

wi(mi)≤widthy,i∈D′；

(19)

pz2(a)+hi(mi)≤Hs,i∈D′。

(20)

在集合D0中找出含有最大面積的貨物即為最佳貨物塊，將其編號為將其編號為{ibest}，其長寬高分別為lbest，wbest，hbest，則

max{lbest×wbest,lbest×hbest,wbest×hbest}

=max{li×wi,li×hi,wi×hi},i∈D0。

(21)

空間搜索流程如圖8所示。裝入第一件貨物后，在X軸方向搜索裝載空間，再選擇最佳貨物塊i裝載。X軸方向裝載不下時，轉(zhuǎn)至二維方向，在已裝載貨物的XZ方向平面上選擇支撐面，得到裝載空間，再選擇最佳貨物塊i裝載。底面裝載不下時，轉(zhuǎn)至三維方向，在已裝載貨物的XY方向平面上選擇支撐面，得到裝載空間，再選擇最佳貨物塊i裝載。

基于重力式空間搜索策略的自適應(yīng)隨機算法具有優(yōu)越性和靈活性，其在空間搜索和算法上進行了如下創(chuàng)新：①不同于常見的分層法和三空間劃分法，在重力式空間搜索策略中，當(dāng)前已擺放貨物的平面均可作為層，貨物和空間的協(xié)同循環(huán)搜索有效利用了貨物擺放產(chǎn)生的廢棄空間；②能夠以當(dāng)前情況為基礎(chǔ)，結(jié)合貪婪思想自動搜索最佳貨物進行裝載，合理分配貨物并自動形成新裝箱單，兩種修復(fù)過程修復(fù)了算法隨機部分的漏洞，提高了產(chǎn)生方案的可行性和優(yōu)越性；③可以根據(jù)實際情況制定不同的擺放方向規(guī)則或結(jié)合多種規(guī)則選擇擺放方向，具有靈活性。

2.2 改進的粒子群算法

(22)

例如，有一組貨物N={1,2,3}，其長寬高li×wi×hi分別為1×1×2，1×2×2，2×2×2，一組待選箱型編號s∈{1,2}，其長寬高Ls×Ws×Hs分別為2×2×2，2×2×4。根據(jù)式(22)求得箱子的部分基因長度r=3，總基因長度為6。基因(3 1 2 1 2 0)表示貨物按編號3，1，2的順序裝載，使用了1，2號兩個箱子。3號貨物裝入1號箱，按照重力式裝載策略，下一個貨物(1號)不能繼續(xù)裝入上一個箱，因此1號貨物裝入2號箱，2號貨物繼續(xù)裝入2號箱。

(1)多樣化變異操作

對于3D-MBSBPP，傳統(tǒng)PSO算法隨機生成的種群得到可行解十分困難，迭代效率很低，為了使算法更加貼合問題，將傳統(tǒng)PSO算法與遺傳算法結(jié)合，執(zhí)行多樣化變異操作，每種變異對問題求解起不同的作用。為使前期盡快搜索到可行解，加入大箱變異操作，設(shè)置變異概率ps1，即有概率ps1使選用的某一箱號增大。建議ps1設(shè)置較大的值，如0.9左右，使算法盡快找到可行解。前期隨著無可行解迭代次數(shù)的增加，動態(tài)增加變異循環(huán)次數(shù)，使多位基因可以同時變異。式(22)得到的基因長度r在絕大多數(shù)情況下大于實際使用箱子的個數(shù)，為得到更好的解，在有可行解的情況下加入減箱變異操作，設(shè)置變異概率ps2，使箱子的部分基因有概率ps2變異為0，建議取值0.3左右。后期為了得到更優(yōu)的解，加入小箱變異操作，設(shè)置變異概率ps3，即有概率ps3使選用的某一箱號減小，建議取值0.3左右。根據(jù)基因進行試裝載后，有些箱型無法裝載下任何貨物，即空箱，這種箱子極大地影響了目標(biāo)值，加入空箱變異操作檢測是否有空箱，并設(shè)置變異概率ps4，使這部分基因有概率ps4變異為0，建議取值0.5左右。貨物裝載順序部分采用隨機互換變異，設(shè)置變異概率ps0隨機交換兩個貨物的裝入順序，建議取值0.1左右。

(2)算法步驟

步驟1輸入裝箱單。獲取待裝載貨物信息和可選箱型信息。

步驟2設(shè)置參數(shù)。包括學(xué)習(xí)因子c1和c2、慣性權(quán)重w、種群大小sizepop、迭代次數(shù)maxgen，以及5種變異概率ps0，ps1，ps2，ps3，ps4。

步驟3生成種群pop。

步驟4計算適應(yīng)度并進行空箱變異。計算過程按照重力式空間搜索策略進行試裝載，若無法完成裝載，則記適應(yīng)值為inf(正無窮大)，否則按照目標(biāo)函數(shù)值Z，即使用箱子的總價格計算。檢查試裝載過程中出現(xiàn)的空箱執(zhí)行空箱變異操作。

步驟5記錄個體最佳gbest和群體最佳zbest。每個個體歷史適應(yīng)值最大的個體為gbest，群體歷史適應(yīng)值最大的個體為zbest。

步驟6根據(jù)最佳個體進行種群更新。個體有概率w保留原基因，有概率c1與gbest交換部分基因，有概率c2與zbest交換部分基因。貨物與箱子兩部分基因分開更新，貨物部分基因要保證不重復(fù)。

步驟7多樣化變異。按規(guī)則進行大箱、小箱、減箱的互換變異操作。

步驟8計算適應(yīng)度。

步驟9更新gbest和zbest，返回步驟6，若達到迭代次數(shù)，則轉(zhuǎn)步驟10。

步驟10輸出結(jié)果。

3 實例分析

3.1 三維裝箱算例

為了證明重力式空間搜索策略的有效性，求解文獻[19]的三維裝箱輸出最大化算例，共30個待裝載長方體，裝載容器為國際標(biāo)準(zhǔn)的20英尺集裝箱，尺寸為2.352×2.388×5.899，單位為m。選擇長方體裝載，目標(biāo)為容器的空間利用率最大。使用重力式搜索策略搜索空間，忽略首件貨物選擇的隨機性。結(jié)果對比如表2所示。

表2 文獻[19]輸出最大化算例的求解結(jié)果對比

使用本文算法提高空間利用率約2.16%，裝載結(jié)果的三維視圖如圖9所示，證明了重力式裝載策略的有效性和優(yōu)越性，為三維裝箱問題提供了新的思路。

3.2 3D-MBSBPP算例

目前尚無關(guān)于3D-MBSBPP的標(biāo)準(zhǔn)算例，按照文獻[20]的方法構(gòu)造算例，比較自適應(yīng)隨機算法和改進PSO算法的性能。具體方法如下：將Martello等構(gòu)造的320個三維裝箱算例根據(jù)尺寸不同范圍劃分為8類，每類算例40個，其中待裝載貨物數(shù)分別為n={50,100,150,200}，每種各10個，數(shù)據(jù)生成器可由鏈接http://www.diku.dk/～pisinger/codes.html獲得。保留三維裝箱算例中待裝載貨物的尺寸數(shù)據(jù)，8類算例分別取n={50,100,150,200}4種情況中的前兩個，共64個算例。待裝載箱型共5種，其三維尺寸隨機在區(qū)間[W/2,W]×[H/2,H]×[D/2,D]內(nèi)取值，W，H，D分別為原問題中箱型的長、寬、高。箱子價值為

(23)

計算結(jié)果用gap表示，

(24)

式中：UB為算法計算的目標(biāo)值結(jié)果；LB為由放松整數(shù)約束的線性規(guī)劃模型計算出的下界值[18]。PSO算法各參數(shù)經(jīng)調(diào)節(jié)對比能得到較好效果的取值如下：ps1=0.9，ps2=0.3，ps3=0.3，ps4=0.5，ps0=0.1，學(xué)習(xí)因子c1=0.8，c2=0.8，慣性權(quán)重w=0.8，種群大小sizepop=80，迭代次數(shù)maxgen=50。兩種算法每個算例運行10次，計算8種類型的gap平均值，如表3所示。圖10所示為改進PSO算法求解n=50的某一算例的適應(yīng)度曲線，圖11所示為自適應(yīng)隨機算法求解n=50的某一算例的三維結(jié)果圖。

表3 兩種算法的計算結(jié)果

由表3可以看出，自適應(yīng)隨機算法求解8類算例的gap值均更小，其平均gap值比PSO算法優(yōu)19.59%，表明結(jié)果與最優(yōu)解的距離更近，求解質(zhì)量更優(yōu)，證明了自適應(yīng)隨機算法求解3D-MBSBPP的優(yōu)越性。

4 結(jié)束語

本文研究訂單貨物選箱背景下的3D-MBSBPP，考慮三維尺寸、物理穩(wěn)定性等約束，以使用箱子總成本最小為目標(biāo)建立了數(shù)學(xué)模型，針對異構(gòu)型訂單貨物的特點提出的模擬重力作用的空間劃分方法是對空間搜索策略的創(chuàng)新，使用重力式空間搜索策略提高了已有三維裝箱算例2.16%的空間利用率，是對剩余空間利用的突破。擺放規(guī)則及有效結(jié)合貪婪思的貨物選擇策略使算法具有自適應(yīng)性，隨機因素和修復(fù)過程提高了解的質(zhì)量。按照已有文獻中的方法構(gòu)造3D-MBSBPP算例，并用兩種算法求解，自適應(yīng)隨機算法比PSO算法的平均gap值優(yōu)19.59%，且具有穩(wěn)定性。3D-MBSBPP在電商行業(yè)的客戶訂單選箱裝箱中有重要應(yīng)用，合理選箱能夠有效節(jié)省紙箱和填充物資源。

在本文研究的基礎(chǔ)上，未來可以從以下方向進行進一步研究：①構(gòu)造同質(zhì)塊，或在裝箱前進行相似塊聚類再進行裝箱；②加入貨物耐壓性、易碎性等其他約束；③進一步消除初始選箱隨機性的影響。