電商RMFS系統訂單分配與路徑規劃聯合優化方法

秦進，楊淑鈞，戴博

(1. 中南大學 交通運輸工程學院，湖南 長沙 410075；2. 湖南工商大學 工商管理學院，湖南 長沙 410205；3. 特魯瓦技術大學 工業系統優化實驗室，法國 特魯瓦 10004)

隨著經濟社會快速發展和互聯網技術的日益更新，電商行業發展迅猛。在面對海量客戶需求的環境下，電商訂單還呈現出高頻率、多品種、小批量等特性，這都使訂單處理變得極為復雜，也對電商物流的運營水平等提出更高要求[1]。在電商物流中心日常運營中，特別是在雙十一、雙十二等大促時期，如何準確快速處理海量訂單、縮短商品交付時間，已成為電商企業核心競爭力的關鍵所在。訂單揀選是電商物流倉儲的關鍵環節，是指按訂單從存儲位置取出商品的全過程。在傳統的“人到貨”揀選系統中，人員行走時間占揀貨總時間的50%+，導致揀選效率低下[1-2]，難以滿足電商時代對訂單處理的需求。為節省人工并提高揀選速度，在智能化趨勢下，越來越多電商企業開始使用移動機器人揀貨系統(Robotic Mobile Fulfillment System, RMFS)完成訂單揀選[3]。以亞馬遜Kiva系統為代表，RMFS采用機器人進行貨物存儲、搜索、選擇和運送工作，實現“貨到人”揀選模式的轉變。然而RMFS系統也帶來一系列新的挑戰。一方面，如何根據訂單信息快速匹配貨架和揀選站，合理規劃機器人行走路徑，對系統協同調度能力提出了考驗；另一方面，目前常用的“先到先揀選”(First-Come-First-Service, FCFS)策略往往會造成貨架重復進出和機器人行走路線迂回，一定程度上會影響揀選設備性能的充分發揮和揀選作業效率。近年來，RMFS優化研究受到越來越多關注。TOMPKINS 等[2]指出Kiva系統中AGV取回貨架的時間占比較大。WEIDINGER等[4]以貨架往返總距離最小化為目標優化返回貨架的位置分配。訂單分配是按一定規則對訂單進行分批或排序，以盡可能地滿足多個訂單的需求，減少人工或設備的重復作業，縮短揀選作業時間。對于人工揀選系統，王轉等[5]指出里程節約的訂單分批方法效果優于相似度分批法和傳統先到先分批規則。MENéNDEZ等[6]運用常規變鄰域搜索算法解決訂單分批和排序問題。相比于人工揀選系統，RMFS系統訂單分配相關研究較少。YANG等[3]將訂單排序與貨架調度問題結合起來。BOYSEN等[7]研究了貨架移動機器人系統中的訂單分批、訂單排序和貨架順序問題，但只關注單個揀選站處理過程，現實情況中往往是多個揀選站并行處理訂單。揀選路徑規劃，目的是找出一條從起始點到目標點的最優路線，縮短揀選員或設備的移動距離。在人工揀選系統中，TOMPKINS等[2]總結了穿越法、最大間隙法、通道接通道法、返回法和中點回轉法等常用的揀貨路徑策略。王宏等[8]考慮了傳統雙區型倉庫下的揀選員行走路徑問題。而RMFS系統下的路徑規劃問題，需要在人工揀貨路徑規劃經驗的基礎上充分考慮機器人移動特性。夏揚坤等[9]將多種類AGV物料配送規劃問題歸結為帶軟時間窗的需求依訂單拆分車輛路徑問題。張喜妹[10]針對Kiva系統的路徑規劃問題提出了改進的A*算法。綜上所述，在RMFS訂單分配決策的既有研究中，較少考慮多訂單、多貨架、多揀選站之間的分配關系和機器人運輸距離。同時，研究多集中于訂單分配或路徑規劃的單獨決策，針對兩者的聯合優化問題目前才開始得到重視。因此，本文立足電商企業場景下的RMFS系統特性，考慮多個揀選站和距離因素，以機器人負載距離最小化為目標，構建訂單分配和路徑規劃聯合優化模型，并設計A*和自適應大領域搜索(Adaptive Large Neighborhood Search, ALNS)算法進行求解和分析。

