侯克金， 袁銳波*， 楊灝泉， 李 煥

(1.昆明理工大學(xué) 機(jī)電工程學(xué)院， 云南 昆明 650500； 2.云南柔控科技有限公司, 云南 昆明 650031)

目前，我國(guó)制造業(yè)正處于基本實(shí)現(xiàn)數(shù)字化網(wǎng)絡(luò)化的上升期，企業(yè)正是數(shù)字化轉(zhuǎn)型與改造的主體，倉(cāng)儲(chǔ)物流的高效管理是建設(shè)智能共享工廠中重要的一步，而自動(dòng)化物流系統(tǒng)中需要解決的關(guān)鍵性難題就有貨物的在線碼垛問(wèn)題[1]。貨物在線碼垛問(wèn)題本質(zhì)上為三維裝箱問(wèn)題(three-dimensional bin packing problem，3D-BPP)，是一種復(fù)雜的空間組合優(yōu)化問(wèn)題，在理論上屬于NP完全問(wèn)題[2]。

三維裝箱由于其廣泛的應(yīng)用領(lǐng)域，國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量深入的研究，主要研究方向?yàn)槟Ｐ偷臉?gòu)建以及現(xiàn)代智能算法的優(yōu)化。在模型構(gòu)建方面,大多學(xué)者采用啟發(fā)式的算法。F.G.Ortman等[3]主要是利用啟發(fā)式、人工智能等方法將裝箱問(wèn)題的布局進(jìn)行優(yōu)化；閻威武等[4]是采用啟發(fā)式算法來(lái)解決實(shí)際問(wèn)題，采用了空間的分割與合并的策略，并且考慮了貨物的裝載方向、重量和卸載位置等約束，選取最優(yōu)裝載方案；張德富等[5]提出了一種有效的復(fù)合塊生成算法和多層塊選擇算法來(lái)搜索最合適的塊進(jìn)行裝載，在填充率上較以往三維裝箱問(wèn)題有所提高；吳蓓等[6]在空間搜索策略方面提出了自適應(yīng)隨機(jī)重力式空間搜索算法。在智能算法優(yōu)化方面：朱向等[7]設(shè)計(jì)了雙層混合遺傳算法對(duì)最優(yōu)方案進(jìn)行求解；李偉等[8]將禁忌搜索算法和遺傳算法相結(jié)合來(lái)解決集裝箱的裝載問(wèn)題；張長(zhǎng)勇等[9]提出了擬人裝載策略，重點(diǎn)考慮了貨物裝載順序以及垛型穩(wěn)定性約束，并且改進(jìn)了標(biāo)準(zhǔn)的遺傳算法，加入適應(yīng)度變換、最優(yōu)保存策略；文獻(xiàn)[10]中張長(zhǎng)勇等基于關(guān)鍵點(diǎn)策略，以改進(jìn)的粒子群算法進(jìn)行空間位置的最優(yōu)解的搜索，空間利用率有了顯著提升。對(duì)于本文中研究涉及的在線裝箱問(wèn)題：2007 年Gerhard等[11]根據(jù)貨物信息是否已知以及貨物碼放是否按照一定順序，將裝箱問(wèn)題分為離線裝箱與在線裝箱；尚正陽(yáng)等[12]將三維問(wèn)題轉(zhuǎn)化為有高度約束的二維問(wèn)題，在大規(guī)?；蛘咝枰诰€快速裝箱時(shí)有較高的適應(yīng)性，但面對(duì)強(qiáng)異構(gòu)型貨物時(shí)有一定的局限性；文獻(xiàn)[13]中張長(zhǎng)勇等對(duì)在線裝箱問(wèn)題提出了一種極值點(diǎn)尋找所有裝箱位置點(diǎn)與模糊算法搜索最佳裝箱點(diǎn)的融合算法，容積率達(dá)到一個(gè)較高的水平。

