基于混合遺傳算法的多箱型三維裝箱問題研究

周麗，楊江龍，趙俊輝，柳虎威,2，王繁

（1.北京物資學(xué)院 信息學(xué)院，北京 101149；2.首都經(jīng)濟(jì)貿(mào)易大學(xué) 管理工程學(xué)院，北京 100070）

在電商倉(cāng)儲(chǔ)領(lǐng)域中，物品裝箱操作速度高度依賴工作人員的經(jīng)驗(yàn)和熟練程度，新手裝箱的速度非常緩慢，且裝箱方案的空間利用率往往較低，導(dǎo)致成本增加。同時(shí)，電商倉(cāng)儲(chǔ)領(lǐng)域也面臨“無人倉(cāng)”與“智能化”的轉(zhuǎn)型趨勢(shì)，有待突破“人工速度慢，裝箱效率低”的瓶頸。因此研究自動(dòng)化裝箱場(chǎng)景下所需的裝箱方案，設(shè)計(jì)電商倉(cāng)儲(chǔ)領(lǐng)域?qū)嶋H有效的智能裝箱算法，提升裝箱工作效率就迫在眉睫。

以維度劃分裝箱問題是非常常見的一種研究分類方式，主要包括一維裝箱問題[1-2]、二維裝箱問題[3-4]和三維裝箱問題（ 3D Bin Packing Problems,3D-BPP）。

關(guān)于二維裝箱問題（又稱“二維下料問題”）的研究非常豐富，不論是二維鍘刀式背包包裝問題[5]，還是帶切刀約束的二維帶材包裝問題[6]，都要求一組物品必須在不重疊的情況下被打包到一個(gè)二維的箱子中[7-8]。根據(jù)物品形狀不同，二維裝箱問題又可以具體分為規(guī)則物品二維裝箱[5,9]和不規(guī)則物品二維裝箱。關(guān)于二維不規(guī)則物品裝箱問題（Two-Dimensional Irregular Packing Problem, 2DIBPP）的研究，有的涉及到下料問題，要切割的小塊具有不規(guī)則形狀[10]；有的涉及到條形包裝問題，需要在一個(gè)矩形物體內(nèi)放置一組多邊形[11]；還有的研究涉及開放維度的不規(guī)則物品二維裝箱問題[12]，非凸不規(guī)則物品的二維裝箱問題[13-14]，以及均勻多箱不規(guī)則物品的二維裝箱問題[15]。

三維裝箱問題是經(jīng)典的一維和二維裝箱問題的自然推廣，很多研究將三維裝箱問題轉(zhuǎn)化為二維裝箱問題進(jìn)行求解[16]。近年來，在這一問題上的研究和出版物迅速增長(zhǎng)[17]。其中，3D-BPP 進(jìn)一步又可以分為規(guī)則物品的裝箱問題、不規(guī)則物品的裝箱問題。規(guī)則物品的裝箱問題根據(jù)物品和箱子類型多少以及形狀大小的差異，又可分為同構(gòu)裝箱問題（Identical 3D-BPP）和異構(gòu)裝箱問題（Heterogeneous 3D-BPP），與物品分類已經(jīng)引入的問題類別相似，將箱子劃分為相同箱子（identical large objects）、弱異構(gòu)箱子（weakly heterogeneous large objects）和強(qiáng)異構(gòu)箱子（strongly heterogeneous large objects）。其中，“同構(gòu)”是指箱子或物品類型單一且尺寸相同，“異構(gòu)”是指箱子或物品類型多樣且尺寸不同。有學(xué)者研究了單一箱型的三維裝箱問題[18]，也有學(xué)者研究了弱異構(gòu)物品同構(gòu)箱子的三維裝箱問題[19]和考慮了物品強(qiáng)弱異構(gòu)的不同情況[20]。