1 問題描述與分析

RMFS系統由可移動貨架、移動機器人、揀選站臺等部分組成，采用網格排列的模式。可移動貨架是RMFS系統中的存儲設備，貨架上的料箱用于存放商品，底部一層中空留出機器人運輸空間。當系統下達訂單任務時，機器人沿著指定路線到達待揀選貨架位置，將貨架頂起離開地面后搬運貨架前往目標揀選站，等待人工揀出商品再運送貨架回到存儲位置。揀選作業區域并行排列多個揀選站，每個揀選站可同時處理的訂單數量有限。在揀選站臺內，揀選員借助激光指示器、條碼掃描儀等設備，從貨架上取出商品放入貨箱中[4]，揀選完畢后訂單對應貨箱經傳送帶輸送到出庫區打包，重復上述過程直到完成所有訂單。

在此場景下，RMFS系統訂單分配的決策問題包括：1) 如何劃分訂單批次；2) 尋找能夠滿足每個批次訂單商品需求的待揀選貨架；3) 為每個批次訂單和待揀選貨架指定一個揀選站。由于待揀選貨架需要借助機器人搬運至揀選站，完成揀貨作業后機器人再運送其返回貨架存儲區域，因此機器人行走距離是影響訂單分配的重要因素。

圖1 RMFS系統倉庫布局示意Fig. 1 Schematic layout of a warehouse section in RMFS

RMFS系統路徑規劃的決策問題是確定機器人行走路線及距離。機器人的行走路徑包含3個部分：1) 從當前位置到目標貨架；2) 運送待揀選貨架至目標揀選站；3) 從揀選站運送貨架返回存儲位置。其中，1) 為空載距離，機器人可以無負荷穿梭于貨架底部；2)和3)為負載距離，機器人只能在通道內運輸貨架。由于機器人在貨架和揀選站之間來回的負載距離占據總距離的主要部分，對負載距離進行優化可以替代機器人行走總距離實現縮短訂單揀選時間、降低機器人能耗的目標[4]。因此，本文以機器人負載距離最小化為目標，將訂單分配與路徑規劃問題聯合起來，并劃分為2個階段：第1階段路徑規劃，找出貨架到不同揀選站之間的最短路徑，即機器人負載距離，標記路線和長度；第2階段訂單分配，根據第1階段所得到的最短距離，以最小化機器人負載距離為目標，生成訂單分批計劃，確定合適的批次出庫貨架及任務揀選站，從而建立起訂單、批次、貨架、揀選站之間的順序關系。

為了便于開展研究且不失一般性，本文做出下列假設：1) 訂單需求信息、貨架存儲信息已知，倉庫采取隨機存儲策略，商品可以存儲在任何可用貨位；2) 無缺貨現象，所有貨架上的商品庫存數量總和大于所有訂單的需求數量；3) 訂單交付時間相同，批次內訂單順序、待揀選貨架到達揀選站順序任意；4) 一個批次訂單只能由同一個揀選站完成揀選，不能拆分到其他揀選站；5) 待揀選貨架不在揀選站之間移動，在一個揀選站完成揀選任務后隨即返回存儲區域；6) 每個貨架規格屬性相同，存儲位置不變，貨架出庫完成揀選任務后回到初始存儲位置；7) 靜態路徑規劃，不考慮機器人行進過程中的擁堵或避碰情況。

2 模型構建

在建立模型前，對參數和變量進行定義，具體如表1所示。

表1 符號定義Table 1 Notation definitions

由此，以機器人負載總距離最小為目標，建立RMFS系統訂單分配與路徑規劃混合整數規劃模型如下：

