移動機器人履行系統(tǒng)配置優(yōu)化研究
——基于閉排隊網(wǎng)絡(luò)理論

馮愛蘭, 楊 騰, 馬立坤, 孔繼利

(北京科技大學(xué) 機械工程學(xué)院,北京 100083; 2.北京科技大學(xué) 天津?qū)W院 機械工程系,天津 301830; 3.北京郵電大學(xué) 現(xiàn)代郵政學(xué)院,北京 100876)

0 引言

移動機器人履行系統(tǒng)(RMFS，Robotic Mobile Fulfillment Systems)是一種“貨到人”的揀選模式，商品被存儲在可移動的貨架中，通過智能倉儲移動機器人搬運可移動貨架，實現(xiàn)貨架在存儲位置和揀選臺之間快速移動，員工在揀選臺完成揀選活動，常見如Kiva系統(tǒng)。移動機器人履行系統(tǒng)具有移動性、模塊化、靈活性等特點，有效解決了B2C企業(yè)訂單數(shù)量多、單筆訂單小、品類多[1]、時效敏感等問題，在亞馬遜、京東、天貓超市等電商企業(yè)得到迅速應(yīng)用。

RMFS的應(yīng)用帶來了揀選模式的顛覆，如何通過模式研究、配置優(yōu)化、策略提出實現(xiàn)系統(tǒng)履行效率優(yōu)化成為學(xué)者關(guān)注的問題。周曉光[2]、John Tersko等[3]對RMFS模式進行了詳細(xì)介紹，分析了RMFS的特點及適用性等問題。李曉杰[4]考慮貨架內(nèi)商品相關(guān)性對系統(tǒng)履行績效的影響，提出基于商品相似度系數(shù)的聚類方法，通過優(yōu)化儲位有效減少貨架調(diào)度次數(shù)。Nils Boysen[5]、Xiang等[6]關(guān)注揀選前的訂單處理行為，通過訂單分批、訂單排序、貨架調(diào)度等問題的算法優(yōu)化實現(xiàn)貨架調(diào)度次數(shù)最少。在揀選過程中，多機器人的路徑規(guī)劃[7～9]和調(diào)度策略[10～13]問題是研究的熱點。同時，學(xué)者常通過系統(tǒng)績效對不同策略和設(shè)施布局進行評估，常見有仿真建模、排隊網(wǎng)絡(luò)建模等方法，Jin等[14]利用仿真研究了在不同的倉庫布局和不同機器人數(shù)量的場景中，訂單指派規(guī)則對系統(tǒng)履行績效的影響。Lamballais T[15]用半開排隊網(wǎng)絡(luò)討論了多種儲位規(guī)則、訂單指派規(guī)則、補貨規(guī)則和貨架調(diào)度規(guī)則對系統(tǒng)履行績效的影響。Zou等[16]通過建立半開的排隊網(wǎng)絡(luò)模型計算不同充電方式在相同吞吐量下的運行時間，探究無線充電、插電充電、更換電池三種充電方式對RMFS履行績效的影響。黃惠春等[17]建立閉排隊網(wǎng)絡(luò)模型對醫(yī)藥配送中心進行研究，通過數(shù)據(jù)分析解決系統(tǒng)的擁堵問題。與仿真極盡還原真實環(huán)境相比，排隊網(wǎng)絡(luò)模型忽略系統(tǒng)的次要因素和環(huán)境的影響，是對系統(tǒng)分析和關(guān)鍵問題的抽象表示，具有模型容易修改、應(yīng)用靈活、求解迅速的優(yōu)點。

考慮到RMFS中，貨架、揀選臺的數(shù)量和位置、機器人的數(shù)量等因素都可以在短時間內(nèi)實現(xiàn)迅速調(diào)整，要充分發(fā)揮RMFS模塊化、機動靈活等優(yōu)勢，就必須將RMFS的布局問題看成隨著業(yè)務(wù)量變化不斷改變的動態(tài)決策問題。本文針對RMFS任務(wù)履行過程的特點，從貨架調(diào)度任務(wù)角度分析建立閉排隊網(wǎng)絡(luò)模型，采用近似平均值分析算法求解，進而評估揀選臺、機器人利用率和調(diào)度任務(wù)履行能力，用仿真實驗驗證其結(jié)果可靠性，并對系統(tǒng)設(shè)施配置進行討論和優(yōu)化。

1 移動機器人履行系統(tǒng)分析