在結(jié)合實(shí)際情況進(jìn)行三維裝箱的研究方面，有學(xué)者研究了三維切割和包裝問題，強(qiáng)制執(zhí)行非重疊約束[21]，有學(xué)者研究了物流平臺(tái)的集裝箱裝載問題[22-23]。關(guān)于集裝箱裝載問題（Container Loading Problem,CLP），又可以細(xì)分為多集裝箱裝載[24]和零擔(dān)裝載（拼箱）[25]。集裝箱裝載問題[17,20]，在物流規(guī)劃和調(diào)度中扮演重要角色[26]。貨物被包裝成標(biāo)準(zhǔn)集裝箱，以便于用輪船、卡車或鐵路車輛運(yùn)輸[27]，以及航空貨物的三維裝箱問題[28-29]。另外，多集裝箱裝載問題也成為研究的關(guān)注點(diǎn)[30-32]。

由于電商倉(cāng)儲(chǔ)領(lǐng)域包裝箱型號(hào)與物品種類眾多，遠(yuǎn)非現(xiàn)有研究中的個(gè)位數(shù)，且現(xiàn)有研究主要優(yōu)化目標(biāo)為箱子的空間利用率，在裝箱方案計(jì)算時(shí)間上并沒有很苛刻的要求，而這并不能滿足電商倉(cāng)儲(chǔ)領(lǐng)域裝箱實(shí)踐環(huán)節(jié)的時(shí)間要求。綜上，文中基于電商倉(cāng)儲(chǔ)領(lǐng)域裝箱實(shí)踐的具體情境，以提高訂單平均裝載率為主要優(yōu)化目標(biāo)，在兼顧計(jì)算耗時(shí)的現(xiàn)實(shí)條件下，構(gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了啟發(fā)式裝箱規(guī)則，然后通過混合遺傳算法來優(yōu)化物品裝箱方案。

1 多箱型三維裝箱混合整數(shù)規(guī)劃模型

1.1 模型變量假設(shè)

1.1.1 箱子型號(hào)選擇

1.1.2 物品裝箱位置選擇

物品裝載位置選擇的0—1 矩陣P如下：

確定物品裝載方向后，最終裝入箱子時(shí)第i件物品在各個(gè)方向上的尺寸大小分別為：

1.2 裝箱模型構(gòu)建

1.1.3 物品裝箱方向選擇

一件物品在裝箱時(shí)共有6 種方向可供選擇，物品裝箱的不同方向可以用物品在不同維度上長(zhǎng)尺寸表示，見圖2。

圖2 物品裝箱旋轉(zhuǎn)方向示意圖Fig.2 Schematic diagram of rotation direction of article packing

第i件物品裝箱方向0—1 選擇矩陣R如下。

1.2.1 模型優(yōu)化目標(biāo)及約束條件

從電商倉(cāng)儲(chǔ)領(lǐng)域的實(shí)際出發(fā)，通過分析裝箱數(shù)據(jù)發(fā)現(xiàn)，每個(gè)訂單都能被裝入一個(gè)箱子中，因此，文中的問題轉(zhuǎn)變?yōu)?，選擇一個(gè)能夠裝入單個(gè)訂單所有物品的箱子，并使箱子的空間利用率最高。其中，物品不能超出選中箱子的空間范圍，物品與物品之間不能出現(xiàn)空間位置的重疊。暫不考慮物品支撐、物品擠壓、物品區(qū)隔等其他約束條件。

關(guān)于非越界約束，如圖1 所示，只要物品的左后下角和右前上角空間坐標(biāo)，即在x軸、y軸、z軸3個(gè)維度上的值，均在箱子所圍成的三維空間范圍內(nèi)，則物品沒有越界。其中，O為箱子左后下角的坐標(biāo)，即原點(diǎn)；O*為箱子右前上角的坐標(biāo)，Bi**為第i件物品在箱子三維坐標(biāo)系空間中右前上角的坐標(biāo)。

圖1 箱子及物品裝箱空間位置示意圖Fig.1 Schematic diagram of space location of boxes and articles

圖3 物品非重疊情況示意圖Fig.3 Schematic diagram of non-overlapping items

1.2.2 裝箱模型構(gòu)建

以訂單物品裝箱的剩余空間最小為優(yōu)化目標(biāo)，構(gòu)建混合整數(shù)規(guī)劃模型如下。

