無人倉系統(tǒng)訂單分批問題及K-max聚類算法

李珍萍，田宇璇,卜曉奇，吳凌云

(1.北京物資學(xué)院 信息學(xué)院，北京 101149；2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京 100190；3.中國科學(xué)院大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，北京 100049)

0 引言

近年來，電子商務(wù)迅速發(fā)展，電商企業(yè)每天要處理的訂單數(shù)量和訂單類型越來越多。在大型配送中心內(nèi)部，訂單揀選作業(yè)時間約占總作業(yè)時間的30%～40%，揀選作業(yè)成本占到總作業(yè)成本的60%[1],對訂單采取分批揀選策略可以有效減少作業(yè)時間、降低揀選成本[2-3]。因此，研究如何對訂單進(jìn)行分批是電商企業(yè)關(guān)注的重要問題之一。

傳統(tǒng)的電商企業(yè)物流配送中心大多采用以人工作業(yè)為主的“人到貨”揀選模式，該模式耗時長、效率低，容易出差錯。近年出現(xiàn)的無人倉系統(tǒng)(如Kiva System[4-5])采用以自動導(dǎo)引小車(Automated Guided Vehicle, AGV)為主要運(yùn)載工具的“貨到人”揀選模式，這種模式具有揀選效率高且勞動強(qiáng)度低的優(yōu)點，特別適合電商企業(yè)的多品種、小批量、多批次訂單[4-5]。在基于AGV的無人倉系統(tǒng)中，對于每一組待處理訂單列表(揀選單)，首先由計算機(jī)控制系統(tǒng)確定需要搬運(yùn)的貨架和搬運(yùn)路線，然后指派AGV將貨架搬運(yùn)至工作臺前，等待工作人員從貨架上揀取商品，再將貨架送回倉庫適當(dāng)?shù)奈恢?。無人倉系統(tǒng)用AGV搬運(yùn)貨架代替人工行走，大大降低了工作人員的勞動強(qiáng)度。

無論是基于人工揀選的傳統(tǒng)倉庫，還是基于AGV的無人倉系統(tǒng)，訂單分批策略都是直接影響訂單揀選效率和揀選成本的最主要因素之一[2,4-5]。訂單分批問題就是將陸續(xù)到達(dá)的眾多訂單按照一定規(guī)則劃分為若干批次，每個批次對應(yīng)一個訂單列表(稱為一個揀選單),每一批次訂單同時進(jìn)行揀選[6]。

訂單分批問題本質(zhì)上屬于聚類問題，因此不同場景下的訂單分批問題均可轉(zhuǎn)化為特定目標(biāo)下的聚類問題。傳統(tǒng)倉庫的訂單分批問題與無人倉系統(tǒng)訂單分批問題的主要區(qū)別在于優(yōu)化目標(biāo)不同，其中傳統(tǒng)倉庫中訂單分批問題的優(yōu)化目標(biāo)是減少工作人員在倉庫中的行走距離或行走時間[7-8]。常用的訂單分批策略包括根據(jù)訂單到達(dá)順序依時間窗分批[9-10]和根據(jù)訂單中的商品所在貨位或通道進(jìn)行分批[11-15]等，傳統(tǒng)倉庫的訂單分批算法主要通過計算訂單之間的相似度進(jìn)行聚類。

由于作業(yè)模式不同，基于AGV的“人到貨”倉庫系統(tǒng)中的訂單分批問題算法不能直接用于解決傳統(tǒng)“貨到人”倉庫系統(tǒng)中的訂單分批問題。

在無人倉系統(tǒng)中，影響訂單揀選時間和揀選成本的主要因素包括工作人員從貨架上揀取商品的次數(shù)和AGV搬運(yùn)貨架的次數(shù)，因此無人倉系統(tǒng)訂單分批問題的優(yōu)化目標(biāo)中應(yīng)該同時包括減少工作人員從貨架上揀取商品的次數(shù)和減少AGV搬運(yùn)貨架的次數(shù)。近年來，國內(nèi)外學(xué)者對無人倉系統(tǒng)訂單分批問題開展了初步研究[16-18]。李曉杰[16]以減少貨架搬運(yùn)次數(shù)為優(yōu)化目標(biāo)，設(shè)計了求解訂單分批問題的相似度函數(shù)，建立了聚類模型和策略評估模型；Xiang等[17]研究了Kiva系統(tǒng)中的儲位分配和訂單分批問題，以最小化貨架的搬運(yùn)次數(shù)作為訂單分批問題的優(yōu)化目標(biāo)，通過最大化順序關(guān)聯(lián)或最小化順序異化獲得初始可行解，并采用變鄰域搜索算法對可行解進(jìn)行改進(jìn)；Boysen等[18]則以搬運(yùn)貨架次數(shù)最少為目標(biāo)研究了訂單的排序處理問題,該問題等價于允許拆單的訂單分批問題。

以上研究的主要優(yōu)化目標(biāo)是減少AGV搬運(yùn)貨架的次數(shù)，很少考慮工作人員從貨架上揀取商品的次數(shù)，而兩者是無人倉系統(tǒng)中影響訂單揀選效率和揀選成本的重要因素，研究訂單分批問題時應(yīng)該同時考慮，以便將無人倉系統(tǒng)的任務(wù)分配和多機(jī)器人路徑規(guī)劃等子問題整合在一起，實現(xiàn)倉庫運(yùn)作效率的整體最優(yōu)[19]。

