翁 迅 張經(jīng)天 胡 曉

(1. 北京郵電大學現(xiàn)代郵政學院，北京 100876；2. 北京郵電大學人工智能學院，北京 100876)

隨著人工智能技術、5G技術、物聯(lián)網(wǎng)技術等飛速發(fā)展，面對以新技術、新產(chǎn)業(yè)、新業(yè)態(tài)和新模式為特征的新經(jīng)濟背景，相關技術從專業(yè)知識點的分割體系轉(zhuǎn)向多學科知識點的跨界交叉融合[1]。隨著搬運機器人等智能裝備在各種新經(jīng)濟領域的應用日益廣泛，其所涉及的知識結構已經(jīng)突破了傳統(tǒng)物流工程的范疇：比如在電商的貨到人系統(tǒng)中考慮充電的搬運機器人排班模型[2]；倉儲環(huán)境下的移動搬運機器人的融合定位系統(tǒng)[3]；或者針對搬運機器人完成行李智能搬運現(xiàn)場試驗平臺的搭建[4]；針對貨架搬運機器人揀選系統(tǒng)的訂單排序與動態(tài)儲位分配問題[5]；針對機器人倉儲作業(yè)系統(tǒng)的作業(yè)流程得出魚骨型貨架布局性能最優(yōu)設計[6]，也有針對基于改進雞群優(yōu)化算法的食品揀取機器人路徑規(guī)劃方法研究[7]；針對食品倉庫的全向搬運機器人跟蹤能力提出改進路徑跟蹤控制方法研究[8]。現(xiàn)有的相關研究在驗證階段采用主流物流系統(tǒng)仿真平臺如Automod、Flexsim等，往往不支持基于實際訂單數(shù)據(jù)的算法接口測試，導致系統(tǒng)建模仿真的驗證效果和實際使用的情況差距較大，進而影響了搬運機器人系統(tǒng)在行業(yè)的應用推廣。

研究擬探討開發(fā)多場景下搬運機器人任務調(diào)度與仿真平臺，旨在通過對搬運機器人在物流中心的整箱揀選、訂單拆零作業(yè)、出入庫搬運作業(yè)等各個場景搭建，利用場景特性分析，探索研究搬運機器人的多智能體任務分配、多車調(diào)度及交通規(guī)劃、單車路徑實時優(yōu)化等特定算法開發(fā)，并通過仿真平臺實現(xiàn)對所設計的算法進行模擬和仿真驗證，最終構建并驗證基于實際訂單數(shù)據(jù)的搬運機器人任務調(diào)度和算法測試平臺的可行性。

1 搬運機器人多場景任務調(diào)度與仿真平臺構建

該任務調(diào)度與仿真平臺的搭建，以Marius等[9]開發(fā)的開源仿真框架RAWSim-O為基礎進行二次開發(fā)，結合國內(nèi)物流行業(yè)的實際情況為應用場景，在此平臺基礎上實現(xiàn)符合物流行業(yè)標準的搬運機器人多場景任務調(diào)度與仿真驗證。通過調(diào)研食品、醫(yī)藥、飲料等物流中心的實際場景應用特性，允許自主設計對應的智能算法并在平臺上進行程序?qū)崿F(xiàn)和驗證。針對以上的目標進行如下平臺設計。

1.1 仿真場景設置

(1) 場景一：針對移動機器人的上架過程的策略仿真。

食品和醫(yī)藥等產(chǎn)品的上架過程涉及貨位指派問題，即將商品的SKU與倉庫中貨位進行綁定的過程，仿真優(yōu)化目標是使得訂單后續(xù)的揀選時間代價最小。

(2) 場景二：針對多揀選臺作業(yè)的訂單波次分批策略仿真。

現(xiàn)代化物流中心的訂單分批是指將截止到當前到達訂單池中的所有訂單按照一定的規(guī)則分若干波次，每次揀選臺處理一個波次的訂單，其目的是為了降低訂單揀選時貨架的搬運次數(shù)、機器人的行走距離或作業(yè)時間。

(3) 場景三：針對存在任務分級的多揀選機器人任務分配策略仿真。

