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

　　黨宏社，孫心妍（陝西科技大學電氣與控制工程學院，陝西 西安 710021）

本文引用地址：http://www.eepw.com.cn/article/201912/408674.htm

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

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

　　０ 引言

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

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

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

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

　　1 工廠AGV路徑規劃的模型

　　1.1 問題描述

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

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

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

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

　　4）單臺AGV的運輸量可以滿足全部機器所需的特定類型物料量。

　　1.2 模型的建立

　　為了使AGV完成物料配送任務的路徑最優，建立如下數學模型：

　　其中 min L 表示一種行駛路徑的最短路徑距離，D( i,i+1) 表示從第 i 臺工作機器到第 i+1 臺工作機器的距離。

　　2 遺傳算法的流程

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

　　3基於遺傳算法的AGV路徑優化

　　本文採用遺傳算法進行工廠AGV路徑優化的研究。

　　3.1 參數編碼

　　本文中，選擇採用直接反映AGV行駛路徑的整數編碼方法 ^[7] ，工廠車間共有20臺機器，機器序號為{1，2，3⋯⋯20}，則編碼位串為：1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20，表示對機器採用升序方法訪問行駛路線。若編碼位串為：20 19 18 17 16 1514 13 12 11 10 9 8 7 6 5 4 3 2 1，則表示按降序方法訪問行駛路線。如下圖2所示，假設編碼位串為：1 3 57 9 10，則表示按照特定順序「1-3-5-7-9-10」依此訪問每個機器，每種行駛路徑就對應一條染色體。

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

　　3.2 初始群體的設定

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

　　本文在Matlab中使用randperm(N)產生一個1*N的矩陣（N為工作機器數量）為一個隨機路徑。利用2N*N矩陣存儲2N個隨機群體作為初始群體。

　　3.3 適應度函數的設計

　　適應度函數的建立是遺傳算法收斂性和穩定性的重要影響因素 ^[8] ，本文中， D(i,j) 代表機器i和機器 j 之間的距離為

　　每個染色體（即N臺機器的隨機排列）的總距離也可以計算出來，因為好的路徑是距離短的，因此選擇將每個隨機全排列的總距離的倒數作為適應度函數，即總距離越短，則適應度越好，滿足要求。

　　3.4 遺傳操作的設計

　　遺傳操作是遺傳算法的精髓，標準遺傳算法的算子一般包括選擇、交叉和變異3種基本形式。

　　3.4.1 選擇操作

　　本文中採用適應值比例選擇的方法，通常採用輪盤賭方式實現。

　　對於給定的規模為n的群體，

　　個體 a_j ∈p的適應值為f ( a_j)，其被選擇的概率為：

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

　　3.4.2 交叉操作

　　本文中，假設隨機選擇兩個已經被複製的個體分別為：A=3 5 7 4 9，B=4 6 2 8 5，確定交叉點，A=35｜7 4 9，B=4 6｜2 8 5，在對應位置交換基因片段，同時保證每個個體依然是1-N的隨機排列，防止進入局部收斂，交叉過程後則產生=4 6 7 4 9，=3 5 2 8 5兩個新個體。

　　3.4.3 變異操作

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

　　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代最優解不發生變化則迭代停止，輸出最優解。

　　４ 實驗仿真與結果分析

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

　　如圖所示，本文提出的算法，可以直接給出AGV運輸５種物料時的路徑優化結果，根據圖3的仿真圖形可以直觀看出，在給定AGV必須經過的固定機器坐標後，隨機產生的AGV行駛路徑比較複雜，並且路徑過長，浪費了時間成本，不能在個別機器缺料時儘快進行物料補給，間接地降低了車間機器的生產效率；而經過遺傳算法優化後的路徑較短，路線簡明，大大節約了運輸時間，能更加高效地為車間工作機器提供物料運輸服務。

　　５ 結論

　　針對工廠AGV的行駛路徑問題，本文在路徑優化操作前加入物料類型的選擇循環套，針對不同的群體規模設定相應的迭代次數，並通過實驗數據選擇優化效果最佳的控制參數，最後進行了數據的仿真驗證，證明了該算法的有效性。本文的研究成果擴大了遺傳算法解決類似路徑規劃問題的應用面。對於工廠的實際生產情況來講，本文的研究成果可以提高車間的生產效率，進而提升工廠經濟效益。

　　參考文獻

　　[1] KOO P H , JANG J , SUH J . Vehicle dispatching forhighly loaded semiconductor production consideringbottleneck machines first[J]. International Journal of FlexibleManufacturing Systems, 2005, 17(1):23-38.

　　[2]樊樹海, 陳金龍, 曹霞, 等. 順序矩陣擴展在流水車間布置中的應用[J].工業工程與管理, 2008(6):51-53.

　　[3]徐翔,梁瑞仕,楊會志.基於改進遺傳算法的智能體路徑規劃仿真[J].計算機仿真,2014(6):357-361.

　　[4] JEON G , LEEP H R , SHIM J Y . A vehicle routing problemsolved by using a hybrid genetic algorithm[J]. Computers andIndustrial Engineering, 2007, 53(4):680-692.

　　[5] HO W . HO G T S , JI P , et al. A hybrid genetic algorithmfor the multi-depot vehicle routing problem[J]. EngineeringApplications of Artificial Intelligence, 2008, 21(4):548-557.

　　[6]李青欣.自動導引車路徑規劃遺傳算法研究[D]. 廣州:廣東工業大學, 2011.

　　[7] BAKER B M , AYECHEW M A . A genetic algorithm for thevehicle routing problem[J]. Computers & Operations Research,2003, 30(5):787-800.

　　[8]王洲,張毅,楊銳敏.基於遺傳算法的移動機器人路徑規劃[J].微計算機信息, 2008, 24(26):187-189.

　　本文來源於科技期刊《電子產品世界》2020年第01期第48頁，歡迎您寫論文時引用，並註明出處。