本文同時考慮工作人員揀取商品次數(shù)和AGV搬運(yùn)貨架次數(shù)，建立以訂單揀選總成本最小化為目標(biāo)的訂單分批問題優(yōu)化模型。根據(jù)訂單分批問題的數(shù)據(jù)特點和優(yōu)化模型的目標(biāo)函數(shù)表達(dá)式，采用取大(max)運(yùn)算符定義訂單分批問題的聚類中心和訂單到聚類中心的加權(quán)距離，進(jìn)一步設(shè)計求解訂單分批問題的改進(jìn)聚類算法。

1 無人倉系統(tǒng)訂單分批問題描述與分析

無人倉系統(tǒng)中的訂單分批問題可以描述為：無人倉中有M種商品存放在S個貨架上，每個貨架上有V個貨位，每個貨位只能存放一種商品，已知每種商品在倉庫中的儲位,且每種商品在相應(yīng)貨位上的存放數(shù)量充足。該無人倉采用“貨到人”揀選模式，貨架搬運(yùn)設(shè)備為AGV機(jī)器人。假設(shè)某時段內(nèi)共接到N張訂單需要揀選，對這N張訂單進(jìn)行分批，使總揀選成本最低。

為了簡化問題，假設(shè)：每種商品在貨架上的貨位固定，每個貨架在倉庫中的存放位置固定；每種商品恰好存放在一個儲位上，即每種商品僅與一個貨架對應(yīng)；在訂單揀選過程中，同時考慮兩種成本，即機(jī)器人搬運(yùn)貨架的成本和揀選人員從貨架上揀取商品的成本；AGV機(jī)器人每次搬運(yùn)各個貨架的成本均相同；揀選人員從貨架上揀取每種商品的成本均相同。

在以上假設(shè)下，影響每個批次訂單揀選效率和揀選成本的主要因素包括：①工作人員從貨架上揀選商品的種類；②AGV將貨架搬運(yùn)至揀選工作臺的次數(shù)。

基于以上假設(shè)，如果兩個訂單中包含的商品品項相同，將其合并揀選可使工作人員從貨架上揀取商品的次數(shù)減少一半；如果兩個訂單中包含的商品存放在同一個貨架上，將其合并揀選可使AGV搬運(yùn)貨架的次數(shù)減少一半。因此在進(jìn)行訂單分批時，應(yīng)綜合考慮訂單中包含的商品品項信息和商品所在貨架信息。

2 訂單分批問題的整數(shù)規(guī)劃模型

(1)符號和變量

為了建立訂單分批問題的數(shù)學(xué)模型，引進(jìn)如下符號：

i為訂單索引，i=1,2,…,N；

k為批次索引，k=1,2,…,K；

s為貨架索引，s=1,2,…,S；

t為商品索引，t=1,2,…,M

e為每個批次允許的最大訂單數(shù)量；

c1為工作人員從貨架上揀取一種商品的成本；

c2為AGV搬運(yùn)一次貨架的成本。

定義決策變量如下：

(2)整數(shù)規(guī)劃模型

基于以上符號和變量，無人倉系統(tǒng)訂單分批問題可以表示為如下0-1規(guī)劃模型：

(1)

s.t.

(2)

(3)

(4)

(5)

xik∈{0,1},?i,k；

(6)

yks∈{0,1},?k,s；

(7)

zkt∈{0,1},?k,t。

(8)

其中：目標(biāo)函數(shù)(1)表示最小化揀選的總成本，總成本包括工作人員從貨架上揀取商品的成本(第1項)和機(jī)器人搬運(yùn)貨架的成本(第2項)；約束條件(2)表示每個訂單恰好被分配到一個批次中；約束條件(3)表示分配到每個批次中的訂單數(shù)量不超過批次容量限制；約束條件(4)表示如果分配到批次k的某個訂單中包含商品t，則批次k包含商品t；約束條件(5)表示如果批次k中包含商品t，則揀選批次k時需要搬運(yùn)一個包含商品t的貨架；約束條件(6)～(8)表示決策變量取值約束。

3 K-max聚類算法

由于訂單分批問題屬于NP-hard問題[20]，當(dāng)問題規(guī)模較大時，在短時間內(nèi)無法通過求解整數(shù)規(guī)劃模型得到精確最優(yōu)解，需要設(shè)計快速有效的近似算法?？紤]到訂單分批問題本質(zhì)上屬于聚類問題，可以按照聚類問題的求解思路設(shè)計算法。

K-means是聚類算法中最常用的一種快速聚類方法[21-23]，該方法原理簡單，適合處理樣本量較大的聚類問題。傳統(tǒng)的K-means聚類算法適用于取值為數(shù)值型的樣本聚類問題，其類中心定義為類內(nèi)樣本的均值，樣本與類中心的距離通常采用歐式距離。因為訂單分批問題的樣本取值為分類型數(shù)據(jù)，其樣本均值沒有意義[24]，所以訂單分批問題的類中心不能使用樣本均值；另一方面，對于分類型數(shù)據(jù)，歐氏距離不能準(zhǔn)確反映樣本與類之間的差異，因此訂單分批問題中訂單與類(批次)之間的差異不能直接使用歐氏距離計算。由此可見，傳統(tǒng)的K-means聚類算法不能直接用來求解訂單分批問題。