其中，式（10）為模型的目標(biāo)函數(shù)，優(yōu)化目標(biāo)為訂單裝入箱子后，使剩余空間最??；式（11）至（13）為裝入箱子中每件物品的左后下角坐標(biāo)在箱子尺寸所允許的范圍內(nèi)，式（14）至（16）為箱子中每件物品的右前上角坐標(biāo)在箱子尺寸所允許的空間范圍內(nèi)；式（17）至（25）分別為2 件物品在x軸、y軸、z軸維度上所占據(jù)區(qū)間之間的關(guān)系，式（26）保證2 件物品之間不存在空間重疊；式（27）至（29）規(guī)定了各個(gè)變量的取值范圍。

2 多箱型三維裝箱啟發(fā)式算法設(shè)計(jì)

2.1 裝箱過程模塊啟發(fā)式算子設(shè)計(jì)

本文設(shè)計(jì)了經(jīng)驗(yàn)?zāi)M算法（Empirical Simulation Algorithm，簡(jiǎn)稱ESA），并基于物品裝箱順序選擇模塊和物品裝箱位置選擇模塊對(duì)裝箱方案進(jìn)行優(yōu)化。

物品裝箱順序選擇是指每次選擇即將裝入箱子的SKU 及物品。物品裝箱順序選擇算子集合主要包括物品體積降序選擇算子o1u和物品裝箱順序函數(shù)選擇算子o2u(φu)。o1u的作用是將訂單中的物品按照體積降序依次裝入箱子。o2u(φu)是指，物品的裝箱順序由函數(shù)φu所確定,其目的是通過調(diào)整物品裝箱順序，優(yōu)化物品裝箱策略，提升訂單裝載率。

2.2 多箱型三維裝箱問題啟發(fā)式算法設(shè)計(jì)

2.2.1 啟發(fā)式算法規(guī)則設(shè)定

電商倉(cāng)儲(chǔ)三維裝箱問題啟發(fā)式算法主要包括4個(gè)環(huán)節(jié)：箱子型號(hào)選擇，物品裝箱順序選擇，物品裝箱位置選擇與物品裝箱方向選擇。

1）箱子型號(hào)選擇的啟發(fā)式規(guī)則。計(jì)算每種箱子類型可容納的體積，根據(jù)箱子容積大小從小到大排列。計(jì)算當(dāng)前訂單中所有物品體積總和。從容積大于等于物品體積總和的箱子中容積最小的箱子開始嘗試，如果當(dāng)前選中的箱子能夠裝入所有物品，則停止計(jì)算。否則，繼續(xù)嘗試超過訂單物品總體積的次小箱子繼續(xù)嘗試。以此類推，直到找到合適的箱子為止。

2）物品裝箱順序的啟發(fā)式規(guī)則。選擇優(yōu)先裝入體積較大的物品，然后再依次裝入體積較小的物品，如果在物品裝箱過程中，出現(xiàn)有物品不能裝入當(dāng)前選中的箱子，則更換更大的箱子重新嘗試。

3）物品裝箱位置的啟發(fā)式規(guī)則。物品裝箱位置的選擇與非越界約束和非重疊約束緊密相關(guān)。文中選擇“左后下角”的啟發(fā)式策略，即將在箱子空間中物品的左后下角位置坐標(biāo)作為物品裝載位置的參考，并從箱子本身三維空間的左后下角（即原點(diǎn)）開始進(jìn)行裝箱。

4）物品裝箱方向的啟發(fā)式規(guī)則。物品裝載方向的確定是根據(jù)圖2 中展示的6 種物品方向，依次進(jìn)行物品裝箱嘗試。得到可行的裝箱方向則停止計(jì)算，否則繼續(xù)嘗試剩余物品方向。如果所有的裝箱方向全部進(jìn)行嘗試并且沒有找到可行的情況，則說明當(dāng)前裝載位置不可行。繼續(xù)嘗試其他裝載位置，直到找到可行的裝載位置和裝箱方向，停止計(jì)算。

根據(jù)上述裝箱問題的啟發(fā)式規(guī)則，設(shè)計(jì)多種箱型三維裝箱啟發(fā)式算法的整體結(jié)構(gòu)框架，見圖4。

圖4 多種箱型三維裝箱啟發(fā)式算法框架圖Fig.4 Framework of 3D packing heuristic algorithm for various box types.

2.2.2 裝箱問題的啟發(fā)式算法集合

