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

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

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

　　０ 引言

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

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

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

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

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

　　1.1 問題描述

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

　　1）單臺AGV只可運(yùn)輸一種物料；

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

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

　　4）單臺AGV的運(yùn)輸量可以滿足全部機(jī)器所需的特定類型物料量。

　　1.2 模型的建立

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

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

　　2 遺傳算法的流程

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

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

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

　　3.1 參數(shù)編碼

　　本文中，選擇采用直接反映AGV行駛路徑的整數(shù)編碼方法 ^[7] ，工廠車間共有20臺機(jī)器，機(jī)器序號為{1，2，3??20}，則編碼位串為：1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20，表示對機(jī)器采用升序方法訪問行駛路線。若編碼位串為：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”依此訪問每個機(jī)器，每種行駛路徑就對應(yīng)一條染色體。

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

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

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

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

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

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

　　每個染色體（即N臺機(jī)器的隨機(jī)排列）的總距離也可以計(jì)算出來，因?yàn)楹玫穆窂绞蔷嚯x短的，因此選擇將每個隨機(jī)全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即總距離越短，則適應(yīng)度越好，滿足要求。

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

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

　　3.4.1 選擇操作

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

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

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

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

　　3.4.2 交叉操作

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

　　3.4.3 變異操作

　　本文中，在已經(jīng)被選擇的個體中，隨機(jī)選取1個個體，同時隨機(jī)選取個體的兩個基因進(jìn)行交換，實(shí)現(xiàn)變異操作。假設(shè)隨機(jī)選取個體A=3 5 7 6 2 8 9 ，選取該個體上的“3”“7“兩個基因進(jìn)行位置互換，可以得到新的個體=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è)置的有效性和合理性，做了如下實(shí)驗(yàn)。

　　3.5.1 交叉概率

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

　　3.5.2 變異概率

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

　　3.5.3 迭代次數(shù)

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

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

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

　　４ 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

　　５ 結(jié)論

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

　　參考文獻(xiàn)

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

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

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