基于ISSA和IA*的AGV集成作業調度及其路徑規劃*

張天瑞,劉 悅

(沈陽大學機械工程學院,沈陽 110044)

0 引言

隨著科學技術的飛速發展,制造業作為高耗能、高排放的產業,據不完全統計全球每年約產生7億噸有害廢物和55億噸無害廢物。同時,碳排放量的增加會與碳達峰、碳中和的目標形成矛盾。因此,推動制造業低碳、綠色發展具有良好的研究意義。目前在工業4.0背景下,自動導引運輸車(automatic guided vehicle,AGV)在工業領域代替人工完成運輸作業,隨著現代化工廠的發展,越來越多的工廠對AGV的需求量也不斷擴大,提高AGV的效率將加快現代化工廠建設[1]。

由于實際生產車間問題的高度復雜性,大多學者使用智能優化算法來解決問題,如蟻群優化算法[2]、洗牌蛙跳算法[3]、果蠅算法[4]、粒子群優化算法[5]等。這些優化算法已被應用于低碳調度,如文笑雨等[6]通過高維低碳調度模型彌補了多目標空間選擇壓力不足的不足,ZHANG等[7]將果蠅優化算法用于優化最小化完工時間的雙資源約束的柔性作業車間調度問題等。

根據AGV路徑搜索策略的不同,路徑搜索算法可以分為仿生算法、幾何模型搜索算法和基于插值的算法。RIAZI等[8]提出一種全新的啟發式算法用于解決自動引導車輛無沖突調度和路由問題。鄒裕吉[9]提出一種基于Dijkstra和時間窗的多目標聚類遺傳算法對AGV無沖突路徑進行研究。楊周等[10]提出了一種將蟻群算法和動態窗口相結合的全局動態路徑規劃算法。潘紋等[11]考慮了配送成本和生產效率提出了一種動態步長果蠅算法。SMOLIC等[12]提出利用向量形式的時間窗口動態求解最短路徑問題的路由方法。HU等[13]針對靜態路徑規劃中的低優先級任務的時間窗進行更新,從而避免了車輛之間的沖突和碰撞。LINA[14]基于粒子濾波來混合布谷鳥遺傳算法進行聚類分析,可以更有效地處理帶時間窗的車輛路徑規劃任務。

目前,針對貪婪算法的優化能力已被多次證實其在優化其他算法方面的有效性。高珊等[15]利用貪婪隨機自適應搜索算法的構造階段來生成初始解。王迪等[16]將貪婪交換技術應用到鯨魚優化算法中,提高了算法的收斂速度。李霄鵬、王凌等[17-19]均將貪婪算法與其他算法進行融合后得到了更好的仿真結果。PETKE[20]通過約束CIT測試集生成的遺傳算法,得出貪婪算法比模擬退火算法在計算時間方面具有更好的結果。

綜上所述,前人對AGV調度和路徑規劃問題的優化研究雖然取得了較好的進展,但同時考慮能耗的相關研究尚有不足?；诖?本文提出了基于改進飛鼠搜索算法(improved squirrel search algorithm,ISSA)和優化A*融合算法的AGV調度和路徑規劃雙層優化模型,通過測試函數與仿真實驗,驗證其可行性、有效性和優越性,為提高AGV集成作業調度效率和路徑規劃安全避障研究提供新的思路和方法。

1 問題描述及數學模型要求

1.1 問題描述

本文針對AGV集成作業調度問題建立雙層規劃模型,上層為考慮最小化成本和最小化能耗碳排放的集成作業調度模型,下層為基于時間窗的AGV最優路徑規劃模型。由于AGV系統中通常有多輛車輛,因此需要通過作業調度和路徑規劃來解決車輛之間的運動沖突。特別是應防止車輛碰撞和死鎖,以避免運行中斷。本模型與傳統AGV路徑規劃模型區別在于:將作業調度和路徑規劃分別作為上下雙層模型進行建模;同時加入綠色碳排放因素,將現實性和易處理性作為原則進行建模,簡化問題存在以下假設:

(1)AGV的初始位置為倉庫邊緣起點,并以一定的間隔時間隨機出發。

(2)AGV完成運輸任務后?？吭跈C器旁邊。

(3)使用最短路徑算法,生成每個車輛的路徑。

(4)各AGV運輸能力相同,每次只能完成一個工件的運輸任務。

(5)每條路徑在同一時刻只允許一臺AGV通過,且任意路徑可容納AGV的車身。

