神州金庫系統中的裝箱算法

神州控股

龔志峰

神州金庫作為科捷自有研發(fā)系統，為客戶(hù)提供B2B/B2C全供應鏈提供一體化服務(wù)，可前端訂單接入、中端訂單數據處理（OMS、BMS、WMS、TMS等）、大數據處理等，亦可對接智能化設備。通過(guò)全國倉包材使用情況統計，發(fā)現B2C業(yè)務(wù)裝箱問(wèn)題比較突出，一是：包材選用不合理，人工裝箱時(shí)沒(méi)有邏輯規則概念，導致每年該部分損耗嚴重；二是：箱材的選用影響效率，且準確率低。裝箱問(wèn)題在倉儲物流行業(yè)也是普遍存在的難題，紛紛進(jìn)行裝箱算法研究。據網(wǎng)上的公開(kāi)信息，阿里對裝箱問(wèn)題進(jìn)行的研究，其物流算法統計，平均可以減少5%的包裝，2017年雙十一發(fā)貨量超過(guò)10億件，可節省4500多萬(wàn)個(gè)箱子。推行菜鳥(niǎo)電子面單替代傳統三聯(lián)面單，阿里電商平臺上商家使用率已經(jīng)達到80%，每一年節約紙張費用達12億元?？平菀劳猩裰萁饚鞂υ摲矫娴膯?wèn)題進(jìn)行了不斷的研究和探索。

01

關(guān)于三維裝箱問(wèn)題主要從以下幾個(gè)方面進(jìn)行探討

三維裝箱問(wèn)題算法：

裝箱工人在裝箱過(guò)程中需要對訂單的商品選擇箱型，評估商品體積和箱子容積的正確比例，這一過(guò)程極其耗費資源，給倉庫作業(yè)帶來(lái)困難的同時(shí)還降低了作業(yè)效率。其次，所送商品會(huì )出現裝箱不合理的情況，如，顧客只是買(mǎi)一款體積很小的商品，收到的確是一個(gè)很大很空的箱子，浪費資源的同時(shí)，也給用戶(hù)帶來(lái)困惑，同時(shí)零售商的專(zhuān)業(yè)性也遭到了質(zhì)疑。

三維裝箱規則：

1) 所有箱子均視為標準的長(cháng)方體或者正方體。長(cháng)寬高為內圍長(cháng)寬高。

2) 所有商品均描述為矩形，長(cháng)寬高為外圍長(cháng)寬高。

3) 裝箱時(shí)，優(yōu)先放置大件商品。如果大件商品放不滿(mǎn)的情況下，考慮次小商品，直到放滿(mǎn)為止。

4) 裝箱時(shí)，優(yōu)先選擇容積小的箱子。容積更小的箱子如果能夠裝下商品，則剩余容積會(huì )更小，說(shuō)明箱子更適合商品。其次優(yōu)先選擇常規指數最大的箱子（值越大越常規，值越小表示是非常規箱型甚至是特型箱）。

5) 如果訂單中的商品恰好已經(jīng)裝完，箱子未滿(mǎn)，嘗試更換容積更小的箱子。如果爆箱則換回原來(lái)的箱型。

6) 如果訂單中的商品恰好已經(jīng)裝完，出現爆箱，嘗試更換小一號箱子，后繼續裝箱剩余商品。如果此時(shí)箱子已經(jīng)是最小，則更換成多個(gè)箱子裝箱。

7) 將箱型按照容積從小到大的順序排列。如果箱子裝不滿(mǎn)優(yōu)先嘗試小的箱型。

8) 箱子優(yōu)先放置大件商品，然后放置次大商品，最后放訂單中最小的商品。

9) 如果所有的箱子都不能一個(gè)箱子裝下單個(gè)訂單內的全部商品，才會(huì )啟用多個(gè)箱子來(lái)裝商品。

對一次裝箱過(guò)程進(jìn)行了分解，每次需要一個(gè)商品和一個(gè)空箱子，同時(shí)會(huì )產(chǎn)生三塊新的更小的剩余空間。這三塊剩余空間又可以看作是新的箱子。和新的合適自己的空間大小的商品去匹配。

那么，這就是一個(gè)遞歸算法，方法輸入一款商品和一個(gè)箱子，每一次遞歸都會(huì )產(chǎn)生三個(gè)新的箱子，新的箱子又可以裝入其它更小的商品。