在裝箱問題過程模塊化的設(shè)計(jì)思路指導(dǎo)下，針對(duì)電商倉(cāng)儲(chǔ)領(lǐng)域的多箱型三維裝箱問題，結(jié)合裝箱過程中各個(gè)環(huán)節(jié)的設(shè)計(jì)以及過程模塊中的算子集合，構(gòu)建了動(dòng)態(tài)復(fù)合塊裝箱的S 類算法。根據(jù)物品裝箱位置選擇方式的不同，將動(dòng)態(tài)復(fù)合塊裝箱的S 類算法分為ESA-SHA-S1 算 法 ， ESA-SHA-S2 算 法 和ESA-SHA-S3 算法。其中，每種算法包含的基本算子集合如表1 所示。

表1 動(dòng)態(tài)復(fù)合塊裝箱的S 類算法算子集合Tab.1 Set of S-class algorithm operators for dynamic composite block packing

3 多箱型三維裝箱問題混合遺傳算法

3.1 裝箱順序優(yōu)化的混合遺傳算法

3.1.1 裝箱順序優(yōu)化的混合遺傳算法基本框架設(shè)計(jì)

在動(dòng)態(tài)復(fù)合塊裝箱的S 類算法基礎(chǔ)上，針對(duì)物品裝箱順序選擇環(huán)節(jié)進(jìn)行優(yōu)化，設(shè)計(jì)裝箱順序優(yōu)化的混合遺傳算法（Hybrid Genetic Algorithm For Packing Sequence Optimization， PSO-HGA）。該算法設(shè)計(jì)的具體內(nèi)容如下。

1）設(shè)計(jì)染色體編碼。本算法染色體采用實(shí)數(shù)編碼，以訂單中SKU 的序列作為編碼對(duì)象，對(duì)物品裝箱順序進(jìn)行排序。通過對(duì)SKU 序列中的元素順序重新排列，可以得到不同的訂單物品裝箱順序，以此作為本算法的單個(gè)染色體編碼。

2）生成初始種群。所設(shè)計(jì)的混合遺傳算法采用最常見的隨機(jī)排序方法。設(shè)種群中包含的染色體的數(shù)量為g，將SKU 序列中的元素隨機(jī)排序g次，得到g個(gè)元素順序不同的染色體，從而形成初始群體。

3）確定適應(yīng)度函數(shù)。該算法將訂單裝載率作為個(gè)體適應(yīng)度，則訂單裝載率的計(jì)算過程為適應(yīng)度函數(shù)。根據(jù)模型，適應(yīng)度函數(shù)可以具體表示為f，則有：

4）進(jìn)行個(gè)體評(píng)價(jià)。根據(jù)種群中染色體信息所確定的物品裝箱順序，在動(dòng)態(tài)復(fù)合塊裝箱的S 類算法框架下，計(jì)算訂單裝載率，可以得到每個(gè)染色體的適應(yīng)度函數(shù)值f。f越大，說明訂單裝載率越高，反之則訂單裝載率越低。

5）設(shè)計(jì)選擇算子。文中設(shè)計(jì)了放大優(yōu)勢(shì)型輪盤賭（Enlarge Advantage Roulette，EAR）算子，即在對(duì)群體適應(yīng)度的值進(jìn)行調(diào)整的基礎(chǔ)上，然后再使用輪盤賭的方式篩選優(yōu)勢(shì)個(gè)體。調(diào)整群體適應(yīng)度的規(guī)則是，在較小的適應(yīng)度值的基礎(chǔ)上增加一個(gè)較小的數(shù)值，在較大適應(yīng)度值的基礎(chǔ)上增加一個(gè)較大的數(shù)值，使得較大適應(yīng)度值對(duì)應(yīng)的個(gè)體有更大的概率被選中。

6）設(shè)計(jì)交叉算子。文中設(shè)計(jì)了“單點(diǎn)交叉，雙位交換”（Single Point Crossing and Double Bit Switching，SPCDBS）算子。首先，將群體中的染色體隨機(jī)分成數(shù)量相同的兩組；其次，然后從每組中隨機(jī)取出1 條染色體組成一個(gè)染色體對(duì)；最后，以一定的交叉概率，對(duì)取出的染色體對(duì)進(jìn)行交叉操作，得到2 條新的染色體，見圖5。