早期學(xué)者大多專注于離線式裝箱的研究，后續(xù)隨著裝箱要求的不斷提高，需要實(shí)時(shí)在線裝箱，但目前對(duì)于在線式的多規(guī)格貨物的裝箱研究仍然較少。課題組針對(duì)實(shí)際托盤碼垛作業(yè)，首先建立了碼垛問(wèn)題的數(shù)學(xué)模型，提出了實(shí)時(shí)在線的碼放策略，同時(shí)采用混合蟻群算法來(lái)優(yōu)化貨物的碼放位置與姿態(tài)，提高了托盤的空間利用率以及碼垛的效率。通過(guò)建模與仿真，證明了課題組的研究可以預(yù)估貨物的垛型，這也為以后機(jī)器人自動(dòng)化碼垛提供了參考。

1 模型建立

1.1 問(wèn)題描述

托盤碼垛即工業(yè)機(jī)器人將貨物放置到托盤上，此時(shí)物件是由傳送帶實(shí)時(shí)傳送到機(jī)器人附近，所以托盤碼垛問(wèn)題可以視為在線裝箱問(wèn)題，要求裝載算法能夠做到對(duì)貨物進(jìn)行實(shí)時(shí)規(guī)劃布局。

目前大多數(shù)碼垛為同種類貨物的碼垛，為簡(jiǎn)化問(wèn)題,針對(duì)多規(guī)格貨物的碼垛做以下假設(shè)和規(guī)定：①貨物簡(jiǎn)化為質(zhì)量均勻的長(zhǎng)方體且為剛體， 忽略擠壓變形；②貨物的重心在其幾何重心上；③任何2個(gè)貨物之間不能重疊；④根據(jù)實(shí)際貨物情況，規(guī)定貨物可以懸空的底面積；⑤為保證貨物的穩(wěn)定性，整體垛型的重心需在安全范圍之內(nèi)。

1.2 數(shù)學(xué)模型

(1)

(2)

xi≥xj+lj∨xi+li≤xj。

(3)

yi≥yj+wj∨yi+wi≤yj。

(4)

zi≥zj+hj∨zi+hi≤zj。

(5)

(xj+lj)/(xi+li)≤1+e。

(6)

(yj+wj)/(yi+wi)≤1+e。

(7)

zi+hi=zj。

(8)

(9)

T=∑liwihi/[max (xi+li)max (yi+wi)max (zi+hi)]。

(10)

式中，?(i,j)∈{1,2,3,…,n}。

式(1)表示貨物不超過(guò)托盤的承載尺寸范圍；式(2)表示貨物的總質(zhì)量不超過(guò)托盤所能承載的質(zhì)量；式(3)～(5)表示任意2個(gè)貨物i，j之間不可以重疊；式(6)～(8)表示在貨物i上的貨物j可以懸空的范圍；式(9)表示貨物的整體垛型重心在安全范圍內(nèi)；式(10)為目標(biāo)函數(shù)，模型的優(yōu)化目標(biāo)為最大化垛型的空間利用率。

2 碼放策略

2.1 可放置點(diǎn)策略

根據(jù)Crainic T G等[14]、張瑩[15]和Mahvash B等[16]對(duì) “關(guān)鍵點(diǎn)”碼放策略的研究，提出了最優(yōu)放置點(diǎn)的啟發(fā)式算法。

最優(yōu)放置點(diǎn)搜索原理：每當(dāng)1件貨物碼放后，會(huì)覆蓋1個(gè)原來(lái)的最優(yōu)放置點(diǎn)，另外產(chǎn)生3個(gè)可放置點(diǎn)(會(huì)出現(xiàn)假可放置點(diǎn)，需設(shè)置一定規(guī)則去剔除假的可放置點(diǎn))，然后根據(jù)裝載規(guī)則以及下一件貨物的尺寸來(lái)選擇出最優(yōu)的放置貨物的坐標(biāo)點(diǎn)。

詳細(xì)步驟如下：

1) 構(gòu)造用于碼垛的o-xyz三維坐標(biāo)系。

2)裝入第1件貨物。當(dāng)托盤上沒(méi)有貨物時(shí)，有很多可以放置貨物的點(diǎn)，但是此時(shí)有1個(gè)最佳放置點(diǎn)坐標(biāo)為(0,0,0),當(dāng)以此坐標(biāo)為頂點(diǎn)，放入1件貨物后，便覆蓋原最優(yōu)坐標(biāo)點(diǎn)，產(chǎn)生另外3個(gè)可放置的坐標(biāo)點(diǎn)。

