基于遺傳算法的工廠AGV路徑優化研究

黨宏社 孫心妍

摘要：針對工廠AGV行駛路徑復雜、應用局限性等問題，vRAGV配送物料行駛路徑最短為目標，采用遺傳算法進行AGV路徑規劃，并加入物料類型選擇的循環套，通過多次實驗確定最合理的控制參數，從而產生AGV運輸多種類型物料的最優路徑結果。使用Maflab軟件對算法進行仿真，結果表明：該算法是有效的，能夠直接實現ACV在輸多種類型物料時所產生的不同種路徑的優化。

關鍵詞：自動導引車;路徑規劃;遺傳算法

0引言

隨著社會生產技術的發展和自動化程度的提高，很多工廠為了提升運輸工作效率，引入了自動導引小車AGV（Automatic Guided Vehicle）進行物流運輸。據相關資料統計，在制造業中不足5%的時間用于加工裝配，而超過95%的時間用于物流配送，因此物料的及時準確供應直接關系到生產線的流暢性。節約車間生產成本，減少物料運輸時間，提升單臺AGV搬運效率，一直以來AGV的路徑規劃問題，即尋找AGV的最優路徑是工廠所關注的焦點。

目前國內外很多學者都對于AGV的路徑規劃問題做了相應的研究。遺傳算法是模仿自然界生物進化機制發展起來的隨機全局搜索優化方法，具有算法效率高、魯棒性強、可實現并行搜索等特點，被廣泛用于解決路徑規劃等領域的問題。G.Jeon和William等人用混合遺傳算法求解車輛路徑規劃問題：李青欣進行了AGV路徑規劃的遺傳算法研究，根據運行環境信息復雜度和數量的不同分別分析了幾種不同類型的路徑規劃。

當前國內外學者在AGV的路徑規劃問題上取得了諸多成果，但是實際的工廠生產情況多變，機器所需的物料并不相同，因而AGV的運輸路徑也有差異。多類型物料的運輸與AGV路徑的優化相結合的研究目前并不多見也不夠完善。

針對遺傳算法解決路徑規劃問題時只能完成單任務、實現單次運輸路徑規劃的不足，為提升規劃效率，擴大應用面，本文在路徑規劃以前，加入對于物料的選擇情況，構建路徑規劃數學模型，設計遺傳算法并進行數據仿真，一次得到AGV運輸多種物料的行駛路徑。仿真結果表明本文提出的基于遺傳算法的AGV路徑規劃方案對于解決此類運輸問題是有效的。

1工廠AGV路徑規劃的模型

1.1問題描述

某工廠的AGV運輸物料模型一般可以描述為：工廠的生產車間共有20臺工作機器，需要5種物料，當AGV運輸不同物料時，途經的機器坐標和數量不同，行駛路徑有很多種。本文將研究如何運用遺傳算法高效直接的產生AGV運輸多種物料時的不同路徑優化結果。鑒于AGV運輸物料的過程比較復雜，且為了便于本文的模型建立及研究，現做如下規定和假設：

1）單臺AGV只可運輸一種物料：

2）AGV初始位置均在物料配送中心：

3）AGV行駛路徑是指從物料配送中心坐標為起點，途經所有需要此種類型物料的機器，最后回到起點;

2遺傳算法的流程

本文采用遺傳算法進行路徑的優化。算法的具體流程圖如下圖1所示：

采用1-N的數字隨機排列的方式進行編碼，可以省去解碼環節，提高了算法的運行效率，其中一條染色體就代表AGV在車間內運輸物料的一種行駛路徑。

3.2初始群體的設定

本文中考慮一般情況下，在編碼空間內均勻采樣，對于Ⅳ臺工作機器，隨機生成一定數目的個體（一般為機器數量的2倍，即2N），每個個體代表AGV運輸特定類型物料的路線。傳統的算法解決路徑規劃問題時，初始群體都是固定值，算法只產生適用一種情況的最優路徑，本文在算法的前端加入了物料類型選擇的循環套。當AGV運輸A、B、C、D、E這5種不同類型的物料時，初始群體的規模也不相同，具體數值如下表所示：

選擇過程體現了自然界生物進化過程中“適者生存”的思想，并且能夠確保適應度強的優良基因遺傳到下一代的個體。

3.4.2交叉操作

本文中，假設隨機選擇兩個已經被復制的個體分別為：A=35749，B=46285，確定交叉點，A=35I 749，B=46I 285，在對應位置交換基因片段，同時保證每個個體依然是1-N的隨機排列，防止進入局部收斂，交叉過程后則產生=46749，=35285兩個新個體。

3.4.3變異操作

本文中，在已經被選擇的個體中，隨機選取1個個體，同時隨機選取個體的兩個基因進行交換，實現變異操作。假設隨機選取個體A=3576289，選取該個體上的“3”“7“兩個基因進行位置互換，可以得到新的個體=7536289。通過變異操作，可增加種群的多樣性，有效地防止了遺傳算法過早的收斂，出現“早熟”現象。

3.5控制參數的設定以及循環終止條件

遺傳算法中關鍵的參數為：交叉概率、變異概率和迭代次數C。交叉概率控制著交叉算子的應用頻率，變異操作是保持群體多樣性的最有效手段，迭代次數決定了遺傳操作的執行次數。為了確保參數設置的有效性和合理性，做了如下實驗。

3.5.1交叉概率

選擇將AGV運輸C類物料的路徑作為研究對象，遍歷機器數目為N=13，AGV行駛路徑個數也即群體規模為2N=26，迭代次數C為50次，設定變異概率，改變交叉概率的數值，每種情況實驗15次，求出不同數值下的平均路徑長度，發現當交叉概率時，平均路徑長度最短。因此，本文中遺傳算法的交叉概率取值為0.6為宜。

3.5.2變異概率

遍歷機器數目、AGV行駛路徑個數、迭代次數保持不變，設定交叉概率，改變交叉概率的數值，每種情況實驗15次，求出不同數值下的平均路徑長度。發現當變異概率時，平均路徑長度最短。因此，本文中遺傳算法的變異概率取值為0.08為宜。

3.5.3迭代次數

本文將AGV運輸不同類型的物料時算法迭代次數設為不同的值，當遍歷機器數目為N時，迭代次數C為4N，從而提高了算法的運行效率。

3.5.4循環終止條件

本文迭代終止條件連續4代最優解不發生變化則迭代停止，輸出最優解。

4實驗仿真與結果分析

在Matlab2016環境下運用改進后的遺傳算法進行路徑的優化，可以一次性得到AGV分別運輸車間要求的5種物料時的優化路徑，仿真結果如下圖3所示：