移動機器人履行系統(tǒng)的訂單處理研究

馮愛蘭，楊 騰，孔繼利

1.北京科技大學 機械工程學院，北京 100083

2.北京郵電大學 現(xiàn)代郵政學院，北京 100876

1 引言

移動機器人履行系統(tǒng)（Robotic Mobile Fulfillment Systems，RMFS）是一種“貨到人”的揀選系統(tǒng)[1]，其通過智能倉儲移動機器人搬運可移動貨架，實現(xiàn)待揀選商品在存儲位置和揀選臺之間快速移動（如圖1所示），從而提高訂單履行效率，大幅度降低揀選人員的工作量，常見如Kiva系統(tǒng)[2-3]。RMFS當前多用于訂單數(shù)量多、單筆訂單規(guī)模小、品種多、配送區(qū)域分布廣、配送時間要求高[4]的B2C電商企業(yè)，這類企業(yè)往往面臨訂單波動大而履行時間有限的問題。RMFS 具有高靈活性、高柔性、組裝調整工期短等特點，有效滿足了B2C電商企業(yè)的需要，在亞馬遜、京東、天貓、唯品會等企業(yè)中得到普遍應用。

訂單處理活動是揀選作業(yè)前的準備工作，是訂單履行過程中的重要環(huán)節(jié)，訂單處理的結果對訂單履行效率具有重要影響。訂單特點和訂單揀選方式是決定訂單處理方法的主要因素：品項多的訂單通常采取按單揀選的方式；訂單數(shù)量多、單個訂單含有品項少的訂單，直接揀選要消耗大量人力物力，并且效率極低，往往需要經(jīng)過一定的處理工作再進行揀選作業(yè)——訂單分批、訂單合并、訂單排序[5-7]都是常見的訂單處理方式。傳統(tǒng)的訂單分批方法試圖通過商品合并和路徑整合實現(xiàn)行走距離最短，但在RMFS系統(tǒng)履行過程中不存在多種商品的路徑整合，傳統(tǒng)訂單處理方式不能完全適用。RMFS的搬運活動以單個貨架為單位，由于每個貨架內(nèi)商品的種類和數(shù)量是有限的，訂單履行順序和貨架調度順序將影響揀選作業(yè)的效率。Boysen 等[8]考慮動態(tài)揀選下的訂單處理過程，將問題拆分成訂單履行順序和貨架調度順序兩個子問題，并對系統(tǒng)機器人的配置數(shù)量問題進行分析。Xiang等[9]關注靜態(tài)揀選方式下的訂單處理問題，研究系統(tǒng)訂單分批和貨架調度過程，以貨架調度次數(shù)最少為目標提出相應的求解算法。張彩霞等[10]從訂單分批、揀選路徑、任務分配三個方面探究“貨到人”的訂單揀選優(yōu)化方法。李曉杰[11]同時考慮RMFS 的儲位指派和訂單分批問題，提出基于聚類方法的優(yōu)化算法對兩問題聯(lián)合優(yōu)化。更有學者[12-15]采用排隊網(wǎng)絡建模、仿真、算法優(yōu)化等方法，從倉庫布局、儲位指派、揀選過程、履行績效等不同方面對RMFS問題進行探究。

電子商務對時效的敏感決定了RMFS 訂單處理活動的重要性，RMFS應用的靈活性也使訂單履行流程更為復雜多樣，而當前對RMFS 的研究相當有限?？梢哉f，RMFS的訂單處理問題仍有許多亟待探索和研究的空間。本文就RMFS的訂單處理過程進行研究，在共享儲位指派優(yōu)化的基礎上，提出OptGA-GR 混合算法，實現(xiàn)訂單履行順序和貨架調度順序的優(yōu)化。

2 問題描述和模型建立

2.1 問題描述和假設

