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

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

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

0 引言

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

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

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

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

1 問題描述與建模

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

以上述假設為基礎(chǔ)，可以得出多AGV系統(tǒng)的時間窗模型為：

(1)

(2)

(3)

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

minT=max(Trx+Twx)

(4)

約束條件為：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

2.1 個體編碼設計

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

2.2 種群初始化

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

2.3 適應度計算

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

(15)

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

2.4 交叉變異操作

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

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

變異操作會有以下幾種可能出現(xiàn)的情況：

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

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

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

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

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

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

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

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

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

圖1 車間路徑網(wǎng)絡模型

2.5 基于時間窗進行調(diào)整

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

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

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

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

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

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) 重新規(guī)劃路徑

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

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

綜合兩種調(diào)整方法，選擇集合時間更短的重新規(guī)劃路徑法。

2.6 迭代終止條件

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

3 仿真與分析

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

表2 任務以及AGV位置信息

3.1 實驗相關(guān)數(shù)據(jù)

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

3.2 仿真結(jié)果分析

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

圖2 平均集結(jié)時間/s

圖3 死鎖產(chǎn)生次數(shù)

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

4 結(jié)語

本文提出了一種帶時間窗的基于改進遺傳算法的AGV集結(jié)路徑規(guī)劃算法。根據(jù)數(shù)學約束條件，通過改進遺傳算法進行求解。為了解決雙向路徑?jīng)_突問題，優(yōu)化個體，使用了時間窗調(diào)整策略，減少了路徑?jīng)_突，優(yōu)化了集結(jié)時間。為解決多AGV系統(tǒng)中執(zhí)行協(xié)同搬運任務前集結(jié)分散的AGV提供了思路。