本章將結(jié)合無人倉系統(tǒng)訂單分批問題的分類型數(shù)據(jù)特征和數(shù)學(xué)模型結(jié)構(gòu)，對K-means聚類算法進(jìn)行改進(jìn)，重新定義類中心和訂單到類中心的距離，在此基礎(chǔ)上設(shè)計求解訂單分批問題的新聚類算法——K-max聚類算法。

3.1 類中心

從訂單分批問題數(shù)學(xué)模型的目標(biāo)函數(shù)表達(dá)式可以看出，訂單分批問題的優(yōu)化目標(biāo)是盡可能減少同一批次訂單中包含的商品種類和揀選同一批次訂單需要搬運(yùn)的貨架數(shù)量，因此可以按照同一批次訂單中包含的所有商品種類和揀選同一批次訂單需要搬運(yùn)的所有貨架定義類中心，由此給出基于商品品項信息的類中心和基于貨架信息的類中心的定義。

(1)基于商品品項的類中心

基于商品品項的類中心根據(jù)同一批次訂單中包含的商品種類信息定義。根據(jù)整數(shù)規(guī)劃模型的約束條件(4)，只要某個批次中有一個訂單包含商品t，則該批次訂單中包含商品t。假設(shè)批次k包含的訂單序號集合為Pk，定義批次k對應(yīng)的基于商品品項的類中心為：

Qk=(qk1,qk2,…,qkM)；

(9)

例如，某一批次訂單中包含3個訂單(如表1)，訂單1～訂單3中包含的商品集合分別為{C,D}，{A,C,D}，{D,E}，則該批訂單對應(yīng)的基于商品品項的類中心為(1,0,1,1,1)，表示揀選該批次訂單需要從貨架上揀取A,C,D,E 4種商品。

表1 某批次3個訂單對應(yīng)的商品信息和基于商品品項的類中心

(2)基于貨架信息的類中心

基于貨架信息的類中心根據(jù)同一批次訂單中包含的商品所在貨架的信息定義。根據(jù)整數(shù)規(guī)劃模型的約束條件(5)，如果某批次訂單中包含商品t，則揀選該批次訂單需要搬運(yùn)一個包含商品t的貨架。由于揀選每個訂單中的商品需要搬運(yùn)的貨架可以通過訂單中包含的商品和商品在貨架上的存儲位置確定，假設(shè)揀選訂單i需要搬運(yùn)的貨架已知，引入符號

假設(shè)批次k包含的訂單序號集合為Pk，則定義批次k對應(yīng)的基于貨架信息的類中心為

Rk=(rk1,rk2,…,rkS)；

(10)

例如，某批次包含3個訂單，各訂單中的商品對應(yīng)的貨架信息如表2所示，訂單1～訂單3中的商品對應(yīng)的貨架集合分別為{2}，{1,2}，{2,3}，則該批訂單基于貨架信息的類中心為R=(1,1,1)，表示揀選該批訂單需要搬運(yùn)倉庫中所有的貨架，即貨架{1,2,3}。

表2 某批次3個訂單對應(yīng)的貨架信息和基于貨架信息的類中心

3.2 訂單到批次(類中心)的距離

根據(jù)無人倉系統(tǒng)訂單分批問題的整數(shù)規(guī)劃模型目標(biāo)函數(shù)表達(dá)式(1)，給定一個待分類訂單i和一個訂單批次(或訂單類)k，可以按照如下思想定義訂單i到批次k的距離。如果將訂單i加入批次k，批次k對應(yīng)的類中心不發(fā)生變化，則定義訂單i到批次k的距離為0；否則，根據(jù)加入訂單i后，批次k對應(yīng)的類中心增量定義訂單i到批次k的距離。下面分別根據(jù)訂單i中包含的商品品項及其所在的貨架，定義兩種訂單i到批次k的類中心之間的距離，將這兩種距離進(jìn)行加權(quán)作為訂單i到批次k的加權(quán)距離。

(1)基于商品品項的訂單到批次的距離

基于商品品項的訂單i到批次k的距離定義為：將訂單i加入批次k以后，批次k中新增加的商品種類數(shù)。假設(shè)Ai為訂單i包含的商品品項向量，

Ai=(ai1,ai2,…,aiM)，

根據(jù)批次k基于商品品項的類中心定義，得到

基于以上符號，定義訂單i與批次k之間基于商品品項的距離

(11)

式中dik表示將訂單i加入批次k后，揀選批次k時額外增加的揀取商品種類數(shù)，對應(yīng)整數(shù)規(guī)劃模型目標(biāo)函數(shù)(1)的第1項。

表3第2行表示訂單4加入之前某個批次的類中心，第3行表示訂單4中包含的商品品項信息，因此訂單4與該批次類中心之間的距離為2。

表3 基于商品品項訂單到批次之間距離的示例

(2)基于貨架信息的訂單到批次的距離

基于貨架信息的訂單i到批次k的距離定義為：將訂單i加入批次k后，揀選批次k時新增加的搬運(yùn)貨架次數(shù)。假設(shè)Ui為訂單i包含的商品所在的貨架向量，

Ui=(ui1,ui2,…,uiS)，

根據(jù)批次k基于貨架信息的類中心定義，得到

基于以上符號，定義訂單i到批次k基于貨架的距離

(12)

式中g(shù)ik表示將訂單i加入批次k以后，揀選批次k時額外增加的搬運(yùn)貨架次數(shù)，對應(yīng)整數(shù)規(guī)劃模型目標(biāo)函數(shù)(1)的第2項。

