基于智能機(jī)器人的“貨到人”系統(tǒng)訂單排序優(yōu)化

夏德龍，吳耀華，王艷艷，鄒 霞

1) 山東大學(xué)控制科學(xué)與工程學(xué)院，山東濟(jì)南250061；2)山東大學(xué)管理學(xué)院，山東濟(jì)南250100； 3) 山東財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，山東濟(jì)南250014

訂單分揀工作是配送中心最重要的過程之一[1]，分揀效率直接影響供應(yīng)鏈下游的服務(wù)水平．傳統(tǒng)的“人到貨”人工揀選系統(tǒng)效率低下，從而出現(xiàn)利用機(jī)器人代替人工作業(yè)的智能機(jī)器人揀選系統(tǒng)．智能機(jī)器人“貨到人”系統(tǒng)使用智能機(jī)器人將貨架搬運(yùn)到揀選站臺，代替揀選人員在倉庫內(nèi)行走揀貨的作業(yè)，極大提高了訂單揀選的效率．在智能機(jī)器人“貨到人”系統(tǒng)中，揀選人員揀選的效率大于貨架出入庫效率，從而貨架出入庫效率成為限制系統(tǒng)整體運(yùn)作效率的瓶頸．

針對“貨到人”系統(tǒng)訂單分揀問題已有不少研究結(jié)果．盧少平等[2]研究自動分揀系統(tǒng)時，以煙草分揀為例，根據(jù)相似系數(shù)分配揀選區(qū)． DORNBERGER等[3]對自動化倉儲系統(tǒng)(automated storage and retrieval system, AS/RS)中貨物到出入口(input/output, I/O)的距離建模，且用改進(jìn)的遺傳算法優(yōu)化訂單揀選順序，有效提高系統(tǒng)揀選效率．張喜妹[4]針對Kiva系統(tǒng)的行走距離最短作為目標(biāo)函數(shù)建模，用以解決訂單的分配問題，并采用A*算法求解模型．王艷艷等[5]對AS/RS和Carousel兩類“貨到人”系統(tǒng)依據(jù)不同訂單類型進(jìn)行系統(tǒng)優(yōu)化．吳穎穎等[6]針對“貨到人”系統(tǒng)中的多層穿梭車系統(tǒng)中批次內(nèi)訂單的排序問題，對同一揀選臺相鄰訂單之間共同需求的貨物進(jìn)行建模，并采用改進(jìn)的K-Means算法求解，但并未考慮揀選臺之間訂單的耦合． BOYSEN等[7]通過研究單揀選臺同時揀選的訂單數(shù)量來減少貨架的出入庫次數(shù)，從而提高整個Kiva系統(tǒng)的揀選效率，但是并未考慮多個揀選臺的情況．劉德寶等[8]通過設(shè)計改進(jìn)的小生境遺傳算法，并用于不同類型揀貨機(jī)的物品分配優(yōu)化模型，最大限度地減少了總揀貨時間． XIANG等[9]通過設(shè)計啟發(fā)式算法求解Kiva系統(tǒng)的訂單分批和儲位分配問題．BOZER等[10]通過Kiva和Miniload系統(tǒng)對處理訂單性能和預(yù)期吞吐量進(jìn)行對比，從而得出Kiva系統(tǒng)的優(yōu)點(diǎn)和局限性． LEE等[11]從人體工程學(xué)出發(fā)研究如何提高Kiva系統(tǒng)訂單揀選效率，對比AS/RS系統(tǒng)，采用數(shù)字人體建模分析各種人體因素對揀選效率的影響．FOUMANI等[12]以最小揀選時間為目標(biāo)函數(shù)，對AS/RS系統(tǒng)進(jìn)行建模，通過探索最優(yōu)揀選順序，縮短系統(tǒng)揀選訂單的時間，進(jìn)而提升系統(tǒng)揀選訂單的效率．BOYSEN等[13]對自動化揀選系統(tǒng)中的訂單合并和訂單分區(qū)分批策略進(jìn)行建模，最大化合并訂單的相似度．ARDJMAND等[14]提出多揀貨機(jī)的訂單分配、訂單批處理和揀貨機(jī)選路問題，并使用改進(jìn)的精確算法求解所提出的數(shù)學(xué)模型，最終得出當(dāng)訂單數(shù)與揀選機(jī)數(shù)之比對揀選時間的影響．