(6)調度周期內AGV與加工設備不會發生故障,AGV電量充足。

(7)AGV運行過程中保持勻速,行駛時車輪不打滑。

(8)不考慮AGV的裝載和卸載時間,即AGV的裝載和卸載時間均為0。

(9)不考慮設備故障、設備停電等不確定因素的影響。

1.2 數學模型

為了更好地理解本文所建立的模型和目標函數,首先將涉及到的主要參數進行定義,如表1所示。

表1 相關參數和定義

(1)上層模型。AGV能耗計算:AGV車輛的二氧化碳排放量是由BEKTA等[21]提出的瞬時燃料消耗模型計算出來的。車輛燃料消耗模型不僅是距離函數,而且是由車輛的行駛距離、載貨量和弧線速度組成的函數。本文問題定義在一個完整的有向圖G=(X,A)上,其中節點為X={0,1,2,…,x},同時也包括目標位置{1,2,…,x}和一個點0共同組成?；表示節點之間所有可能的連接,定義為{(m,n):m,n∈X,i≠j}。AGV在孤(m,n)上每輛AGV的所需要消耗的總機械功率計算如式(1)所示。

(1)

需要通過式(2)來計算電弧中的電弧比常數(m,n);其中,g表示為重力常數(m/s2)為9.81,Cr為滾動阻力系數0.01。

αmn=α+gsinθmn+gCrcosθmn

(2)

為計算運行中每輛AGV車輛碳排放量,如式(3)所示。

Cbmn≈～207.68×Emn·r

(3)

EPmn為本研究使用的效率值;其中effm=1.2,effd=1.1,effp=0.75,Efftotal估計為1.00。

EPmn≈effm·effd·effp·Pmn

(4)

式(5)為最小化AGV最大允許行駛時間:

(5)

(2)下層模型。為了在最大程度上減少AGV車輛的沖突和死鎖,采用單向導引路徑網絡(unidirectional guide path network,UNG)來降低對路徑的管理難度,使得AGV車輛只允許單向行駛且兩條相鄰路徑的方向保持反向行駛,即wij≠wji。i,j為路徑網絡節點編號,i,j=1,2,…,k為AGV行駛路徑編號,k=1,2,…,k,其中Vk為路徑k中所有節點的集合。v(k1,k2)為路徑k1和k2中相同節點的集合。對AGV進行路徑規劃,在AGV車輛運行過程中,停車等待和重新路徑規劃是解決路徑沖突的最常見的策略。w為路徑網絡中路段的集合,其中wij={i→j,i,j∈V},表示節點i到節點j之間的距離;w(k1,k2)為路徑k1和k2中重疊路段的集合,wij≠wji表示AGV車輛保持單向行駛狀態。

采用二維空間有限地圖柵格圖對AGV運行路徑進行模擬仿真,以20×20為例,劃分后的柵格圖如圖1所示,柵格圖建模流程如圖2所示。

圖1 柵格地圖示例

由多個規則矩形組成(障礙物空間和自由空間),障礙物空間為車間設備等物品無法進行行駛,自由空間是AGV車輛可行進的路徑。障礙物由黑色區域表示,自由行進空間由白色區域表示,為了保證AGV車輛可以在車間內正常同行,實際生產車間中會存在一些不規則的障礙物,將其補償為矩形。

1.3 飛鼠搜索算法

飛鼠搜索算法(squirrel search algorithm,SSA)是一種性能良好的群智能算法[23],旨在描述南方飛鼠覓食和躲捕食者的過程中進行滑翔的行為,是一種有效的節省覓食成本的方式,通過建立解決全局最優問題的模型,完成對復雜問題的求解。圖3為飛鼠搜索算法的基本搜索過程。

圖3 飛鼠搜索算法流程圖

(1)隨機初始化:假設森林中存在N只飛鼠,通過矢量來確定森林中每一個飛鼠的位置。通過式(6)隨機確定飛鼠初始位置。

FSij=FSi,L+U(0,1)×(FSi,U-FSi,L)

(6)

式中:FSij是第i只飛鼠在第j維上值,U、L是第j維的上界和下界,U(0,1)是處于0和1間的均勻分布值。

(2)適應值排序和隨機選擇:飛鼠的適應值由食物源等級進行排序,包括3種類型:最佳食物源、正常食物源和無食物來源,分別代表的是山核桃樹、橡樹和普通樹。將適應度值最小的飛鼠將留在山核桃樹上,接下來的3只飛鼠將停留在橡樹上或是選擇是否向山核桃樹移動,其余飛鼠則留在普通樹上。