表4第2行表示訂單5加入之前某個批次的類中心為{2,4,5}，訂單5對應(yīng)的貨架集合為{1,2,5}，將訂單5加入該批次后揀選該批次訂單需要多搬運(yùn)一個貨架4,因此訂單5與該批次之間的距離為1。

表4 基于貨架信息的訂單到批次之間距離的示例

(3)訂單到批次的加權(quán)距離

基于商品品項的訂單i到批次k的距離dik反映了在批次k中加入訂單i后新增加的商品數(shù)目，將訂單加入與其距離最小的批次可以減少從貨架上揀取商品的總次數(shù)；基于貨架信息的訂單i到批次k的距離gik反映了在批次k中加入訂單i后增加的貨架搬運(yùn)次數(shù)，將訂單加入與其距離最小的批次中可以減少貨架搬運(yùn)的總次數(shù)。根據(jù)整數(shù)規(guī)劃模型的目標(biāo)函數(shù)表達(dá)式(1)，將訂單i加入批次k后，揀選批次k需要增加的總成本為c1dik+c2gik。基于以上分析，定義任意訂單i到批次k的加權(quán)距離

wik=c1dik+c2gik。

(13)

加權(quán)距離綜合考慮了商品揀選成本(次數(shù))和貨架搬運(yùn)成本(次數(shù))。根據(jù)加權(quán)距離進(jìn)行聚類，使同一批次內(nèi)訂單的平均加權(quán)距離極小化等價于使訂單揀選總成本極小化(即整數(shù)規(guī)劃模型的目標(biāo)函數(shù)(1)極小化)，因此根據(jù)加權(quán)距離進(jìn)行聚類可以得到訂單分批問題的近似最優(yōu)解?；谝陨戏治?，本文設(shè)計K-max聚類算法。

3.3 K-max聚類算法步驟

K-max聚類算法步驟如下：

步驟1根據(jù)每一批次能容納的最大訂單數(shù)e確定批次數(shù)量K，任意選擇K個訂單作為初始類中心。

步驟2對每個i=1,2,…,N,按照式(11)～式(13)計算訂單i到任意類中心k(k=1,2,…,K)的加權(quán)距離wik，并按wik由小到大對批次(類)進(jìn)行排序。

步驟3在滿足各批次訂單容量約束的前提下，依次將各訂單分配到加權(quán)距離最小的批次中。

對于每個待分配訂單i(i=1,2,…,N)，首先選擇對應(yīng)wik最小的批次k，若批次k包含的訂單總量尚未達(dá)到最大訂單數(shù)量，則將待分配訂單i分配到批次k中，更新批次k內(nèi)包含的訂單信息；否則，從尚未達(dá)到最大訂單量的批次中，選擇與待分配訂單i之間加權(quán)距離最小的批次h，將待分配訂單i分配到批次h中，更新批次h內(nèi)包含的訂單信息，直到為所有訂單重新分配了類別(批次)。

步驟4對每一個批次k=1,2,…,K，分別按式(9)和式(10)重新計算其對應(yīng)的兩種類中心，返回步驟2。

重復(fù)步驟2～步驟4,直到各批次對應(yīng)的兩種類中心均不發(fā)生變化，或迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大值為止。輸出訂單分批結(jié)果，計算對應(yīng)的揀選總成本。

在步驟1中，每一批次能容納的最大訂單數(shù)e根據(jù)實際情況設(shè)定，最大分批批次數(shù)K=[N/e]+1，其中N為訂單總數(shù)，[]為取整函數(shù)。

為了減少算法的迭代次數(shù)，在步驟1中確定K個初始類中心時，應(yīng)該使初始類中心彼此間的距離盡可能遠(yuǎn)。本文算法步驟1的設(shè)計思路如下：首先，將每個訂單作為類中心，計算任意訂單到任意類中心的加權(quán)距離，并找出最大加權(quán)距離對應(yīng)的訂單和類中心作為兩個初始類中心k和h；然后，尋找與類中心k距離最大的訂單i和與類中心h距離最大的訂單j，分別計算i和j到k和h的加權(quán)距離之和，選擇加權(quán)距離之和較大的訂單對應(yīng)的類中心作為新的初始類中心。依次尋找與已得到的類中心加權(quán)距離之和最大的訂單作為新增加的初始類中心，直到找到K個初始類中心。

與K-means聚類算法不同，步驟4中計算兩種類中心時采用的式(9)和式(10)均使用了取大運(yùn)算符，因此稱該算法為K-max聚類算法。

3.4 算法復(fù)雜性分析

定理1設(shè)置最大迭代次數(shù)為T,則K-max聚類算法的計算復(fù)雜度為O(N2MlogN)+O(TNK(M+S))。

證明K-max聚類算法步驟1中，如果按照最遠(yuǎn)距離策略選擇類中心，則總的計算次數(shù)為O(N2MlogN)；步驟2計算訂單到類中心的加權(quán)距離運(yùn)算次數(shù)為O(NK(M+S)),將每一個訂單對應(yīng)的加權(quán)距離排序的運(yùn)算次數(shù)為O(NlogK)，因此步驟2的總運(yùn)算次數(shù)不超過O(NK(M+S))；步驟3為每一個訂單確定分類的運(yùn)算次數(shù)為O(NK)；步驟4重新計算類中心的運(yùn)算次數(shù)不超過O(N(M+S))。

