范 媛，李文鋒，賀利軍

(武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

隨著電子商務(wù)行業(yè)的飛速發(fā)展，物流倉儲內(nèi)的訂單揀選逐漸成為電商發(fā)展的核心環(huán)節(jié)。傳統(tǒng)的“人到貨”揀選模式中，60%～70%的時間都耗費在來回揀選貨品上，且有較高的出錯率。此外，當(dāng)前電商行業(yè)訂單結(jié)構(gòu)的特點為品種多、批量小、批次多、周期短[1]，電商行業(yè)對物流倉儲的揀選作業(yè)效率和準(zhǔn)確率提出了更高的要求。現(xiàn)代智能倉儲系統(tǒng)已采用“貨到人”的揀選模式[2]，引入多移動機器人，將貨品直接送至揀選臺或揀選員，大幅度提高了揀選作業(yè)的效率，降低了揀選作業(yè)的出錯率，減少了工人的勞動強度，降低維護成本并且使倉儲空間布局具有良好的重構(gòu)性。因此，構(gòu)建基于多移動機器人的智能倉儲系統(tǒng)已成為當(dāng)下倉儲物流研究的一大熱點[3]。

多移動機器人的協(xié)同調(diào)度是實現(xiàn)構(gòu)建基于多移動機器人智能倉儲的關(guān)鍵。針對多移動機器人的協(xié)同調(diào)度問題，國內(nèi)外學(xué)者已展開了較多的研究。蔣家志等[4]提出一種改進粒子群算法解決訂單任務(wù)調(diào)度，考慮了多訂單間的協(xié)同運輸，提高了智能倉儲的效率，但該模型未考慮多個移動機器人利用率的因素，導(dǎo)致其調(diào)度方案中單個機器人的能耗較高。沈博聞等[5]基于A*算法提出綜合考慮路徑代價和等待時間代價的機器人調(diào)度方法，實現(xiàn)多機器人的靜態(tài)智能調(diào)度，但A*算法僅適用于小規(guī)模運算，無法解決多任務(wù)多機器人的情況。TRIGUI等[6]提出了擴展的分布式市場化算法來解決機器人任務(wù)分配問題，通過交換任務(wù)以提高工作效率，但其為局部調(diào)度，未考慮全局的最優(yōu)性。MA等[7]根據(jù)倉庫任務(wù)的特點，提出了全局任務(wù)先分組再重新分配的任務(wù)分組方法，將傳統(tǒng)的靜態(tài)分配算法應(yīng)用于動態(tài)任務(wù)中，提高了全局任務(wù)路徑均衡的性能。以上文獻(xiàn)均是對多機器人進行任務(wù)分配和路徑規(guī)劃，但未考慮移動機器人電池的放電特性，以及移動機器人空載和載貨時的耗電差異。

智能倉儲多移動機器人在不飽和電量下進行“貨到人”揀選作業(yè)，考慮移動機器人載貨和空載時的耗電差異，將剩余電量作為機器人調(diào)度的約束條件，以多移動機器人作業(yè)總代價最小、作業(yè)代價均衡為優(yōu)化目標(biāo)，構(gòu)建多移動機器人調(diào)度多目標(biāo)優(yōu)化模型。將改進遺傳算法應(yīng)用求解多目標(biāo)優(yōu)化模型，將多個任務(wù)分配至多移動機器人，實現(xiàn)多移動機器人協(xié)同調(diào)度，從而降低智能倉儲多移動機器人作業(yè)成本，提高揀選作業(yè)效率。

1 智能倉儲“貨到人”揀選系統(tǒng)

智能倉儲系統(tǒng)揀選作業(yè)為“貨到人”模式，移動機器人接收上層控制系統(tǒng)(CCS)下發(fā)的任務(wù)序列，根據(jù)任務(wù)序列指令順序搬運貨架至揀選站臺，待揀選人員將貨物揀選完畢，再將貨架搬運至原始位置。移動機器人的導(dǎo)航方式為二維碼導(dǎo)航。移動機器人通過掃描貨架上的二維碼，獲取貨架坐標(biāo)，掃描地面上的二維碼，識別路徑，并將自身位置信息和任務(wù)執(zhí)行情況實時上傳至CCS控制中心[8]。多個系統(tǒng)協(xié)同完成任務(wù)分配與多機器人調(diào)度的流程如圖1所示。

圖1 智能倉儲任務(wù)分配與多機器人調(diào)度流程

智能倉儲布局如圖2所示[9]，從右向左依次為倉儲貨架區(qū)、高速運行區(qū)、排隊等待區(qū)、揀選站臺區(qū)，所有區(qū)域釆用網(wǎng)格排列的模式，多移動機器人在網(wǎng)格構(gòu)成的環(huán)境中直線運行，每個巷道只能通過一個移動機器人。二維碼位于每個網(wǎng)格的中心，移動機器人的步進距離為相鄰兩個二維碼之間的直線距離，且通過二維碼信息判斷下一步的行駛方向。

圖2 智能倉儲布局圖

圖3 單機器人的行駛路徑圖

建立基于場景的坐標(biāo)圖，如圖3所示。單個移動機器人分別搬運A、B、C、D、E這5個貨架行駛至對應(yīng)1～5號揀選臺(縱軸上方框處)，每個機器人的移動單位為兩個小圓點間的距離，箭頭表示機器人的行駛方向。起點為坐標(biāo)(0，1)，方案一的揀選順序為A→B→C→D→E，方案二的揀選順序為A→C→B→E→D。移動機器人運行過程中產(chǎn)生的自身代價定義為移動機器人從任務(wù)起點搬運貨架至揀選臺，再將貨架搬運回原點產(chǎn)生的能耗代價，關(guān)聯(lián)代價的定義為移動機器人以空載狀態(tài)從一個任務(wù)節(jié)點行駛至下一個任務(wù)節(jié)點產(chǎn)生的能耗代價，其代價均與移動機器人的行駛距離成正比。兩種調(diào)度方案產(chǎn)生的自身代價(方形內(nèi))和關(guān)聯(lián)代價(圓圈內(nèi))如圖4所示，其中a為自身代價系數(shù)，b為關(guān)聯(lián)代價系數(shù)。

圖4 兩種方案的自身代價與關(guān)聯(lián)代價

2 問題描述與多目標(biāo)模型

2.1 問題描述

假設(shè)企業(yè)資源計劃系統(tǒng)(ERP系統(tǒng))接收來自電子商務(wù)平臺的一批訂單，完成這批訂單的揀選工作需搬運n個貨架，控制中心基于調(diào)度算法將任務(wù)分為m組，分配至m個空閑機器人，智能倉儲共有e個揀選臺，每個訂單由一個揀選臺單獨完成。單個移動機器人執(zhí)行任務(wù)序列的過程中分為空載和載貨兩個狀態(tài)[10]，兩個狀態(tài)下行駛的單位距離耗電量不同，耗電量與機器人的行駛距離成正比。同時考慮鋰電池的放電特性[11]，電池消耗比值與剩余里程量關(guān)系如圖5所示，可見隨著電池使用量的增加，剩余行駛距離也在加速下降。針對不同剩余電量的移動機器人調(diào)度問題，應(yīng)考慮剩余電量與任務(wù)代價的關(guān)系。

圖5 電池消耗比值與剩余里程量關(guān)系圖

2.2 模型符號說明

機器人只能朝東南西北4個方向行駛，故定義任意兩個節(jié)點之間為曼哈頓距離：Cij為移動機器人從貨架i行駛至貨架j的曼哈頓距離，即任務(wù)關(guān)聯(lián)距離，Cij=d×(|Xi-Xj|+|Yi-Yj|)；Uip為移動機器人搬運貨架i至揀選臺p的曼哈頓距離，即任務(wù)自身距離，Uip=d×(|Xi-Xp|+|Yi-Yp|)。

2.3 數(shù)學(xué)模型

基于“貨到人”的揀選作業(yè)模式，構(gòu)建多機器人的代價優(yōu)化模型。模型考慮多移動機器人作業(yè)總代價最少、多移動機器人作業(yè)代價均衡兩個優(yōu)化目標(biāo)，其目標(biāo)函數(shù)如式(1)所示，F(xiàn)(π)取值越小，表示多移動機器人調(diào)度方案越優(yōu)，其中π為一種調(diào)度方案。式(2)表示所有機器人的總?cè)蝿?wù)代價，包括任務(wù)自身代價、任務(wù)關(guān)聯(lián)代價。式(3)為任務(wù)代價均衡值。式(4)表示兩個子目標(biāo)f(π)與h(π)對總目標(biāo)影響的重要程度，當(dāng)w1w2時表示總代價最小為優(yōu)化主要目標(biāo)。式(5)為單個機器人的任務(wù)代價。式(6)為總?cè)蝿?wù)代價的平均值。式(7)表示機器人空載運行代價要小于機器人載貨運行代價。式(8)表示機器人電池消耗與剩余里程數(shù)之間的關(guān)系[12]。式(9)表示每個機器人的行走里程均在電量約束范圍內(nèi)，且有預(yù)留的安全電量返回其充電區(qū)。因剩余相同電量時，L空載>L載貨，保證載貨機器人能安全行駛的電量，也能保證空載機器人安全行駛相同距離，故僅考慮載貨狀態(tài)的剩余里程數(shù)滿足安全電量要求。式(10)表示一個任務(wù)僅被一個機器人執(zhí)行。式(11)表示任務(wù)全部分配至機器人。

