基于重力裝載的自適應(yīng)隨機(jī)算法求解多箱型三維裝箱問(wèn)題

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

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

0 引言

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

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

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

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

1 選箱模型的建立

1.1 問(wèn)題描述

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

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

1.2 變量及符號(hào)說(shuō)明

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

表1所示為本文使用的符號(hào)集。

表1 符號(hào)集

續(xù)表1

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

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

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

1.4 模型

以使用箱子的總價(jià)格最低為目標(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個(gè)維度方向都不超過(guò)箱子尺寸；式(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í)，參數(shù)li(mi)，wi(mi)，hi(mi)的計(jì)算方式；式(5)表示貨物各邊與箱子各邊平行或正交擺放；式(6)表示保證貨物擺放的物理穩(wěn)定性，假設(shè)貨物k在貨物i下方且k頂面與i底面接觸，則貨物i的重心G必須受到貨物k的頂面支撐，如圖3所示。

2 算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)

(8)

(9)

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

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

具體流程如圖4所示。

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

(1)一維過(guò)程

一維方向的裝載過(guò)程沿著X軸方向裝載，按初始規(guī)則在箱型為s的箱子j(s)中裝入第一個(gè)貨物，貨物的一條邊與箱邊重合，此時(shí)py2(i,s,j(s))=0,i∈D。按照式(10)計(jì)算X軸方向箱子的剩余長(zhǎng)度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中含有最長(zhǎng)邊的貨物即為最佳貨物塊，將其編號(hào)為{ibest}，其長(zhǎng)寬高分別為lbest，wbest，hbest，則

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

i∈D0。

(14)

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

(2)二維過(guò)程

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

(15)

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

(16)

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

(17)

(3)三維過(guò)程

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

(18)

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

(19)

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

(20)

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

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

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

(21)

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

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

2.2 改進(jìn)的粒子群算法

(22)

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

(1)多樣化變異操作

對(duì)于3D-MBSBPP，傳統(tǒng)PSO算法隨機(jī)生成的種群得到可行解十分困難，迭代效率很低，為了使算法更加貼合問(wèn)題，將傳統(tǒng)PSO算法與遺傳算法結(jié)合，執(zhí)行多樣化變異操作，每種變異對(duì)問(wèn)題求解起不同的作用。為使前期盡快搜索到可行解，加入大箱變異操作，設(shè)置變異概率ps1，即有概率ps1使選用的某一箱號(hào)增大。建議ps1設(shè)置較大的值，如0.9左右，使算法盡快找到可行解。前期隨著無(wú)可行解迭代次數(shù)的增加，動(dòng)態(tài)增加變異循環(huán)次數(shù)，使多位基因可以同時(shí)變異。式(22)得到的基因長(zhǎng)度r在絕大多數(shù)情況下大于實(shí)際使用箱子的個(gè)數(shù)，為得到更好的解，在有可行解的情況下加入減箱變異操作，設(shè)置變異概率ps2，使箱子的部分基因有概率ps2變異為0，建議取值0.3左右。后期為了得到更優(yōu)的解，加入小箱變異操作，設(shè)置變異概率ps3，即有概率ps3使選用的某一箱號(hào)減小，建議取值0.3左右。根據(jù)基因進(jìn)行試裝載后，有些箱型無(wú)法裝載下任何貨物，即空箱，這種箱子極大地影響了目標(biāo)值，加入空箱變異操作檢測(cè)是否有空箱，并設(shè)置變異概率ps4，使這部分基因有概率ps4變異為0，建議取值0.5左右。貨物裝載順序部分采用隨機(jī)互換變異，設(shè)置變異概率ps0隨機(jī)交換兩個(gè)貨物的裝入順序，建議取值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計(jì)算適應(yīng)度并進(jìn)行空箱變異。計(jì)算過(guò)程按照重力式空間搜索策略進(jìn)行試裝載，若無(wú)法完成裝載，則記適應(yīng)值為inf(正無(wú)窮大)，否則按照目標(biāo)函數(shù)值Z，即使用箱子的總價(jià)格計(jì)算。檢查試裝載過(guò)程中出現(xiàn)的空箱執(zhí)行空箱變異操作。

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

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

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

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

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

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

3 實(shí)例分析

3.1 三維裝箱算例

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

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

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

3.2 3D-MBSBPP算例

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

(23)

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

(24)

式中：UB為算法計(jì)算的目標(biāo)值結(jié)果；LB為由放松整數(shù)約束的線性規(guī)劃模型計(jì)算出的下界值[18]。PSO算法各參數(shù)經(jīng)調(diào)節(jié)對(duì)比能得到較好效果的取值如下：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。兩種算法每個(gè)算例運(yùn)行10次，計(jì)算8種類型的gap平均值，如表3所示。圖10所示為改進(jìn)PSO算法求解n=50的某一算例的適應(yīng)度曲線，圖11所示為自適應(yīng)隨機(jī)算法求解n=50的某一算例的三維結(jié)果圖。

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

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

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

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

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