本研究中，將根據(jù)訂單的信息確定“揀選臺—訂單”“訂單—貨架”“貨架—揀選商品”的對應關系，為揀選活動提供訂單揀選順序和貨架調度順序的信息，輔助系統(tǒng)在最短時間完成所需要的揀選活動。由于訂單揀選時間和貨架調度次數(shù)直接相關，因此將問題目標由揀選時間最短轉化成貨架調度次數(shù)最少。研究基于動態(tài)揀選場景，揀選人員按照揀選臺所能容納的訂單數(shù)量進行揀選，每有一個訂單完成則立即補入新訂單（如圖2所示）。與靜態(tài)揀選相比，動態(tài)揀選始終保持揀選訂單數(shù)量一定，使每一次貨架調度能夠為更多訂單服務。該揀選方法中，訂單需要時時補充，貨架調度要滿足不斷變化的SKU需求，訂單之間包含的相同SKU數(shù)量、一次貨架調度可以提供的SKU 種類都會對訂單履行效率產(chǎn)生影響。因此，訂單順序和貨架調度順序成為影響RMFS動態(tài)訂單揀選的重要因素，是訂單處理活動所要解決的主要問題。Boysen 等[8]在其研究中證明了訂單處理問題是NP-hard問題，其子問題訂單排序問題和貨架調度問題也都是NP-hard問題，求解難度大且耗時長，對問題規(guī)模十分敏感。

圖2 RMFS動態(tài)訂單揀選和靜態(tài)訂單揀選對比

本文基于如下假設條件：

（1）在RMFS中，采用共享儲位的儲位指派原則：一種商品可以存儲在多個移動貨架中，同時一個貨架可以存儲多種商品。

（2）貨架上存放的商品能始終滿足訂單中商品數(shù)量的需要。該假設具有一定的合理性：一方面，B2C 訂單表現(xiàn)出SKU 種類多但每類SKU 需求量小的特點，訂單行數(shù)為1～2的訂單占80%以上，而共享儲位使補貨能及時進行，大大降低了貨架存放的商品無法滿足訂單需求的可能性。另一方面，在訂單處理過程中考慮貨架儲存量和訂單需求的關系將極大增加問題的復雜性，使問題的求解時間延長。并且，小概率的貨架存量不足問題完全可以通過揀選過程中合理的應對措施及時處理。

（3）揀選臺的訂單容量是一定的，揀選臺可處理的訂單數(shù)量不受到訂單規(guī)模、箱子體積的影響。

（4）貨架的一次調度只能為一個揀選臺服務。本文只考慮單一揀選臺，該方法在多揀選臺分區(qū)域揀選，貨架服務唯一揀選臺的場景中同樣適用，具有一定的現(xiàn)實意義。

（5）忽略因貨架位置不同導致的貨架調度順序和貨架揀選順序的不一致。

2.2 符號設置和模型建立

相關參數(shù)及變量的描述見表1和表2。

表1 參數(shù)描述

表2 決策變量描述

數(shù)學模型如下：

式（1）目標函數(shù)是求完成所有訂單調度貨架次數(shù)最少。約束（2）表示完成所有訂單需調度貨架次數(shù)的上限等于總訂單行數(shù)；約束（3）表示一次最多只能調度一個貨架；約束（4）表示每一次調度的貨架都為一個以上的訂單服務；約束（5）表示一個貨架服務的訂單數(shù)量不大于緩沖區(qū)待揀選訂單數(shù)量；約束（6）表示訂單中的每一個SKU都能被滿足；約束（7）表示保證調度的貨架能提供相應的商品；約束（8）為參數(shù)的基本約束。

2.3 共享儲位優(yōu)化

共享儲位規(guī)則[16]對RMFS 具有十分重要的意義。這種模式不僅可以滿足多揀選臺請求同種商品的情況，實現(xiàn)及時響應，減少等待時間，也可以通過貨架內(nèi)存儲商品的合理指派，增加一次貨架調度滿足多個訂單中SKU的可能性，從而減少貨架調度次數(shù)。

