基于改進遺傳算法的AGV集結路徑研究

趙睿，樓佩煌，錢曉明，武星，胡泊

(南京航空航天大學 機電學院，江蘇 南京 210016)

0 引言

隨著中國制造2025和工業4.0的不斷推進，多AGV(automated guided vehicle)系統也越來越多地應用于各類倉庫和生產車間中[1]。然而實際環境要復雜得多，多AGV系統可能面臨尺寸、質量、形狀差異較大的搬運任務，而單臺AGV由于載重、尺寸限制無法完成全部的搬運任務。為了解決這個問題，需要將具備協同搬運能力的AGV加入到多AGV系統中。

當搬運任務發布，確定了多AGV系統中需要執行協同搬運任務的AGV序列之后，需要為這幾臺AGV規劃從當前位置到達任務點的路徑，使AGV從分散狀態集中到需要執行協同搬運任務的工位點，即協同搬運AGV的集結。集結速度的快慢直接影響了多AGV系統響應任務的速度。集結速度過慢會導致搬運任務的等待時間過長，如果路徑規劃不當還會造成AGV行駛時沖突，則任務可能陷入死鎖狀態。

為了尋找合適的路徑規劃算法，許多學者對此進行了深入研究。文獻[2]通過區域劃分及引入啟發式策略，提出基于區域自治的分布式動態路徑規劃算法，可顯著提高路徑規劃的效率；文獻[3]提出了一種將遺傳算法和人工勢場法相結合的復雜環境下雙層路徑規劃思想，能夠提高機器人路徑規劃能力；文獻[4]以AGV運行時間最短為目標，將多種群遺傳算法引入到兩階段路徑規劃策略；文獻[5]引入分節拍的處理思想，通過將約束條件變成一種染色體裂變和合并操作結合的遺傳算子，對每個節拍內的分揀路徑進行優化。

綜合以上考慮，對于雙向單車道的工作環境，選擇了一種通過遺傳算法進行求解基于時間窗的最短路徑規劃方案[6]，用以解決多AGV系統中的AGV集結問題。

1 問題描述與建模

本文假設選定執行協同搬運任務的AGV都處于空閑狀態，選定的AGV初始狀態可以在路徑網絡的任意位置，且不受到系統中其他AGV的影響。因此，只要考慮選定執行任務的幾臺AGV的沖突關系，不用考慮整個多AGV系統里其他AGV的堵塞問題。假定AGV的狀態只有勻速行駛、停止和轉彎，不考慮AGV遇到障礙以及在交通路口減速加速的過程。

以上述假設為基礎，可以得出多AGV系統的時間窗模型為：

(1)

(2)

(3)

本文的優化目標是使所有AGV由初始點到達集合點的用時最短，即到達集合點最晚的那臺AGV用時最短。AGV運行時間包括運行時間和等待時間(阻塞時間)，即建立的目標函數如下：

minT=max(Trx+Twx)

(4)

約束條件為：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2 改進遺傳算法的求解流程

2.1 個體編碼設計

遺傳算法是一種啟發式搜索算法，適應于本文研究NP難的問題。對于路徑規劃問題，編碼方式可以采用AGV的路徑串表示染色體，路徑串上的一個個路徑節點表示染色體上的基因。染色體的長度可變，但是起點和終點由AGV當前位置和目標位置決定。每條染色體的編碼不得產生閉環回路，即AGV運行過程中不得回頭。

2.2 種群初始化

根據任務選取的AGV數量，確定染色體支線的數量n；根據AGV的初始位置和任務點的位置，確定染色體的頭尾基因；查詢上位機的路徑網絡信息以及上位機交通管理的約束條件，從初始點開始，選取任一個可以到達的下一節點作為下一個基因，直到找到終了節點。如果尋找的過程中產生了回路，即尋找到了之前走過的路徑節點，則把這段回路整個刪除，重新尋找。由于路徑網絡復雜度不高，因此種群數選為30。重復上述步驟30次，產生一個包含30個個體Si的初始種群。

2.3 適應度計算

適應度是評價個體優劣的衡量指標，適應度越高則個體被選中的概率越高。適應度值計算標準采用如下的評價函數：

(15)

式中：length表示整條路徑的總長度；Ni表示路徑拐彎點的個數；ti表示由于時間窗調整需要等待的時間；c1、c2、c3表示權重值，且c1+c2+c3=1。

2.4 交叉變異操作

交叉操作是將兩個父代的個體提取其中的一部分基因，互相進行替換以及重組生成新的個體，為的是增加個體基因的豐富性。交叉操作是否進行由交叉概率Pc決定，取Pc=1。由于染色體是由N條獨立的子染色體組成，因此不能用常規的單點或雙點交叉模式。為了保證AGV到達集合點的時間差距不會太大，因此需要保證N條子染色體適應度比較接近，提出一種平均化交叉模式。該交叉模式的基本思想是保證染色體的評價值比較平均，不會出現評價值特別低的子染色體，從而拖慢整體的集合時間。該交叉操作包含以下幾個步驟：首先根據評價值從兩個父代個體中S1和S2選出最差的一條子染色體，然后將S1中最差的子染色體用S2中對應的子染色體替換掉，將S2中最差的子染色體用S1中對應的子染色體替換掉，從而得到兩個子代P1和P2。

變異操作是否進行由變異概率Pm決定，取Pm=0.1。隨機的選取每條子染色體的一個基因，然后將其替換為一個新的路徑節點位置。

