葉杭璐,何利力

(浙江理工大學(xué) 信息學(xué)院,杭州 310018)

目前,我國物流業(yè)發(fā)展的特點(diǎn)之一是智慧物流進(jìn)入創(chuàng)新爆發(fā)時期,“互聯(lián)網(wǎng)+智慧倉儲”等創(chuàng)新模式迅速發(fā)展.人工智能技術(shù)已經(jīng)融入到了物流行業(yè)的生產(chǎn)倉儲環(huán)境中,智慧倉儲物流設(shè)備的使用大大節(jié)省了人力資源,充分發(fā)揮機(jī)器換人、貨物找人、可視管理的運(yùn)行理念,遵循依托物聯(lián)網(wǎng)與智能算法,進(jìn)行物流倉儲的全流程自動控制的核心思想,通過生產(chǎn)物流的信息化、快速、高效、可追溯性,實(shí)現(xiàn)真正智能化.智慧倉儲物流通過依托物聯(lián)網(wǎng)與智能算法,進(jìn)行全流程自動控制,實(shí)時、有效地管理物流,提供更具社會價值的物流效應(yīng)[1].中國作為生產(chǎn)大國,智慧物流為大勢所趨.

智慧物流調(diào)度設(shè)計(jì)的關(guān)鍵是要滿足系統(tǒng)訂單貨物運(yùn)送的要求,滿足客戶、AGV 和云技術(shù)之間動態(tài)協(xié)作的需求以及滿足物流倉儲的實(shí)際操作需求.高效率和一致性是智慧物流調(diào)度系統(tǒng)的關(guān)鍵.在智慧倉儲中,貨物被放在可以移動的貨架上,用來進(jìn)行貨物運(yùn)送工作的自動引導(dǎo)車(Automated Guided Vehicle,AGV)是一種先進(jìn)的自動化物流設(shè)備,具有自動化程度高,生產(chǎn)線靈活的特點(diǎn).當(dāng)接收到需要處理的命令時,控制系統(tǒng)對AGV 發(fā)送指令,AGV 執(zhí)行具體的指令,完成物料貨架的搬運(yùn)工作,等貨架上的物品被取下后,然后再將貨架再送回至指定位置[2].

本文通過對概率轉(zhuǎn)換公式的改進(jìn)和更新信息素,提出一種改進(jìn)的蟻群算法,規(guī)劃AGV 的運(yùn)行路線.在規(guī)劃最佳路徑的同時,需要考慮AGV 互相之間的碰撞或與貨架碰撞的情況.通過時間窗模型,為優(yōu)化路徑規(guī)劃的模型和算法提供了有效的方法.最后在基于理論的基礎(chǔ)上,結(jié)合倉儲物流的實(shí)際運(yùn)行環(huán)境,建立柵格地圖,通過模擬仿真實(shí)驗(yàn),表明該算法可以快速、準(zhǔn)確地獲得最優(yōu)解.

1 建立AGV 的工作環(huán)境模型

在智慧倉儲的制造車間內(nèi),從AGV 的起始移動位置到指定貨物對應(yīng)的貨架位置,需要獲取一條優(yōu)化的路徑來引導(dǎo)AGV 的運(yùn)動[3].首先根據(jù)AGV 的工作環(huán)境建立模型,通過模型的建立把車間內(nèi)AGV 的工作環(huán)境轉(zhuǎn)化為機(jī)器能夠識別的信息.在制造車間內(nèi),由于貨物數(shù)量龐大,貨架布局時會盡量工整、對稱,為AGV的行駛設(shè)計(jì)出便于通行的過道.因此在制造車間內(nèi),只考慮靜態(tài)障礙物的情況下,所有障礙物的數(shù)量及規(guī)模都是有限的且已知的[4].

1.1 柵格法

柵格法建立模型時將需要建模的空間環(huán)境視為一個平面,然后將平面分割成一個個柵格,存儲了環(huán)境信息.柵格類型可分為兩種類型：陰影部分表示障礙柵格(由1 表示),AGV 禁止通行的區(qū)域；白色部分表示自由柵格(由0 表示),AGV 可以通行的區(qū)域[5].AGV 只能在自由柵格中移動,單位柵格的大小必須完全包含AGV[6].為了避免碰撞,在規(guī)定障礙物柵格時應(yīng)該適當(dāng)?shù)念A(yù)留出一定的安全空間.本文使用柵格法[7]將制造車間劃分為由m×n個大小相同的柵格方塊組成的二維空間.