1.1 系統(tǒng)組成和參數(shù)設(shè)置

RMFS由可移動貨架、智能倉儲移動機器人、揀選臺組成。貨架在倉庫中按一定規(guī)則排布，通常以矩陣塊的形式存在。貨架之間存在橫縱巷道，貨架通過巷道實現(xiàn)在存儲位置和揀選臺之間的移動。單向巷道的設(shè)計在一定程度上減少了空間面積的占用，在RMFS場景中應(yīng)用較多。智能倉儲移動機器人是系統(tǒng)的關(guān)鍵組成部分，貨架的搬運需要借助機器人實現(xiàn)，倉庫的揀貨和補貨活動都需要機器人的參與?？蛰d的機器人可以在貨架下自由的穿行，馱載貨架的機器人則需要按照巷道規(guī)定的方向在巷道內(nèi)移動。揀選臺一般設(shè)置在倉庫的側(cè)邊，揀選員只需按照系統(tǒng)的指示，揀選當(dāng)前貨架內(nèi)的指定商品或?qū)⒅付ㄉ唐贩湃胴浖苤?。典型布局如圖1所示。

圖1 移動機器人履行系統(tǒng)

系統(tǒng)布局參數(shù)設(shè)置如表1所示。

表1 布局參數(shù)描述

1.2 系統(tǒng)分析和數(shù)學(xué)表達

倉庫的布局、設(shè)備設(shè)施的數(shù)量、訂單履行的流程和策略都會對系統(tǒng)履行績效產(chǎn)生影響。在系統(tǒng)中，儲區(qū)矩陣塊的規(guī)模為5×2，當(dāng)縱向巷道和橫向巷道的數(shù)量確定時，可以得到儲區(qū)可容納的貨架數(shù)量Cw=2×5×(na+1)(nb+1)，倉庫的長寬可以用公式(1)求得。

(1)

貨架位置用(Xai,Xbi,Yai,Ybi)表示，其中Xai表示沿X軸正方向，貨架位于第幾個矩陣塊，Xai=1,2,…,na+1;Xbi表示貨架位于矩陣塊中的第幾個貨架，Xbi=1,2,…,5;Yai表示沿Y軸正方向，貨架位于第幾個矩陣塊，Yai=1,2,…,nb+1；Ybi表示貨架位于矩陣塊中的第幾個貨架，Ybi=1,2。如圖1中所示的貨架坐標(biāo)可用公式(2)表示:

(2)

揀選臺位于倉庫的側(cè)邊，當(dāng)同側(cè)有多個揀選臺時，揀選臺均勻分布。用(Xst，Yst)表示揀選臺的坐標(biāo)，NE,NW,NS,NN分別表示東、西、南、北四側(cè)揀選臺的數(shù)量，各個方向揀選臺的坐標(biāo)如下：

(3)

(4)

2 閉排隊網(wǎng)絡(luò)分析與建模

2.1 RMFS任務(wù)履行過程

在RMFS履行過程中，原始訂單經(jīng)過處理形成揀選訂單批次，并確定訂單履行順序及相應(yīng)的貨架調(diào)度任務(wù)。貨架調(diào)度任務(wù)指派給智能倉儲移動機器人，由機器人實現(xiàn)貨架在揀選臺和存放位置之間的搬運，揀選臺按照系統(tǒng)指派的任務(wù)完成訂單揀選或補貨工作。RMFS履行過程即貨架調(diào)度任務(wù)的完成過程，一次貨架調(diào)度任務(wù)主要可以分為以下過程：

(1)裝載貨架：機器人獲得貨架調(diào)度指令，從駐留點向目標(biāo)貨架所在位置移動。該過程中，機器人空載行駛，可以自由地從貨架底部穿過，機器人的運行路徑為駐留點到目標(biāo)貨架位置之間的最短路徑，長度為兩地之間的曼哈頓距離。到達目標(biāo)貨架下方后，機器人將目標(biāo)貨架抬起，機器人的狀態(tài)變?yōu)樨?fù)載狀態(tài)。

(2)搬運貨架：機器人將貨架從目標(biāo)貨架所在位置搬運至揀選臺。馱載著貨架的機器人只能在預(yù)先規(guī)劃的單向通道中行駛，行駛距離為遵循通道行駛方向的最短路徑。

