馮愛蘭，楊 騰，孔繼利

1.北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083

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

1 引言

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

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

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

2 問題描述和模型建立

2.1 問題描述和假設(shè)

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

圖2 RMFS動(dòng)態(tài)訂單揀選和靜態(tài)訂單揀選對(duì)比

本文基于如下假設(shè)條件：

（1）在RMFS中，采用共享儲(chǔ)位的儲(chǔ)位指派原則：一種商品可以存儲(chǔ)在多個(gè)移動(dòng)貨架中，同時(shí)一個(gè)貨架可以存儲(chǔ)多種商品。

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

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

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

（5）忽略因貨架位置不同導(dǎo)致的貨架調(diào)度順序和貨架揀選順序的不一致。

2.2 符號(hào)設(shè)置和模型建立

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

表1 參數(shù)描述

表2 決策變量描述

數(shù)學(xué)模型如下：

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

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

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

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

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

（2）為每個(gè)SKU指派一個(gè)貨架存儲(chǔ)位置。按Sij的降序?qū)ι唐穒、j進(jìn)行指派。如果i、j均不在貨架中，則尋找一個(gè)可行貨架放入商品i、j；如果只有商品i存在某貨架中，且該貨架未滿，則將商品j放入，否則隨機(jī)選擇未滿貨架放入商品j。

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

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

3 RMFS訂單處理過程

3.1 訂單履行順序問題和貨架選擇調(diào)度問題

訂單順序?qū)τ唵温男行视兄匾绊?，合理的訂單順序能夠有效地減少貨架的調(diào)度次數(shù)，從而提高整個(gè)系統(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}，揀選臺(tái)容量C=2,如圖3所示。方案一顯示，訂單履行順序[O1,O2,O3,O4]需要調(diào)度[P3,P1,P2,P1]四次貨架滿足。方案二中，按照[O3,O4,O2,O1] 順序揀選訂單，只需要調(diào)度[P3,P1,P2]三次貨架，即訂單履行順序不同，需要調(diào)度貨架的次數(shù)不同。當(dāng)同一揀選臺(tái)上的訂單有較多相同SKU 時(shí)，一次貨架調(diào)度能滿足多個(gè)訂單中的SKU 需要，對(duì)優(yōu)化系統(tǒng)效率起到正向作用。

圖3 RMFS訂單順序?qū)τ唵温男行实挠绊懯纠?/p>

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

圖4 RMFS貨架調(diào)度對(duì)訂單履行效率的影響示例

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

3.2 OptGA-GR混合算法

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

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

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

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

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

3.2.2 交叉和變異

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

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

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

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

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

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

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

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

3.2.3 基于改進(jìn)貪婪算法得到適應(yīng)度

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

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

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

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

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

表3 貨架選擇調(diào)度問題的貪婪算法思想

3.2.4 算法結(jié)構(gòu)

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

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

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

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

（4）當(dāng)算法達(dá)到終止條件時(shí)停止。

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

4 實(shí)例分析

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

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

表4 實(shí)驗(yàn)參數(shù)設(shè)置

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

表5 不同規(guī)模問題運(yùn)算結(jié)果比較

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

表6 Wilcoxon檢驗(yàn)統(tǒng)計(jì)量分析

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

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

圖8 揀選臺(tái)容量對(duì)貨架調(diào)度次數(shù)的影響

5 結(jié)語

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

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