在具體的儲位指派中，本文提出基于聚類的兩步式啟發(fā)式方法，增強貨架中商品的相關性?？紤]實際應用場景，限定一個SKU最多存儲在M_max個貨架中。具體步驟如下：

（1）通過歷史訂單計算商品之間的相關性。Ai表示包含商品i的訂單集合，則商品相關系數(shù)可以用兩商品共同存在的訂單和兩商品存在的總訂單之比表示。利用公式（9）計算所有商品之間的相關系數(shù)，將相關系數(shù)按降序排列。

（2）為每個SKU指派一個貨架存儲位置。按Sij的降序對商品i、j進行指派。如果i、j均不在貨架中，則尋找一個可行貨架放入商品i、j；如果只有商品i存在某貨架中，且該貨架未滿，則將商品j放入，否則隨機選擇未滿貨架放入商品j。

（3）實現(xiàn)商品多儲位指派優(yōu)化。按照SKU 出現(xiàn)頻次對SKU 降序排列，得到(i1,i2,…,is)。按照商品i與其他商品相關系數(shù)降序指派商品i、j，直到貨架位置全滿，指派過程中保證每個SKU 存儲貨架數(shù)量不超過M_max。如果有只存儲了商品i或j的未滿貨架，則將另一商品存入該貨架，否則將商品i、j放入空貨架中。如果不存在空貨架，則尋找可行貨架放入商品i、j。當對于所有的Sij，以上方法都不可行時，轉入步驟4。

（4）將所有貨架中的空位置隨機指派SKU，停止。

3 RMFS訂單處理過程

3.1 訂單履行順序問題和貨架選擇調度問題

訂單順序對訂單履行效率有著重要影響，合理的訂單順序能夠有效地減少貨架的調度次數(shù)，從而提高整個系統(tǒng)的效率。假如有SKU 集合U={A,B,C,D} ，訂單O1={A,B,C},O2={A,B,C,D},O3={A,C,D},O4={C,D} ，貨架P1={A,C},P2={B,D},P3={C,D}，揀選臺容量C=2,如圖3所示。方案一顯示，訂單履行順序[O1,O2,O3,O4]需要調度[P3,P1,P2,P1]四次貨架滿足。方案二中，按照[O3,O4,O2,O1] 順序揀選訂單，只需要調度[P3,P1,P2]三次貨架，即訂單履行順序不同，需要調度貨架的次數(shù)不同。當同一揀選臺上的訂單有較多相同SKU 時，一次貨架調度能滿足多個訂單中的SKU 需要，對優(yōu)化系統(tǒng)效率起到正向作用。

圖3 RMFS訂單順序對訂單履行效率的影響示例

當訂單履行順序確定后，待揀選訂單的更新和待揀選商品的狀態(tài)主要取決于貨架的選擇和調度。如圖4所示，訂單履行順序同為[O1,O2,O3,O4]時，貨架調度順序不同，貨架調度次數(shù)也不相同。

圖4 RMFS貨架調度對訂單履行效率的影響示例

由此，可以將訂單履行順序和貨架選擇調度作為影響訂單履行效率的關鍵因素，提出RMFS訂單處理過程的優(yōu)化算法。

3.2 OptGA-GR混合算法

RMFS 中訂單排序問題和貨架選擇調度問題均為NP-hard問題，且整個訂單揀選過程受兩因素的影響，因此提出OptGA-GR混合算法，將改進遺傳算法和改進貪婪算法相結合，并引入訂單關聯(lián)實現(xiàn)初始解的優(yōu)化和算法的迅速收斂，達到短時間內(nèi)得到滿意訂單處理結果的目的。

3.2.1 基于訂單關聯(lián)的貪婪算法產(chǎn)生初始種群