采用隨機選擇的方法來選擇出已滿足日常能量的飛鼠并向山核桃樹飛行,其余則往橡樹進行移動。同時飛鼠覓食過程中會遇到天敵,根據天敵出現的概率來決定飛鼠的移動策略。在飛鼠搜索覓食過程中存在以下3種情況,分別如式(7)～式(9)所示。

①停留在橡樹上的飛鼠向山核桃移動。

(7)

②停留在普通樹上的飛鼠向橡樹移動。

(8)

③部分吃了橡果的飛鼠停留在普通樹上,但它們也可能會向山核桃樹移動來儲存食物。

(9)

(10)

式中:hg=8 m是飛鼠滑行后發生的高度差量,需計算dg所有參數值,5～25 m是普通飛鼠正常一次滑行的水平距離,在該算法中,dg控制在9～20 m的范圍里。

(11)

(12)

式中:t是當前迭代次數,mt為最大迭代值,算法的全局和局部搜索能力Smin值的影響,滑動常數Gc用于平衡搜索能力,也可以在迭代中自適應地改變Smin值來實現。若滿足季節變化條件,則隨機選擇變換普通樹上飛鼠的位置,得到位置如式(13)所示。

(13)

1.4 A*算法

A*算法是由Dijkstra進化而來的,本質上兩者是相同的,由于Dijkstra算法缺少啟發式,導致其需要對每個方向上同時按照均勻的速度進行搜索拓展。這使得其搜索效率極大降低,增加了許多無效的搜索區域,相對于A*算法搜索速率較慢。

傳統A*算法是在靜態環境下對路徑搜索的啟發式算法,對路徑進行全局搜索,在一定程度上避免了無效路徑,提高了搜索效率。根據目標位置和全局地圖進行全局路徑規劃,將搜索區域劃分成正方形格,簡化搜索區域,節點作為方格的中心點。A*算法的核心就是對方格移動的節點數量的計算,其函數如式(14)所示。

F(x,y)=G(x,y)+H(x,y)

(14)

A*算法可以通過對H值的預先估計有效地降低尋路走彎路的可能性,相對于其他算法更高效尋找到距離最小路徑。由于其他尋路方法缺少啟發性算法,只是針對路徑進行一一列舉再依次尋找最短路徑,這使得A*算法相對于其他算法具有更強的魯棒性。

原始A*算法針對起始點到單個節點的路線進行搜索,其全局規劃的路徑會存在拐點,轉彎次數過多會影響AGV運行時間。因此,本文引入時間因子和安全距離因子,提出一種優化A*算法,在剔除多余拐點同時增加路徑安全性達到優化AGV運動路徑的目的。

2 算法設計

2.1 優化飛鼠搜索算法

2.1.1 貪婪策略優化初始種群

初始種群的質量對算法的求解質量和收斂速度有非常大的影響,根據柔性作業車間特點,提出了基于貪婪策略優化飛鼠搜索過程的算法,對飛鼠搜索算法初始種群進行貪婪處理,生成局部最優的初始種群來提高搜索能力,針對具體執行飛鼠位置隨機初始化過程為:

針對森林中M個飛鼠,采用均勻分布對每個飛鼠位置進行初始化,針對初始種群進行依次迭代采用貪婪策略,建立上一次迭代的飛鼠位置與當前迭代的飛鼠位置的排序映射,求得上下兩代優秀飛鼠個體并記錄當前最優解。將第N次迭代和N-1次迭代的優秀個體均進行保留處理,并依次代入位置進行更新迭代直至結束,具體流程如圖4所示。

圖4 貪婪初始化飛鼠搜索算法流程

通過貪婪策略來對飛鼠搜索算法的種群初始化由于原有飛鼠搜索算法初始解是隨機方式生成,該方式生成初始種群對求解結果影響較小。大部分研究表明,隨機生成的可以有效地保證種群的多樣性,但非隨機生成的方法有可能會產生高質量的解。部分策略初始化偽碼為:

fitness=zeros(1,pop);
for i=1:pop
fitness(i)=fob j(FS(i,:));
end
[～,index]=sort(fitness);
GBestF=fitness(index(1));
GBestX=FS(index(1),:);
curve=zeros(Max_iter,1);
curve(1)=GBestF;

