基于混合蟻群算法的貨物碼垛模型研究

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

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

目前，我國制造業正處于基本實現數字化網絡化的上升期，企業正是數字化轉型與改造的主體，倉儲物流的高效管理是建設智能共享工廠中重要的一步，而自動化物流系統中需要解決的關鍵性難題就有貨物的在線碼垛問題[1]。貨物在線碼垛問題本質上為三維裝箱問題(three-dimensional bin packing problem，3D-BPP)，是一種復雜的空間組合優化問題，在理論上屬于NP完全問題[2]。

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

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

1 模型建立

1.1 問題描述

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

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

1.2 數學模型

(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)表示貨物不超過托盤的承載尺寸范圍；式(2)表示貨物的總質量不超過托盤所能承載的質量；式(3)～(5)表示任意2個貨物i，j之間不可以重疊；式(6)～(8)表示在貨物i上的貨物j可以懸空的范圍；式(9)表示貨物的整體垛型重心在安全范圍內；式(10)為目標函數，模型的優化目標為最大化垛型的空間利用率。

2 碼放策略

2.1 可放置點策略

根據Crainic T G等[14]、張瑩[15]和Mahvash B等[16]對 “關鍵點”碼放策略的研究，提出了最優放置點的啟發式算法。

最優放置點搜索原理：每當1件貨物碼放后，會覆蓋1個原來的最優放置點，另外產生3個可放置點(會出現假可放置點，需設置一定規則去剔除假的可放置點)，然后根據裝載規則以及下一件貨物的尺寸來選擇出最優的放置貨物的坐標點。

詳細步驟如下：

1) 構造用于碼垛的o-xyz三維坐標系。

2)裝入第1件貨物。當托盤上沒有貨物時，有很多可以放置貨物的點，但是此時有1個最佳放置點坐標為(0,0,0),當以此坐標為頂點，放入1件貨物后，便覆蓋原最優坐標點，產生另外3個可放置的坐標點。

3) 放入第2件貨物。第2件貨物的最佳放置點，需要根據后續的裝箱規則得出，此時覆蓋原最優放置點，新產生3個可放置點。

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

圖1 可放置點示意圖

最優放置點啟發式算法是可以很好的契合在線裝箱的條件，實時做出碼放的決策，并給出最優放置點的坐標。

2.2 可放置點坐標及范圍

2.2.1 新增可放置點

貨物在滿足可以裝入的情況下，首先可以確定3個后續的貨物可放置點坐標，理論上分別位于貨物平

行于x軸、y軸、z軸方向上的邊的延長線上； 其次， 可以確定每個可放置點的空間范圍。

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

圖2 可放置點坐標及范圍

(11)

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

(12)

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

2.2.2 確定最優可放置點

考慮到實際機器人作業情況，貨物碼放的順序一般為先沿著托盤的一條邊，然后鋪滿底面，貨物的高度差不能太大，最后不斷碼高垛型，因此需要改變放置點的優先權，Px>Py>Pz，使其按照機器人可作業的方式進行。將正要碼放的貨物在每個放置點試放，并改變不同的擺放姿態，這里設置適應值函數來評價可放置點優劣。

(13)

式中：Fi為貨物i在每個可放置點的適應值函數，Fi最小時表示該點為最優放置點；st表示為貨物i在左、后、底面的面積，sT為貨物i在左、后、底面所接觸的其他貨物的面積；N(s)表示貨物i在左、后、底面所接觸到的其他貨物數，1≤N(s)≤3。

3 混合蟻群算法

由于托盤碼垛的可放置點選擇是根據當前貨物擇優選擇的，不能進行整體空間的合理規劃，而且后續可放置點較多時，難以挑選出最合適的貨物以及最優的放置點，因此設計了混合蟻群算法來得到一個合理的碼放順序以及貨物擺放姿態。

3.1 算法描述

根據可放置點尋優的策略，同時借鑒常用的免疫遺傳算法求解三維裝箱問題的交叉變異的思路，設計混合蟻群算法來求解該問題。因此需要重新定義蟻群算法中的螞蟻含義、信息素和概率轉移函數等特征。

1) 個體信息，將貨物視為螞蟻，螞蟻數等于貨物數。

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

3) 概率轉移函數，即為選擇下一件貨物的概率，同樣設置貨物序列選擇概率函數和貨物姿態選擇函數。

4) 目標函數，以貨物的體積占用率為目標函數。

3.2 基本定義

對算法的基本初始定義進行設置。

3.2.1 貨物的屬性

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

3.2.2 貨物的放置姿態

每個待裝貨物i有其放置的姿態，用ri表示。當各個方向上沒有約束時，其放置姿態有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。

如果有方向約束，則從其中選出所對應的ri，放置姿態示意如圖3所示。

