[發(fā)明專利]一種基于改進(jìn)的K-Means算法的訂單分批方法

有效

• 申請?zhí)枺?/td>: 201610016607.8
• 申請日: 2016-01-07
• 公開（公告）號: CN105678607B
• 公開（公告）日: 2019-05-31
• 發(fā)明（設(shè)計）人: 胡小建;韋超豪;張美艷
• 申請（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06K9/62
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于改進(jìn)的K-Means算法的訂單分批方法，其特征是按如下步驟進(jìn)行：

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

步驟2、通過交叉檢驗法獲得距離閾值T₁和T₂，且T₁＞T₂；

步驟3、利用Canopy算法得到中心點(diǎn)集合：

步驟3.1、初始化j＝1；并以第i個訂單x_i作為第j個中心點(diǎn)c_j；以第p個訂單x_p作為第j+1個中心點(diǎn)c_j+1；p≠i；1≤p≤n；

步驟3.2、獲得n個訂單分別與第j個中心點(diǎn)c_j之間的距離集合，記為表示第i個訂單x_i與第j個中心點(diǎn)c_j之間的距離；再獲得n個訂單分別與第j+1個中心點(diǎn)c_j+1之間的距離，記為表示第i個訂單x_i與第j+1個中心點(diǎn)c_j+1之間的距離，并有：d_i,j+1表示分揀第i個訂單和第j+1個訂單中所有商品品項在倉庫中所走的路程，d_j+1表示分揀第j+1個訂單中所有商品品項在倉庫中所走的路程；

步驟3.3、初始化i＝1；

步驟3.4、若或則將第i個訂單x_i加入到第j個中心點(diǎn)c_j的Canopy集合K_j中或第i個訂單x_i加入到第j+1個中心點(diǎn)c_j+1的Canopy集合K_j+1中；若或則將第i個訂單x_i從訂單集X中刪除，將距離從距離集合D_j中刪除或?qū)木嚯x集合D_j+1中刪除；

步驟3.5、將i+1賦值給i，并判斷i＞n是否成立，若成立，則表示獲得更新的距離集合D′_j、D′_j+1和訂單集X′；并執(zhí)行步驟3.6；否則，返回步驟3.4執(zhí)行；

步驟3.6、從所述更新的距離集合D′_j和D′_j+1中分別選出最大距離記為和若則以所對應(yīng)的訂單作為第j+2個中心點(diǎn)c_j+2，若則以所對應(yīng)的訂單作為第j+2個中心點(diǎn)c_j+2；

步驟3.7、判斷更新的訂單集X′是否為空，若為空，則表示獲得中心點(diǎn)集合，記為c＝{c₁,c₂,…,c_j,…c_q}；1≤j≤q；q表示中心點(diǎn)的個數(shù)；否則，將j+1賦值給j，并返回步驟3.2執(zhí)行；

步驟4、使用改進(jìn)的K-Means算法進(jìn)行聚類：

步驟4.1、初始化i＝1；

步驟4.2、利用式(1)計算第i個訂單x_i的商品品項m_i與第j個中心點(diǎn)c_j的相似度從而獲得第i個訂單x_i與q個中心點(diǎn)的相似度

步驟4.3、從第i個訂單的相似度S_i中選出一個最大值并計算最大值所對應(yīng)的中心點(diǎn)所在的第max個簇K_max中所有訂單的總品項體積與最大值所對應(yīng)的訂單品項體積之和是否超出分揀車的容量V，若超出，則將最大值所對應(yīng)的訂單劃分到次最大值所對應(yīng)的中心點(diǎn)所在的簇中；否則，將最大值所對應(yīng)的訂單劃分到第max個簇K_max中；

步驟4.4、將i+1賦值給i，并判斷i＞n是否成立，若成立，則表示由所述中心點(diǎn)集合c形成q個簇，記為K＝{K₁,K₂,…,K_j,…,K_q}；K_j表示第j個簇；并有表示第j個簇K_j中第r個訂單；R_j表示第j個簇K_j中的訂單總數(shù)；并輸出q個簇K后，執(zhí)行步驟5；否則，返回步驟4.2執(zhí)行；

步驟5、計算第j個簇K_j中x_j個訂單的平均到達(dá)時間T_j，從而獲得q個簇的平均到達(dá)時間{T₁,T₂,…,T_j,…,T_q}并按照升序進(jìn)行排序，從而獲得最優(yōu)簇K′＝{K′₁,K′₂,…,K′_j,…,K′_q}。