基于遺傳算法的工廠(chǎng)AGV路徑優(yōu)化研究

　　黨宏社，孫心妍（陜西科技大學(xué)電氣與控制工程學(xué)院，陜西?西安?710021）

　　摘?要：針對工廠(chǎng)AGV行駛路徑復雜、應用局限性等問(wèn)題，以AGV配送物料行駛路徑最短為目標，采用遺傳算法進(jìn)行AGV路徑規劃，并加入物料類(lèi)型選擇的循環(huán)套，通過(guò)多次實(shí)驗確定最合理的控制參數，從而產(chǎn)生AGV運輸多種類(lèi)型物料的最優(yōu)路徑結果。使用Matlab軟件對算法進(jìn)行仿真，結果表明：該算法是有效的，能夠直接實(shí)現AGV在運輸多種類(lèi)型物料時(shí)所產(chǎn)生的不同種路徑的優(yōu)化。

　　關(guān)鍵詞：自動(dòng)導引車(chē)；路徑規劃；遺傳算法

　　０ 引言

　　隨著(zhù)社會(huì )生產(chǎn)技術(shù)的發(fā)展和自動(dòng)化程度的提高，很多工廠(chǎng)為了提升運輸工作效率，引入了自動(dòng)導引小車(chē)AGV（Automatic Guided Vehicle）進(jìn)行物流運輸。據相關(guān)資料統計，在制造業(yè)中不足 5% 的時(shí)間用于加工裝配，而超過(guò) 95% 的時(shí)間用于物流配送，因此物料的及時(shí)準確供應直接關(guān)系到生產(chǎn)線(xiàn)的流暢性 ^[1-2] 。節約車(chē)間生產(chǎn)成本，減少物料運輸時(shí)間，提升單臺AGV搬運效率，一直以來(lái)AGV的路徑規劃問(wèn)題，即尋找AGV的最優(yōu)路徑是工廠(chǎng)所關(guān)注的焦點(diǎn)。

　　目前國內外很多學(xué)者都對于A(yíng)GV的路徑規劃問(wèn)題做了相應的研究。遺傳算法是模仿自然界生物進(jìn)化機制發(fā)展起來(lái)的隨機全局搜索優(yōu)化方法，具有算法效率高、魯棒性強、可實(shí)現并行搜索等特點(diǎn) ^[3] ，被廣泛用于解決路徑規劃等領(lǐng)域的問(wèn)題。G.Jeon ^[4] 和William ^[5] 等人用混合遺傳算法求解車(chē)輛路徑規劃問(wèn)題；李青欣 ^[6] 進(jìn)行了AGV路徑規劃的遺傳算法研究，根據運行環(huán)境信息復雜度和數量的不同分別分析了幾種不同類(lèi)型的路徑規劃。

　　當前國內外學(xué)者在A(yíng)GV的路徑規劃問(wèn)題上取得了諸多成果，但是實(shí)際的工廠(chǎng)生產(chǎn)情況多變，機器所需的物料并不相同，因而AGV的運輸路徑也有差異。多類(lèi)型物料的運輸與AGV路徑的優(yōu)化相結合的研究目前并不多見(jiàn)也不夠完善。

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

　　1 工廠(chǎng)AGV路徑規劃的模型

　　1.1 問(wèn)題描述

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

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

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

　　3）AGV行駛路徑是指從物料配送中心坐標為起點(diǎn)，途經(jīng)所有需要此種類(lèi)型物料的機器，最后回到起點(diǎn)；

　　4）單臺AGV的運輸量可以滿(mǎn)足全部機器所需的特定類(lèi)型物料量。

　　1.2 模型的建立

　　為了使AGV完成物料配送任務(wù)的路徑最優(yōu)，建立如下數學(xué)模型：

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

　　2 遺傳算法的流程

　　本文采用遺傳算法進(jìn)行路徑的優(yōu)化。算法的具體流程圖如下圖1所示：

　　3基于遺傳算法的AGV路徑優(yōu)化

　　本文采用遺傳算法進(jìn)行工廠(chǎng)AGV路徑優(yōu)化的研究。

　　3.1 參數編碼

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

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

　　3.2 初始群體的設定

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

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