變異操作會有以下幾種可能出現的情況：

1) 變異的節點與初始路徑無法連通，屬于獨立于原路徑的節點：

對無法連通的子路徑段進行節點搜索，增加節點使其連通；

·4，6，9，11，12，15

由圖1可知，節點6與路徑不相連，因此增加節點補充在路徑上，變異后子染色體為

·4，1，3，6，17，9，11，12，15

2) 變異的節點與初始路徑重合，則將變異點與重合點之間的節點刪除重新選擇；

·4，12，9，11，12，15

由圖1可知，節點6與路徑不相連，因此增加節點補充在路徑上，變異后子染色體為

·4，10，2，5，7，15

圖1 車間路徑網絡模型

2.5 基于時間窗進行調整

初始種群和經過交叉變異的種群需要通過調整時間窗，從而解決AGV運行時干涉或者死鎖的問題。對于3車集合的問題來說：以集合點為11-12之間的某個任務為例，該任務需要3臺AGV共同執行協同搬運任務。隨機在種群中選擇1條染色體，該染色體由3條子染色體組成，如表1所示。

表1 染色體基因表以及對應的時間窗

通過分析時間窗可知，時間窗沖突如下：

路徑15—25，AGV1和AGV3產生了相向沖突，時間窗口為[22.3，33.6]。由于同一段時間窗內，一條路徑只能允許一個方向通行AGV，這種路徑沖突需要重新規劃時間窗；在路徑12—終點，AGV1和AGV3產生了同向沖突，時間窗為[39.8,57.7]。由于路徑單向可以容納多臺AGV運行，通過分析得出：兩臺AGV間隔距離>最小運行間隔，并且路徑承載數>2，不需要調整時間窗。

有兩種方法可以對時間窗的沖突進行調整：延遲時間窗和路徑重新規劃。

1) 延遲時間窗

該方法是通過暫停AGV的運行，來使得該AGV的時間窗后移，從而解決時間窗的沖突問題。對于路徑15—25在時間窗口[22.3，33.6]的沖突，則可以通過延遲AGV1到達時間或者AGV3到達的時間。需要延遲的時間為：

(16)

(17)

通過延遲AGV1時間窗，3臺AGV需要花的時間為65.9—30.2—46.8；延遲AGV2的時間窗，3臺AGV需要花費的時間為57.7—30.2—60.1。雖然延遲AGV3的時間窗花費時間較多，但是總集合時間較短，因此選擇延遲AGV3的時間窗，總集合時間為60.1s。

2) 重新規劃路徑

對于15—25的路徑沖突也可以采用重新規劃AGV1或者AGV3的路徑，從而避免產生相向沖突。對于兩條沖突路徑，遵循以下幾條原則進行調整：根據到達集合點的總時間進行排序，優先對集合時間最長的AGV進行重新路徑規劃；將重新規劃后的路徑與初始路徑進行比較，如果增加了路徑段，則放棄重新規劃的路徑，選擇次長路徑進行重新規劃。如本例中對AGV1進行重新規劃，路徑是21—18—15—12—終點。

重新規劃后僅存在通向沖突，并且符合路徑的容納能力，不需要調整時間窗。總的集合時間為46.8s。

綜合兩種調整方法，選擇集合時間更短的重新規劃路徑法。

2.6 迭代終止條件

如果變異后的連續Nr代子個體中最佳個體沒有變化，或者達到了最大迭代次數Nm，則停止迭代。本文中Nr=10,Nm=100。

3 仿真與分析

為了評估該方法的優化性能，對其進行計算機仿真分析。對于路徑網格內的12個工作站，生成10個搬運任務，每個任務所需的AGV數量在2-4臺之間，并隨機生成AGV的初始位置，數據信息如表2所示。

表2 任務以及AGV位置信息

3.1 實驗相關數據

利用上文所提出的IGA、傳統最短路徑算法DGA進行求解路徑序列，對結果進行比較。比較集合總時間和死鎖次數。采用生產系統仿真軟件Plant Simulation進行仿真。設定的AGV運行速度為0.5m/s，每個任務進行100次仿真運行，結果取平均值。

3.2 仿真結果分析

該系統集結效率的評價指標主要有集結時間和死鎖故障率。圖2對比了3種路徑規劃方式下，AGV由分散狀態集結到任務點需要的總時間平均值。如果實驗發生死鎖，則該次實驗不計入平均時間。圖3對比了3種路徑規劃方式下，AGV由于相向沖突造成的死鎖次數，死鎖次數越少表示系統運行的可靠性越高，需要人工介入進行調整的概率越小。

圖2 平均集結時間/s

圖3 死鎖產生次數

通過對比可知，對于3種路徑規劃方式，IGA時間普遍小于GA與DGA，優化效率更高，而兩車集結時，3種規劃方法的優化效率差距不大。IGA能夠有效避免死鎖的發生，而DGA更容易造成AGV的死鎖，尤其是4臺AGV集結時情況尤其嚴重。

4 結語

本文提出了一種帶時間窗的基于改進遺傳算法的AGV集結路徑規劃算法。根據數學約束條件，通過改進遺傳算法進行求解。為了解決雙向路徑沖突問題，優化個體，使用了時間窗調整策略，減少了路徑沖突，優化了集結時間。為解決多AGV系統中執行協同搬運任務前集結分散的AGV提供了思路。