圖5 SPCDBS 算子染色體交叉機(jī)制示意圖Fig.5 SPCDBS schematic diagram of operator chromosome crossover mechanism

7）設(shè)計(jì)變異算子。文中設(shè)計(jì)了“單點(diǎn)變異，隨機(jī)順序”（Single point variation and sequential random，簡(jiǎn)稱SPVSR）算子，即從種群中依次提取每個(gè)染色體，以一定的變異概率對(duì)取出的染色體進(jìn)行變異操作。染色體變異機(jī)制見圖6。

圖6 SPVSR 算子染色體變異機(jī)制Fig.6 SPVSR schematic diagram of operator chromosome variation mechanism

8）迭代終止條件。該模型求解的終止條件綜合考慮最大迭代次數(shù)（T）與訂單裝箱方案平均計(jì)算耗時(shí)2個(gè)因素，以優(yōu)化訂單裝載率為主要目標(biāo)，適當(dāng)放寬計(jì)算耗時(shí)方面的要求。在訂單物品裝箱方案計(jì)算耗時(shí)為分鐘級(jí)的時(shí)間內(nèi)，確定最大迭代次數(shù)作為終止條件。

3.1.2 動(dòng)態(tài)復(fù)合塊裝箱的PSO-HGA 算法

結(jié)合動(dòng)態(tài)復(fù)合塊裝箱的S 類算法中各個(gè)算法的基本算子，可以進(jìn)一步構(gòu)建PSO-HGA 算法系列，具體包括：PSO-HGA-S1 算法、PSO-HGA-S2 算法和PSO-HGA-S3 算法。

其中，PSO-HGA-S1 算法是以ESA-SHA-S1 算法為基礎(chǔ)，用o2u(φu)代替o1u，將混合遺傳算法作為φu函數(shù)，根據(jù)搜索得到的物品裝箱順序，求得更優(yōu)的訂單裝載率。PSO-HGA-S2 算法與PSO-HGA-S3 算法同理。因此，PSO-HGA 算法系列基本上繼承了動(dòng)態(tài)復(fù)合塊裝箱S 類算法的很多優(yōu)點(diǎn)，例如計(jì)算耗時(shí)短，訂單裝載率高，并在適當(dāng)放寬計(jì)算耗時(shí)的條件下，進(jìn)一步優(yōu)化提升裝載率。

3.2 帶有改進(jìn)算子的混合遺傳算法

3.2.1 初始群體優(yōu)選的混合遺傳算法

初始群體優(yōu)選的混合遺傳算法（Hybrid genetic algorithm for initial population optimization，簡(jiǎn)稱IPO-HGA），主要是基于PSO-HGA 算法框架，針對(duì)其中“生成初始種群”的環(huán)節(jié)，不再是采用隨機(jī)策略生成初始種群，而是根據(jù)o1u的規(guī)則，按照物品SKU 的體積進(jìn)行從大到小排序，從而得到染色體信息。將該條由啟發(fā)式規(guī)則得到的染色體信息復(fù)制g次，生成初始群體。

3.2.2 帶鄰域搜索算子的混合遺傳算法

帶鄰域搜索算子的混合遺傳算法（Hybrid genetic algorithm with neighborhood search operator，簡(jiǎn)稱NSO-HGA），是在PSO-HGA 算法中加入鄰域搜索算子NSO，以彌補(bǔ)其局部搜索能力的不足。如圖7 所示，針對(duì)當(dāng)前最優(yōu)染色體的實(shí)數(shù)編碼序列（Co），依次僅交換相鄰2 個(gè)位置的元素所得到的新染色體集合（Cn），記為原染色體的鄰域范圍。計(jì)算新得到的鄰域集合中所有染色體的適應(yīng)度函數(shù)值，并與原有群體中的染色體合并，然后采用EAR 算子選擇得到g個(gè)染色體，從而形成新的群體并應(yīng)用于后續(xù)計(jì)算過程。

圖7 原染色體與鄰域染色體編碼信息變換情況Fig.7 Transformation of coding information between proto chromosome and neighborhood chromosome.

3.2.3 綜合多種算子的混合遺傳算法