目標函數(1)表示所有批次出庫貨架往返于存儲位置和揀選站之間的距離，即機器人負載總距離最小，drs為機器人運送貨架r到揀選站s的最短距離。式(2)～(10)表示約束條件。式(2)和(3)確定訂單與批次的對應關系，式(2)表示一個訂單只能被分配到一個批次，式(3)表示批次容量，每一批次中最多包含C個訂單。式(4)～(6)確定批次訂單與貨架的對應關系，式(4)表示從待揀選貨架上揀出的商品數量必須滿足每一批次訂單需求，式(5)表示初始庫存限制，式(6)建立揀選商品數量與貨架是否被選擇之間的關系，使約束線性化。式(7)和(8)確定批次訂單與揀選站、批次貨架集與揀選站之間的對應關系，式(7)表示一個批次訂單只能在同一個揀選站中進行揀選作業，式(8)表示每一批次出庫貨架集前往該批次指定的揀選站。式(9)和(10)表示變量的取值范圍。

3 求解算法設計

RMFS系統訂單分配與路徑規劃聯合問題在訂單分批問題的基礎上增加了貨架和揀選站的任務指派及機器人路徑規劃，是NP難問題。精確算法求解此類問題需要耗費較長時間，本文設計了兩階段的啟發式算法對訂單分配和路徑規劃聯合問題進行求解。

由于A*算法是靜態路網中求解最短路徑的有效方法，被廣泛應用于機器人路徑規劃[11-12]，第1階段首先使用A*算法求解路徑規劃問題。自適應大領域搜索算法(Adaptive Large Neighborhood Search, ALNS)最初由ROPKE等[13]提出用于解決帶時間窗的取送貨車輛問題，算法通過動態選擇移除算子和修復算子不斷對解進行破壞和重構，具有快速收斂的特性，容易跳出局部最優，已適應越來越多的優化場景。?ULJ等[14]構建了ALNS和TS禁忌搜索的組合方法解決大規模訂單分批問題。王新等[15]根據車輛與無人機聯合配送路徑問題特性設計了相應的ALNS算法。李婷玉[16]指出在多商戶多車程同城物流配送車輛路徑問題中，ALNS算法能夠以較低成本獲得最優解，效果優于TS算法。因此，第2階段使用ALNS算法對訂單分配問題進行求解。

3.1 A＊算法

A*算法結合了Dijkstra算法和最佳優先搜索的思想，通過選擇合適的估價函數計算當前節點到目標節點代價最小的距離，啟發式選擇路徑的搜索方向，最終確定整條路徑。A*算法的估價函數可表示為：f(n)=g(n) +h(n)。其中，f(n)表示從起點到終點的估價函數，g(n)表示從起點到當前節點n的實際代價，h(n)表示當前節點n到終點的估計代價。

由于RMFS系統通常設置在網格上，而且機器人只能朝正北、正南、正東、正西4個方向直線移動，選擇柵格法對倉庫環境進行建模，對機器人運動的二維平面區域建立直角坐標系，以1為單位建立一個柵格，采用曼哈頓距離對距離進行度量，兩點之間的曼哈頓距離為南北方向距離加上東西方向距離，即：d=|x1-x2|+|y1-y2|，其中，(x1， y1)和(x2， y2)分別表示2點坐標。

3.2 自適應大領域搜索算法(ALNS)

在傳統ALNS算法的基礎上，根據RMFS訂單分配問題特性，設計改進ALNS算法進行模型求解。

3.2.1 初始解生成

采用隨機方法生成初始解。首先在不違反批次容量約束的前提下，依次將訂單隨機放入候選批次，生成訂單分批方案。接著根據商品庫存信息，尋找滿足每個批次訂單需求的貨架，為批次隨機分配任務揀選站，得到初始解決方案。為了更好地表示訂單分批以及貨架揀選站分配的過程，設計了對應解的編碼。

訂單分批時按訂單編號順序排列，每一訂單i位置上的數字對應著批次b。例如編碼[1, 3, 2, 1]表示訂單1和4劃分到批次1中，訂單2劃分到批次3中，訂單3劃分到批次2中。分配貨架和揀選站時，建立如圖2所示的二維數組，縱軸為批次，橫軸為貨架。貨架出庫狀態用0和正整數表示，0表示在批次訂單b中貨架r不出庫；正整數表示揀選站編號，即貨架r出庫執行批次訂單b的揀選任務，去往批次指定的揀選站s。示例中批次1的出庫貨架為2，3和5，前往揀選站3進行揀選。