3) 放入第2件貨物。第2件貨物的最佳放置點(diǎn)，需要根據(jù)后續(xù)的裝箱規(guī)則得出，此時(shí)覆蓋原最優(yōu)放置點(diǎn)，新產(chǎn)生3個(gè)可放置點(diǎn)。

4) 碼放第3件貨物。此時(shí)如圖1(d)所示，第3件貨物與第1件貨物的右面剛好齊平或者超出，此時(shí)貨物3的右側(cè)可放置點(diǎn)為假點(diǎn)，需要剔除。

圖1 可放置點(diǎn)示意圖

最優(yōu)放置點(diǎn)啟發(fā)式算法是可以很好的契合在線裝箱的條件，實(shí)時(shí)做出碼放的決策，并給出最優(yōu)放置點(diǎn)的坐標(biāo)。

2.2 可放置點(diǎn)坐標(biāo)及范圍

2.2.1 新增可放置點(diǎn)

貨物在滿足可以裝入的情況下，首先可以確定3個(gè)后續(xù)的貨物可放置點(diǎn)坐標(biāo)，理論上分別位于貨物平

行于x軸、y軸、z軸方向上的邊的延長(zhǎng)線上； 其次， 可以確定每個(gè)可放置點(diǎn)的空間范圍。

如圖2所示，假設(shè)尺寸為(li,wi,hi)的貨物i，放在可放置點(diǎn)o處，o點(diǎn)坐標(biāo)為(ox,oy,oz)，則理論上其新增的3個(gè)分別與x軸或y軸或z軸同方向上的可放置點(diǎn)坐標(biāo)計(jì)算方式如下：

圖2 可放置點(diǎn)坐標(biāo)及范圍

(11)

假設(shè)可放置點(diǎn)o點(diǎn)的空間范圍為So，在o點(diǎn)處放置1個(gè)貨物i，則x軸向可放置點(diǎn)的剩余可放置空間為Sx，y軸向可放置點(diǎn)的剩余可放置空間為Sy，z軸向可放置點(diǎn)的剩余可放置空間為Sz，其計(jì)算方式如下：

(12)

分別按照剩余空間的算法進(jìn)行計(jì)算剩余空間范圍。另外，z軸方向比較特殊，由于可以允許貨物部分懸空，因此這里設(shè)置懸空因數(shù)e，表示可以懸空的長(zhǎng)度占底面邊長(zhǎng)的比例。

2.2.2 確定最優(yōu)可放置點(diǎn)

考慮到實(shí)際機(jī)器人作業(yè)情況，貨物碼放的順序一般為先沿著托盤的一條邊，然后鋪滿底面，貨物的高度差不能太大，最后不斷碼高垛型，因此需要改變放置點(diǎn)的優(yōu)先權(quán)，Px>Py>Pz，使其按照機(jī)器人可作業(yè)的方式進(jìn)行。將正要碼放的貨物在每個(gè)放置點(diǎn)試放，并改變不同的擺放姿態(tài)，這里設(shè)置適應(yīng)值函數(shù)來(lái)評(píng)價(jià)可放置點(diǎn)優(yōu)劣。

(13)

式中：Fi為貨物i在每個(gè)可放置點(diǎn)的適應(yīng)值函數(shù)，F(xiàn)i最小時(shí)表示該點(diǎn)為最優(yōu)放置點(diǎn)；st表示為貨物i在左、后、底面的面積，sT為貨物i在左、后、底面所接觸的其他貨物的面積；N(s)表示貨物i在左、后、底面所接觸到的其他貨物數(shù)，1≤N(s)≤3。

3 混合蟻群算法

由于托盤碼垛的可放置點(diǎn)選擇是根據(jù)當(dāng)前貨物擇優(yōu)選擇的，不能進(jìn)行整體空間的合理規(guī)劃，而且后續(xù)可放置點(diǎn)較多時(shí)，難以挑選出最合適的貨物以及最優(yōu)的放置點(diǎn)，因此設(shè)計(jì)了混合蟻群算法來(lái)得到一個(gè)合理的碼放順序以及貨物擺放姿態(tài)。

3.1 算法描述

