無(wú)人倉(cāng)系統(tǒng)中訂單分批策略研究

胡鴻

摘要：針對(duì)目前訂單多品類小批量的特點(diǎn)，構(gòu)建了基于聚類算法的解求解訂單分批問(wèn)題的新思路。本文介紹了無(wú)人倉(cāng)系統(tǒng)的構(gòu)成要素和訂單揀選模式，分析了改進(jìn)的密度峰值聚類算法，研究了基于改進(jìn)的密度峰值聚類算法的訂單分批問(wèn)題的求解思路，并進(jìn)行總結(jié)。

關(guān)鍵詞：無(wú)人倉(cāng)系統(tǒng);訂單;聚類算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2019）05-0108-02

0 引言

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

1 無(wú)人倉(cāng)系統(tǒng)中訂單揀選模式概述

1.1 無(wú)人倉(cāng)系統(tǒng)構(gòu)成要素簡(jiǎn)介

無(wú)人倉(cāng)規(guī)劃系統(tǒng)分為倉(cāng)儲(chǔ)區(qū)、分揀區(qū)、生產(chǎn)加工區(qū)三部分，各個(gè)區(qū)主要由操作站臺(tái)、AGV小車、貨架、通道、貨品等要素組成。由于本文主要研究訂單分批揀選問(wèn)題，所以只以揀選站臺(tái)為重點(diǎn)介紹對(duì)象，下面對(duì)各個(gè)部分進(jìn)行簡(jiǎn)單概括：

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

1.2 基于無(wú)人倉(cāng)系統(tǒng)的訂單揀選模式

在無(wú)人倉(cāng)系統(tǒng)中訂單揀選的業(yè)務(wù)流程為：倉(cāng)庫(kù)中AGV小車接收到來(lái)自客戶的訂單，按照訂單揀貨信息單的相關(guān)信息，AGV小車將貨架運(yùn)送至揀選臺(tái)，工作人員揀選相關(guān)的貨品后，AGV小車將貨架運(yùn)送回貨架原位置。可以看出無(wú)人倉(cāng)系統(tǒng)是基于“貨到人”的揀選模式進(jìn)行操作的系統(tǒng)，相對(duì)于傳統(tǒng)的“人到貨”的揀選模式，減少了人工成本和人工揀選時(shí)間等因素，大大提高了揀選效率。無(wú)人倉(cāng)系統(tǒng)的訂單揀選模式流程圖如圖1所示。

2 訂單分批策略

2.1 傳統(tǒng)的分批策略

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

2.2 基于改進(jìn)密度峰值聚類算法的訂單分批問(wèn)題研究

2.2.1 改進(jìn)密度峰值聚類算法的算法設(shè)計(jì)

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

參數(shù)解釋如：式（1）中為數(shù)據(jù)點(diǎn)的局部密度值，S為數(shù)據(jù)集合，S={1，2，.......n}，為指標(biāo)函數(shù)，是數(shù)據(jù)點(diǎn)i與j之間的歐氏距離，是人為設(shè)定的截?cái)嗑嚯x，它被定義為：，代表各數(shù)據(jù)點(diǎn)的平均局部密度為總數(shù)據(jù)量的，其中式（1）適用于對(duì)海量的數(shù)據(jù)集的計(jì)算，式（2）適用于對(duì)較小規(guī)模的數(shù)據(jù)集。式（3）中表示高密度最小距離，當(dāng)該數(shù)據(jù)點(diǎn)為最高密度時(shí)，其值為離該點(diǎn)最遠(yuǎn)點(diǎn)的長(zhǎng)度，即。式（4）為原算法的改進(jìn)地方，利用該式（4）替代原算法中的式（3），即由和畫決策圖，然后選取決策中心。

2.2.2 改進(jìn)密度峰值聚類算法求解訂單分批問(wèn)題的研究

步驟4：計(jì)算訂單的局部密度，以訂單的中心點(diǎn)位圓心，截?cái)嗑嚯x為半徑畫圓，落在園內(nèi)的中心點(diǎn)坐標(biāo)的個(gè)數(shù)就是訂單的局部密度，圓內(nèi)的中心點(diǎn)數(shù)量越多表示密度越大，該訂單就越可能成為聚類中心。

步驟5：計(jì)算訂單到更高密度點(diǎn)的最小距離。

步驟6：計(jì)算各個(gè)訂單之間的密度引力。

步驟7：以局部密度為橫坐標(biāo)，密度引力的倒數(shù)為縱坐標(biāo)，畫出決策圖，通過(guò)觀察決策圖選取兩個(gè)值都同時(shí)較大的點(diǎn)為聚類中心;或者計(jì)算局部密度和密度引力倒數(shù)的乘積，該值越大，說(shuō)明該中心點(diǎn)為聚類中心點(diǎn)概率越大。

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

步驟9：將分好批次的訂單放入無(wú)人倉(cāng)系統(tǒng)中進(jìn)行實(shí)驗(yàn)驗(yàn)證。

以上是對(duì)該算法應(yīng)用于訂單分批問(wèn)題的求解思路，可能不是很成熟，后續(xù)還會(huì)繼續(xù)深入研究。

3 結(jié)語(yǔ)

本文主要介紹基于改進(jìn)聚類算法的訂單分批問(wèn)題研究，包括密度峰值聚類算法的改進(jìn)設(shè)計(jì)和應(yīng)用于訂單分批的求解思路。該算法相對(duì)于其他聚類算法來(lái)說(shuō)比較新，目前對(duì)于該算法的研究大多集中在改進(jìn)算法上，對(duì)算法實(shí)際應(yīng)用研究比較少，所以本文嘗試將該算法進(jìn)行改進(jìn)并用于實(shí)際問(wèn)題的研究中，所以比較有研究潛力和研究?jī)r(jià)值。

參考文獻(xiàn)

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

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

[3] 李曉杰.移動(dòng)貨架倉(cāng)庫(kù)系統(tǒng)中貨位分配和訂單分批聯(lián)合優(yōu)化研究[D].清華大學(xué)，2016.

[4] 王占磊.配送中心訂單分批及揀選路徑優(yōu)化問(wèn)題研究[D].吉林大學(xué)，2013.

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

[6] 黃亞.零售商競(jìng)爭(zhēng)環(huán)境下延保服務(wù)協(xié)調(diào)策略研究[D].電子科技大學(xué)，2016.

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