神州金庫(kù)系統(tǒng)中的裝箱算法
神州控股
龔志峰
神州金庫(kù)作為科捷自有研發(fā)系統(tǒng)，為客戶提供B2B/B2C全供應(yīng)鏈提供一體化服務(wù)，可前端訂單接入、中端訂單數(shù)據(jù)處理（OMS、BMS、WMS、TMS等）、大數(shù)據(jù)處理等，亦可對(duì)接智能化設(shè)備。通過全國(guó)倉(cāng)包材使用情況統(tǒng)計(jì)，發(fā)現(xiàn)B2C業(yè)務(wù)裝箱問題比較突出，一是：包材選用不合理，人工裝箱時(shí)沒有邏輯規(guī)則概念，導(dǎo)致每年該部分損耗嚴(yán)重；二是：箱材的選用影響效率，且準(zhǔn)確率低。裝箱問題在倉(cāng)儲(chǔ)物流行業(yè)也是普遍存在的難題，紛紛進(jìn)行裝箱算法研究。據(jù)網(wǎng)上的公開信息，阿里對(duì)裝箱問題進(jìn)行的研究，其物流算法統(tǒng)計(jì)，平均可以減少5%的包裝，2017年雙十一發(fā)貨量超過10億件，可節(jié)省4500多萬個(gè)箱子。推行菜鳥電子面單替代傳統(tǒng)三聯(lián)面單，阿里電商平臺(tái)上商家使用率已經(jīng)達(dá)到80%，每一年節(jié)約紙張費(fèi)用達(dá)12億元?？平菀劳猩裰萁饚?kù)對(duì)該方面的問題進(jìn)行了不斷的研究和探索。
01
關(guān)于三維裝箱問題主要從以下幾個(gè)方面進(jìn)行探討
三維裝箱問題算法：
裝箱工人在裝箱過程中需要對(duì)訂單的商品選擇箱型，評(píng)估商品體積和箱子容積的正確比例，這一過程極其耗費(fèi)資源，給倉(cāng)庫(kù)作業(yè)帶來困難的同時(shí)還降低了作業(yè)效率。其次，所送商品會(huì)出現(xiàn)裝箱不合理的情況，如，顧客只是買一款體積很小的商品，收到的確是一個(gè)很大很空的箱子，浪費(fèi)資源的同時(shí)，也給用戶帶來困惑，同時(shí)零售商的專業(yè)性也遭到了質(zhì)疑。
三維裝箱規(guī)則：
1) 所有箱子均視為標(biāo)準(zhǔn)的長(zhǎng)方體或者正方體。長(zhǎng)寬高為內(nèi)圍長(zhǎng)寬高。
2) 所有商品均描述為矩形，長(zhǎng)寬高為外圍長(zhǎng)寬高。
3) 裝箱時(shí)，優(yōu)先放置大件商品。如果大件商品放不滿的情況下，考慮次小商品，直到放滿為止。
4) 裝箱時(shí)，優(yōu)先選擇容積小的箱子。容積更小的箱子如果能夠裝下商品，則剩余容積會(huì)更小，說明箱子更適合商品。其次優(yōu)先選擇常規(guī)指數(shù)最大的箱子（值越大越常規(guī)，值越小表示是非常規(guī)箱型甚至是特型箱）。
5) 如果訂單中的商品恰好已經(jīng)裝完，箱子未滿，嘗試更換容積更小的箱子。如果爆箱則換回原來的箱型。
6) 如果訂單中的商品恰好已經(jīng)裝完，出現(xiàn)爆箱，嘗試更換小一號(hào)箱子，后繼續(xù)裝箱剩余商品。如果此時(shí)箱子已經(jīng)是最小，則更換成多個(gè)箱子裝箱。
7) 將箱型按照容積從小到大的順序排列。如果箱子裝不滿優(yōu)先嘗試小的箱型。
8) 箱子優(yōu)先放置大件商品，然后放置次大商品，最后放訂單中最小的商品。
9) 如果所有的箱子都不能一個(gè)箱子裝下單個(gè)訂單內(nèi)的全部商品，才會(huì)啟用多個(gè)箱子來裝商品。
對(duì)一次裝箱過程進(jìn)行了分解，每次需要一個(gè)商品和一個(gè)空箱子，同時(shí)會(huì)產(chǎn)生三塊新的更小的剩余空間。這三塊剩余空間又可以看作是新的箱子。和新的合適自己的空間大小的商品去匹配。
那么，這就是一個(gè)遞歸算法，方法輸入一款商品和一個(gè)箱子，每一次遞歸都會(huì)產(chǎn)生三個(gè)新的箱子，新的箱子又可以裝入其它更小的商品。
如此循環(huán)往復(fù)，直到每一個(gè)新的箱子連最小的商品都裝不下了，或者沒有任何商品可以裝進(jìn)箱子里了，這個(gè)過程就會(huì)自動(dòng)結(jié)束。這是遞歸的出口條件。
02
目前使用較多的算法
1) Heuristic Algorithm啟發(fā)式演算法：工業(yè)應(yīng)用，時(shí)間短。用于在合理時(shí)間內(nèi)找到可接受的擺放方式（結(jié)果）。
2) Exact Methods精準(zhǔn)算法：學(xué)術(shù)應(yīng)用，用于研究Global Optimality，Solution Error Bound。最早的數(shù)學(xué)編程模型，混合整數(shù)線性規(guī)劃模型，但是，利用整數(shù)規(guī)劃解決問題不太現(xiàn)實(shí)，計(jì)算量太大不好實(shí)現(xiàn)，很難用線性的求解器去精準(zhǔ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)給定體積；輸入：剩余長(zhǎng)方體體積，需要打包物品，已打包物品；輸出：剩余長(zhǎng)方體體積（更新），需要打包物品（更新），已打包物品（更新）。
c) insert_items_into_dimensions：將需要打包的所有物體塞進(jìn)給定體積；輸入：剩余長(zhǎng)方體體積，需要打包物品，已打包物品；輸出：剩余長(zhǎng)方體體積（更新），需要打包物品（更新），已打包物品（更新）。best_fit：將需要打包單個(gè)物體放進(jìn)給定體積并給出最好切割方法；輸入：給定長(zhǎng)方體體積，物品體積；輸出：剩余長(zhǎng)方體體積，三個(gè)長(zhǎng)方體。
03
針對(duì)以上算法進(jìn)行算法測(cè)試設(shè)計(jì)
對(duì)比1：和僅考慮總體積的情況比較。僅考慮體積篩選會(huì)選出一些箱型會(huì)擺放不開的小箱子，進(jìn)行篩選和比較。例：物體體積小但特別長(zhǎng)。
對(duì)比2：和僅考慮總體積+能容納所有物體三邊的情況比較。此種篩選會(huì)篩選掉因?yàn)槲矬w過長(zhǎng)而放不進(jìn)去的小箱子，依然會(huì)選出些擺放不下所有物體的小箱子。例：物體形狀平均但因?yàn)槲恢藐P(guān)系擺放不下。
對(duì)比3：先和Ortools的結(jié)果對(duì)比。因?yàn)镺rtools跑出來的結(jié)果不夠理想，起碼要比Ortools的表現(xiàn)好。從良品鋪?zhàn)游锲非鍐魏蜕蜿柫计?包材維護(hù)中抽取隨機(jī)訂單，訂單長(zhǎng)度（0-6個(gè)）。（因?yàn)橐话愕挠唵未笮《荚谶@個(gè)范圍內(nèi)）看看生成的箱型是否比Ortools的小一些。
04
真實(shí)數(shù)據(jù)測(cè)試
選用200個(gè)出庫(kù)運(yùn)單，每個(gè)運(yùn)單對(duì)應(yīng)一個(gè)箱子，箱子中物體從1到21不等。數(shù)據(jù)來源沈陽良品庫(kù)，9個(gè)箱型。已刪除0體積物品（贈(zèng)品海報(bào)一類）。無拆單，拆單率不足1%。
結(jié)論：200個(gè)出庫(kù)運(yùn)單中，表現(xiàn)最好的是3DFFD先放長(zhǎng)物體的策略，和之前隨機(jī)訂單生成的測(cè)試結(jié)果一致。
05
算法表現(xiàn)分析
算法進(jìn)行的是切割。再拼湊的問題，會(huì)直接拋棄掉一些放不進(jìn)東西的體積（優(yōu)化）。切割是演變式算法的弊端，不好規(guī)避。訂單的物品越少，切割次數(shù)越少，效率會(huì)越高。和之前隨機(jī)訂單生成的測(cè)試結(jié)果一致，3DFFD是表現(xiàn)最好的算法。對(duì)表現(xiàn)不好的案例分析，算法本身的效率不低，差值存在于對(duì)物品的擠壓狀況。切割體積造成的問題。
?京公網(wǎng)安備11010802043876