對于有N個待揀選訂單和M個貨架，揀選臺容量為C的RMFS系統(tǒng)，訂單揀選順序及對應的貨架調度方案用以下集合表示：δ={α,β}，α=[Oα(1),Oα(2),…,Oα(N)]，β=[Pβ(1),Pβ(2),…,Pβ(m)]。α表示需要揀選的訂單集合及相應的訂單順序，β表示揀選臺需要調度的貨架及相應的貨架調度順序，m為完成該批次訂單需要調度的貨架數(shù)量，算法目標函數(shù)為min(m)。

在傳統(tǒng)的遺傳算法中往往通過隨機方法產(chǎn)生隨機解組成算法的初始種群，這種方法有收斂速度慢的弊端，使大規(guī)模問題求解耗時較長。本文在初始解的產(chǎn)生過程中引入訂單的相似關系，用S(Oi,Oj)表示訂單i和訂單j的相似性，Oi表示訂單i的SKU集合，訂單的相似系數(shù)即兩訂單共有的SKU種類數(shù)和總SKU種類數(shù)之比，通過公式（10）計算兩訂單的相似性。

初始解的產(chǎn)生采用貪婪算法進行優(yōu)化，首先隨機選擇訂單Oi作為當前訂單，然后在尚未指派的訂單中選擇與當前訂單相關性S(Oi,Oj)最強的訂單Oj作為下一個訂單，更新當前訂單Oj為Oi繼續(xù)搜索直到所有訂單都加入個體。最終得到的個體α包含所有需要揀選的訂單，α中基因排列順序代表訂單的揀選順序。

3.2.2 交叉和變異

OptGA-GR混合算法選擇使用循環(huán)貪心交叉法，將訂單的相關性作為交叉選擇的指標，實現(xiàn)在交叉過程中提高后代質量的目的。循環(huán)貪心交叉法遵循以下四個步驟，示例如圖5：

步驟1將父代的染色體看成首尾相連的閉環(huán)，即最后一個訂單的后一個訂單為第一個訂單。隨機選擇一個訂單作為兩個子代的首個訂單，計為A。

步驟2分別找出父代中與當前訂單相鄰的后（前）一個訂單，記為E1、E2(W1、W2) ，比較當前訂單和后（前）訂單的相似性。

步驟3在E1、E2(W1、W2)中選擇未指派且相似性更強的訂單作為子代一（子代二）的下一個訂單加入子代個體。如果兩訂單均已存在于子代個體中，則隨機選擇未被擴展的訂單加入子代。

圖5 循環(huán)貪婪交叉法

步驟4將子代中最后被加入的訂單作為當前訂單，重復步驟2和步驟3，直到子代染色體完整生成。

算法采用逆轉變異的方法，在染色體中隨機選擇兩個點，將這兩個點之間的子串進行反序，并插入到該染色體的原位置?？紤]到在實際運行中交叉概率和變異概率同樣會對算法的結果產(chǎn)生重要影響，選擇使用于瑩瑩等[17]在其研究中提出的自適應概率機制，考慮進化階段、歷史最優(yōu)解和交叉、變異概率的關系，實現(xiàn)算法在不同階段交叉概率和變異概率的動態(tài)調節(jié)。

算法通過交叉和變異改變個體α中的基因排列，探尋提高系統(tǒng)履行效率的訂單揀選順序。

3.2.3 基于改進貪婪算法得到適應度

算法取貨架調度次數(shù)的倒數(shù)為個體的適應度值，把個體代表的訂單順序作為輸入?yún)?shù)，采用加入跳出規(guī)則的貪婪算法尋找目標函數(shù)最大的個體。

當訂單履行順序確定時，訂單揀選的一般狀態(tài)表示成(U1,U2,…,UC,Podline,OC+1)，C表示揀選臺容量，Uk表示揀選臺k位置的訂單中尚未被滿足的SKU 集合，k=1,2,…,C,Ot表示下一個待揀選訂單，Podline表示該狀態(tài)下已調度的貨架序列。