圖2 貨架和揀選站分配編碼Fig. 2 Rack and picking station assignment code

3.2.2 移除算子和修復算子

在生成初始解后，ALNS算法采用移除算子將一定比例ξ的節點從解中刪除，再利用修復算子將移除列表里的節點重新插入到不完整的解中，形成新解。

對于訂單分批問題，設計了2種移除算子和2種修復算子。1) 隨機移除訂單。在當前解中隨機選擇一定數量的訂單，將它們移出原來所在的批次。該操作可增加解的多樣性，使其不易陷入局部最優解。2) 最差距離訂單移除。計算每一訂單對應的批次負載距離，移除距離較長的訂單。3)隨機修復訂單。隨機生成批次編號，插入到被破壞的解中。4) 貪婪插入批次。將移除的訂單插入到距離最短的批次中。

對于貨架和揀選站的分配，同樣設計2種移除算子和2種修復算子。1) 隨機移除貨架和揀選站。選擇一定數量的批次，移除批次中對應的任務貨架和揀選站。2) 移除最差批次貨架和揀選站。計算負載距離較長的批次，移除貨架和揀選站。3) 隨機修復貨架和揀選站。隨機分配貨架和揀選站給被破壞的批次解。4) 貪婪修復貨架和揀選站。比較貨架和揀選站的不同分配情況，選擇使批次負載距離增加最少的分配結果。

3.2.3 自適應機制

自適應機制是ALNS算法的核心部分，其基本思想是根據產生的新解情況為移除算子和修復算子賦予相應的分數。當得到新的全局最優解時，算子加分σ1；當得到一個尚未接受過但比當前解更好的解時，算子加分σ2；當得到一個尚未接受過且比當前解差，但滿足接受準則的解時，算子加分σ3。將ALNS算法分為若干階段，算法根據前一個階段的表現更新算子的權重，權重更新公式如下：

其中：wi表示算子第i階段的權重；βi表示算子評分；αi表示算子累計的調用次數；ρ為權重更新系數，控制權重變化速度。算子的表現越好，得分和權重越高，下一階段被輪盤賭選擇的概率越大。

3.2.4 接受準則和終止條件

為了避免陷入局部最優，根據模擬退火算法的Metropolis準則以一定概率P=e-[f(xnew)-f(xcurrent)/T]接受劣解。其中，T為當前溫度，每次迭代T=T0·θ，T0為模擬退火初始溫度，θ∈[0， 1]為降溫速率；f(xnew)為新解的目標函數值；f(xcurrent)為當前解的目標函數值。每次迭代中內層模擬退火過程的終止溫度為Tend，算法達到最大迭代次數后停止搜索。

4 算例分析

4.1 算例構造

如圖3所示，生成小規模(10×8)、中等規模(10×15)、大規模(10×30)3種不同大小的倉庫柵格地圖進行仿真實驗。貨架、揀選站、機器人大小相同且占用一個柵格，機器人行走步長為1。小、中、大3種規模算例的參數設置分別如下：貨架個數為25，50和100，揀選站個數為2、3和4，訂單分批容量為5，10和15，SKU商品總數為50、100和200，每張訂單上SKU種類范圍為[1, 3]，[1, 5]和[1, 7]。另外，倉庫內每個貨架隨機存儲1～6種SKU，每種SKU的庫存量范圍為[10, 50]，訂單需求量范圍為[1, 5]。仿真實驗測試的最大訂單數量為500。

圖3 小規模、中等規模、大規模仿真倉庫柵格地圖Fig. 3 Small scale， medium scale， large scale simulation warehouse grid map