路徑規(guī)劃的目標(biāo)是尋找包含開始網(wǎng)格、結(jié)束網(wǎng)格和有序網(wǎng)格子集的網(wǎng)格集,并在遇到障礙物網(wǎng)格時避開它們[8].AGV 實(shí)時上報位置信息,在這些柵格化的環(huán)境中,將通過相應(yīng)的算法檢索路線,遍歷整個柵格地圖并記錄整個路線[9].本文柵格環(huán)境的編號是從左到右、由下往上的,如圖1所示,為模擬車間的10×10 的柵格圖模型.

圖1 環(huán)境柵格模型圖

按行駛方向,圖1中AGV1 在節(jié)點(diǎn)32,則它下一步到達(dá)的節(jié)點(diǎn)為33,AGV2 在節(jié)點(diǎn)55,則它下一步到達(dá)的節(jié)點(diǎn)為45.

1.2 時間窗模型

AGV 從進(jìn)入節(jié)點(diǎn)到離開節(jié)點(diǎn)所形成的時間周期稱為時間窗,每個時間窗口的時間段只能通過當(dāng)前AGV,其他AGV 不允許通過當(dāng)前AGV 停留時間窗內(nèi)的節(jié)點(diǎn)[10].在對多個AGV 進(jìn)行路徑規(guī)劃時,為了避免出現(xiàn)沖突和死鎖現(xiàn)象,每個節(jié)點(diǎn)在任務(wù)開始到任務(wù)結(jié)束期內(nèi),通過節(jié)點(diǎn)的AGV 小車將時間劃分為不同的預(yù)留時間段,每個節(jié)點(diǎn)預(yù)留時間段中間的空閑時間間隔可以用來規(guī)劃其他AGV 的行駛路徑,此時其他AGV 可以通過該節(jié)點(diǎn).

AGV 通過每個網(wǎng)格的時間可以通過各種傳感器收集,并且可以分為保留時間和空閑時間.如圖2引入變量：保留時間是在第n個節(jié)點(diǎn)占用的第k個時間窗；空閑時間是在第n個節(jié)點(diǎn)占用的第k個空閑時間窗[11].通過空閑時間窗口來計(jì)劃避障,根據(jù)圖1的兩個AGV的行駛方向,規(guī)劃路徑：AGV1 的路徑信息位節(jié)點(diǎn)32、33、34、35、36,最終到達(dá)目標(biāo)節(jié)點(diǎn)37,相應(yīng)節(jié)點(diǎn)的保留時間窗為AGV2 從起始節(jié)點(diǎn)55 出發(fā),經(jīng)過節(jié)點(diǎn)45、35、25,到達(dá)目標(biāo)節(jié)點(diǎn)15,相應(yīng)節(jié)點(diǎn)的保留時間窗為兩個AGV 的時間窗口模型的示意圖如圖2所示.

當(dāng)出現(xiàn)選擇路徑?jīng)_突時,AGV 行進(jìn)的優(yōu)先級先后順序根據(jù)3 個方面來制定：(1)裝有行李架的AGV的優(yōu)先級高于未裝有行李架的；(2)任務(wù)完成設(shè)定的時間早的AGV 優(yōu)于任務(wù)完成時間遲的；(3)當(dāng)出現(xiàn)兩個AGV 朝同一目標(biāo)節(jié)點(diǎn)移動的情況,后一個AGV 根據(jù)等待策略重新規(guī)劃[12].

圖2 時間窗模型圖

2 基于蟻群算法的路徑規(guī)劃

在智慧倉儲物流中的路徑調(diào)度規(guī)劃需要解決3 方面問題：(1)AGV 與障礙物碰撞問題；(2)實(shí)現(xiàn)任務(wù)完成的時間最小化和貨物運(yùn)送效率最大化的目標(biāo)；(3)傳統(tǒng)的蟻群算法不能直接用于解決有障礙的最短路徑問題.因此,應(yīng)改進(jìn)蟻群算法的實(shí)用性來解決障礙問題,這也解決了理論上的困境問題.

2.1 基本蟻群算法

蟻群算法是以類比蟻群現(xiàn)實(shí)生活中尋找食物的行為為靈感.螞蟻在覓食的過程中隨機(jī)行走,并在沿途鋪設(shè)名為信息素的化學(xué)痕跡.信息網(wǎng)將信息發(fā)送給其他成員,其他螞蟻則很可能沿著鋪有信息素的路徑行走,而不是隨意走動.這一觀察結(jié)果啟發(fā)了意大利學(xué)者Dorigo 等人,提出了一種智能多主體系統(tǒng)的啟發(fā)式算法,魯棒性更強(qiáng),速度更快,分布式計(jì)算和良好的可擴(kuò)展性[13],并且具有實(shí)現(xiàn)全局最優(yōu)解的概率更高.