　　3.3 適應度函數的設計

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

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

　　3.4 遺傳操作的設計

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

　　3.4.1 選擇操作

　　本文中采用適應值比例選擇的方法，通常采用輪盤(pán)賭方式實(shí)現。

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

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

　　選擇過(guò)程體現了自然界生物進(jìn)化過(guò)程中“適者生存”的思想，并且能夠確保適應度強的優(yōu)良基因遺傳到下一代的個(gè)體。

　　3.4.2 交叉操作

　　本文中，假設隨機選擇兩個(gè)已經(jīng)被復制的個(gè)體分別為：A=3 5 7 4 9，B=4 6 2 8 5，確定交叉點(diǎn)，A=35｜7 4 9，B=4 6｜2 8 5，在對應位置交換基因片段，同時(shí)保證每個(gè)個(gè)體依然是1-N的隨機排列，防止進(jìn)入局部收斂，交叉過(guò)程后則產(chǎn)生=4 6 7 4 9，=3 5 2 8 5兩個(gè)新個(gè)體。

　　3.4.3 變異操作

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

　　3.5 控制參數的設定以及循環(huán)終止條件

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

　　3.5.1 交叉概率

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

　　3.5.2 變異概率

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

　　3.5.3 迭代次數

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

　　3.5.4 循環(huán)終止條件

　　本文迭代終止條件連續4代最優(yōu)解不發(fā)生變化則迭代停止，輸出最優(yōu)解。

　　４ 實(shí)驗仿真與結果分析

　　在Matlab2016環(huán)境下運用改進(jìn)后的遺傳算法進(jìn)行路徑的優(yōu)化，可以一次性得到AGV分別運輸車(chē)間要求的5種物料時(shí)的優(yōu)化路徑，仿真結果如下圖3所示：

　　如圖所示，本文提出的算法，可以直接給出AGV運輸５種物料時(shí)的路徑優(yōu)化結果，根據圖3的仿真圖形可以直觀(guān)看出，在給定AGV必須經(jīng)過(guò)的固定機器坐標后，隨機產(chǎn)生的AGV行駛路徑比較復雜，并且路徑過(guò)長(cháng)，浪費了時(shí)間成本，不能在個(gè)別機器缺料時(shí)盡快進(jìn)行物料補給，間接地降低了車(chē)間機器的生產(chǎn)效率；而經(jīng)過(guò)遺傳算法優(yōu)化后的路徑較短，路線(xiàn)簡(jiǎn)明，大大節約了運輸時(shí)間，能更加高效地為車(chē)間工作機器提供物料運輸服務(wù)。

　　５ 結論

　　針對工廠(chǎng)AGV的行駛路徑問(wèn)題，本文在路徑優(yōu)化操作前加入物料類(lèi)型的選擇循環(huán)套，針對不同的群體規模設定相應的迭代次數，并通過(guò)實(shí)驗數據選擇優(yōu)化效果最佳的控制參數，最后進(jìn)行了數據的仿真驗證，證明了該算法的有效性。本文的研究成果擴大了遺傳算法解決類(lèi)似路徑規劃問(wèn)題的應用面。對于工廠(chǎng)的實(shí)際生產(chǎn)情況來(lái)講，本文的研究成果可以提高車(chē)間的生產(chǎn)效率，進(jìn)而提升工廠(chǎng)經(jīng)濟效益。

　　參考文獻

　　[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]樊樹(shù)海, 陳金龍, 曹霞, 等. 順序矩陣擴展在流水車(chē)間布置中的應用[J].工業(yè)工程與管理, 2008(6):51-53.

　　[3]徐翔,梁瑞仕,楊會(huì )志.基于改進(jìn)遺傳算法的智能體路徑規劃仿真[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òng)導引車(chē)路徑規劃遺傳算法研究[D]. 廣州:廣東工業(yè)大學(xué), 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]王洲,張毅,楊銳敏.基于遺傳算法的移動(dòng)機器人路徑規劃[J].微計算機信息, 2008, 24(26):187-189.

　　本文來(lái)源于科技期刊《電子產(chǎn)品世界》2020年第01期第48頁(yè)，歡迎您寫(xiě)論文時(shí)引用，并注明出處。