用于倉儲物流的工業(yè)機器人碼垛算法

張 濤

上海發(fā)那科機器人有限公司 上海 201906

1 研究背景

在現代工業(yè)物流自動化領域中，使用機器人來進行碼垛裝箱、拆垛搬運已經成為一種高效、快捷的方式［1-4］。機器人技術的應用［5-6］是企業(yè)間相互競爭和未來發(fā)展的重要因素，托盤碼垛技術已成為高效物流的關鍵技術之一。

對于托盤碼垛技術，國內外學者進行了大量研究［7-9］，但大多集中在單一尺寸物料方面，而對于多尺寸物料的場景，雖也有少部分研究［10-12］，但模型卻較為簡單，使用條件有限。筆者結合實際物流自動化領域碼垛應用的需要，從新的角度對機器人混箱碼垛問題展開探討。針對多貨品不同尺寸的混箱碼垛場景，基于各種箱子和托盤的尺寸，設計了一種工業(yè)機器人碼垛算法，能分析出最佳的碼垛序列。

2 混箱碼垛問題

2.1 混箱碼垛定義

混箱碼垛指面對多個尺寸不同的箱子，需要計算出如何選擇最多的箱子碼放在固定的托盤上，并保證碼垛整齊。碼垛工作將由工業(yè)機器人來完成。

定義一個托盤，其長度為L，寬度為W，需要在托盤上盡可能多地擺放各種不同尺寸的箱子。以某電商的托盤為例，其長度固定為1 200 mm，寬度為1 000 mm，托盤自身高150 mm，可擺放的最大高度為1 350 mm。所有箱子的長寬尺寸在200 mm×200 mm至600 mm×600 mm的范圍內，高度不確定。

所有可抓取箱子的尺寸通過上位機傳給機器人，機器人根據所有箱子的尺寸，完成垛型的規(guī)劃，并進行碼垛。

2.2 混箱碼垛約束條件

為了實現將盡可能多的箱子搬運至托盤內，在算法設計時，需滿足以下約束條件：

（1）擺放至托盤上的箱子不得超出托盤的邊界；

（2）擺放至托盤上的箱子不得發(fā)生重疊；

（3）擺放至托盤上的箱子應盡可能貼著托盤邊存放；

（4）擺放至托盤上的箱子，其長邊與短邊應與托盤邊界平行；

（5）擺放至托盤上的箱子只有兩種姿態(tài)，箱子的長邊與托盤的長邊平行，或箱子的長邊與托盤的短邊平行，不得出現傾倒或傾斜擺放的現象；

（6）底層箱子放滿后，上層箱子落位在底層箱子上，依次類推，最大高度不得超出限制。

2.3 集合定義

定義所有可抓取的n個箱子的集合S＝｛S1，S2，S3，…，Sn｝，對應編號集合I＝｛1，2，3，…，n｝。每個Si（i∈I，Si表示第i個箱子）都具備自己的屬性，如長度Li、寬度Wi、高度Hi及原始位置的旋轉角Ri，Ri＝0或90°。為方便計算，定義所有箱子的長度不小于寬度。計算完成之后，每個Si又會產生新的屬性，如順序Oi、坐標Pi、層級Qi等。

3 算法模型

要建立針對混箱碼垛的工業(yè)機器人碼垛算法模型，并尋求最優(yōu)的垛型，對底層碼垛規(guī)則的定義尤為重要?，F對托盤進行區(qū)域劃分，如圖1所示，劃成若干個區(qū)域，并建立坐標系。

圖1 坐標系

定義托盤長邊方向為X軸，短邊方向為Y軸。對于區(qū)域1，選擇集合｛Si｝中箱子占地面積最大的那一個，如Sa（1≤a≤n，且a∈Z），占用整塊區(qū)域1，且Sa長邊放在X軸方向，短邊放在Y軸方向。

