[發明專利]一種基于改進的K-Means算法的訂單分批方法

有效

• 申請號: 201610016607.8
• 申請日: 2016-01-07
• 公開（公告）號: CN105678607B
• 公開（公告）日: 2019-05-31
• 發明（設計）人: 胡小建;韋超豪;張美艷
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06K9/62
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

一種基于改進的K?Means算法的訂單分批方法。本發明公開了一種基于數據挖掘的訂單分批方法，包括如下步驟：1對數據集進行向量化處理，獲得訂單集X；2通過交叉檢驗法獲得距離閾值T₁和T₂；3利用Canopy算法得到簇個數K及中心點；4利用上一步得到的K值以及中心點，使用改進的K?Means算法進行聚類；5得到最終的聚類結果之后，按照每個聚類的訂單的平均到達時間進行排序，得到訂單分批的結果。本發明能準確地對大批量的物流訂單進行分批，從而提高分揀作業的效率，減少分揀環節所占用的時間。

技術領域

本發明屬于數據挖掘領域，具體說是一種基于改進的K-Means算法的訂單分批方法。

背景技術

網購時代的來臨，電商企業會產生大量的物流訂單，這些訂單數量呈現海量性，訂單中物品品項呈現小批量、多品種、多批次的特點，給第三方物流企業的分揀作業帶來很大的難度。分揀環節在整個訂單履行環節中是除了運輸之外最耗費時間的環節，平均分揀時間要占倉庫內訂單履行時間的40％以上，如果按照訂單到達時間順序分揀不僅費時費力，而且易出差錯，效率低下。

訂單分批是一個NP難問題，使用傳統的精確算法，無法有效地解決這個問題，因而普遍采用啟發式算法來解決。在訂單分批問題的解決方法中，主要分為優先規則算法、種子算法、節約算法以及數據挖掘算法。Ruben&Jacobs提出了一種優先規則算法，定義了“訂單信封”：一對數字，代表一個訂單在通道左右兩邊所必需的分揀的品項數，對比各訂單的“訂單信封”的數字大小，選擇優先級更高的訂單進行分揀；Hwang and Lee和Pan and Liu等文獻考慮了單貨架MOB AS/RS分揀系統的種子算法，按照相應規則進行種子選擇，然后選擇其他訂單與種子進行匹配；譚俊華、李詩珍構建的數學模型僅考慮工人的行走距離，采用節約啟發式算法求解分批問題；李詩珍先進行聚類,然后通過啟發式算法求解。Chen&Wu描述了一種基于關聯規則挖掘和整數規劃的訂單分批方法，考慮每一對訂單的支持度，將關聯性較大的訂單歸為一批；Ling-Feng Hsieh，Fan Chia-Yun應用自組織映射的思想，考慮訂單之間的相似性，對訂單進行分批；Xu Shaoyun，Li Tieke，Wang Lei和Wang Bailin提出了考慮處理時間和投遞目的地的改進K-Means聚類算法。

這些算法中，優先規則算法比較簡單，但是沒有考慮訂單之間的相關性，導致分揀路徑的重復；種子算法的初始值的選擇比較難以確定；而節約算法也是只考慮了目標分揀距離的最短，沒有深入考慮訂單的本身屬性以及訂單之間的關系。傳統的啟發式算法只能針對小數據集進行計算，而K-Means算法可以處理大數據集，算法可伸縮并且效率很高，可以對目前的海量訂單的數據進行高效處理，但是，目前所使用K-Means聚類方法的文獻僅僅考慮了運輸、處理時間等屬性，沒有考慮訂單品項中的重復的通道數量，也缺乏對初始聚類中心合理選擇，并且容易陷入局部最優。

發明內容

本發明為了克服現有技術的不足之處，提出了一種基于改進的K-Means算法的訂單分批方法，以期能有效地利用訂單的實時信息，以及利用訂單之間的相似性計算訂單之間的距離，準確地對大批量的物流訂單進行分批，從而提高分揀作業的效率，減少分揀環節所占用的時間。

為了達到上述目的，本發明所采用的技術方案為：

本發明一種基于改進的K-Means算法的訂單分批方法的特點是按如下步驟進行：

步驟1、對數據集進行向量化處理，獲得訂單集X，記為X＝{x₁,x₂,…,x_i,…,x_n}；x_i表示第i個訂單；記第i個訂單x_i的到達時間為t_i；記第i個訂單x_i的商品品項為m_i；記第i個訂單x_i的品項體積為v_i；1≤i≤n；記分揀車的容量為V；