當下個貨架j調度時，狀態(tài)更新為(U1-Pj,U2-Pj,…,UC-Pj,[Podline,j],O′)。如果第k個訂單揀選完成，那么Uk=Ot+1-Pj；如果本次貨架調度有n個訂單揀選完成，則O′=Ot+n。狀態(tài)更新過程體現(xiàn)了貨架調度過程中商品、訂單和貨架的關聯(lián)：待揀選商品被貨架j部分滿足；貨架的調度可能引起待揀選訂單的更替。

揀選的初始狀態(tài)可以表示為(U1,U2,…,UC,?,OC+1)，最終狀態(tài)為(?,?,…,?,Podline,?) ，該狀態(tài)下揀選位上的待揀選商品集合(U1,U2,…,UC)為空，且不存在待揀選訂單，Podline中貨架能滿足所有訂單，則Podline為貨架調度順序β。

由于貨架存儲了所有SKU，任何狀態(tài)下揀選臺需要的商品都能被貨架滿足，且存在能提供最多SKU 的最優(yōu)貨架。因此，可以將每個狀態(tài)下貨架調度問題看成是貨架調度的子問題，用貪婪算法逐步構造最優(yōu)解（如表3）。在不同狀態(tài)下，通過選擇能提供更多SKU 的貨架，尋求整體貨架調度次數(shù)最少。但貪婪算法每一步只考慮當前狀態(tài)，選取滿足局部最優(yōu)的子問題的解，具有一定的局限性。本算法為減少搜索次數(shù)且跳出局限，加入跳出機制：每次搜索前將貨架搜索順序亂序，當搜索到某貨架可以提供一半以上需求SKU 時，認為該貨架為最優(yōu)貨架，跳出本次搜索。

表3 貨架選擇調度問題的貪婪算法思想

3.2.4 算法結構

基于上述的分析，本文提出的OptGA-GR混合算法如圖6所示，基本流程如下：

（1）基于訂單關聯(lián)的貪婪算法產(chǎn)生初始種群。

（2）在每一代的進化過程中，首先利用改進的貪婪算法獲得貨架調度次數(shù)，取其倒數(shù)作為適應度值。將求解適應度的問題視為訂單履行順序一定的貨架調度次數(shù)最少問題，采用加入跳出機制的貪婪算法求解貨架調度順序。

（3）執(zhí)行選擇、交叉、變異過程。在父代個體和子代個體中選擇最優(yōu)的N個個體作為新種群執(zhí)行交叉和變異的過程。交叉和變異過程分別采用循環(huán)貪心交叉法和逆轉變異法實現(xiàn)，交叉、變異概率服從自適應概率機制。

（4）當算法達到終止條件時停止。

圖6 OptGA-GR混合算法流程圖

4 實例分析

為了便于分析比較，倉庫布局、訂單產(chǎn)生方法等數(shù)據(jù)參考文獻[16]和文獻[18]，實驗參數(shù)設置如表4。設定移動貨架在倉庫中隨機分布并在揀選完成之后隨機回到任一空閑位置。共產(chǎn)生300 個數(shù)據(jù)樣本，研究小、中、大三類倉庫規(guī)模共30種不同的場景，每個場景運算10次。

本文將提出的OptGA-GR 算法與基于先到先服務的貪婪算法（FCFS-GR）、TSP 標準遺傳算法[19]+貪婪算法（GA-GR）、SA-OS算法[8]相比較，其中，比較算法根據(jù)原論文內(nèi)容編程實現(xiàn)。為保證公平比較，根據(jù)算法的收斂情況，限定算法運行時間為1 800 s。使用MATLAB R2018a 對問題進行設計實現(xiàn)，實驗環(huán)境為Windows 10 i5-8250U，內(nèi)存8.0 GBRAM。

表4 實驗參數(shù)設置