(3)揀選貨架：機器人經(jīng)過排隊到達揀選臺，揀選員工按照系統(tǒng)指示放入或揀出商品，完成工作后向機器人發(fā)送完成信號。

(4)卸載貨架：機器人按照貨架調(diào)度指令，將貨架馱載回儲區(qū)的空閑位置，放下貨架并在該位置駐留待命。

2.2 RMFS閉排隊網(wǎng)絡(luò)建模

閉排隊網(wǎng)絡(luò)是排隊網(wǎng)絡(luò)的一種，是一個完全封閉的系統(tǒng)，系統(tǒng)中的服務(wù)臺、顧客數(shù)量都是恒定的，顧客在不同的節(jié)點之間轉(zhuǎn)移，沒有顧客到達或離開系統(tǒng)。

機器人在整個任務(wù)履行過程中，不僅有空載、負(fù)載、行駛、駐留的狀態(tài)變化，還存在裝、卸貨架的行為轉(zhuǎn)換。因此，可以根據(jù)機器人狀態(tài)、行為的不同，將RMFS看成一個閉排隊網(wǎng)絡(luò)，機器人作為顧客需要接受裝載貨架、運輸貨架、卸載貨架的服務(wù)。為描述機器人馱載貨架到揀選臺的活動，需要虛設(shè)一個“運輸”服務(wù)節(jié)點。因為不存在兩個機器人接受同一個貨架調(diào)度任務(wù)的情況，所以裝、卸載貨架的服務(wù)臺節(jié)點設(shè)置成無限服務(wù)臺類型。另外，由于倉庫面積足夠大，足夠容納所有機器人運輸貨架，運輸服務(wù)節(jié)點同樣設(shè)置成無限服務(wù)臺節(jié)點。

整個任務(wù)履行過程中，智能倉儲移動機器人始終不會離開系統(tǒng)，數(shù)量保持一定，機器人的速度一定，揀選人員工作簡單，操作過程中意外事件概率較低，因此排隊網(wǎng)絡(luò)可以達到穩(wěn)態(tài)。各個節(jié)點任務(wù)結(jié)束后，轉(zhuǎn)移方向互不干擾，各節(jié)點之間是相互獨立的。根據(jù)上述條件，將智能倉儲移動機器人視為顧客，貨架調(diào)度的四個過程視為四個服務(wù)節(jié)點，建立閉排隊網(wǎng)絡(luò)模型如圖2所示。

圖2 RMFS閉排隊網(wǎng)絡(luò)模型

在訂單揀選過程中，由于貨架在倉庫中隨機擺放，貨架裝載位置或貨架卸載位置在任一貨位的概率是相等的，即:

(5)

3 閉排隊網(wǎng)絡(luò)求解

3.1 近似平均值分析算法

在RMFS訂單揀選過程中，服務(wù)節(jié)點的服務(wù)時間無法用傳統(tǒng)的概率分布描述，屬于非馬爾可夫排隊網(wǎng)絡(luò)，因此乘積形式求解排隊網(wǎng)絡(luò)的方式已經(jīng)不再適用?？紤]到模型各個節(jié)點的平均服務(wù)時間及標(biāo)準(zhǔn)差等是可求得的，選擇采用近似平均值分析算法求解，其參數(shù)的定義見表2。

表2 近似平均值分析算法參數(shù)設(shè)置

節(jié)點i的相對到達率λi可以通過公式(6)求得，其中pij表示節(jié)點i向節(jié)點j轉(zhuǎn)移的概率。在本文中，由于轉(zhuǎn)移方向一定，pij均取1/H。

(6)

詳細(xì)求解過程如下：

1:Initialization2:Qi(0)=0,Li(0)=0,i=1,2,…,H %數(shù)據(jù)始化3:Preprocessing4:for i=1:Hdo5:Remi=Ei2(1+(σiEi)2) %節(jié)點i的殘余服務(wù)時間6:end for7:for i=1:Hdo8:for i=1:Rdo9:Wi(r)=Qi(r-1)Remisi+Li(r-1)EiSi %節(jié)點i中機器人的平均等待時間10:Wpi(r)=Wi(r)+Ei %節(jié)點i中機器人的平均逗留時間11:end for12:for i=1:R do13:HTi(r)=r×λi∑Hi=1λi×Wpi(r) %節(jié)點i單位時間內(nèi)任務(wù)的平均到達量14:Li(r)=THi(r)·Wi(r) %節(jié)點i的平均隊長15:ρi(r)=THi(r)·Ei/Si %節(jié)點i的服務(wù)利用率16:if