鑒于鮮有研究涉及“貨到人”智能機(jī)器人系統(tǒng)多揀選臺相互影響的批次內(nèi)訂單排序問題，本研究考慮揀選臺內(nèi)相鄰訂單和揀選臺之間訂單的耦合，對“貨到人”智能機(jī)器人系統(tǒng)進(jìn)行訂單排序優(yōu)化，可以在不增加設(shè)備成本的情況下，提高整個系統(tǒng)的訂單揀選效率，對整個揀選系統(tǒng)優(yōu)化的成本控制，以及提高商家服務(wù)水平具有重要意義．

1 “貨到人”智能機(jī)器人系統(tǒng)流程

1.1 “貨到人”智能機(jī)器人系統(tǒng)

隨著商對客電子商務(wù)模式(business-to-consumer, B2C)的發(fā)展，傳統(tǒng)的“人到貨”揀選方式已經(jīng)不適應(yīng)高增長的業(yè)務(wù)需求，而“貨到人”智能機(jī)器人系統(tǒng)以其自動化程度高及運(yùn)行成本低等優(yōu)點(diǎn)備受電商用戶青睞．其中，美國亞馬遜公司的Kiva系統(tǒng)成為“貨到人”智能機(jī)器人系統(tǒng)的典型．

“貨到人”智能機(jī)器人系統(tǒng)主要由主控制臺、智能機(jī)器人、可移動貨架及揀選臺等組成，如圖1．系統(tǒng)重新定義了貨物出庫流程，智能機(jī)器人先移動到訂單需要的貨架下方，隨后搬運(yùn)貨架至揀選工人面前，由揀選工人完成訂單的揀選．

圖1 “貨到人”智能機(jī)器人系統(tǒng)Fig.1 (Color online) Parts-to-picker intelligent robot system

1.2 系統(tǒng)作業(yè)流程

系統(tǒng)作業(yè)如圖1(a)，首先由主控制臺分配若干訂單組至各個揀選臺，訂單組為系統(tǒng)合單之后揀選臺同時揀選的訂單單位，每個訂單組包含若干個訂單；隨后智能機(jī)器人(如圖1(b))搬運(yùn)所需的可移動貨架至揀選臺(如圖1(c))，揀選工人根據(jù)訂單需求從貨架中揀選出訂單組內(nèi)訂單所需貨物，放入各個訂單對應(yīng)的訂單箱中，完成訂單揀選；最后由智能機(jī)器人搬運(yùn)貨架回庫或送至需要該貨架的揀選臺．

隨著訂單量的增多，貨架頻繁出入庫，出入庫效率成為限制系統(tǒng)效率的瓶頸．通過有效的訂單聚類分批，批次內(nèi)訂單組順序排序優(yōu)化，可有效減少貨架的出入庫搬運(yùn)次數(shù)，提高整個系統(tǒng)的運(yùn)作效率．

本模型對“貨到人”智能機(jī)器人系統(tǒng)做以下假設(shè)：① 貨架上貨物量滿足一個批次的訂單需求，即在訂單揀選過程中不存在缺貨現(xiàn)象；② 各揀選臺的任務(wù)量遵循均衡原則，兩兩揀選臺之間訂單組數(shù)量差≤1；③ 各揀選臺上貨架的緩存容量相同；④ 訂單已按最優(yōu)原則分成若干訂單組，且每個訂單組訂單數(shù)相同；⑤ 多個揀選臺共用一個貨架時，優(yōu)先選擇排隊較少或者無排隊的揀選臺．