F(π)=min(w1f(π)+w2h(π))

(1)

(2)

(3)

w1+w2=1,0

(4)

(5)

(6)

s.t.

θ1<θ2

(7)

L(x)=ax2+bx+c

(8)

L(1-k(r))-L(1-v)，

?r∈{1,2,…,m}

(9)

(10)

(11)

3 面向多移動機器人協(xié)同調(diào)度的遺傳算法

隨著任務(wù)數(shù)量和移動機器人數(shù)量的增加，問題求解空間呈指數(shù)增長，經(jīng)證明屬于NP難題。針對此類問題的求解難度，遺傳算法以生物進化為原型，具有很好的全局性，計算時間少，魯棒性高，已被廣泛應(yīng)用于求解各類NP難題[13- 14]。故擬采用遺傳算法求解多移動機器人協(xié)同調(diào)度模型。針對遺傳算法在應(yīng)用過程中出現(xiàn)的收斂慢和封閉競爭問題，將增加虛擬任務(wù)進行任務(wù)分配，快速排除不可行解，提高遺傳算法的運行速度?；谔摂M任務(wù)的改進遺傳算法的實現(xiàn)流程如圖6所示。

圖6 基于虛擬任務(wù)的遺傳算法實現(xiàn)流程

3.1 初始種群與編碼