在蟻群算法中,螞蟻運(yùn)動的過程可用圖3表示.蟻巢(起點(diǎn)) 和食物(終點(diǎn)) 之間往往有多條路徑,可用{e1}、{e2、e3}集合表示.在螞蟻覓食尋路的過程中,信息素殘留量會開始蒸發(fā),因此減少對螞蟻的吸引力.路徑越長,信息素蒸發(fā)量越多.因此最短路徑上的信息素強(qiáng)度增加到與蒸發(fā)速率相平衡的水平,導(dǎo)致較短路徑上的信息素數(shù)量比較長路徑上的信息素增量更快.在自動催化過程中通過信息素的積累,當(dāng)螞蟻面對交叉點(diǎn)時,信息素量越大的路徑更易優(yōu)先被選擇.

完整的螞蟻的尋路過程包括兩部分：路徑選擇和信息素釋放.

圖3 螞蟻尋路模型圖

(t)表示在t時刻,螞蟻k位于柵格i時,選擇下一柵格j的概率,表達(dá)式如式(1)所示：

其中,allowk表示螞蟻k當(dāng)前可以選擇到達(dá)的節(jié)點(diǎn)的集合；α表示信息啟發(fā)因子,用來表示螞蟻在行路過程中積累的信息量產(chǎn)生的作用大小[14],β表示期望啟發(fā)因子,值越大,表示啟發(fā)信息在螞蟻運(yùn)動方向的選擇中越受重視[15],τij表示t周期時路段(i,j)上的聯(lián)系信息素,dij表示城市i與j之間的距離,ηij表示啟發(fā)函數(shù),ηij和dij的關(guān)系如式(2)所示：

螞蟻在每次覓食中信息素的量主要由兩個因素組成：蒸發(fā)的信息素和新添加的信息素.經(jīng)過一段時間n后,螞蟻完成一個周期,會更新并更改通過路徑上的信息素數(shù)量,t+n時刻在路徑(i,j)上信息素更新規(guī)則為：

其中,ρ是信息素蒸發(fā)的速率,且取值范圍為ρ ∈(0,1),1?ρ為 信息素殘差因子,Δτij(t,t+n)是 在時間段(t,t+n)內(nèi)路徑(i,j)增 加的信息素的量,在循環(huán)開始時,Δτij(0)=c.(t,t+n)是由螞蟻k在(t,t+n)增加的信息素的量.

2.2 改進(jìn)蟻群算法

智慧物流制造車間的空間環(huán)境屬于靜態(tài)空間,改進(jìn)的蟻群算法通過環(huán)境地圖和目標(biāo)節(jié)點(diǎn)的位置信息,通過優(yōu)化概率轉(zhuǎn)移公式來改變運(yùn)動方向和信息素更新兩個方面[16],選擇從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑.在改進(jìn)的算法中,提高算法全局尋優(yōu)能力和收斂性[17].

2.2.1 優(yōu)化概率轉(zhuǎn)移規(guī)則

蟻群算法在禁忌表的限制下,前期迭代的過程中會產(chǎn)生大量交叉路徑,導(dǎo)致螞蟻行進(jìn)的過程中容易進(jìn)入一個凹形的障礙物區(qū)域,出現(xiàn)無路可走的“死鎖”狀態(tài)時,就成為路徑死鎖[18].螞蟻進(jìn)入死角時,死鎖狀態(tài)的位置如圖4所示.

圖4 死角示意圖

圖4中,螞蟻運(yùn)動到13 節(jié)點(diǎn)時,進(jìn)入死角,成為死鎖狀態(tài).在路徑搜索過程中進(jìn)入死角,則死角的位置會被列在禁忌表中,螞蟻會返回到前一個位置,然后搜索下一個位置.本文通過建立死角表并引入懲罰函數(shù)[19]來解決這個問題.當(dāng)螞蟻遇到死角時,使用懲罰函數(shù)而不是更新規(guī)則,懲罰函數(shù)為：

懲罰函數(shù)使死角的周圍邊緣信息素減少,指引螞蟻在下一個迭代搜索的過程中忽略那些邊緣,解決了死鎖問題,加快找到運(yùn)動方向路徑.

2.2.2 信息素更新優(yōu)化

S為起點(diǎn),E為終點(diǎn),n是從S到E(包括S和E)所經(jīng)過的路徑上的網(wǎng)格數(shù)[20],m為轉(zhuǎn)彎處網(wǎng)格數(shù),AGV的速度保持恒定且轉(zhuǎn)向模式是繞自己的中心旋轉(zhuǎn),則用vs表示角速度.網(wǎng)格的單位長度用ln.基本蟻群算法的路徑成本函數(shù)為：