1.3 兩種優(yōu)化情況

在基礎(chǔ)條件下，每完成1個訂單行的揀選作業(yè)，機(jī)器人會對相應(yīng)貨架執(zhí)行2次搬運(yùn)作業(yè)(1次入庫和1次出庫)，以下提出2種可以減少機(jī)器人搬運(yùn)作業(yè)的情況．

情況1單揀選臺的效率優(yōu)化．設(shè)揀選臺t的相鄰兩個訂單組都包含貨架m中的貨物，則可通過使貨架m不回庫，減少兩次機(jī)器人的搬運(yùn)作業(yè)，從而減少貨架出入庫時間和頻次，提高訂單揀選效率．

圖2 多揀選臺之間共用貨架Fig.2 (Color online) Shared racks in multiple picking stations

情況2多揀選臺間的效率優(yōu)化．設(shè)揀選臺t1在揀選訂單組O1時用到貨架m中的貨物，而揀選臺t2,t3,…,tn揀選訂單組O2,O3,…,On時也需要用到貨架m中的貨物，則揀選臺t1揀選完成之后，機(jī)器人搬運(yùn)貨架m至揀選臺t2,t3,…,tn， 如圖2．當(dāng)待揀選臺tn的揀選完成后，貨架m有兩種情況：① 揀選臺ti(1≤i≤n)下一個訂單組會用到貨架m中的貨物，則揀選臺tn揀選完成后，貨架m回到揀選臺ti緩存區(qū)，對應(yīng)圖2中⑤；② 揀選臺ti(1≤i≤n)下一個訂單組不會用到貨架m中的貨物，則貨架m回庫，對應(yīng)圖2中④．對于以上貨架m的2種情況，均可減少搬運(yùn)作業(yè)次數(shù)．

根據(jù)以上優(yōu)化思路，本研究對“貨到人”智能機(jī)器人系統(tǒng)貨架出入庫搬運(yùn)次數(shù)進(jìn)行建模，通過對揀選臺的訂單組揀選順序優(yōu)化，提升系統(tǒng)效率．

2 模型建立

2.1 貨架出入庫搬運(yùn)作業(yè)次數(shù)

假設(shè)有N個訂單組，共有S個揀選臺，貨架的個數(shù)為R，Qt為揀選臺t分配的訂單組個數(shù)，且

(1)

Otk表示第t個揀選臺揀選順序為k的訂單組，在不考慮訂單之間耦合的情況下，揀選訂單組Otk所需要的貨架搬運(yùn)作業(yè)總次數(shù)為

(2)

由此可得在不考慮訂單組之間耦合情況下，揀選所有訂單組所需的貨架搬運(yùn)作業(yè)次數(shù)為

(3)

(4)

其中，d為揀選臺中貨架的緩存數(shù)量．

(5)

(6)

其中，dr表示揀選臺剩余的貨架緩存容量．

(7)

由于實際中揀選臺的揀選速度并不完全一致，所以揀選臺之間訂單組的耦合所減少的搬運(yùn)作業(yè)次數(shù)可能小于γ1， 引入ε表示不同揀選臺揀選速度之間的影響因子， 0<ε≤1． 故揀選N個訂單組貨架總搬運(yùn)作業(yè)次數(shù)為

γ=γ0-γ2-「εγ1?

(8)

2.2 系統(tǒng)出入庫模型建立

從2.1節(jié)分析可知，無論是揀選臺之間訂單組的耦合，還是揀選臺內(nèi)部訂單組之間的耦合，都可以有效減少貨架的搬運(yùn)次數(shù)，并且通過減少貨架的搬運(yùn)次數(shù)，能夠有效提高整個系統(tǒng)的運(yùn)作效率，增加揀選臺的分揀效率．根據(jù)以上2種減少貨架搬運(yùn)作業(yè)次數(shù)的途徑，以“貨到人”智能機(jī)器人系統(tǒng)貨架出入庫搬運(yùn)次數(shù)為目標(biāo)函數(shù)建立如下模型．