機器人搬運物流系統(tǒng)中，“貨到人”機器人系統(tǒng)的任務分配是按照一定的規(guī)則，把空閑的搬運機器人資源和系統(tǒng)待執(zhí)行任務進行最佳匹配的過程。

(4) 場景四：針對有存儲規(guī)則限制的多機器人路徑規(guī)劃與協(xié)調(diào)策略仿真。

不同的存儲規(guī)則設置對機器人的路徑選擇有較大影響。合理地進行多機器人路徑動態(tài)規(guī)劃，可以有效避免出現(xiàn)通道擁塞等問題。

1.2 仿真驗證要求

1.2.1 場景一：針對移動機器人的上架過程的策略仿真

以食品和醫(yī)藥物流中心為例，在滿足食品質(zhì)量管理規(guī)范的情況下，通?？紤]SKU的關聯(lián)性、貨物周轉(zhuǎn)率等因素進行優(yōu)化。比如藥品要根據(jù)GSP的相關要求，需要滿足藥品和非藥品分開、外用用藥和內(nèi)服用藥分開、監(jiān)管類藥品和非監(jiān)管類藥品分開、易串味藥品和其他藥品分開等規(guī)則。這樣的上架過程和傳統(tǒng)的電商上架策略有明顯區(qū)別。在仿真平臺中可以針對物流上架過程的策略進行算法設計并進行模擬驗證。

1.2.2 場景二：針對多揀選臺作業(yè)的訂單波次分批策略仿真 由于食品物流中心需要嚴格進行先進先出的批次管理。在多個揀選臺同時作業(yè)的情況下，如果設計的訂單波次分批策略中訂單波次分批的聚類度不高，則容易導致機器人的搬運次數(shù)較多，系統(tǒng)需要配置較多的搬運機器人才能滿足需求；如果設計的訂單波次分批的聚類度過高，則容易導致存在某個批次的尾訂單箱在各個揀選臺之間的揀選任務耦合的問題，導致整個揀選作業(yè)的效率難以提升。食品行業(yè)的特性導致訂單波次分批策略和傳統(tǒng)電商系統(tǒng)的處理策略有較大區(qū)別。在試驗過程中可以針對實際的訂單數(shù)據(jù)進行訂單波次分批策略算法設計，并針對設計的算法進行仿真模擬以驗證其效果。

1.2.3 場景三：針對存在任務分級的多揀選機器人任務分配策略仿真 任務分配通常需要考慮機器人行駛距離的最優(yōu)、機器人的電量情況、任務執(zhí)行的時間窗等。由于任務分配是一個動態(tài)分配的過程，因為不斷有機器人完成釋放任務，不斷有新的任務到達。另外，還有充電任務也要根據(jù)充電策略及時插入機器人的任務序列中，且優(yōu)先級最高。在食品物流中心，由于訂單存在截單時間要求等問題，任務是非均勻下發(fā)至機器人調(diào)度系統(tǒng)；部分訂單還存在緊急配送的需求、需要進行緊急插單或者需要增補訂單內(nèi)容等情況。物流中心的業(yè)務特性導致的機器人任務分批策略和傳統(tǒng)電商的任務分批策略有較大區(qū)別。平臺可以針對實際的物流中心場景進行任務分配算法設計，并針對設計的任務分配算法進行仿真模擬以驗證其效果。

1.2.4 場景四：針對有存儲規(guī)則限制的多機器人路徑規(guī)劃與協(xié)調(diào)策略仿真 傳統(tǒng)的電商物流系統(tǒng)中，儲位分配是基于銷售品種的熱銷情況決定具體分布方式。通常而言，熱銷品種設置得離揀選站臺較近，冷門商品設置得離揀選站臺較遠。這種儲位分配方式下的多機器人路徑規(guī)劃，相對比較簡單。在食品物流中心，由于各自產(chǎn)品的存儲需要遵循相關的存儲規(guī)則，比如巧克力、酸奶等產(chǎn)品必須在溫度控制區(qū)進行存儲等。不同存儲特性的產(chǎn)品必須分區(qū)存放，在訂單執(zhí)行過程中，要實現(xiàn)跨區(qū)揀選的任務需求，平臺可以針對食品物流的儲位分配特點進行多機器人路徑規(guī)劃與協(xié)調(diào)算法設計，通過實際場景的布局和任務對算法進行仿真驗證，從而測試多機器人路徑規(guī)劃與協(xié)調(diào)算法的效果。