由此可以計算系統(tǒng)評價的相關(guān)指標(biāo)，系統(tǒng)的任務(wù)處理能力為(TH3(R)×3600)件/小時，機器人的利用率為(1-L3(R)/R)，揀選臺的利用率為ρ3(R)。

3.2 服務(wù)節(jié)點的平均服務(wù)時間和標(biāo)準(zhǔn)差

近似平均值分析算法是利用節(jié)點平均服務(wù)時間和標(biāo)準(zhǔn)差評估系統(tǒng)的方法。在RMFS中，受通道方向和最短行走距離的限制，機器人的行駛軌跡是可得的。在機器人行走速度一定的條件下，各個服務(wù)節(jié)點的平均服務(wù)時間和標(biāo)準(zhǔn)差也是可求的。另外，為方便計算，簡化問題的復(fù)雜度，將貨架寬度近似于貨架儲位寬度，同時假設(shè)貨架能在通道中順利行駛，不產(chǎn)生擁堵碰撞。

②搬運貨架過程中，馱載著目標(biāo)貨架的機器人只能在預(yù)先規(guī)劃的單向通道中行駛，行駛距離為遵循通道行駛方向的最短路徑。

當(dāng)揀選臺(Xst，Yst)位于倉庫的南或北側(cè)時，貨架到揀選臺的平均服務(wù)時間是相同的。以揀選臺位于南側(cè)為例，貨架到揀選臺的行駛過程分為四個階段:(1)機器人將貨架馱載到臨近的巷道；(2)到達最近的下行巷道；(3)行駛到倉庫最底部；(4)行駛至揀選臺。距離Lp2s是以上四個階段的距離之和。

當(dāng)揀選臺位于倉庫的東側(cè)或西側(cè)時，貨架到揀選臺的平均服務(wù)時間是相同的。以揀選臺位于西側(cè)為例，貨架到揀選臺的行駛過程分為五個階段:(1)機器人將貨架馱載到臨近的巷道；(2)到達最近的巷道；(3)行駛到朝向揀選臺的最近橫向巷道；(4)沿橫向巷道行駛至最西側(cè)；(5)行駛至揀選臺。距離Lp2s是以上五個階段的距離之和。

4 實驗分析

以圖1所示的倉庫布局為基本的實驗場景，具體的實驗參數(shù)值如表3所示。將建立的閉排隊網(wǎng)絡(luò)模型和近似平均值分析算法應(yīng)用到算例中，為驗證結(jié)果的可靠性，將算法結(jié)果與仿真實驗結(jié)果對比。在此基礎(chǔ)上，對整個系統(tǒng)的設(shè)施配置進行分析和優(yōu)化。

表3 實驗參數(shù)值設(shè)置

由于節(jié)點1、2、4都為無限服務(wù)臺節(jié)點，機器人到達該節(jié)點時能立即得到服務(wù)，不會產(chǎn)生等待時間?？梢酝茰y當(dāng)機器人數(shù)量足夠多時，節(jié)點3即揀選臺的服務(wù)能力是整個系統(tǒng)的瓶頸。因此，揀選臺的數(shù)量和位置是影響系統(tǒng)履行能力的重要因素。考慮到揀選臺位于南側(cè)NS和北側(cè)NN(東側(cè)NE和西側(cè)NW)的對稱位置時，其各個節(jié)點的平均服務(wù)時間相同，本文僅討論對稱揀選臺位置中的一側(cè)。參考文獻[15]設(shè)置，假設(shè)揀選臺的揀選時間服從U[20,50]的均勻分布，實驗對10/15臺機器人和4個揀選臺的系統(tǒng)場景進行實驗探究。仿真實驗采用Matlab的離散仿真計算方法，對N=50000條貨架調(diào)度任務(wù)的履行過程進行模擬，隨機產(chǎn)生初始貨架分布位置、任務(wù)調(diào)度貨架及相應(yīng)的目標(biāo)揀選臺，由R個機器人依次完成貨架調(diào)度任務(wù)，具體計算流程如圖3所示。最終，系統(tǒng)的任務(wù)處理能力TH(R)=N/Tf，機器人的利用率ρR=Σ(Tt2p+Tp2s+Ts+Ts2p)/(R×Tf)，揀選臺利用率ρs=ΣTs/(H×Tf)，揀選臺平均等待隊長通過統(tǒng)計不同時間段揀選臺前等待的機器人數(shù)量求得。