在組合優(yōu)化問題中，采用整數(shù)編碼方式對求解問題進行直觀描述。設(shè)所需完成的任務(wù)數(shù)為Ns，可調(diào)度的移動機器人數(shù)為Mr，設(shè)置虛擬任務(wù)數(shù)為Mr-1，故個體的染色體編碼長度為Ns+Mr-1位。每位基因表示一個任務(wù)序號，基因的位置表示任務(wù)的執(zhí)行順序。除了第一組任務(wù)序列，其余任意兩個虛擬任務(wù)之間的任務(wù)作為一個任務(wù)序列組。任務(wù)分配算法實現(xiàn)流程為：輸入初始種群M、任務(wù)序列Ns=[Ns(1),Ns(2),…，Ns(q)]，其中q為任務(wù)的總數(shù)量，虛擬任務(wù)數(shù)組POS=[POS(1),POS(2),…,POS(k-1),POS(k),…,POS(Mr-1)]，隨機分配方案， 每個任務(wù)相鄰位置為虛擬任務(wù)可選空位，虛擬任務(wù)數(shù)組POS表示Mr-1個虛擬任務(wù)選擇的插入位置數(shù)組，Sk={NS[POS(k-1)+1],NS[POS(k-1)+2],…,NS[POS(k)]}表示插入虛擬任務(wù)后機器人k的任務(wù)序列，算法結(jié)束后輸出Sk,k=1,2,…,Mr。