根據(jù)可放置點(diǎn)尋優(yōu)的策略，同時(shí)借鑒常用的免疫遺傳算法求解三維裝箱問(wèn)題的交叉變異的思路，設(shè)計(jì)混合蟻群算法來(lái)求解該問(wèn)題。因此需要重新定義蟻群算法中的螞蟻含義、信息素和概率轉(zhuǎn)移函數(shù)等特征。

1) 個(gè)體信息，將貨物視為螞蟻，螞蟻數(shù)等于貨物數(shù)。

2) 信息素，螞蟻搜索的信息素設(shè)定為2種，一為貨物的選擇序列，一為貨物的放置姿態(tài)。

3) 概率轉(zhuǎn)移函數(shù)，即為選擇下一件貨物的概率，同樣設(shè)置貨物序列選擇概率函數(shù)和貨物姿態(tài)選擇函數(shù)。

4) 目標(biāo)函數(shù)，以貨物的體積占用率為目標(biāo)函數(shù)。

3.2 基本定義

對(duì)算法的基本初始定義進(jìn)行設(shè)置。

3.2.1 貨物的屬性

定義貨物編號(hào)為ki，其中i∈(1,2,3,…,n),表示第i個(gè)碼放的貨物;貨物的屬性包括兩部分：一為定位屬性，表示為B={xi,yi,zi,li,wi,hi}，(xi,yi,zi)為貨物的定位坐標(biāo)，{li,wi,hi}為其長(zhǎng)寬高；二為貨物的碼放屬性，為U={u1,u2,u3,…,un}，其中ui包括貨物的編號(hào)和放置姿態(tài)，即ui={ki,ri}，ri為放置姿態(tài)，有?i≠j,ki≠kj，即對(duì)任意2個(gè)不同的貨物，其編號(hào)不能相同。

3.2.2 貨物的放置姿態(tài)

每個(gè)待裝貨物i有其放置的姿態(tài)，用ri表示。當(dāng)各個(gè)方向上沒(méi)有約束時(shí)，其放置姿態(tài)有6種，按與托盤的L,W,H分別平行后得到，如下所示：

li∥L,wi∥W,hi∥H,ri=1;

li∥W,wi∥L,hi∥H,ri=2;

li∥H,wi∥W,hi∥L,ri=3;

li∥H,wi∥L,hi∥W,ri=4;

li∥W,wi∥H,hi∥L,ri=5;

li∥L,wi∥H,hi∥W,ri=6。

如果有方向約束，則從其中選出所對(duì)應(yīng)的ri，放置姿態(tài)示意如圖3所示。

圖3 貨物擺放姿態(tài)示意圖

3.2.3 信息素函數(shù)

(14)

式中，τi,j(0)為初始時(shí)刻貨物i到貨物j的信息素。

如果選擇不同的貨物，則信息素增大，有較大的趨勢(shì)選擇另一種貨物，避免出現(xiàn)選到同一個(gè)貨物的情況。

為保證貨物可以順利的放進(jìn)箱體中，首先對(duì)每個(gè)貨物進(jìn)行姿態(tài)分析，即篩選出可以放進(jìn)箱體中的姿態(tài)形式。具體方法為：將貨物做6種姿態(tài)擺放，判斷其是否可以放入箱體中，然后去除不可以擺放的姿態(tài)。

(15)

3.2.4 貨物選擇概率函數(shù)

螞蟻搜索路徑上的信息素以及根據(jù)概率轉(zhuǎn)移公式，通過(guò)輪盤賭法選擇下一個(gè)要碼放的貨物。

t時(shí)刻，螞蟻m在貨物i碼放完成后選擇貨物j的概率轉(zhuǎn)移函數(shù)為：

(16)

(17)

從概率轉(zhuǎn)移公式可以看出，貨物選擇下一個(gè)貨物的概率與貨物選擇的信息素成正比，因此只要經(jīng)過(guò)迭代后，在最優(yōu)的路徑上留下最多的信息素，那么最后則可以得到最優(yōu)的貨物碼放的序列。

3.2.5 姿態(tài)選擇概率函數(shù)

每種貨物不同的姿態(tài)也影響最終的垛型，因此對(duì)于不同姿態(tài)的選擇也設(shè)置了概率函數(shù)。