對于其它區(qū)域，分別建立最優(yōu)化模型，并加上約束條件，來求取最優(yōu)解。例如，對于區(qū)域2，其長度為L－La，其中L為托盤長度，La為落位在區(qū)域1中箱子Sa的長度。為使區(qū)域2的長邊能擺放更多的箱子，且保證區(qū)域2內的箱子盡可能整齊，將所有箱子｛Si｝的長和寬合并成一個集合C＝｛Ci，j｝，其中j＝1或2，且Ci，1＝Li，Ci，2＝Wi。此外，定義已經完成落位的箱子的編號集合為D，并定義尚未落位的箱子的編號集合為E，且E＝I－D。例如，當5號箱子落位在區(qū)域1之后，D＝｛5｝，E＝｛1，2，3，4，6，7，…，n｝；再當3、7、10號箱子落位在區(qū)域2之后，D＝｛3，5，7，10｝，E＝｛1，2，4，6，8，9，11，12，…，n｝；依次類推。隨著箱子在各區(qū)域上的落位，集合D會發(fā)生變化，同時E也會發(fā)生變化，因此集合D和集合E不是固定元素的集合。

根據托盤和所有箱子的尺寸，可以判斷沿區(qū)域2的X方向擺放的箱子數量范圍為1～4個。區(qū)域2箱子的擺放可橫放，旋轉角為0°，也可豎放，旋轉角為90°，所以計算能擺放在區(qū)域2內的箱子的總長時，需同時考慮使用每個箱子的Li或Wi來計算，并記錄旋轉角。

建立區(qū)域2最優(yōu)化模型如下為：

式中：p＝1，2，3，4；j＝1，2；ik∈E；Ap為區(qū)域2的X方向擺放了p個箱子以后剩余的長度；Bp為區(qū)域2擺放了p個箱子之后，Y方向各箱子的最大尺寸差，其值越小，說明箱子擺放得越整齊；g為各箱子之間需要留出的間隙；Cik，j為從尚未落位的箱子集合E中取出一個箱子，編號為ik，且1≤k≤p，當j＝1時，Cik，j＝Lik，Cik，3－j＝Wik，當j＝2時，Cik，j＝Wik，Cik，3－j＝Lik。

按照如圖2所示計算流程，最終可輸出一組最優(yōu)化結果。值得注意的是，每個箱子間需留有一定的間隙，即參數g，g需要提前設定，作為已知的參數。即使g發(fā)生1 mm的變化，計算出來的最優(yōu)化結果也會發(fā)生改變。

當區(qū)域2內的箱子落位之后，其區(qū)域尺寸就確定了，記錄各ik和j的值，并更新集合D和E。下面進行區(qū)域3的規(guī)劃，在進行區(qū)域3規(guī)劃之前，需要先考慮區(qū)域6的情況。由于區(qū)域1～區(qū)域5內箱子擺放的不確定性，在進行區(qū)域6規(guī)劃的時候需考慮如圖3所示的幾種情形。

圖2 計算流程

為避免箱子之間可能存在的干涉，在進行區(qū)域3計算時需加上一個額外的限制條件，即 max｛Cik，3－j｝≤La。如此，可避免情形B和情形D的出現，進行區(qū)域6規(guī)劃的時候只需考慮情形A和情形C。

考慮邊界條件，區(qū)域3在Y方向的尺寸應小于W－Wa，且根據箱子及托盤的尺寸，可以判斷區(qū)域3 Y方向擺放的箱子數量范圍為1～3個。

建立區(qū)域3最優(yōu)化模型為：

式中：p＝1，2，3；j＝1，2；ik∈E。

計算出最優(yōu)的ik和j之后，區(qū)域3的箱子就可以落位了，同時記錄j的值以判斷落位時是否需要旋轉90°，并更新集合D和E。

區(qū)域4、區(qū)域5的箱子也可采用相同的方法，最后剩下托盤中心的區(qū)域6。

對于區(qū)域6，首先計算其X方向和Y方向的尺寸，然后選擇兩者中較大的那一個作為長邊，采用類似區(qū)域2的最優(yōu)化算法，最后針對剩下的空間，如仍有大于150 mm×150 mm的空間，則可以再次在沒有落位的箱子中選取合適的箱子。