(9)

(10)

(11)

φikt=0或1

(12)

其中，式(10)表示每個訂單組僅被分配在一個揀選臺中，且在該揀選臺中順序固定；式(11)表示固定揀選臺和揀選順序僅會被分配一個訂單組；式(12)中φikt表示訂單組i是否被分配至第t個揀選臺中，且在第t個揀選臺中揀選次序是否為k， 若是則φikt=1， 反之為0．

3 改進(jìn)的帶權(quán)值K-Means聚類算法

K-Means聚類算法輸入聚類個數(shù)和數(shù)據(jù)源，可以得到方差最小的K個聚類，且同一聚類下的對象相似度高于不同聚類的對象．K-Means算法具有以下優(yōu)點(diǎn)：① 算法簡單，求解速度快；② 在求解大數(shù)據(jù)集時，算法收斂快；③ 時間復(fù)雜度接近線性，時間復(fù)雜度低．因此，該算法被廣泛用于各種數(shù)據(jù)挖掘場景中．

如果把訂單組之間的耦合因子看作距離，則可以把訂單組之間的排序看作旅行商問題(travelling salesman problem, TCP)，本研究采用改進(jìn)的K-Means算法求解模型．

訂單組i可以表示為向量(xi1,xi2,…,xiR)， 其中，xim(1≤m≤R)表示訂單組i是否包含貨架m中的貨物，若有，則xim=1； 反之，xim=0． 計算所有訂單組兩兩之間的耦合因子，得到耦合矩陣為

(13)

對于模型的求解主要分為3個步驟：① 計算所有訂單組的耦合矩陣；② 為所有揀選臺分配初始訂單組；③采用改進(jìn)的帶權(quán)值K-Means聚類算法分配剩余的訂單組至各個揀選臺．算法的偽代碼請掃描論文末頁右下角二維碼．

4 仿真分析

通過仿真驗證“貨到人”智能機(jī)器人系統(tǒng)貨架出入庫模型的正確性，并且通過仿真數(shù)據(jù)檢驗算法的有效性．通過將優(yōu)化模型同不考慮揀選臺之間和揀選臺內(nèi)訂單耦合的情況進(jìn)行比較(優(yōu)化前模型正常揀選1個訂單行，進(jìn)行2次搬運(yùn)作業(yè))，找出降低貨架出入庫次數(shù)的各種影響因素．引入批次訂單相似系數(shù)來反映該批次訂單組的相似度，訂單相似系數(shù)通過計算平均訂單耦合因子來估計批次內(nèi)訂單的耦合程度，且

(14)

由計算機(jī)隨機(jī)模擬出3組不同訂單相似系數(shù)的訂單，每組訂單的訂單組數(shù)量均為40個，且根據(jù)3組不同訂單的仿真結(jié)果，可以預(yù)估該模型對不同批次訂單減少貨架搬運(yùn)次數(shù)的情況．

仿真中貨架數(shù)量R默認(rèn)為50個，揀選臺個數(shù)S默認(rèn)為4個，揀選臺貨架緩存?zhèn)€數(shù)d默認(rèn)為4個，揀選臺間影響因子ε默認(rèn)設(shè)定為0.5．

表1為3組不同相似系數(shù)訂單仿真數(shù)據(jù)．可見，訂單組順序優(yōu)化后，3組訂單貨架搬運(yùn)次數(shù)分別減少了32.04%、35.75%及39.11%，平均減少35.63%．造成減少貨架搬運(yùn)次數(shù)百分比不同的主要原因是批次訂單相似系數(shù)的差異．優(yōu)化減少的貨架搬運(yùn)次數(shù)百分比隨著訂單相似系數(shù)的增大而增大，這是由于訂單相似系數(shù)增大的同時，訂單組之間共用的貨架數(shù)量增大，從而訂單組排序優(yōu)化后，減少的貨架搬運(yùn)次數(shù)百分比增大，優(yōu)化效果更顯著．