(18)

3.3 交叉變異

為了尋找出更優(yōu)的解，將當(dāng)代螞蟻搜索得到的解和歷史最優(yōu)解進(jìn)行交叉變異，從而形成3個(gè)解，然后從3個(gè)解中取出最優(yōu)的裝載序列作為本代最優(yōu)的解。為了使交叉變異后得到的其他2個(gè)裝載序列是有效的，則需要使同一個(gè)貨物編號(hào)不能在裝載序列中同時(shí)出現(xiàn)2次。

具體交叉變異操作如下：

3.4 信息素更新

信息素的更新使最終結(jié)果更加偏向于最優(yōu)值。在計(jì)算出螞蟻的路徑(碼垛順序)以及每個(gè)箱子的放置姿態(tài)后，評(píng)選出此時(shí)路徑中最優(yōu)的一個(gè)目標(biāo)結(jié)果。如果當(dāng)代最好結(jié)果比歷史最優(yōu)值大，則選擇該最優(yōu)值為新的最優(yōu)值，更新貨物選擇信息素和貨物姿態(tài)信息素。分別為2種信息素設(shè)置了2個(gè)揮發(fā)系數(shù)，避免某些路徑產(chǎn)生局部最優(yōu)。同時(shí)加入負(fù)反饋更新，即在一條螞蟻路徑不通時(shí)，減少該條路徑上的貨物選擇信息素和姿態(tài)選擇信息素，加快算法收斂速度。

1) 首先，進(jìn)行首選貨物的信息素更新。

(19)

式中：ρ為貨物選擇信息素?fù)]發(fā)系數(shù)，Q為貨物選擇新增的信息素。

2) 后續(xù)貨物選擇信息素更新。

(20)

3) 貨物姿態(tài)信息素更新。

(21)

式中：ρ′為貨物姿態(tài)信息素?fù)]發(fā)系數(shù)，Q′貨物姿態(tài)新增的信息素。

同理，若本代同一種貨物的擺放姿態(tài)和上一代的相同，則使用較小的揮發(fā)系數(shù)，同時(shí)，額外增加下一代相同貨物相同的姿態(tài)的信息素，保證較大概率選取最優(yōu)解的貨物姿態(tài)。

3.5 算法流程

求解該問(wèn)題的混合蟻群的算法流程如下：

1) 首先獲取貨物信息。

2) 初始化蟻群個(gè)數(shù)m、迭代次數(shù)iiter、貨物選擇信息素和貨物姿態(tài)信息素以及它們各自對(duì)應(yīng)的揮發(fā)系數(shù)。

3) 選出初始碼放貨物，然后根據(jù)概率選擇公式，選擇下一件貨物以及其放置姿態(tài)。

4) 判斷是否有剩余箱子，若是，對(duì)貨物選擇和姿態(tài)信息素進(jìn)行負(fù)反饋，跳轉(zhuǎn)到步驟3)；否則，跳轉(zhuǎn)到步驟5)。

5) 在得出一代所有的貨物碼放序列后，選出最優(yōu)的貨物碼垛序列。

6) 判斷是否為歷史最優(yōu)碼垛順序，若不是，則最優(yōu)值不變，跳轉(zhuǎn)到步驟7)更新信息素；否則，更新最優(yōu)值。

7) 更新貨物姿態(tài)和貨物選擇信息素。

8) 判斷是否大于最大迭代次數(shù)，若是，則循環(huán)結(jié)束；否則，返回步驟3)。

9) 輸出最優(yōu)碼放序列。

圖4 混合蟻群算法流程圖

4 實(shí)例測(cè)試分析

為驗(yàn)證混合蟻群算法對(duì)于托盤碼垛問(wèn)題的適用性，實(shí)驗(yàn)數(shù)據(jù)采用云南某公司在實(shí)際托盤作業(yè)中的貨物訂單信息。因?yàn)槠湟话阃斜P碼放的貨物數(shù)量在 24～30件之間，因此，分別選取數(shù)量為25和30的貨物訂單作測(cè)試，25和35件特碼放貨物數(shù)據(jù)如表1和2所示。托盤的尺寸為1 300 mm×1 000 mm，限高1 900 mm，允許承載的質(zhì)量為800 kg。