例如一批訂單的揀選作業(yè)需搬運10個貨架，即生成10個任務(wù)，可調(diào)度5輛移動機器人，增設(shè)4個虛擬任務(wù)(任務(wù)11、12、13、14)，則每個個體的編碼由14個數(shù)組成。任務(wù)編碼與分配方案示例如表1所示，M1～M5分別為分配后多的5組任務(wù)組。遺傳算法中，將虛擬任務(wù)與實際任務(wù)之間的關(guān)聯(lián)代價設(shè)置為0，將兩個虛擬任務(wù)之間的關(guān)聯(lián)代價設(shè)置為無窮大，則虛擬任務(wù)相鄰的方案(如方案2和方案4)就會被淘汰。

表1 任務(wù)編碼與分配方案示例

3.2 適應(yīng)度函數(shù)

在遺傳算法的運行過程中，需要通過適應(yīng)度函數(shù)值來評價個體在種群中的優(yōu)劣程度。個體的適應(yīng)度值越大，代表個體越優(yōu)秀。將適應(yīng)度函數(shù)選取為：

(11)

其中，F(xiàn)(π)為方案π的目標(biāo)函數(shù)，即方案π的總代價。

4 實驗結(jié)果與分析

為了驗證模型的準(zhǔn)確性及遺傳算法的有效性，采用Matlab進行仿真實驗。實驗設(shè)置100 m×100 m的柵格地圖為實驗環(huán)境，d=1 m，揀選站臺的數(shù)量e=5，機器人的安全電量為總電量的10%，即v=10%可以滿足機器人在倉儲中的任意位置返回充電區(qū)。機器人數(shù)量m=5，每個機器人的剩余電量如表2所示。

表2 移動機器人剩余電量

隨機生成待分配的任務(wù)數(shù)n=20，隨機生成任務(wù)的位置與任務(wù)需到達(dá)揀選臺的編號如表3所示。

表3 隨機生成任務(wù)信息表

改進遺傳算法的種群M=50，進化代數(shù)G=450，交叉概率Pc=0.7，變異概率Pm=0.01，初代個體編碼串為隨機數(shù)產(chǎn)生。筆者將改進遺傳算法與模擬退火算法做比較，兩種算法求解模型的收斂結(jié)果分別如圖7和圖8所示,可以看出改進遺傳算法與模擬退火算法最終的適應(yīng)度值相差不大，但改進遺傳算法迭代至150代左右就開始收斂，比模擬退火算法的收斂效果更好。

圖7 改進遺傳算法收斂圖

表4所示為改進遺傳算法求解的任務(wù)序列、隨機分配的任務(wù)序列及兩種求解方法下的單個機器人代價值，其中，w1、w2均取0.5。改進遺傳算法得到的調(diào)度方案中，移動機器人執(zhí)行任務(wù)的代價值大幅減少，且滿足電量要求。隨機分配的調(diào)度方案中，單個移動機器人執(zhí)行任務(wù)的代價值均較高，且3號和4號移動機器人執(zhí)行任務(wù)的代價值超過了安全電量值，不符合實際工程情況。

圖8 模擬退火算法收斂圖

機器人編號改進遺傳算法求解的任務(wù)序列隨機分配的任務(wù)序列單個機器人代價值(f)改進遺傳算法隨機分配11-2-3-4-51-3-4-141 618.081 972.6026-7-20-85-7-10-91 260.731 624.38311-12-14-1311-6-8-201 852.702 378.08416-20-10-916-13-12-151 589.692 048.22517-18-19-1517-18-19-21 484.491 912.68