將仿真計算得到的平均數(shù)據(jù)指標(biāo)與算法結(jié)果進行對比，結(jié)果如表4所示。

圖3 仿真計算流程圖

表4 服務(wù)臺位置對系統(tǒng)績效的影響

從表4結(jié)果可以看出，揀選臺位置會對系統(tǒng)履行績效產(chǎn)生一定影響。揀選臺位于南、北兩側(cè)的系統(tǒng)履行績效要優(yōu)于揀選臺位于東西兩側(cè)的場景。這是因為當(dāng)揀選臺位于南北兩側(cè)時，機器人完成一次調(diào)度任務(wù)所需要行走的平均距離小于東西兩側(cè)的場景。同時，揀選臺利用率的提高伴隨著機器人利用率的降低，原因是揀選臺平均等待隊長增長，機器人在排隊等待中消耗了更多的時間。其次，揀選臺分散于兩側(cè)與集中于一側(cè)相比，系統(tǒng)的履行績效有所提升。因此在考慮倉庫揀選臺布置時，應(yīng)優(yōu)先將揀選臺布置在倉庫較長的側(cè)邊，且將多個揀選臺分布在兩側(cè)而非集中于一側(cè)。

節(jié)點3是整個系統(tǒng)的瓶頸，揀選臺的利用率決定了系統(tǒng)的履行效率。同時，機器人是整個系統(tǒng)履行過程的重要參與者，機器人數(shù)量太少會降低系統(tǒng)履行效率，機器人數(shù)量過多又會增加不必要的投入和能耗。合理的機器人配置應(yīng)該在保證系統(tǒng)績效的前提下數(shù)量最少。

以研究所得的揀選臺最優(yōu)位置0/0/2/2為基本場景，探究機器人數(shù)量配置問題。由圖4可知，當(dāng)揀選臺數(shù)量一定時，隨著揀選臺利用率的增加，系統(tǒng)任務(wù)履行能力在逐漸增強，同時伴隨著機器人利用率的降低。結(jié)合實際很容易理解這種變化的合理性：揀選臺利用率增加伴隨著平均隊長的增加，同時意味著等待揀選的機器人越多，機器人在等待中浪費的時間越長，利用率越低。當(dāng)機器人數(shù)量為17時，揀選臺的利用率接近100%，但考慮到實際應(yīng)用場景中，各種設(shè)備機械都有最佳利用率，100%的利用率并不利于設(shè)備的保養(yǎng)。通過綜合考慮，當(dāng)機器人數(shù)量為13臺或14臺時，機器人和揀選臺的利用率均在85%以上，綜合利用率較高。

圖4 機器人數(shù)量優(yōu)化配置

綜上，揀選臺數(shù)量為4臺，均勻布置于南、北兩側(cè)時，機器人可選擇投放數(shù)量為13或14，控制揀選臺利用率在85%以上，系統(tǒng)履行效率較高。

5 結(jié)論

本文將RMFS中貨架調(diào)度任務(wù)的履行過程拆分成裝載貨架、搬運貨架、揀選貨架、卸載貨架四個過程，進而轉(zhuǎn)化成四個服務(wù)節(jié)點建立閉排隊網(wǎng)絡(luò)模型，采用近似平均值分析算法求解。通過仿真實驗驗證了算法的有效性，并通過計算結(jié)果對系統(tǒng)設(shè)施配置問題進行分析，實現(xiàn)系統(tǒng)履行績效的評估。由分析可知，揀選臺均勻分布于倉庫較長的兩側(cè)能夠提高系統(tǒng)履行效率，且存在機器人較優(yōu)投放數(shù)量使系統(tǒng)履行效率較高。研究從貨架調(diào)度任務(wù)角度對系統(tǒng)進行分析，不考慮訂單波動和訂單揀選方式對系統(tǒng)履行績效的影響，對系統(tǒng)初始規(guī)劃具有重要意義。

采用排隊網(wǎng)絡(luò)模型分析忽略了多機器人運行場景中可能出現(xiàn)的擁堵、避讓等狀況。另外，當(dāng)前的研究關(guān)注于典型布局中揀選臺位置及機器人數(shù)量對系統(tǒng)履行績效的影響，忽略了機器人任務(wù)指派方法、貨架儲位指派等因素，相關(guān)問題可以作為進一步的研究方向。