表1 25件待碼放貨物數(shù)據(jù)

實(shí)驗(yàn)仿真環(huán)境為：CPU為i5-6200U；主頻為2.4 GHz；內(nèi)存為8 GB；操作系統(tǒng)64位Windows10；編程環(huán)境為Python3.8及Visual Studio Code1.59。實(shí)驗(yàn)針對(duì)不同數(shù)量的貨物選擇等量的螞蟻數(shù)，每個(gè)螞蟻分別代表每一種貨物，最大迭代次數(shù)iiter為100，貨物選擇信息素?fù)]發(fā)系數(shù)ρ=0.15，貨物選擇新增的信息素Q=0.30，姿態(tài)信息素?fù)]發(fā)系數(shù)ρ′=0.10，姿態(tài)新增的信息素Q′=0.16，每種數(shù)量的貨物分別測(cè)試5次。

分別運(yùn)用可放置點(diǎn)算法和混合蟻群算法進(jìn)行實(shí)例測(cè)試，測(cè)試的結(jié)果見(jiàn)表3，貨物碼垛仿真效果圖見(jiàn)圖5。從仿真圖中可以很明顯地看出混合蟻群算法所仿真出的垛型，貨物排列緊密，平整性較高，沒(méi)有較大空隙。

圖5 多規(guī)格貨物碼垛仿真圖

由表3數(shù)據(jù)可知：可放置點(diǎn)的算法在碼垛高度上均高于優(yōu)化后的混合蟻群算法的垛型高度；混合蟻群算法可以明顯提高托盤碼垛的空間利用率，可放置點(diǎn)的算法空間利用率在76.45%，優(yōu)化后平均空間利用率在85.46%，平均提高了9.11%；在算法求解時(shí)間上，混合蟻群算法相較于可放置點(diǎn)算法較長(zhǎng)，因?yàn)榛旌舷伻核惴榱藢ふ页龊线m可放置點(diǎn)和貨物而進(jìn)行了迭代，增加了算法運(yùn)行的時(shí)間，但時(shí)間在實(shí)際作業(yè)要求內(nèi)，可以作為參考。

表2 30件待碼放貨物數(shù)據(jù)

表3 多規(guī)格貨物碼垛測(cè)試數(shù)據(jù)

由表3和圖5可知：多規(guī)格貨物的碼垛，可放置點(diǎn)算法可以在較短的時(shí)間內(nèi)仿真出貨物的垛型，但是空間利用率方面有待提高；混合蟻群算法優(yōu)化后，可以使空間利用率提升9.11%，但是算法的求解時(shí)間相較于可放置點(diǎn)算法較高，對(duì)于在線式的裝箱有一定的影響，但在碼垛的可控制范圍內(nèi)，因此混合蟻群算法仍具有較高的適應(yīng)性。

5 結(jié)語(yǔ)

課題組綜合考慮了在線碼垛作業(yè)過(guò)程中的實(shí)際約束，提出了可放置點(diǎn)的裝載策略，并設(shè)置了適應(yīng)度函數(shù)來(lái)選出當(dāng)前最優(yōu)的可放置點(diǎn)。為尋找更合理的碼放方案，加入混合蟻群算法進(jìn)行優(yōu)化，重新定義信息素以及概率轉(zhuǎn)移函數(shù)以解決該問(wèn)題。最后實(shí)例測(cè)試表明，可放置點(diǎn)的算法求解時(shí)間較短，但是最終垛型的空間利用率不高，混合蟻群算法優(yōu)化后，碼垛的空間利用率提升了9.11%，但求解時(shí)間相對(duì)延長(zhǎng)，從最終目標(biāo)看，混合蟻群算法模型仍具有一定的可行性，能夠增加垛型的空間利用率，減少包裝成本，對(duì)在線式貨物碼垛有一定的參考性。

未來(lái)進(jìn)一步研究可以從以下幾個(gè)方面入手：設(shè)定合理的算法中的參數(shù)，加快算法收斂速度，減少算法運(yùn)行時(shí)間；考慮機(jī)械臂的運(yùn)動(dòng)軌跡，使貨物的碼放順序更符合實(shí)際作業(yè)情況。