綜合多種算子的混合遺傳算法（Hybrid genetic algorithm integrating multiple operators ， 簡(jiǎn) 稱IMO-HGA），還綜合了PSO-HGA 算法，IPO-HGA算法的IPO 算子和NSO-HGA 算法的NSO 算子，將改進(jìn)算子作為o2u(φu)中的φu函數(shù)，其他裝箱方案的計(jì)算環(huán)節(jié)不變。算法之間兩兩組合，得到帶有改進(jìn)算子的混合遺傳算法系列，如表2 所示。

表2 帶有改進(jìn)算子的混合遺傳算法系列Tab.2 Series of hybrid genetic algorithms with improved operator

4 實(shí)例驗(yàn)證與分析

4.1 混合遺傳算法超參數(shù)確定

為了確定混合遺傳算法系列的超參數(shù)設(shè)置，選擇PSO-HGA-S1 算法作為典型代表，將京東企業(yè)裝箱實(shí)踐數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，其中各種箱型包裝箱尺寸信息見表3。文中的研究主要針對(duì)電商的B2B 業(yè)務(wù)領(lǐng)域。與個(gè)人訂單相比，訂單中物品的種類和數(shù)量較多，屬于異構(gòu)性較強(qiáng)的裝箱問題。文中所采用的基本數(shù)據(jù)量為企業(yè)脫敏后的1 000 個(gè)訂單，并在此基礎(chǔ)上以該業(yè)務(wù)場(chǎng)景的訂單統(tǒng)計(jì)特征為依據(jù)，可以生成任意數(shù)量的測(cè)試訂單數(shù)據(jù)集。嘗試不同的超參數(shù)組合，通過計(jì)算實(shí)驗(yàn)最終確定各個(gè)超參數(shù)的取值，在設(shè)定一般取值范圍[33]的基礎(chǔ)上，結(jié)果見表4。

表3 各種箱型包裝箱尺寸信息Tab.3 Size information of various box types mm

表4 混合遺傳算法超參數(shù)設(shè)置情況Tab.4 Super parameter setting of hybrid genetic algorithm.

由計(jì)算實(shí)驗(yàn)結(jié)果可知，遺傳算法參數(shù)確定測(cè)試集的平均訂單裝載率為82.61%，訂單裝箱方案平均計(jì)算耗時(shí)為39.54 s。經(jīng)過108 組參數(shù)組合計(jì)算實(shí)驗(yàn)，最終確定參數(shù)取值，如表5 所示，群體數(shù)量（M）為10，迭代次數(shù)（T）為30，交叉概率（Pc）為0.65，變異概率（Pm）為0.1。

4.2 混合遺傳算法計(jì)算實(shí)驗(yàn)結(jié)果

4.2.1 裝箱順序優(yōu)化的混合遺傳算法實(shí)驗(yàn)結(jié)果

根據(jù)表4 得到的混合遺傳算法超參數(shù)設(shè)置數(shù)值，在JD 數(shù)據(jù)集上采用PSO-HGA 算法系列進(jìn)行計(jì)算實(shí)驗(yàn)，得到計(jì)算結(jié)果見表5。其中，PSO-HGA-S1 算法在訂單平均裝載率指標(biāo)上表現(xiàn)最佳，達(dá)到了70.92%，其他算法雖然略有差距，但整體上都達(dá)到了70%以上的裝載率；另外，在訂單平均計(jì)算耗時(shí)方面，PSO-HGA-S1 的計(jì)算耗時(shí)最短（裝載率也最低）為39.22 s，其他2 個(gè)算法的計(jì)算耗時(shí)都超過了40 s，雖然將訂單裝載方案計(jì)算耗時(shí)控制在了1 分鐘以內(nèi)，但對(duì)于計(jì)算效率要求較高的場(chǎng)景還是存在一定劣勢(shì)。

表5 JD 數(shù)據(jù)集PSO-HGA 算法系列計(jì)算結(jié)果Tab.5 Calculation results of PSO-HGA algorithm series of JD dataset

圖8 JD 數(shù)據(jù)集PSO-HGA 算法系列迭代過程Fig.8 Iterative process of PSO-HGA algorithm series of JD dataset

4.2.2 帶有改進(jìn)算子的混合遺傳算法實(shí)驗(yàn)結(jié)果