當(dāng)設(shè)置最大迭代次數(shù)為T時，K-max聚類算法的總計算次數(shù)不超過O(N2MlogN)+O(TNK(M+S))。

3.5 訂單分批問題數(shù)學(xué)模型和算法的幾點說明

3.5.1 商品揀選成本與貨架搬運(yùn)成本

本文建立的訂單分批問題數(shù)學(xué)模型目標(biāo)函數(shù)中同時考慮了商品揀選成本和貨架搬運(yùn)成本。本文算法基于訂單之間的加權(quán)相似度進(jìn)行聚類，其中按照訂單中包含的商品品項進(jìn)行分批(聚類)可以減少商品揀取次數(shù)，按照訂單對應(yīng)的貨架進(jìn)行分批(聚類)可以減少貨架搬運(yùn)次數(shù)。雖然在無人倉中，工作人員從貨架上揀取商品的次數(shù)和AGV搬運(yùn)貨架的次數(shù)之間存在較強(qiáng)的相關(guān)性，但是兩者并不能互相替代。下面用兩個例子說明，對于一些特殊情況，只考慮一個指標(biāo)時不一定能得到最優(yōu)分批結(jié)果。

例110種商品{1,2,3,4,5,6,7,8,9,10}存放在同一個貨架上。有10個訂單需要揀選，10個訂單包含的商品品項分別為G1=G2={1,2},G3=G4={3,4},G5=G6={5,6},G7=G8={7,8},G9=G10={9,10}。假設(shè)每個批次最多包含2個訂單。

分批結(jié)果①中，每批次兩個訂單中均包含4種商品，5個批次對應(yīng)的商品揀選總次數(shù)為20次；分批結(jié)果②中，每批次兩個訂單中均包含2種商品，5個批次對應(yīng)的商品揀選總次數(shù)為10次。顯然分批結(jié)果②優(yōu)于分批結(jié)果①。由于對應(yīng)貨架搬運(yùn)次數(shù)最少的解有多個，在不考慮商品揀選次數(shù)的情況下，很難保證得到分批結(jié)果②；如果在進(jìn)行訂單分批時，同時考慮商品揀取次數(shù)最少，即利用加權(quán)相似度指標(biāo)進(jìn)行分批，則可以直接得到分批結(jié)果②，即最優(yōu)分批結(jié)果。

例2已知倉庫中有2個貨架，共存放了10種商品，各種商品在貨架上的分布情況為S1={1,2,3,4,5}，S2={6,7,8,9,10}?，F(xiàn)有10個訂單需要揀選，每個訂單恰好包含一種商品，即G1={1},G2={2},…,Gj={j},…,G9={9}，G10={10}。假設(shè)每個批次最多包含2個訂單，則10個訂單至少需要分成5批。

因為任何兩個訂單中包含的商品均不相同，所以任意兩個訂單之間基于商品品項的相似度均為0。如果只考慮商品揀選次數(shù)，即利用基于商品品項的訂單相似度進(jìn)行分批，則一共有105種不同的分批結(jié)果，每種分批結(jié)果對應(yīng)的揀選商品總次數(shù)均為10次。進(jìn)一步分析發(fā)現(xiàn)，不同分批結(jié)果對應(yīng)的貨架搬運(yùn)次數(shù)可能差別較大。例如：①B1={G1,G6},B2={G2,G7},B3={G3,G8},B4={G4,G9},B5={G5,G10}；②B1={G1,G2}，B2={G3,G4},B3={G5,G6},B4={G7,G8},B5={G9,G10}。

分批結(jié)果①對應(yīng)的搬運(yùn)貨架總次數(shù)為10次，分批結(jié)果②對應(yīng)的搬運(yùn)貨架總次數(shù)為6次，顯然分批結(jié)果②為最優(yōu)分批結(jié)果。

實際上，例2的10個訂單中，前5個訂單中包含的商品均存放在第1個貨架上，后5個訂單中包含的商品均存放在第2個貨架上。因此，前5個訂單和后5個訂單各自之間基于貨架的相似度均為1，但分別來自于不同組的兩個訂單之間基于貨架的相似度為0。

對于例2中的數(shù)據(jù)，若不考慮貨架搬運(yùn)次數(shù)，只考慮商品揀取次數(shù)，則很難找到最優(yōu)分批結(jié)果。如果在進(jìn)行訂單分批時同時考慮商品揀選次數(shù)和貨架搬運(yùn)次數(shù)，利用加權(quán)相似度進(jìn)行分批，則可以直接得到分批結(jié)果②，即最優(yōu)分批結(jié)果。

綜上所述，由于實際無人倉系統(tǒng)中的訂單具有小批量多批次的特征，例1和例2對應(yīng)的特殊情況時有發(fā)生，為了確保在各種情況下均能得到最優(yōu)的分批結(jié)果，在進(jìn)行訂單分批時，需要同時考慮商品揀選次數(shù)和貨架搬運(yùn)次數(shù)。已有文獻(xiàn)多按照訂單中包含的商品品項相似度進(jìn)行分批，或者單純以搬運(yùn)貨架次數(shù)最少為目標(biāo)進(jìn)行分批[17]，然而對于無人倉系統(tǒng)中的一些特殊情況，單純考慮一個指標(biāo)的分批方法可能得不到最優(yōu)分批方案。本文模型和算法同時考慮商品揀選次數(shù)和貨架搬運(yùn)次數(shù)，可以確保在各種情況下均能得到整體最優(yōu)的訂單分批方案。