改進(jìn)的路徑成本函數(shù)為：

因此,Δτij(t,t+n)可以表示為：

Q表示信息素總量,能在螞蟻運(yùn)動的過程中影響算法速度.Lk表示在此次任務(wù)中,螞蟻k所經(jīng)過的路徑長度.

2.2.3 算法步驟

本算法選用蟻群算法對智慧倉儲物流的車間的地圖模型進(jìn)行優(yōu)化,設(shè)AGV 的出發(fā)點(diǎn)為S,目標(biāo)貨架為E處,算法的目的目的是繞開所有障礙物,尋找一條從S到E的最短路徑,引導(dǎo)AGV 小車運(yùn)作.基于改進(jìn)蟻群算法的路徑規(guī)劃的算法實(shí)現(xiàn)步驟如算法1.

算法1.基于改進(jìn)蟻群算法的路徑規(guī)劃算法1)初始化參數(shù).首先讀取柵格地圖的信息,設(shè)置AGV 個數(shù)m,最大迭代次數(shù)K,信息素強(qiáng)度Q 以及、、,初始化常數(shù).將螞蟻放在起始位置S 處,同時將此網(wǎng)格位置設(shè)置為禁忌表 的第一個元素,此時各邊上的信息素相等,則；2)當(dāng)螞蟻k 選擇了下一個網(wǎng)格時,如果不是目標(biāo)網(wǎng)格,則螞蟻根據(jù)式(1)選擇概率最高的下一個空閑網(wǎng)絡(luò)；如果是目標(biāo)網(wǎng)格,則該螞蟻將在循環(huán)中完成了此次無碰撞路徑的任務(wù).3)根據(jù)式(4)和式(8)更新路由,由式(7)計(jì)算在路線上消耗的最佳時間.4)重復(fù)執(zhí)行2)、3),直到螞蟻到達(dá)終點(diǎn)或者無處可去,迭代結(jié)束.5)根據(jù)式(3)更新信息素矩陣,并且不考慮到達(dá)目的地的螞蟻,直到迭代結(jié)束.α β ρ Δτij(0)=c tabuk Δτij(0)=0

通過改進(jìn)的蟻群算法,結(jié)合時間窗網(wǎng)格法,多AGV的避障規(guī)劃算法步驟如算法2.

算法2.多AGV 的避障規(guī)劃算法1)根據(jù)優(yōu)先級對所有AGV 進(jìn)行排序,對優(yōu)先級最高的AGV 進(jìn)行最優(yōu)路徑搜索,得了該AGV 所經(jīng)過的所有網(wǎng)格都占據(jù)的時間窗,然后初始化時間窗.2)安排下一個優(yōu)先級高的任務(wù),并搜索下一個AGV 的最佳路徑,同時獲得該AGV 通過的網(wǎng)格的時間窗口,并更新所有網(wǎng)格的時間窗口.將網(wǎng)格進(jìn)行比較,以確定是否發(fā)生時間窗口沖突.3)如果2)中存在沖突,則根據(jù)優(yōu)先級規(guī)則采用等待策略,將在表(k=1,2,…,m)中放置沖突節(jié)點(diǎn),然后再次搜索路線.如果2)中沒有沖突,則規(guī)劃結(jié)束.tabuk

基于改進(jìn)蟻群算法的多AGV 的避障路徑規(guī)劃算法步驟流程圖如圖5所示.

3 實(shí)驗(yàn)分析

3.1 路徑優(yōu)化仿真實(shí)驗(yàn)

已知某工廠生產(chǎn)車間的貨物暫存區(qū)的平面設(shè)計(jì)圖如圖6所示.

本文通過Matlab 仿真實(shí)驗(yàn)驗(yàn)證算法,首先利用柵格法建立25×25 仿真環(huán)境模型,從左到右、從下到上對該環(huán)境進(jìn)行編號,螞蟻數(shù)量m、信息啟發(fā)因子 α、期望啟發(fā)式值 β、信息素的蒸發(fā)系數(shù) ρ、信息素強(qiáng)度Q、最大迭代次數(shù)K的參數(shù)設(shè)置如表1所示.

AGV 車從起始節(jié)點(diǎn)25,到達(dá)目標(biāo)節(jié)點(diǎn)510.仿真結(jié)果如圖7、圖8所示.

圖5 多AGV 路徑規(guī)劃算法流程圖

圖6 某生產(chǎn)車間平面布置圖

表1 仿真實(shí)驗(yàn)系數(shù)設(shè)置表

圖7 基本蟻群算法路徑規(guī)劃圖