圖3 貨物擺放姿態示意圖

3.2.3 信息素函數

(14)

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

如果選擇不同的貨物，則信息素增大，有較大的趨勢選擇另一種貨物，避免出現選到同一個貨物的情況。

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

(15)

3.2.4 貨物選擇概率函數

螞蟻搜索路徑上的信息素以及根據概率轉移公式，通過輪盤賭法選擇下一個要碼放的貨物。

t時刻，螞蟻m在貨物i碼放完成后選擇貨物j的概率轉移函數為：

(16)

(17)

從概率轉移公式可以看出，貨物選擇下一個貨物的概率與貨物選擇的信息素成正比，因此只要經過迭代后，在最優的路徑上留下最多的信息素，那么最后則可以得到最優的貨物碼放的序列。

3.2.5 姿態選擇概率函數

每種貨物不同的姿態也影響最終的垛型，因此對于不同姿態的選擇也設置了概率函數。

(18)

3.3 交叉變異

為了尋找出更優的解，將當代螞蟻搜索得到的解和歷史最優解進行交叉變異，從而形成3個解，然后從3個解中取出最優的裝載序列作為本代最優的解。為了使交叉變異后得到的其他2個裝載序列是有效的，則需要使同一個貨物編號不能在裝載序列中同時出現2次。

具體交叉變異操作如下：

3.4 信息素更新

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

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

(19)

式中：ρ為貨物選擇信息素揮發系數，Q為貨物選擇新增的信息素。

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

(20)

3) 貨物姿態信息素更新。

(21)

式中：ρ′為貨物姿態信息素揮發系數，Q′貨物姿態新增的信息素。

同理，若本代同一種貨物的擺放姿態和上一代的相同，則使用較小的揮發系數，同時，額外增加下一代相同貨物相同的姿態的信息素，保證較大概率選取最優解的貨物姿態。

3.5 算法流程

求解該問題的混合蟻群的算法流程如下：

1) 首先獲取貨物信息。

2) 初始化蟻群個數m、迭代次數iiter、貨物選擇信息素和貨物姿態信息素以及它們各自對應的揮發系數。

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

4) 判斷是否有剩余箱子，若是，對貨物選擇和姿態信息素進行負反饋，跳轉到步驟3)；否則，跳轉到步驟5)。

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

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

7) 更新貨物姿態和貨物選擇信息素。

8) 判斷是否大于最大迭代次數，若是，則循環結束；否則，返回步驟3)。

9) 輸出最優碼放序列。

圖4 混合蟻群算法流程圖

4 實例測試分析

為驗證混合蟻群算法對于托盤碼垛問題的適用性，實驗數據采用云南某公司在實際托盤作業中的貨物訂單信息。因為其一般托盤碼放的貨物數量在 24～30件之間，因此，分別選取數量為25和30的貨物訂單作測試，25和35件特碼放貨物數據如表1和2所示。托盤的尺寸為1 300 mm×1 000 mm，限高1 900 mm，允許承載的質量為800 kg。

表1 25件待碼放貨物數據

實驗仿真環境為：CPU為i5-6200U；主頻為2.4 GHz；內存為8 GB；操作系統64位Windows10；編程環境為Python3.8及Visual Studio Code1.59。實驗針對不同數量的貨物選擇等量的螞蟻數，每個螞蟻分別代表每一種貨物，最大迭代次數iiter為100，貨物選擇信息素揮發系數ρ=0.15，貨物選擇新增的信息素Q=0.30，姿態信息素揮發系數ρ′=0.10，姿態新增的信息素Q′=0.16，每種數量的貨物分別測試5次。

分別運用可放置點算法和混合蟻群算法進行實例測試，測試的結果見表3，貨物碼垛仿真效果圖見圖5。從仿真圖中可以很明顯地看出混合蟻群算法所仿真出的垛型，貨物排列緊密，平整性較高，沒有較大空隙。

圖5 多規格貨物碼垛仿真圖

由表3數據可知：可放置點的算法在碼垛高度上均高于優化后的混合蟻群算法的垛型高度；混合蟻群算法可以明顯提高托盤碼垛的空間利用率，可放置點的算法空間利用率在76.45%，優化后平均空間利用率在85.46%，平均提高了9.11%；在算法求解時間上，混合蟻群算法相較于可放置點算法較長，因為混合蟻群算法為了尋找出合適可放置點和貨物而進行了迭代，增加了算法運行的時間，但時間在實際作業要求內，可以作為參考。

表2 30件待碼放貨物數據

表3 多規格貨物碼垛測試數據

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

5 結語

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

未來進一步研究可以從以下幾個方面入手：設定合理的算法中的參數，加快算法收斂速度，減少算法運行時間；考慮機械臂的運動軌跡，使貨物的碼放順序更符合實際作業情況。