3.5.2 分批揀選之后按訂單拆分產(chǎn)生的成本

在本文的訂單分批揀選問題數(shù)學(xué)模型的目標(biāo)函數(shù)(1)中，只包括AGV搬運(yùn)貨架產(chǎn)生的成本，和工作人員從貨架上揀取商品產(chǎn)生的成本，沒有考慮訂單分批合并揀選之后，進(jìn)一步按訂單拆分產(chǎn)生的成本。

實際中，當(dāng)訂單分批揀選后，需要進(jìn)一步按訂單拆分同一批次訂單合并后揀取到的商品，并對各個訂單進(jìn)行打包和配送，由此產(chǎn)生按訂單拆分成本。

按訂單拆分產(chǎn)生的成本主要包括兩部分：①同一批訂單合并后，將貨架上揀取到的每一種商品按照其對應(yīng)的訂單拆分成若干份，分別放入各個訂單箱；②對每一個訂單箱中的所有商品進(jìn)行打包和配送。下面證明在一定假設(shè)下，以上兩部分成本之和均為常數(shù)。

另一方面，對每個訂單箱中的商品進(jìn)行打包和配送所產(chǎn)生的成本與訂單數(shù)量成正比，不妨設(shè)比例系數(shù)為γ，則對所有訂單進(jìn)行打包和配送的總成本為γM，也為常數(shù)。

如果將某批次訂單合并后揀取的任一種商品拆分并放入相應(yīng)訂單箱所需要的時間(成本)，與該商品對應(yīng)的訂單(箱)數(shù)量之間不為正比例關(guān)系，則按訂單拆分的總成本有可能與訂單分批策略有關(guān)。此時需要在訂單分批問題數(shù)學(xué)模型的目標(biāo)函數(shù)中增加一項按訂單拆分產(chǎn)生的成本，然后結(jié)合目標(biāo)函數(shù)的具體表達(dá)式重新設(shè)計求解模型的算法，后續(xù)研究將對該問題開展深入探討。

4 模擬計算與結(jié)果分析

4.1 算例描述

某電商企業(yè)小型無人倉中30種商品存放在10個貨架上，每個貨架上恰好有3個貨位，每種商品恰好存放在一個貨位上，各種商品在貨架上的存放位置如表5所示，在某段時間內(nèi)收到的100個訂單(如表6)需要分批揀選。

表5 無人倉中10個貨架上存放的商品序號

表6 各訂單中包含的商品信息

續(xù)表6

目前公司按照訂單到達(dá)的先后順序進(jìn)行分批，將每10個訂單作為一個批次進(jìn)行揀選。按照這種分批策略，揀選100個訂單需要工作人員從貨架上揀取商品的總次數(shù)為140次，AGV機(jī)器人搬運(yùn)貨架的總次數(shù)為73次。

為了采用本文模型和算法進(jìn)行分批，并比較不同分批結(jié)果的優(yōu)劣，本文首先設(shè)置模型中用到的兩個主要參數(shù)：工作人員揀選一種商品的平均成本c1和AGV搬運(yùn)一次貨架的平均成本c2。其中：c1=工作人員的單位時間工資×揀選一種商品的平均時間;c2=AGV來回搬運(yùn)一次貨架的平均折舊成本+平均能耗成本，平均折舊成本按每臺AGV的平均價格和平均使用壽命計算。

在實驗室環(huán)境模擬無人倉系統(tǒng)工作人員揀選商品的過程并獲取實驗數(shù)據(jù)，統(tǒng)計分析得到工作人員從貨架上揀取一種商品并按訂單信息將商品放入各個訂單(箱)的平均時間為0.75 min。參考國家統(tǒng)計局2019年5月份公布的全國規(guī)模以上企業(yè)的平均工資68 380元/年，按照每年52周，每周5個工作日，每天工作8 h計算，工作人員每分鐘的平均工資約為0.547元。根據(jù)揀選每種商品平均耗時0.75 min，可得c1=0.4元。

根據(jù)網(wǎng)上調(diào)查資料，每臺AGV的平均價格為15萬元，平均使用壽命為10年(約合3 650天)。根據(jù)實驗室模擬運(yùn)行的統(tǒng)計數(shù)據(jù)，去掉充電和設(shè)備檢修時間，AGV每天搬運(yùn)貨架的平均工作時間為12 h，每小時平均可以搬運(yùn)6次貨架，由此得到AGV每次搬運(yùn)貨架的平均折舊成本約為0.57元。參照Kiva機(jī)器人的各項性能參數(shù)計算AGV每次搬運(yùn)貨架的能耗成本。Kiva機(jī)器人的能源來自4個串聯(lián)的12 V，28 Ah鉛蓄電池，充一次電可以使用8 h～10 h。參照工業(yè)用電價格1.5 元/度，AGV每次充電可以使用9 h，平均每小時可以搬運(yùn)6次貨架，據(jù)此計算出AGV平均每次搬運(yùn)貨架的耗電量約折合0.037元。因此c2=0.6元。

本文利用以上參數(shù)計算100個訂單的不同分批結(jié)果對應(yīng)的揀選總成本。

