基于改進蟻群算法的智慧物流調度規劃①

葉杭璐,何利力

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

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

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

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

1 建立AGV 的工作環境模型

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

1.1 柵格法

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

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

圖1 環境柵格模型圖

按行駛方向,圖1中AGV1 在節點32,則它下一步到達的節點為33,AGV2 在節點55,則它下一步到達的節點為45.

1.2 時間窗模型

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

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

當出現選擇路徑沖突時,AGV 行進的優先級先后順序根據3 個方面來制定：(1)裝有行李架的AGV的優先級高于未裝有行李架的；(2)任務完成設定的時間早的AGV 優于任務完成時間遲的；(3)當出現兩個AGV 朝同一目標節點移動的情況,后一個AGV 根據等待策略重新規劃[12].

圖2 時間窗模型圖

2 基于蟻群算法的路徑規劃

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

2.1 基本蟻群算法

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

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

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

圖3 螞蟻尋路模型圖

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

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

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

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

2.2 改進蟻群算法

智慧物流制造車間的空間環境屬于靜態空間,改進的蟻群算法通過環境地圖和目標節點的位置信息,通過優化概率轉移公式來改變運動方向和信息素更新兩個方面[16],選擇從起始節點到目標節點的最佳路徑.在改進的算法中,提高算法全局尋優能力和收斂性[17].

2.2.1 優化概率轉移規則

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

圖4 死角示意圖

圖4中,螞蟻運動到13 節點時,進入死角,成為死鎖狀態.在路徑搜索過程中進入死角,則死角的位置會被列在禁忌表中,螞蟻會返回到前一個位置,然后搜索下一個位置.本文通過建立死角表并引入懲罰函數[19]來解決這個問題.當螞蟻遇到死角時,使用懲罰函數而不是更新規則,懲罰函數為：

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

2.2.2 信息素更新優化

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

改進的路徑成本函數為：

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

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

2.2.3 算法步驟

本算法選用蟻群算法對智慧倉儲物流的車間的地圖模型進行優化,設AGV 的出發點為S,目標貨架為E處,算法的目的目的是繞開所有障礙物,尋找一條從S到E的最短路徑,引導AGV 小車運作.基于改進蟻群算法的路徑規劃的算法實現步驟如算法1.

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

通過改進的蟻群算法,結合時間窗網格法,多AGV的避障規劃算法步驟如算法2.

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

基于改進蟻群算法的多AGV 的避障路徑規劃算法步驟流程圖如圖5所示.

3 實驗分析

3.1 路徑優化仿真實驗

已知某工廠生產車間的貨物暫存區的平面設計圖如圖6所示.

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

AGV 車從起始節點25,到達目標節點510.仿真結果如圖7、圖8所示.

圖5 多AGV 路徑規劃算法流程圖

圖6 某生產車間平面布置圖

表1 仿真實驗系數設置表

圖7 基本蟻群算法路徑規劃圖

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

采用改進的蟻群算法對路徑優化進行仿真,仿真結果如圖9.

圖9 基于改進蟻群算法路徑規劃圖

根據實驗結果結果表明,由圖8基本蟻群算法收斂曲線可得經過73 次迭代后,達到最短路徑40,而根據圖10可得改進蟻群算法可以經過60 次迭代后,達到最優路徑長度為38.因此改進的蟻群算法具有更好的性能,能加快收斂速度,更快地找到最優路徑.

3.2 多個AGV 避障規劃仿真實驗

避障路徑規劃的仿真實驗設計了3 個AGV,設置優先順序為AGV1＞AGV2＞AGV3,各AGV 的起始節點和目標節點位置參數如表2所示.

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

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

圖10 基于改進蟻群算法收斂曲線

表2 多AGV 節點位置

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

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

通過時間窗再次檢測沖突,由于沒有沖突,所以執行第二步,根據AGV1 和AGV2 的路徑規劃,更新所有節點的時間窗,并搜索AGV3 的最短路徑.當沖突未解決時,仿真結果如圖13所示.

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

根據時間窗模型,當AGV3 到達節點238 之后,與AGV1 之間存在沖突,因此再次搜索AGV3 的最短路徑,并將節點238 放置在AGV3 的tabuk表中,最后進行路徑規劃.仿真結果如圖14所示.

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

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

將本方法應用于某大型制造企業的生產物流系統設計中,在Flexsim 平臺對該系統的入庫環節進行物流仿真實驗,AGV 的數量為12,各AGV 的利用率如圖15所示.

本方法應用于實際系統中,在多AGV 的路徑規劃中,能夠合理規劃各AGV 的行駛路線,進而提高系統整體運輸任務的效率,保證系統順利運行.

圖15 入庫環節各AGV 的利用率

4 結論與展望

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

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