如此循環(huán)往復，直到每一個(gè)新的箱子連最小的商品都裝不下了，或者沒(méi)有任何商品可以裝進(jìn)箱子里了，這個(gè)過(guò)程就會(huì )自動(dòng)結束。這是遞歸的出口條件。

02

目前使用較多的算法

1) Heuristic Algorithm啟發(fā)式演算法：工業(yè)應用，時(shí)間短。用于在合理時(shí)間內找到可接受的擺放方式（結果）。

2) Exact Methods精準算法：學(xué)術(shù)應用，用于研究Global Optimality，Solution Error Bound。最早的數學(xué)編程模型，混合整數線(xiàn)性規劃模型，但是，利用整數規劃解決問(wèn)題不太現實(shí)，計算量太大不好實(shí)現，很難用線(xiàn)性的求解器去精準解決非線(xiàn)性的問(wèn)題

3) Three-dimensional open-dimension rectangular packing probloems(3D-ODRPP)。

3D-ODRPP算法詳解：

a) box_selection：選出所有箱子中最小體積的那個(gè)；輸入：所有箱子體積；輸出：輸出已打包物品清單，找到的最小箱型；pack_boxes：判斷單個(gè)箱子打包所有物品；輸入：?jiǎn)蝹€(gè)箱子體積；輸出：輸出已打包物品清單。

b) pack_boxes：判斷單個(gè)箱子打包所有物品；輸入：?jiǎn)蝹€(gè)箱子體積；輸出：輸出已打包物品清單；insert_items_into_dimensions：將需要打包的物體塞進(jìn)給定體積；輸入：剩余長(cháng)方體體積，需要打包物品，已打包物品；輸出：剩余長(cháng)方體體積（更新），需要打包物品（更新），已打包物品（更新）。

c) insert_items_into_dimensions：將需要打包的所有物體塞進(jìn)給定體積；輸入：剩余長(cháng)方體體積，需要打包物品，已打包物品；輸出：剩余長(cháng)方體體積（更新），需要打包物品（更新），已打包物品（更新）。best_fit：將需要打包單個(gè)物體放進(jìn)給定體積并給出最好切割方法；輸入：給定長(cháng)方體體積，物品體積；輸出：剩余長(cháng)方體體積，三個(gè)長(cháng)方體。

03

針對以上算法進(jìn)行算法測試設計

對比1：和僅考慮總體積的情況比較。僅考慮體積篩選會(huì )選出一些箱型會(huì )擺放不開(kāi)的小箱子，進(jìn)行篩選和比較。例：物體體積小但特別長(cháng)。

對比2：和僅考慮總體積+能容納所有物體三邊的情況比較。此種篩選會(huì )篩選掉因為物體過(guò)長(cháng)而放不進(jìn)去的小箱子，依然會(huì )選出些擺放不下所有物體的小箱子。例：物體形狀平均但因為位置關(guān)系擺放不下。

對比3：先和Ortools的結果對比。因為Ortools跑出來(lái)的結果不夠理想，起碼要比Ortools的表現好。從良品鋪子物品清單和沈陽(yáng)良品-包材維護中抽取隨機訂單，訂單長(cháng)度（0-6個(gè)）。（因為一般的訂單大小都在這個(gè)范圍內）看看生成的箱型是否比Ortools的小一些。

04

真實(shí)數據測試

選用200個(gè)出庫運單，每個(gè)運單對應一個(gè)箱子，箱子中物體從1到21不等。數據來(lái)源沈陽(yáng)良品庫，9個(gè)箱型。已刪除0體積物品（贈品海報一類(lèi)）。無(wú)拆單，拆單率不足1%。

結論：200個(gè)出庫運單中，表現最好的是3DFFD先放長(cháng)物體的策略，和之前隨機訂單生成的測試結果一致。

05

算法表現分析

算法進(jìn)行的是切割。再拼湊的問(wèn)題，會(huì )直接拋棄掉一些放不進(jìn)東西的體積（優(yōu)化）。切割是演變式算法的弊端，不好規避。訂單的物品越少，切割次數越少，效率會(huì )越高。和之前隨機訂單生成的測試結果一致，3DFFD是表現最好的算法。對表現不好的案例分析，算法本身的效率不低，差值存在于對物品的擠壓狀況。切割體積造成的問(wèn)題。