目前公司的做法是按照訂單到達(dá)的先后順序進(jìn)行分批，將每10個訂單作為一個批次進(jìn)行揀選。按照這種分批策略，揀選100個訂單需要工作人員從貨架上揀取商品的總次數(shù)為140次，AGV機(jī)器人搬運(yùn)貨架的總次數(shù)為73次，揀選100個訂單的總成本為99.8元。

接下來采用K-max聚類方法進(jìn)行分批，并比較K-max聚類方法得到的分批結(jié)果與按訂單到達(dá)先后順序分批結(jié)果對應(yīng)的工作人員揀取商品次數(shù)，以及AGV搬運(yùn)貨架次數(shù)和揀選100個訂單的總成本變化情況。

4.2 K-max聚類結(jié)果分析

采用MATLAB軟件編寫K-max聚類算法實現(xiàn)程序，設(shè)定每個批次中最多包含11個訂單，最大迭代次數(shù)為100次，在Intel(R)Core(TM)i5-3320M CPU@2.60 GHz筆記本電腦上運(yùn)行程序，經(jīng)過9.477 s，得到100個訂單的分批結(jié)果，如表7所示。按照表7中的分批結(jié)果，工作人員需要揀取商品的總次數(shù)為93次，AGV搬運(yùn)貨架的總次數(shù)為48次，揀選100個訂單的總成本為66元。

與企業(yè)當(dāng)前采取的按訂單到達(dá)先后順序分批的策略相比，根據(jù)K-max聚類算法進(jìn)行分批，可使工作人員揀選商品的次數(shù)降低47次，AGV搬運(yùn)貨架的次數(shù)降低25次，節(jié)約總揀選成本33.8元，揀選100個訂單的總成本降低34%。由此可見，采用K-max聚類算法進(jìn)行訂單分批可以有效降低揀選成本、提高揀選效率。

表7 采用K-max聚類算法得到的分批結(jié)果

為了分析本文模型和算法的有效性，利用文獻(xiàn)[17]模型對算例進(jìn)行求解。文獻(xiàn)[17]模型的目標(biāo)函數(shù)是最小化貨架搬運(yùn)次數(shù)，等價于本文只考慮基于貨架的相似度指標(biāo)。按照文獻(xiàn)[17]模型計算得到的分批結(jié)果為：工作人員需要揀取商品次數(shù)115次，AGV需要搬運(yùn)貨架次數(shù)37次?？梢?，當(dāng)只考慮貨架搬運(yùn)次數(shù)最少時，所得分批結(jié)果對應(yīng)的貨架搬運(yùn)次數(shù)比本文模型(同時考慮商品揀取次數(shù)和貨架搬運(yùn)次數(shù)時)所得分批結(jié)果對應(yīng)的貨架搬運(yùn)次數(shù)減少了11次，但其對應(yīng)的商品揀選次數(shù)增加了22次，相應(yīng)的總揀選成本為68.2元，比本文模型和算法得到的總成本66元增加了2.2元。分析可見，如果增加工作人員揀選商品的單位成本，則按照文獻(xiàn)[17]模型得到的分批結(jié)果與本文模型得到的分批結(jié)果之間的誤差會越來越大，即隨著人工作業(yè)成本的增加，本文模型和算法的優(yōu)越性會越來越明顯。

4.3 靈敏度分析

本節(jié)采用算例分析參數(shù)c1,c2的變化對聚類結(jié)果的影響，包括工作人員揀取商品總次數(shù)、AGV搬運(yùn)貨架總次數(shù)和總揀選成本等隨參數(shù)變化的趨勢。

(1)參數(shù)c1變化

固定AGV搬運(yùn)一次貨架的成本c2=1元，令c1從0.1元逐漸增加到1元,分析其對聚類結(jié)果的影響。

設(shè)置最大迭代次數(shù)為100次，分別計算每組參數(shù)下的訂單分批結(jié)果，如表8所示?？梢?，隨著c1的增大，基于商品品項距離所占的比重越來越大，而基于貨架距離所占的比重越來越小，分批結(jié)果對應(yīng)的工作人員揀取商品的總次數(shù)呈現(xiàn)單調(diào)遞減的趨勢，AGV搬運(yùn)貨架的總次數(shù)呈現(xiàn)單調(diào)遞增的趨勢，揀選100個訂單的總成本呈現(xiàn)單調(diào)遞增的趨勢。

表8 參數(shù)c1變化的分析結(jié)果

(2)參數(shù)c2變化

固定c1=0.1元，令c2從0.1元逐漸增加到1元，分析c2的變化對聚類結(jié)果的影響。

設(shè)置最大迭代次數(shù)為100次，分別計算每組參數(shù)下的訂單分批結(jié)果，如表9所示。可見，隨著c2的增大，基于貨架距離所占的比重越來越大，基于商品品項距離所占比重越來越小。分批結(jié)果對應(yīng)的AGV搬運(yùn)貨架次數(shù)呈現(xiàn)單調(diào)遞減的趨勢，工作人員揀取商品總次數(shù)呈現(xiàn)單調(diào)遞增的趨勢，揀選100個訂單的總成本呈現(xiàn)單調(diào)遞增的趨勢。

表9 參數(shù)c2變化的分析結(jié)果

以上針對c1和c2的靈敏度分析結(jié)果，與訂單分批問題數(shù)學(xué)模型的目標(biāo)函數(shù)表達(dá)式中蘊(yùn)含的數(shù)量關(guān)系完全吻合。

5 結(jié)束語