在JD 數(shù)據(jù)集上采用帶有改進(jìn)算子的混合遺傳算法計(jì)算訂單實(shí)例的裝箱方案，計(jì)算結(jié)果如表6 所示。其中，IPO-HGA-S1 算法的表現(xiàn)最佳，訂單平均裝載率達(dá)到了70.93%，訂單平均計(jì)算耗時(shí)為40.57 s，與其他帶有改進(jìn)算子的混合遺傳算法相比，計(jì)算耗時(shí)僅略高于IPO-HGA-S3 算法，比其他算法的計(jì)算耗時(shí)均短，并且低于PSO-HGA-S1 算法的訂單平均計(jì)算耗時(shí)。在所有帶改進(jìn)算子的混合遺傳算法中，NSO-HGA 類算法整體表現(xiàn)最差，訂單平均裝載率低于 IMO-HGA 類算法，且訂單平均計(jì)算耗時(shí)高于IPO-HGA 類算法；IPO-HGA 算法雖然有較高的訂單平均裝載率，但是計(jì)算耗時(shí)也是最長(zhǎng)的；IPO-HGA算法的訂單平均計(jì)算耗時(shí)遠(yuǎn)低于NSO-HGA 類算法和IMO-HGA 類算法，并且IPO-HGA-S1 算法與PSO-HGA 算法系列相比，以更短的計(jì)算耗時(shí)得到了更高的訂單平均裝載率。

表6 JD 數(shù)據(jù)集帶有改進(jìn)算子的HGA 算法系列計(jì)算結(jié)果Tab.6 Calculation results of HGA algorithm series with improved operator in JD dataset

另外，NSO-HGA 類算法與IMO-HGA 算法的訂單平均計(jì)算耗時(shí)均超過了 1 min ， 最長(zhǎng)的IMO-HGA-S2 算法更是達(dá)到2 min 以上，主要原因是這兩類算法都采用了NSO 算子對(duì)每次迭代得到的代際最優(yōu)個(gè)體進(jìn)行領(lǐng)域搜索，根據(jù)染色體鄰域搜索編碼信息，NSO 算子的加入相當(dāng)于使每個(gè)迭代步驟增加了 70%的個(gè)體數(shù)量，加上與 EAR、SPCDBS 以及SPVSR 之間的相互作用，因此導(dǎo)致計(jì)算耗時(shí)大幅增加，但是，從迭代過程與最終結(jié)果來看，相較于IPO算子，NSO 算子在提升訂單平均裝載率方面的作用較弱。

圖9 JD 數(shù)據(jù)集JD 數(shù)據(jù)集帶有改進(jìn)算子的HGA 算法系列迭代過程Fig.9 Iterative process of HGA algorithm series with improved operator in JD dataset

5 結(jié)語

文中基于裝箱問題領(lǐng)域已有的研究成果，結(jié)合電商倉(cāng)儲(chǔ)領(lǐng)域的裝箱實(shí)踐問題，提出了多箱型三維裝箱混合整數(shù)規(guī)劃模型。基于空間劃分的思想與物品非重疊非越界約束設(shè)計(jì)啟發(fā)式規(guī)則，針對(duì)多種箱型的三維裝箱問題，設(shè)計(jì)了多種啟發(fā)式算子集合與組合設(shè)計(jì)，提出裝箱過程模塊算法體系，保證了裝箱方案的裝載率與計(jì)算耗時(shí)能夠滿足現(xiàn)實(shí)需要，達(dá)到了秒級(jí)的響應(yīng)速度。

文中研究還有更多可以改進(jìn)的地方，例如，在算法優(yōu)化方面，文中僅對(duì)過程模塊算法體系中的裝箱順序算法環(huán)節(jié)進(jìn)行了智能化改造，對(duì)于多個(gè)算法模塊共同聯(lián)合優(yōu)化由于求解搜索空間過于龐大尚未涉及。后續(xù)研究可以對(duì)不同環(huán)節(jié)的算子進(jìn)行算法優(yōu)化，如物品裝箱位置選擇與物品裝箱方向選擇等，也可以對(duì)于多個(gè)算法模塊共同聯(lián)合優(yōu)化。