為了進一步評估模型和算法，令機器人個數(shù)分別取8、10，分別對50、100個任務(wù)進行分配。任務(wù)分配結(jié)果如圖9所示，分配至同一個機器人的任務(wù)用同一連線相連，不同的機器人接收任務(wù)的結(jié)果用不同的連線區(qū)分。

投入3種不同數(shù)量機器人時，模型求解結(jié)果如表5所示，可以看出與模擬退火算法、任務(wù)隨機分配方法相比，改進遺傳算法優(yōu)化后的各項函數(shù)值均小于模擬退火算法、隨機分配方法的各項函數(shù)值，即優(yōu)化后的協(xié)調(diào)調(diào)度方案在滿足電量安全的情況下，有效減少了機器人執(zhí)行任務(wù)代價且任務(wù)分配均衡。改進遺傳算法優(yōu)化函數(shù)值大多比模擬退火優(yōu)化函數(shù)值更小，且改進遺傳算法收斂速度優(yōu)于模擬退火算法的收斂速度。故改進后的遺傳算法可快速得到機器人協(xié)同調(diào)度的優(yōu)化方案。

圖9 任務(wù)分配結(jié)果

(m,n)算法[F,f,h]w1=0.2,w2=0.8w1=0.5,w2=0.5w1=0.8,w2=0.2m=5n=20遺傳算法[7 877.92, 7 805.70, 72.22][7 877.92, 7 805.70, 72.22][7 346.79, 7 279.44, 67.35]模擬退火[8 198.32, 8 120.20, 78.20][8 301.32, 8 230.12, 71.20][8 770.21, 8 701.01, 69.20]隨機分配[13 005.77 , 12 489.12 , 516.65][10 231.61, 10 057.15, 174.46][12 149.15, 11 647.10, 502.05]m=8n=50遺傳算法[21 931.79, 21 855.96, 75.83][1 7661.08, 17 600.02, 61.06][20 453.15, 20 382.43, 70.71]模擬退火[22 081.43, 22 010.22, 71.21] [19 093.35, 19 013.05, 80.30][21 861.80, 21 789.61, 72.19 ]隨機分配[35 497.02, 34 969.54, 527.48][28 643.21, 28 160.03, 483.18][33 124.03, 32 611.89, 512.14]m=10n=100遺傳算法[46 915.45, 46 834.20, 81.25][37 779.74, 37 714.32, 65.42][43 752.41, 43 676.64, 75.77]模擬退火[47 194.68, 47 102.38, 92.30][39167.26, 39 087.46, 79.80][57 039.67, 56 958.04, 81.63]隨機分配[75 478.46, 74 934.72, 543.74][60 839.18, 60 342.91, 496.27][70 409.92, 69 882.62, 527.30]

5 結(jié)論

筆者針對智能倉儲環(huán)境中多移動機器人協(xié)同調(diào)度問題，構(gòu)建了多移動機器人協(xié)同調(diào)度的多目標(biāo)優(yōu)化模型。該多目標(biāo)優(yōu)化模型考慮了機器人空載行駛與載貨行駛的耗電差異約束條件，以及多機器人執(zhí)行任務(wù)的自身代價與任務(wù)間的關(guān)聯(lián)代價兩個優(yōu)化目標(biāo)。為求解該多目標(biāo)優(yōu)化模型，提出了面向多移動機器人調(diào)度問題的改進遺傳算法，算法通過引入虛擬任務(wù)，以構(gòu)造任務(wù)分配序列。將隨機分配方法、模擬退火算法與筆者的算法進行對比實驗分析，結(jié)果表明，采用改進遺傳算法求解文中模型可獲得更好的求解結(jié)果，多移動機器人執(zhí)行任務(wù)的總代價小且任務(wù)分配均衡，同時改進遺傳算法的收斂性優(yōu)于模擬退火算法，證明了模型的準(zhǔn)確性及改進遺傳算法在解決智能倉儲多移動機器人協(xié)同調(diào)度問題的有效性。