1.3 搬運機器人多場景任務調(diào)度與仿真平臺框架

搬運機器人多場景任務調(diào)度與仿真平臺的本質(zhì)是搭建一個離散事件系統(tǒng)仿真平臺。其核心是針對搬運機器人作業(yè)的任務場景，模擬搬運機器人的隨機和動態(tài)發(fā)生的事件，最終構建各個事件之間的關聯(lián)關系。在搬運機器人多場景任務調(diào)度與仿真平臺的基礎上，通過算法接口完成某個具體場景下的大量隨機試驗，最終對試驗結果進行統(tǒng)計，從而獲得相應場景下的算法優(yōu)劣性評估?；诖?agent)的仿真建模方法被認為是研究復雜系統(tǒng)的有效途徑，這種建模仿真技術，在建模的靈活性、層次性和直觀性方面較傳統(tǒng)的建模技術都有明顯的優(yōu)勢，非常適合機器人搬運系統(tǒng)的建模與仿真。

基于代理的仿真建模方法，通過從個體到整體、從微觀到宏觀來研究復雜系統(tǒng)的復雜性，從而克服了復雜系統(tǒng)難以自上而下建立傳統(tǒng)數(shù)學模型的困難，有利于研究復雜系統(tǒng)具有的偶發(fā)性、非線性、隨機性等特點。因此該仿真驗證平臺考慮采用基于代理和離散事件系統(tǒng)建模的方法進行仿真平臺的構建，其基本框架見圖1。

圖1 仿真平臺系統(tǒng)框架Figure 1 System framework of simulation platform

在仿真平臺的系統(tǒng)框架中，“代理”主要是模擬搬運機器人系統(tǒng)中的物理世界對象(如機器人、貨架、貨位、工作站、商品等)，也可以模擬搬運機器人系統(tǒng)中的虛擬實體(如模擬訂單流等)。

“仿真器”在整個仿真平臺系統(tǒng)的任務包括：① 更新代理的屬性；② 將“代理”觸發(fā)的事件傳遞給“控制器”，“控制器”可以立即做出決策，也可以緩沖多個請求，稍后通過優(yōu)化算法后再發(fā)布決策；③ 將最終的信息公開給可視化組件，用戶通過界面觀測仿真系統(tǒng)的運行情況，也可以與界面進行交互，改變策略，實時干涉仿真的運行。

仿真平臺模擬的揀選作業(yè)仿真流程如圖2所示。

圖2 揀選作業(yè)仿真流程Figure 2 Simulation of picking process

在仿真平臺的系統(tǒng)框架中，“控制器”是決策問題的具體實現(xiàn)，在該仿真驗證平臺中，所有的算法都體現(xiàn)在“控制器”的算法接口當中，仿真平臺僅定義與控制器交互的接口，“控制器”包括訂單分配(POA)控制器、任務分配(TA)控制器、路徑規(guī)劃(PP)控制器、貨架儲位分配(PSA)控制器、揀選貨架選擇(PPS)控制器等。當“控制器”運行優(yōu)化算法時，允許控制器緩沖某些決策(如分揀訂單的波次分配)，并行運行優(yōu)化過程，并稍后提交決策。由于部分算法需要較長的計算時間以得出決策，在這種情況下，可以通過軟件上的多線程技術在算法運算的同時計算和更新其他與此無關對象的狀態(tài)，從而加快仿真平臺的推進速度。

2 基于記憶精英種群的災變自適應大鄰域搜索算法(MEPCALNS)

針對場景三“針對存在任務分級的多揀選機器人任務分配策略仿真”，根據(jù)醫(yī)藥物流中心的作業(yè)特點，考慮在揀選工作站排隊約束和“待揀選”貨架的唯一性約束，以機器人完工時間最小為目標建立任務分配數(shù)學模型，并進行仿真驗證。構建的典型地圖布局示意圖如圖3所示。