根據ROPKE等[13]的分析，通過多次實驗確定ALNS算法參數：自適應機制中算子分數設置為σ1=33，σ2=9，σ3=13，權重更新系數ρ=0.1；根據文獻[16]，破壞解的長度比例ξ=0.2；在接受準則中，每次迭代內層模擬退火過程的初始溫度T0=100，終止溫度Tend=10，降溫速率θ=0.99，外層最大迭代次數為100。

4.2 結果分析

所有實驗均在Python 3.6中編程實現，運行環境Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz ，16 GB內存，調用IBM ILOG CPLEX12.8，最大運行時間設為5 h(18 000 s)，每組實驗重復10次取均值。

在A*算法得到貨架至揀選站最短距離及機器人搬運路線的基礎上，使用FCFS、CPLEX和ALNS算法分別求解小、中、大3種規模算例的結果如表2～4所示，并將實際運營中常采用的先到先揀選結果(FCFS)作為對比基準。其中Obj表示目標函數即機器人負載總距離，Imp表示CPLEX或ALNS求解結果對比FCFS基準數值的改進程度，Gap表示ALNS與CPLEX求解結果之間的差異程度。

表2 小規模算例求解結果Table 2 Results of small-scale experiments

從小規模算例求解結果中可以看出，相比簡單的FCFS規則，進行訂單分配后優化效果明顯。其中CPLEX求解平均減少49.3%的機器人負載距離，在訂單數量I=20時效果最佳，減少52.5%負載距離。ALNS算法的求解質量也較高，平均減少31.1%的機器人負載距離，在I=10時最大可減少47.6%的負載距離，與CPLEX求解差距均值15.2%，最少為5.8%，得到與CPLEX質量相近的解。

求解時間方面，當訂單數量較少時(I≤20)，CPLEX可以在1 s內求得最優解。但隨著訂單數量的增加，CPLEX求解時間呈指數級增長，在I=40時，計算時間已高達7 027.4 s，當訂單數量為50時已無法在可接受的時間(5 h)內獲得可行解。

對于倉庫規模大、訂單數量多、時間要求高的場景來說，使用CPLEX對訂單進行優化分配實用性差。而ALNS算法受訂單數量增加變化的影響較小，在訂單數量達到100時仍可在較短時間內(588.1 s)獲得21.1%的優化效果，時間優勢明顯，相比CPLEX求解器更適合求解規模較大的訂單分配問題。

由于CPLEX在訂單數量較大的小規模算例中已難生成可行解，中等規模算例中僅對比FCFS和ALNS算法的求解結果。ALNS算法在中等規模算例中仍保持著平均20.1%的優化效果，時間成本低，可在較短時間內獲得高質量的解。

表3 中等規模算例求解結果Table 3 Results of medium-scale experiments

表4 大規模算例求解結果Table 4 Results of large-scale experiments

在大規模算例中，ALNS算法平均可減少10.7%的機器人負載距離，最大可減少15.8%的負載距離(I=360)。當訂單增加到500時，ALNS算法的運行時間也仍保持在合理范圍內(3 967.9 s)。

圖4記錄了ALNS算法在不同規模算例下的計算迭代過程。可以看出ALNS算法基本不依賴初始解的狀態，能顯著減少機器人負載距離，算法收斂較快，性能穩定。

圖4 ALNS算法迭代過程Fig. 4 Iterative process of ALNS algorithm

5 結論

1) 研究電商物流中心RMFS揀選系統多訂單、多貨架、多揀選站場景下的訂單分配和路徑規劃聯合優化問題，構建了以機器人負載距離最小為目標的混合整數規劃模型，并使用A*算法和自適應大鄰域搜索算法(ALNS)進行求解。

2) 仿真結果表明，提出的優化模型和算法最大可縮短47.6%的機器人負載距離，ALNS算法可在較短時間內獲得高質量的解，優化效果良好，能夠有效縮短機器人行走距離，提高訂單揀選效率，降低倉儲成本，研究結論可為電商企業提供運營指導。

3) 未來的研究可以引入更多決策因素，如訂單順序、到達時窗、動態貨位、機器人任務分配等，細化訂單分配與路徑規劃聯合問題特征，使問題更符合RMFS系統實際運營場景。