基于改進(jìn)遺傳算法的智能倉儲(chǔ)多移動(dòng)機(jī)器人協(xié)同調(diào)度

范 媛，李文鋒，賀利軍

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

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

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

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

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

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

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

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

圖2 智能倉儲(chǔ)布局圖

圖3 單機(jī)器人的行駛路徑圖

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

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

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

2.1 問題描述

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

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

2.2 模型符號(hào)說明

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

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

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

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 面向多移動(dòng)機(jī)器人協(xié)同調(diào)度的遺傳算法

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

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

3.1 初始種群與編碼

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

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

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

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

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

(11)

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

4 實(shí)驗(yàn)結(jié)果與分析

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

表2 移動(dòng)機(jī)器人剩余電量

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

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

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

圖7 改進(jìn)遺傳算法收斂圖

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

圖8 模擬退火算法收斂圖

機(jī)器人編號(hào)改進(jìn)遺傳算法求解的任務(wù)序列隨機(jī)分配的任務(wù)序列單個(gè)機(jī)器人代價(jià)值(f)改進(jìn)遺傳算法隨機(jī)分配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

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

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

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