無人倉系統中訂單分批策略研究

胡鴻

摘要：針對目前訂單多品類小批量的特點，構建了基于聚類算法的解求解訂單分批問題的新思路。本文介紹了無人倉系統的構成要素和訂單揀選模式，分析了改進的密度峰值聚類算法，研究了基于改進的密度峰值聚類算法的訂單分批問題的求解思路，并進行總結。

關鍵詞：無人倉系統;訂單;聚類算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1007-9416（2019）05-0108-02

0 引言

隨著物流行業的快速發展，智能倉儲、智能分批等名詞漸漸進入人們的視野，物流訂單能在短短一天甚至是半小時內就能完成，這樣的驚人效率主要取決于智能化的設備和相關算法研究。在對訂單分批的求解中有以下研究：李詩珍等[1]采用貨品在倉庫中位置特征向量為衡量標準進行訂單分批，并用啟發式算法的思想求解最短揀選距離。邵澤熠等[2]利用相似度系數最高為衡量標準進行訂單的劃分，并用改進的遺傳算法K-means算法求解訂單分批模型問題。李曉杰[3]針對移動貨架倉庫系統中儲位分配和點分批綜合進行考慮，提高揀選效率。王占磊[4]在雙區型倉庫環境背景中，實行多AGV并行揀選策略，詳細設計了遺傳算法求解訂單分批的思路，有效減少了揀選距離。胡小建[5]采用基于Canopy和k-means算法對訂單分批進行求解，減少主觀因素帶來的計算偏差。

1 無人倉系統中訂單揀選模式概述

1.1 無人倉系統構成要素簡介

無人倉規劃系統分為倉儲區、分揀區、生產加工區三部分，各個區主要由操作站臺、AGV小車、貨架、通道、貨品等要素組成。由于本文主要研究訂單分批揀選問題，所以只以揀選站臺為重點介紹對象，下面對各個部分進行簡單概括：

（1）操作站臺。操作站臺包括分揀站臺、揀選站臺、打包站臺、充電站臺等，各個站臺對應著不同的工作范圍。無人倉系統中揀選站主要由揀選操作人員、傳送帶、裝載訂單貨物的載貨架、上位機等組成，為了提高揀選效率，每個倉庫中都會有多個揀選臺、多臺AGV小車并行工作，每個揀選臺上有一個工作人員進行揀選工作。（2）貨架。無人倉系統中的貨架用于存儲貨品，每個貨架基本類似于豎著的長方體，分為多層，一般每層由多個貨格組成，每個貨架可以放多種貨品，被稱為共享貨架[6]。（3）AGV小車。在無人倉系統中，AGV小車一般由兩部分組成：行駛模塊和升舉模塊，行駛部分只要使用電力為動力來源，升舉部分大約載重量為1000KG，可以用于旋轉貨架，AGV小車通過具有實時避障功能，通過陀螺儀調整角度，實時矯正AGV小車的行駛方向。

1.2 基于無人倉系統的訂單揀選模式

在無人倉系統中訂單揀選的業務流程為：倉庫中AGV小車接收到來自客戶的訂單，按照訂單揀貨信息單的相關信息，AGV小車將貨架運送至揀選臺，工作人員揀選相關的貨品后，AGV小車將貨架運送回貨架原位置。可以看出無人倉系統是基于“貨到人”的揀選模式進行操作的系統，相對于傳統的“人到貨”的揀選模式，減少了人工成本和人工揀選時間等因素，大大提高了揀選效率。無人倉系統的訂單揀選模式流程圖如圖1所示。

2 訂單分批策略

2.1 傳統的分批策略

（1）總合計量分批。當接收到的訂單中的品相數目達到閾值時，則將這些訂單歸為一批進行揀選。比如閾值為100時，則表示無論多短或多長的時間內，訂單中的品相數目達到100時則將這些訂單歸為一批進行揀選任務。（2）時窗分批。時窗分批（Batching with Time Window）也是設置閾值，該閾值為一個時間段，該方法適合于訂單量比較集中在一個時間段或比較緊急的訂單。（3）固定訂單量分批。固定訂單量采用先到先處理的基本原則，當接收到訂單總量達到設定的閾值時，訂單歸為一批次進行揀貨。該方法適用于客戶訂單比較持續，才能保證揀選作業效率。（4）智能型分批。智能型分批是近幾年比較流行的分批方法，效率一般比傳統的分批方法更高。該方法是將接收到的客戶訂單經過計算機預處理，將相似度大的訂單歸為一批進行揀選。采用這種分批方法能大大降低揀選路徑和揀選時間，提高揀選效率和客戶滿意度。