本文研究了基于AGV的無人倉庫系統(tǒng)訂單分批問題，同時考慮了工作人員從貨架上揀取商品的成本和AGV搬運(yùn)貨架的成本，以總成本極小化為目標(biāo)建立了訂單分批問題的整數(shù)規(guī)劃模型?；诔Ｓ玫腒-means聚類算法的思想，設(shè)計了求解訂單分批問題的K-max聚類算法，其主要創(chuàng)新點在于，結(jié)合訂單分批問題的數(shù)據(jù)特征和整數(shù)規(guī)劃模型的目標(biāo)函數(shù)表達(dá)式，利用取極大(max)算子分別定義了兩種類中心和訂單到類中心的距離；進(jìn)一步以工作人員揀取一種商品的成本和AGV搬運(yùn)一個貨架的成本為權(quán)重，定義了訂單到類中心的加權(quán)距離。最后利用具體算例進(jìn)行模擬計算，分析了K-max聚類算法的分批效果，以及加權(quán)系數(shù)變化對分批結(jié)果和總費用的影響，驗證了采用K-max聚類算法求解訂單分批問題的有效性。

通過比較K-max聚類算法的分批結(jié)果與按時間窗分批結(jié)果對應(yīng)的揀選總成本發(fā)現(xiàn)，利用K-max聚類算法進(jìn)行訂單分批，可大幅降低工作人員揀取商品總次數(shù)、AGV搬運(yùn)貨架總次數(shù)和訂單揀選總成本，本文算例利用K-max聚類算法得到的分批結(jié)果，比按時間窗分批結(jié)果對應(yīng)的訂單揀選總成本降低了34%。

通過比較本文同時考慮商品揀選次數(shù)與貨架搬運(yùn)次數(shù)的訂單分批模型和文獻(xiàn)中僅考慮貨架搬運(yùn)次數(shù)的訂單分批模型的計算結(jié)果發(fā)現(xiàn)，本文模型得到的訂單分批結(jié)果優(yōu)于文獻(xiàn)模型得到的分批結(jié)果，且隨人工揀選成本的增加，本文模型和算法的優(yōu)越性愈加明顯。

從靈敏度分析結(jié)果可見，當(dāng)AGV搬運(yùn)一次貨架的成本保持不變時，隨著工作人員揀取商品單位成本的增大，K-max聚類算法分批結(jié)果中的工作人員揀取商品總次數(shù)單調(diào)遞減，AGV搬運(yùn)貨架總次數(shù)單調(diào)遞增。當(dāng)工作人員揀取商品的單位成本保持不變時，隨著AGV搬運(yùn)貨架單位成本的增大，K-max聚類算法分批結(jié)果中的AGV搬運(yùn)貨架次數(shù)單調(diào)遞減，工作人員揀取商品總次數(shù)單調(diào)遞增。

對于本文包含100個訂單的算例，筆者曾嘗試直接采用商業(yè)軟件求得其對應(yīng)的整數(shù)規(guī)劃模型的精確解，由于模型為非線性，用Lingo軟件編程直接求解時，程序運(yùn)行26 h仍然得不到最終結(jié)果，而采用K-max聚類算法在幾秒內(nèi)就可以得到近似最優(yōu)解。由于實際中的訂單分批問題均為大規(guī)模在線問題，必須在短時間內(nèi)得到近似最優(yōu)結(jié)果，因此本文設(shè)計的K-max算法是求解這類問題的有效方法。

本文僅研究了基于AGV的無人倉系統(tǒng)訂單分批問題的簡單情況，實際中還會涉及到很多不確定性和更復(fù)雜的因素，有待深入研究。如：本文假設(shè)一個貨位上最多存放一種商品且沒有考慮缺貨情況，實際中為了提高揀選效率，經(jīng)常會將同一種商品存放在多個不同的貨架上。另外本文假設(shè)待分批的訂單是已知的且具有相同的優(yōu)先級，沒有考慮訂單實時到達(dá)和不同訂單的優(yōu)先級差別，后續(xù)研究中，可以研究考慮訂單優(yōu)先級的在線訂單分批問題。

本文假設(shè)無人倉系統(tǒng)中貨架在倉庫中的位置固定，AGV搬運(yùn)各個貨架的成本均相同。然而在實際中，貨架在倉庫中的存放位置不同，AGV搬運(yùn)該貨架需要行走的距離不同，搬運(yùn)成本也不同，考慮該成本差異，需要將訂單分批揀選問題與貨架位置的動態(tài)調(diào)整問題聯(lián)合優(yōu)化，從而得出總成本更低的倉儲運(yùn)作方案，未來可以對這類聯(lián)合優(yōu)化問題進(jìn)行深入探討。

K-max聚類算法專門針對分類型數(shù)據(jù)的聚類問題設(shè)計，可用于求解無人倉系統(tǒng)的訂單分配問題，還可推廣應(yīng)用到其他分類型數(shù)據(jù)的聚類問題。然而K-max聚類算法中最大化算子對應(yīng)的函數(shù)為分段函數(shù)，而且因為在分段點不連續(xù)，所以基于取大算子定義的距離與歐氏距離完全不同。因此K-max聚類算法與K-means聚類算法必然存在很多不同的性質(zhì)，后續(xù)研究需要對K-max聚類算法進(jìn)行理論分析，以進(jìn)一步優(yōu)化算法步驟，提高求解效率。