圖8 基本蟻群算法收斂曲線

采用改進(jìn)的蟻群算法對路徑優(yōu)化進(jìn)行仿真,仿真結(jié)果如圖9.

圖9 基于改進(jìn)蟻群算法路徑規(guī)劃圖

根據(jù)實(shí)驗(yàn)結(jié)果結(jié)果表明,由圖8基本蟻群算法收斂曲線可得經(jīng)過73 次迭代后,達(dá)到最短路徑40,而根據(jù)圖10可得改進(jìn)蟻群算法可以經(jīng)過60 次迭代后,達(dá)到最優(yōu)路徑長度為38.因此改進(jìn)的蟻群算法具有更好的性能,能加快收斂速度,更快地找到最優(yōu)路徑.

3.2 多個AGV 避障規(guī)劃仿真實(shí)驗(yàn)

避障路徑規(guī)劃的仿真實(shí)驗(yàn)設(shè)計(jì)了3 個AGV,設(shè)置優(yōu)先順序?yàn)锳GV1＞AGV2＞AGV3,各AGV 的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)位置參數(shù)如表2所示.

根據(jù)算法2 中步驟1)規(guī)劃AGV1 和AGV2 的行駛路徑,分別從S1 和S2 出發(fā),沖突未解決時,仿真結(jié)果如圖11所示.

根據(jù)柵格地圖和時間窗,在節(jié)點(diǎn)94 時存在沖突,則AGV2 將采用等待策略,它將在節(jié)點(diǎn)上等待1 s,以便AGV1 能夠提前通過沖突,路徑規(guī)劃后的仿真結(jié)果如圖12所示.

圖10 基于改進(jìn)蟻群算法收斂曲線

表2 多AGV 節(jié)點(diǎn)位置

圖11 存在沖突的AGV 行駛路線

圖12 沖突解決后的AGV 行駛路線

通過時間窗再次檢測沖突,由于沒有沖突,所以執(zhí)行第二步,根據(jù)AGV1 和AGV2 的路徑規(guī)劃,更新所有節(jié)點(diǎn)的時間窗,并搜索AGV3 的最短路徑.當(dāng)沖突未解決時,仿真結(jié)果如圖13所示.

圖13 存在沖突的多AGV 行駛路線

根據(jù)時間窗模型,當(dāng)AGV3 到達(dá)節(jié)點(diǎn)238 之后,與AGV1 之間存在沖突,因此再次搜索AGV3 的最短路徑,并將節(jié)點(diǎn)238 放置在AGV3 的tabuk表中,最后進(jìn)行路徑規(guī)劃.仿真結(jié)果如圖14所示.

圖14 沖突解決后的多AGV 行駛路線

通過對仿真結(jié)果的分析,將改進(jìn)的蟻群算法與時間窗模型相結(jié)合,得到了較為理想的結(jié)果.

將本方法應(yīng)用于某大型制造企業(yè)的生產(chǎn)物流系統(tǒng)設(shè)計(jì)中,在Flexsim 平臺對該系統(tǒng)的入庫環(huán)節(jié)進(jìn)行物流仿真實(shí)驗(yàn),AGV 的數(shù)量為12,各AGV 的利用率如圖15所示.

本方法應(yīng)用于實(shí)際系統(tǒng)中,在多AGV 的路徑規(guī)劃中,能夠合理規(guī)劃各AGV 的行駛路線,進(jìn)而提高系統(tǒng)整體運(yùn)輸任務(wù)的效率,保證系統(tǒng)順利運(yùn)行.

圖15 入庫環(huán)節(jié)各AGV 的利用率

4 結(jié)論與展望

在智慧物流制造車間的環(huán)境下,通過改進(jìn)的蟻群算法結(jié)合帶有時間窗的網(wǎng)格法根據(jù)環(huán)境的變化不斷調(diào)整AGV 的行駛軌跡.本文以制造車間實(shí)際環(huán)境為模型,建立仿真實(shí)驗(yàn),對單個AGV 和多個AGV 避障規(guī)劃情況進(jìn)行分析,驗(yàn)證了該算法能有效避免在設(shè)備的碰撞問題.本設(shè)計(jì)已經(jīng)應(yīng)用于某大型制造企業(yè)的生產(chǎn)物流的設(shè)計(jì)過程中,不久將全面投入使用.

隨著人工智能的迅猛發(fā)展,發(fā)展智能制造,智慧倉儲物流已是整個制造業(yè)必然的發(fā)展趨勢.以智慧物流為核心的科學(xué)管理的、信息豐富的、決策智能的物流運(yùn)營模式會成為人類社會不斷追求的生產(chǎn)生活方式.