2.2 基于改進密度峰值聚類算法的訂單分批問題研究

2.2.1 改進密度峰值聚類算法的算法設計

CFSFDP（clustering by fast search and find of density peaks）[7]是在聚類分析算法中一種比較新的以密度為衡量標準的算法，該算法的基本原理就是數據集合的聚類中心點一般具有較大局部密度值和彼此間較大距離值，然后將剩余部分的數據集按照高密度距離最小歸類 ，實現數據集合的最終聚類劃分。本文引入萬有引力定律改進該算法，由該定律啟發人們，距離可以被引力F所取代，從而有一個更好的度量標準來檢測粒子聚類中心和異常點，所以依據次思想改進密度峰值聚類算法，并將改進后的新算法用到訂單分批中求解訂單分批問題。改進后算法的參數公式如下：

參數解釋如：式（1）中為數據點的局部密度值，S為數據集合，S={1，2，.......n}，為指標函數，是數據點i與j之間的歐氏距離，是人為設定的截斷距離，它被定義為：，代表各數據點的平均局部密度為總數據量的，其中式（1）適用于對海量的數據集的計算，式（2）適用于對較小規模的數據集。式（3）中表示高密度最小距離，當該數據點為最高密度時，其值為離該點最遠點的長度，即。式（4）為原算法的改進地方，利用該式（4）替代原算法中的式（3），即由和畫決策圖，然后選取決策中心。

2.2.2 改進密度峰值聚類算法求解訂單分批問題的研究

步驟4：計算訂單的局部密度，以訂單的中心點位圓心，截斷距離為半徑畫圓，落在園內的中心點坐標的個數就是訂單的局部密度，圓內的中心點數量越多表示密度越大，該訂單就越可能成為聚類中心。

步驟5：計算訂單到更高密度點的最小距離。

步驟6：計算各個訂單之間的密度引力。

步驟7：以局部密度為橫坐標，密度引力的倒數為縱坐標，畫出決策圖，通過觀察決策圖選取兩個值都同時較大的點為聚類中心;或者計算局部密度和密度引力倒數的乘積，該值越大，說明該中心點為聚類中心點概率越大。

步驟8：將其余訂單按照聚類后生成的的密度引力大小進行歸類。

步驟9：將分好批次的訂單放入無人倉系統中進行實驗驗證。

以上是對該算法應用于訂單分批問題的求解思路，可能不是很成熟，后續還會繼續深入研究。

3 結語

本文主要介紹基于改進聚類算法的訂單分批問題研究，包括密度峰值聚類算法的改進設計和應用于訂單分批的求解思路。該算法相對于其他聚類算法來說比較新，目前對于該算法的研究大多集中在改進算法上，對算法實際應用研究比較少，所以本文嘗試將該算法進行改進并用于實際問題的研究中，所以比較有研究潛力和研究價值。

參考文獻

[1] 李詩珍，杜文宏.基于聚類分析的訂單分批揀貨模型及啟發式算法[J].統計與決策，2008（12）：53-56.

[2] 邵澤熠，董寶力.基于改進遺傳K-均值算法的多品種小批量訂單分批方法[J].浙江理工大學學報（自然科學版），2018，39（6）：732-738.

[3] 李曉杰.移動貨架倉庫系統中貨位分配和訂單分批聯合優化研究[D].清華大學，2016.

[4] 王占磊.配送中心訂單分批及揀選路徑優化問題研究[D].吉林大學，2013.

[5] 胡小建，韋超豪.基于Canopy和k-means算法的訂單分批優化[J].合肥工業大學學報（自然科學版），2017，40（3）：414-419.

[6] 黃亞.零售商競爭環境下延保服務協調策略研究[D].電子科技大學，2016.

[7] Rodriuez A， Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science， 2014（344）：1492-1496.