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

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

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

　　關(guān)鍵詞：自動導(dǎo)引車；路徑規(guī)劃；遺傳算法

　　０ 引言

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

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

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

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

　　1 工廠AGV路徑規(guī)劃的模型

　　1.1 問題描述

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

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

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

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

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

　　1.2 模型的建立

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

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

　　2 遺傳算法的流程

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

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

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

　　3.1 參數(shù)編碼

　　本文中，選擇采用直接反映AGV行駛路徑的整數(shù)編碼方法 ^[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所示，假設(shè)編碼位串為：1 3 57 9 10，則表示按照特定順序“1-3-5-7-9-10”依此訪問每個機器，每種行駛路徑就對應(yīng)一條染色體。

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

　　3.2 初始群體的設(shè)定

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

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

　　3.3 適應(yīng)度函數(shù)的設(shè)計

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

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

　　3.4 遺傳操作的設(shè)計

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

　　3.4.1 選擇操作

　　本文中采用適應(yīng)值比例選擇的方法，通常采用輪盤賭方式實現(xiàn)。

　　對于給定的規(guī)模為n的群體，

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

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

　　3.4.2 交叉操作

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

　　3.4.3 變異操作

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

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

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

　　3.5.1 交叉概率

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

　　3.5.2 變異概率

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

　　3.5.3 迭代次數(shù)

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

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

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

　　４ 實驗仿真與結(jié)果分析

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

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

　　５ 結(jié)論

　　針對工廠AGV的行駛路徑問題，本文在路徑優(yōu)化操作前加入物料類型的選擇循環(huán)套，針對不同的群體規(guī)模設(shè)定相應(yīng)的迭代次數(shù)，并通過實驗數(shù)據(jù)選擇優(yōu)化效果最佳的控制參數(shù)，最后進行了數(shù)據(jù)的仿真驗證，證明了該算法的有效性。本文的研究成果擴大了遺傳算法解決類似路徑規(guī)劃問題的應(yīng)用面。對于工廠的實際生產(chǎn)情況來講，本文的研究成果可以提高車間的生產(chǎn)效率，進而提升工廠經(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]樊樹海, 陳金龍, 曹霞, 等. 順序矩陣擴展在流水車間布置中的應(yīng)用[J].工業(yè)工程與管理, 2008(6):51-53.

　　[3]徐翔,梁瑞仕,楊會志.基于改進遺傳算法的智能體路徑規(guī)劃仿真[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ǎo)引車路徑規(guī)劃遺傳算法研究[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]王洲,張毅,楊銳敏.基于遺傳算法的移動機器人路徑規(guī)劃[J].微計算機信息, 2008, 24(26):187-189.

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