表1 不同批次訂單優(yōu)化情況

訂單組個數(shù)變化時，優(yōu)化減少的貨架搬運(yùn)次數(shù)百分比變化如圖3．可見，3組訂單隨訂單組個數(shù)的增加，優(yōu)化減少的搬運(yùn)次數(shù)百分比同樣增大．3條曲線的斜率隨訂單組個數(shù)的增大而減小，反映出優(yōu)化減少的搬運(yùn)次數(shù)百分比增大的幅度隨訂單組個數(shù)的增大而減少．

圖3 訂單組個數(shù)對貨架搬運(yùn)次數(shù)的影響Fig.3 The influence of order numbers on rack visits

揀選臺貨架緩存數(shù)量從1增大到6時，優(yōu)化減少的搬運(yùn)次數(shù)百分比變化如圖4．d從1變化到4時，3條曲線優(yōu)化減少的搬運(yùn)次數(shù)百分比逐漸增大，d從4變化到6時，訂單批次2和3的曲線縱坐標(biāo)變化較小，批次訂單1曲線縱坐標(biāo)不變．這是由于訂單組優(yōu)化后耦合因子主要集中在4左右，d從1變化到4時，揀選臺貨架緩存容量小于大部分訂單組間耦合因子，所以，隨著d的增大，曲線的縱坐標(biāo)迅速增加；但是d從4變化到6時，d不再成為減少貨架搬運(yùn)次數(shù)的主要限制因素，故曲線變化幅度不大．

圖4 揀選臺貨架緩存數(shù)量對貨架搬運(yùn)次數(shù)的影響Fig.4 The influence of picking station’s rock capacity on rock visits

3組訂單中訂單組個數(shù)變化和揀選臺貨架緩存容量變化時，對出入庫次數(shù)百分比影響的敏感度分析結(jié)果如表2．其中，訂單組個數(shù)選擇基準(zhǔn)為20個，揀選臺貨架緩存容量選擇基準(zhǔn)為4個，表2中相對變化率為出入庫次數(shù)變化與訂單組個數(shù)變化，或揀選臺貨架緩存容量變化的比值．由表2可見，相對變化率隨訂單組個數(shù)的增大逐漸變小，出入庫次數(shù)對訂單組個數(shù)的敏感度逐漸降低，對比3組訂單，訂單批次3對訂單組個數(shù)變化的敏感度最高，說明訂單相似系數(shù)越高，揀選時對訂單組個數(shù)變化的依賴越高；同理，出入庫次數(shù)對揀選臺緩存容量變化的敏感度隨緩存容量的增大而逐漸降低，當(dāng)緩存增加50%時，敏感度降至最低，訂單相似系數(shù)越高，出入庫頻次對揀選臺緩存容量的敏感度越高．

表2 不同批次訂單敏感度分析

結(jié) 語

采用“貨到人”智能機(jī)器人系統(tǒng)模型和改進(jìn)的K-Means算法可有效減少系統(tǒng)的貨架搬運(yùn)次數(shù)，減少的貨架搬運(yùn)次數(shù)百分比隨批次訂單相似系數(shù)的增加而增加；一個批次內(nèi)訂單組的數(shù)量對減少貨架搬運(yùn)次數(shù)百分比具有重要影響．訂單數(shù)量大于一定數(shù)值之后，優(yōu)化減少的貨架搬運(yùn)次數(shù)百分比不再增加；在系統(tǒng)貨架及智能機(jī)器人等設(shè)備不變的情況下，適當(dāng)增加揀選臺的貨架緩存容量可有效減少貨架的搬運(yùn)次數(shù)；出入庫頻次對訂單個數(shù)和揀選臺容量的敏感度隨訂單相似系數(shù)的增大而增大，通過優(yōu)化算法提高訂單相似度有助于提高揀選效率．