整個過程需要五六次最優(yōu)化建模及求解。為縮短求解時間，如有m個尺寸相同的箱子，則在計算時只有4個箱子參與，其它箱子不進入計算搜索范圍。

圖3 區(qū)域6情形

通過求解，將會使托盤區(qū)域內存放的箱子數量最多，從而使托盤平面上箱子的占有率最大。在求解結果時，當一個箱子落位后，應在集合Si中刪除。所得最優(yōu)解不僅確定了托盤上箱子的數量，而且確定了每個箱子在托盤上的存放位置。

以上是底層碼垛的方法，對于高層碼垛，由于底層箱子高度可能參差不齊，因此無法將高層的箱子同時落位在底層多于1個箱子之上。對于高層碼垛，將底層箱子的上表面作為一個區(qū)域，再使用最優(yōu)化算法對高層箱子進行落位，例如，將區(qū)域1的箱子Sa作為底層箱子，其上表面的尺寸將作為高層碼垛優(yōu)化算法的邊界條件。

建立高層最優(yōu)化模型為：

4 應用舉例

4.1 同尺寸箱子

上述設計的算法，不僅適用于混裝的不同尺寸箱子，而且適用于同尺寸箱子。對于全都是400 mm×300 mm×350 mm的箱子，設置間隙為3 mm。使用所設計的算法，可得到最優(yōu)化結果如圖4～圖7所示。

圖4 同尺寸箱子底層碼垛平面圖

圖5 同尺寸箱子底層碼垛立體圖

圖6 同尺寸箱子二層碼垛立體圖

按照區(qū)域1～區(qū)域6的算法，數字1～8為箱子的落位順序。三層箱子高度為1 050 mm，未超過總高1 200 mm的限制條件。

圖7 同尺寸箱子更高層碼垛立體圖

4.2 不同尺寸箱子

在混箱碼垛例子中，共有50種可被碼垛的不同尺寸的箱子，見表1。

按照所述算法，表1中碼垛了27個箱子，沒有落位順序的另外23個箱子沒有辦法存放在同一個托盤上。計算結果如圖8～圖11所示。所生成的混箱碼垛序列和每個箱子的位置可以發(fā)送給機器人，由機器人來完成碼垛作業(yè)。

圖8 不同尺寸箱子底層碼垛平面圖

圖9 不同尺寸箱子底層碼垛立體圖

4.3 間隙分析

由于間隙的不同，所產生的的結果也會不同，間隙分別設置為2 mm、3 mm、4 mm時所產生的計算結果依次如圖12、圖13、圖14所示。

表1 混箱尺寸

圖10 不同尺寸箱子二層碼垛立體圖

圖11 不同尺寸箱子更高層碼垛立體圖

圖12 間隙2 mm時計算結果

圖13 間隙3 mm時計算結果

比較間隙為2 mm、3 mm、4 mm時的優(yōu)化計算結果，可以發(fā)現雖然順序的前幾個箱子編號相同，但放第六個箱子時，編號已經不同了，這說明間隙對優(yōu)化的順序影響是很大的。另外，間隙2 mm的條件下，只能放25個箱子，但這并不能說明2 mm間隙時箱子放得少這種結果不是最佳的。這是因為間隙小時，需填充的各區(qū)域面積會變大，所選擇的箱子尺寸也就會大，這樣可能會減少能夠選擇的箱子數量。因此，需要根據實際情況來決定間隙值，而不是根據能擺放的總數來決定。

圖14 間隙4 mm時計算結果

5 結語

針對在倉儲物流行業(yè)中出現的混箱碼垛問題，設計了一種工業(yè)機器人碼垛算法。通過算法，對托盤進行區(qū)域劃分，在每個區(qū)域中分別建立最優(yōu)化模型，計算出最優(yōu)解，最終生成整個托盤的碼垛序列及碼垛位置，為工業(yè)機器人的實際碼垛提供了指令，實現了工業(yè)機器人碼垛的智能化。