圖3 典型地圖布局示意圖Figure 3 Typical diagram of map layout

任務分配問題可以描述為：考慮下發(fā)給拆零揀選工作站某個批次的揀選任務可以按訂單行拆分為M個揀選作業(yè)任務(簡稱任務)；現(xiàn)有N個機器人共同執(zhí)行這些任務，每個搬運任務只能由一個機器人進行執(zhí)行，滿足每個機器人同時只能執(zhí)行一個搬運作業(yè)任務；任務分配算法需要在滿足客戶訂單設置的優(yōu)先級約束下為每個機器人分配一個任務列表，機器人按優(yōu)化后的作業(yè)流程順序執(zhí)行任務列表中相應的任務，目標期望達到所有機器人完成其對應的任務列表的最大完工時間最短。

建立數(shù)學模型，各參數(shù)含義見表1。

表1 數(shù)學模型參數(shù)說明Table 1 Description of mathematical model parameters

目標函數(shù)

(1)

約束于

J1J2∪…∪JN=J，

(2)

Jr∩J2=?,?r∈R,?s∈R,r≠s，

(3)

(4)

(5)

其中，目標函數(shù)式(1)表示所有機器人的最大任務列表的完工時間最小化。約束條件式(2)表示所有任務均可以被分配，式(3)表示機器人所分配到的任務不會重復，式(4)、式(5)為客戶訂單執(zhí)行的優(yōu)先級約束。式(4)表示任務隊列中，內(nèi)部排序中后序任務的優(yōu)先級不能高于前序任務的優(yōu)先級；式(5)表示任務隊列之間后序任務隊列的優(yōu)先級不能高于前序任務隊列的優(yōu)先級。

針對上述模型的求解，提出基于記憶精英種群的災變自適應大鄰域搜索算法(Memory Elite Population based Catastrophe Adaptive Large Neighborhood Search，MEPCALNS)，其算法流程見圖4。

圖4 MEPCALNS流程圖Figure 4 MEPCALNS flow chart

MEPCALNS在仿真平臺設置參數(shù)見表2。

表2 平臺參數(shù)設置Table 2 Experimental parameter settings

基于大、中、小3種訂單規(guī)模以及5種地圖規(guī)模隨機生產(chǎn)正交算例RAND1-1～RAND1-5、RAND2-1～RAND2-5、RAND3-1～RAND3-5。具體算例設置見表3。

表3 算例設置Table 3 Example settings

采用仿真平臺對派遣規(guī)則、自適應大領域搜索算法(Adaptive Large Neighborhood Search，ALNS)和試驗設計的基于記憶精英種群的災變自適應大鄰域搜索算法MEPCALNS進行實驗驗證，結果見表4。

表4 算法有效性試驗結果?Table 4 Experimental results of algorithm effectiveness

由表4可知，啟發(fā)式算法在所有算例中的求解效果均明顯優(yōu)于傳統(tǒng)的派遣規(guī)則。而基于記憶精英種群的災變自適應大鄰域搜索算法(MEPCALNS)相對ALNS算法而言，算例的提升效率比較穩(wěn)定，說明MEPCALNS算法在求解“場景三”的相關問題時，相比ALNS算法存在優(yōu)越性，算法效率平均提升3.16%。

3 結論

試驗表明，通過搬運機器人多場景任務調(diào)度與仿真平臺的構建，可以根據(jù)使用者所選擇的場景進行實際調(diào)研，設計各種優(yōu)化算法，并在平臺上采用同樣的參數(shù)配置和場景地圖，將設計的算法和傳統(tǒng)的算法進行仿真驗證，有效解決了現(xiàn)有仿真平臺的不足。該任務調(diào)度與仿真平臺目前是基于仿真時鐘的事件驅(qū)動模式，隨著5G和數(shù)字孿生技術的進一步發(fā)展，未來存在通過5G技術采集現(xiàn)場實時狀態(tài)信息，升級為數(shù)字孿生平臺的可能性。