FS0=x_ini;
FS1=Tent Initialization(pop,dim,ub,lb);
FS=[FS0;FS1]

2.1.2 編碼和解碼操作

本文采用的編碼方式為機器工序雙層編碼方式,編碼方式示例如圖5所示,每個工序編碼對應一個數字從左到右,表示其工序加工順序。工序層編碼為“13213231”,其中第1個位置上的數字“1”表示工序O1,1,第2次出現的數字“1”表示工序O1,2,第3個位置上的數字“2”表示工序O2,1,第5個位置上的數字“3”表示工序O3,2,以此類推。

圖5 工序機器編碼圖

機器編碼中每臺機器對應一個的數字,機器編碼的每個整數對應其數字下工序所選擇的機器序號,機器加工依次順序從左至右進行。機器層編碼為“13211323”,第1個位置上的數字“1”表示為工序O1,1在機器M1上加工,第3個位置上的數字“2”表示工序O2,1在機器M2上進行加工。

本文解碼方式采用全主動解碼,為了更清楚的展示給出了一組實例的解碼過程,其初始工序序列為[3,1,3,2,1,3,2]。圖6為半主動調度解,在機床M1上,工序O1,1前存在可允許O2,2插入的空閑時間;在前存在可允許O3,3插入的空閑時間;在機床M3上,工序O1,2前存在可允許O2,1插入的空閑時間。半主動調度解可獲得Cmax為8的半主動調度解,全主動解碼可獲得Cmax為8的全主動調度解,全主動調度解碼后的工序序列更新為[1,2,3,2,3,3,1]。

圖6 半主動調度解

解碼具體過程為:首先依次讀取工序編碼串,在機器編碼部分找到與其工序Oij對應的機器Mn信息并提取;在機器Mn上選擇空閑時間段[Tp,Tq],分別為空閑時間的開始時間和結束時間。判斷[Tp,Tq]是否大于Tij的加工時間,若滿足Tij的加工時間則選擇Oij插入到[Tp,Tq]空閑時間段內,否則將工序Oij移動到機器Mn上進行加工,當Mn完成全部工序加工時再對工序Oij進行加工,具體如圖7所示。

2.2 優化A*算法

2.2.1 安全距離因子

傳統A*算法在計算節點估價函數時,節點周圍并無懲罰值產生,AGV無法延時轉彎這必將會增加轉彎操作從而增加AGV行駛時間。同時,全局路徑規劃中無法保證其安全性,也存在過多的冗余節點、運動軌跡轉彎過多的情況。通過對AGV機器人和障礙物之間的最大距離進行比較,在保證運輸路徑安全的同時優化AGV運輸路徑。本文基于以上問題提出了基于安全距離因子的優化A*算法,目的為AGV減少轉彎次數和提高路徑安全性。安全距離因子如式(15)所示。

(15)

式中:lmax為機器人與障礙物間的最大距離,lmin為機器人與障礙物間的最小距離,lxy為機器人當前位置與障礙物之間的距離。

引入安全距離因子后的傳統A*算法的估價函數如式(21)所示,更新后A*算法流程如圖8所示。

(16)

圖8 引入安全因子A*算法流程

2.2.2 路徑平滑

由于AGV的能耗受到運行時間和運行路徑的影響,AGV移動路徑的節點越多從而會增加路徑運行的時間,導致多余能耗的浪費。對A*算法路徑規劃中的冗余節點進行處理,減少多余的節點平滑路徑,縮短AGV最短移動路徑。因此,本文基于梯度下降法對所有路徑點進行迭代優化,以減少路徑中的非必要的轉彎節點,節約運行時間和能耗。

具體操作過程為:從起點開始進行,依次選擇起點后相鄰的5個路徑中的節點來定義平滑度與路徑節點的關系,并將第3個節點進行位置移動,若相鄰兩個節點2和節點4之間沒有障礙物且連接后路徑可移動的范圍內則保留新路徑。將原先節點3剔除,直接從節點2移動至節點4,直線縮短AGV移動距離,梯度方向保留原先節點3的移動方向,使得5個路徑節點的平滑度達到最小值。若移動節點3位置后移動范圍之間有障礙物且無法達到安全距離因子,則保留原先節點路徑。依次歷遍全部節點直至選取目標節點結束操作。

定義節點的最優位移為ΔP,ΔP的大小為移動距離且移動方向為梯度方向。通過平滑度對ΔP的一階導等于0可求得梯度方向如式(17)所示。