實驗結果中，用Obj表示該規(guī)模問題下算法運行十次的平均值，ARG表示算法和OptGA-GR混合算法的平均相對差距。從表5 中四種算法的目標值可以明顯看出，OptGA-GR混合算法在大、中、小三種規(guī)模的問題中都表現(xiàn)出一定的優(yōu)勢，尤其是在中、小規(guī)模問題中優(yōu)勢明顯。先到先服務的貪婪算法在幾種算法中總體表現(xiàn)較差，其ARG 始終高于15%，在小規(guī)模問題中更是在40%左右，這意味著對相同的一批訂單，先到先服務策略要多調度近一半的貨架。但在實際應用中，先到先服務可以保證訂單的即時履行，在一些重要客戶、緊急訂單履行的情景中具有現(xiàn)實意義。雖然TSP 標準遺傳算法+貪婪算法（GA-GR）與OptGA-GR 混合算法相比，在不同規(guī)模問題的尋優(yōu)能力始終稍差，但通過比較可以看出，隨著問題規(guī)模增大，這種差距有所縮減。SA-SO 算法與OptGA-GR混合算法相比，在不同規(guī)模問題中ARG相對穩(wěn)定，相比于OptGA-GR 混合算法，SA-SO 算法局部搜索能力較強但全局搜索能力較弱，所以在有限時間的求解過程中尋優(yōu)能力表現(xiàn)較差。

表5 不同規(guī)模問題運算結果比較

圖7 算法穩(wěn)定性分析

表6 Wilcoxon檢驗統(tǒng)計量分析

同時，對算法的穩(wěn)定性進行分析，計算不同算法不同場景的10 次運算結果的標準差值，結果如圖7 所示。從整體趨勢來看，隨著問題規(guī)模的增大，各算法的穩(wěn)定性均有所降低，其中SA-SO算法的波動最為明顯。與其他算法相比，OptGA-GR 混合算法表現(xiàn)出更強的魯棒性，在相同時間內(nèi)求解結果更為穩(wěn)定，尤其是在訂單規(guī)模較小(N=50)的場景中。此外，Wilcoxon 配對的符號秩檢驗在95%置信水平下進行。表6的結果表明，算法差異性顯著，p值＜0.05。很明顯，統(tǒng)計檢驗進一步證實了OptGA-GR 混合算法在求解本文所研究的訂單處理問題的穩(wěn)定性能。

另外，就揀選臺訂單容量來看，隨著容量C的增加，完成一批訂單需要的貨架調度次數(shù)逐漸減少（如圖8所示）。這是由于當揀選臺容量增加時，一個貨架可為更多的訂單提供SKU，從而減少了貨架調度次數(shù)。合理地揀選臺訂單容量應該成為RMFS 倉庫設計時的重要考察因素。但這種考慮忽略了多訂單揀選過程中SKU數(shù)量的合并以及多個訂單同時揀選活動中揀選時間的增加，不能直接地反應訂單的履行效率。

圖8 揀選臺容量對貨架調度次數(shù)的影響

5 結語

本文對RMFS 單揀選臺動態(tài)揀選場景下的訂單處理活動進行研究：首先通過對RMFS 系統(tǒng)特點的分析選擇共享儲位指派方式，提出優(yōu)化共享存儲的啟發(fā)式方法。進而圍繞訂單揀選和貨架調度兩個子問題，建立問題模型和設計OptGA-GR 混合算法。通過引入訂單相關性、循環(huán)貪心交叉、跳出機制等多種方法進行算法優(yōu)化，在提高算法的收斂速度的同時防止算法陷入局部最優(yōu)。通過與SA-SO、FCFS-GR 和GA-GR 算法的比較證明：OptGA-GR 混合算法能夠在較短時間找到訂單履行順序和貨架調度順序的滿意解，同時保持解的穩(wěn)定性。

本文在貨架調度順序的決策中，僅考慮貨架對SKU種類的滿足與否，忽略了訂單履行過程中的其他因素，如貨架實際到達順序對系統(tǒng)績效的影響。另外，本文僅研究了單揀選臺的訂單處理活動，沒有考慮多揀選臺揀選時，訂單任務分配和調度沖突等問題，這些問題可作為接下來的研究方向。