(17)

3 實驗仿真與結果分析

3.1 標準函數和基本算例驗證

為保證測試實驗的客觀性和公平性,不同的算法均使用相同的硬件和軟件平臺,硬件環境為Intel(R)Core(TM)i5-7200UCPU@2.50 GHz,軟件環境為Win10操作系統上的MATLAB 2018b仿真軟件,所有算法的種群規模設為40,最大迭代次數設為1000。依次采用SSA、ISSA和PSO對Sphere、Rosenbrock、Rastrigrin、Geriwank、Schafferf6和Ackley六個函數進行20次理論極值的搜索。針對優化算法分別采用3個多峰函數和3個單峰函數進行測試,測試函數如表2所示。測試函數實驗結果的迭代曲線圖如圖9～圖14所示。

圖9 f1(x)函數的收斂曲線

圖11 f3(x)函數的收斂曲線

圖13 f5(x)函數的收斂曲線

表2 6個測試函數信息

由表2和圖9～圖14的測試結果可知,本文提出的ISSA算法針對單峰測試函數與多峰測試函數的尋優效果都是最優的,并且對于函數f1(x)、f2(x)、f3(x)、f5(x)、f6(x)中都可以搜索得到理論的全局最優值,此外ISSA在這5個函數結果得出的標準差都是極小的,說明ISSA具有良好的魯棒性。在測試函數f4(x)中,SSA算法與PSO算法的尋優表現均相對較差,而利用ISSA算法對測試函數f3(x)進行尋優時,ISSA在迭代125次時即可快速收斂達到最優值,說明該算法的尋優能力更強。對于6個測試函數而言,ISAA算法在實驗結果中的數據均優于SSA算法與PSO算法,得出結論ISSA算法的尋優精度和尋優能力更強。

為了保證優化飛鼠搜索算法在FJSP問題中的有效性,采用文獻[24]中的8×8和10×10經典問題實例進行測試,在經典實例中,均給出了工件數量、并行機數量、加工時間等詳細加工數據。其中SSA和ISSA的種群規模設為40,最大迭代次數設為50。Cmax表示最大完成時間,Aver表示算法50次求得最優值的均值,比較結果如表3所示。

表3 8×8和10×10案例結果對比

從表3可看出SSA和ISSA算法在8×8和10×10算例中均能找到最優解,且ISSA尋優結果優于SSA,說明ISSA算法具有較好的尋優能力。10×10算例的最優解甘特圖如圖15b所示,橫坐標為抽象作業單位的加工時間,縱坐標為機器序號,同一種顏色代表同一個工件。SSA和ISSA最大完成時間分別為8和7,ISSA算法找到該算例的最優解。

(a) 優化前 (b) 優化后

3.2 優化A*算法驗證

為驗證優化A*算法可行性,本文利用柵欄圖建模進行環境模擬,采用MATLAB 2018b進行仿真驗證。首先為了保證優化A*可以在障礙物分布復雜且環境空間大的情況下的性能,環境模型的搭建基礎,分別設置了30 m×30 m和40 m×40 m的柵格地圖。為了驗證論文所提出方法的有效性,進行了多組仿真對比實驗,仿真結果如圖16所示,灰色優化前的路線,黑色為優化后的路線。每輛AGV的最短路徑長度、拐點數量和運行時間如表4所示。

(a) 30×30 (b) 40×40

表4 AGV路徑仿真實驗結果

從表4中可以看出,優化后的A*可以有效地避免路段沖突和節點沖突。且優化A*在路徑運行時間和最短路徑長度上都比傳統A*更早更快。拐點數量也比傳統A*低22%,節約能耗21%。因此,本文提出的優化A*是可行的。

4 結論

本文提出了考慮能耗的AGV作業調度和路徑規劃問題雙層優化模型,首次采用貪婪策略優化飛鼠搜索算法應用到AGV調度優化中,進而將引入安全距離因子的A*算法用于解決路徑規劃的問題。通過仿真實驗與結果分析,驗證了ISSA和優化A*的有效性,得出以下結論:

(1)將貪婪策略引入飛鼠搜索算法初始解,基于6個測試函數的尋優和kacem經典案例中ISSA的尋優能力和尋優速度相比于SSA和PSO,ISSA算法表達出更好的性能。

(2)IA*分別在30×30和40×40中隨機復雜障礙物的情況下進行建模仿真,拐點數量減少22%,其運行時間也節約了21%。