劉 旭,樓佩煌,錢(qián)曉明,武 星

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

基于改進(jìn)遺傳算法的物料配送多AGV調(diào)度優(yōu)化

劉 旭,樓佩煌,錢(qián)曉明,武 星

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

為解決混流作業(yè)車(chē)間中物料配送多自動(dòng)導(dǎo)引車(chē)(AGV)的調(diào)度優(yōu)化問(wèn)題，以AGV配送物料行駛時(shí)間最短為目標(biāo)建立數(shù)學(xué)優(yōu)化模型，提出了一種改進(jìn)的遺傳算法進(jìn)行AGV的任務(wù)分配和配送路徑優(yōu)化。在算法設(shè)計(jì)過(guò)程中，采用直接反映AGV配送路徑和任務(wù)分配的整數(shù)編碼方式，為避免常規(guī)交叉變異過(guò)程中產(chǎn)生不可行解的情況，改進(jìn)了交叉變異算子，采用最好-最壞交叉模式和基因段隨機(jī)交換的變異模式，獲得了優(yōu)化的調(diào)度方案。最后，以某重型機(jī)械公司裝配車(chē)間內(nèi)物料輸送AGV調(diào)度優(yōu)化為實(shí)例，并與遺傳算法和分支定界法進(jìn)行對(duì)比，驗(yàn)證了所提方法的可行性和有效性。

自動(dòng)導(dǎo)引車(chē)；調(diào)度；數(shù)學(xué)優(yōu)化模型；改進(jìn)遺傳算法

隨著自動(dòng)化技術(shù)和計(jì)算機(jī)技術(shù)不斷發(fā)展，自動(dòng)導(dǎo)引車(chē)(Automated Guided Vehicle，AGV)作為一種靈活高效的輸送設(shè)備在制造系統(tǒng)、碼頭以及倉(cāng)儲(chǔ)系統(tǒng)等領(lǐng)域得到廣泛的推廣和應(yīng)用。據(jù)相關(guān)資料統(tǒng)計(jì)，在制造業(yè)中不足5%時(shí)間用于加工裝配，而超過(guò)95%時(shí)間用于物流配送，因此物料的及時(shí)準(zhǔn)確供應(yīng)直接關(guān)系到生產(chǎn)線的流暢性[1-2]。AGV作為物流配送的關(guān)鍵設(shè)備，如何合理地進(jìn)行調(diào)度，以提高物料搬運(yùn)效率和降低生產(chǎn)成本，一直是企業(yè)關(guān)注的焦點(diǎn)。目前國(guó)內(nèi)外對(duì)AGV調(diào)度的研究也比較多，主要集中于AGV路徑和生產(chǎn)效率優(yōu)化方面[3]。王國(guó)新[4]等針對(duì)制造系統(tǒng)中單AGV任務(wù)調(diào)度優(yōu)化問(wèn)題，提出離散仿真和分支定界(Branch and Bound Algorithm，BBA)相結(jié)合的方法，但是該方法迭代次數(shù)較多；羅建[5]等針對(duì)自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)調(diào)度優(yōu)化問(wèn)題，建立單 AGV調(diào)度數(shù)學(xué)模型，運(yùn)用一種改進(jìn)量子微粒群算法(Quantum Particle Swarm Optimization， QPSO)來(lái)求解模型，但是沒(méi)有考慮多任務(wù)調(diào)度問(wèn)題；Nishi[6]等針對(duì)制造系統(tǒng)中多AGV路徑規(guī)劃問(wèn)題，建立多AGV調(diào)度模型，提出一種分解算法進(jìn)行求解。

以上研究多集中在單AGV或單任務(wù)調(diào)度優(yōu)化問(wèn)題上，本文對(duì)車(chē)間物料輸送多AGV調(diào)度優(yōu)化問(wèn)題進(jìn)行了深入的研究，在建立多AGV調(diào)度優(yōu)化數(shù)學(xué)模型的基礎(chǔ)上，提出了一種改進(jìn)的遺傳算法(Improved Genetic Algorithm, IGA)進(jìn)行求解，最后針對(duì)具體實(shí)例，給出了物料配送路徑和AGV任務(wù)分配優(yōu)化結(jié)果，證明了所提方法的有效性和可行性。

1 問(wèn)題的描述和建模

混流作業(yè)車(chē)間物料輸送是根據(jù)各工作站的物料配送需求，合理調(diào)度AGV將物料準(zhǔn)確及時(shí)地運(yùn)送到各需求點(diǎn)?；炝髯鳂I(yè)車(chē)間物料配送AGV調(diào)度優(yōu)化問(wèn)題比較復(fù)雜，在建模過(guò)程中必須考慮AGV任務(wù)分配原則、物料需求情況、AGV路徑?jīng)_突、車(chē)載容量等因素。如果AGV調(diào)度不合理，可能使物料配送時(shí)間過(guò)長(zhǎng)，導(dǎo)致生產(chǎn)成本增加。鑒于混流作業(yè)車(chē)間中物料配送多AGV調(diào)度比較復(fù)雜，故作如下假設(shè)：

a.系統(tǒng)生產(chǎn)節(jié)拍、系統(tǒng)布局、系統(tǒng)AGV數(shù)量和導(dǎo)引路徑均是已知，AGV啟動(dòng)、停止時(shí)間和運(yùn)行故障問(wèn)題(系統(tǒng)癱瘓、脫線等)忽略不計(jì)，AGV在工作站中的服務(wù)時(shí)間是固定的。

b.所有缺料的工作站只需配送一次，同一個(gè)工作站不允許配送兩次。

c.AGV初始位置均在物料配送中心，沿著最短路徑，以固定速率運(yùn)行。

d.AGV可以同時(shí)接收多個(gè)任務(wù)，依次執(zhí)行，并且AGV可以同時(shí)搬運(yùn)不同品種的物料，物料配送一旦開(kāi)始，則配送過(guò)程是連續(xù)的，不允許出現(xiàn)中斷。

混流作業(yè)車(chē)間物料配送AGV調(diào)度優(yōu)化問(wèn)題可以描述為：在混流作業(yè)車(chē)間中共有V輛相同容量的AGV小車(chē)，某階段制造系統(tǒng)有N個(gè)工位或工作站需要物料配送，AGV在裝載好物料后將物料依次送到工作站，直至完成所有物料配送后返回到物料配送中心。為了使AGV完成物料配送耗時(shí)最短，建立的數(shù)學(xué)模型如下：

(1)

(2)

(3)

約束條件如下：

(4)

(5)

(6)

(7)

Xij1≥Xij2≥…≥Xijk?i,j

(8)

(9)

其中:Ti,j表示第i輛AGV完成第j個(gè)任務(wù)所需的時(shí)間；ti,j-1表示第i輛AGV的(j-1)個(gè)任務(wù)所在的工作站到第j個(gè)任務(wù)所在工作站所需的時(shí)間；Ui,k表示第i輛AGV在工作站k中的物料卸載時(shí)間。式(1)表示最小化完成所有配料任務(wù)的時(shí)間；式(2)表示最小化物料配送的平均時(shí)間，作為輔助目標(biāo)用于算法過(guò)程中優(yōu)良個(gè)體的選擇；式(4)表示每個(gè)工作站只能配送物料一次；式(5)表示每臺(tái)AGV每次只能執(zhí)行一個(gè)任務(wù)；式(6)表示每個(gè)工作站只有一次配料任務(wù)，并且每個(gè)任務(wù)只能由一臺(tái)AGV來(lái)執(zhí)行；式(7)表示AGV完成了所有工作站的物料配送任務(wù)；式(8)表示每輛AGV的多個(gè)任務(wù)是依次連續(xù)排列的；式(9)表示第i輛車(chē)第j個(gè)任務(wù)的完成時(shí)間等于第i輛車(chē)第(j-1)個(gè)任務(wù)的完成時(shí)間和AGV在工作站間的行駛時(shí)間以及物料卸載時(shí)間三者之和。

2 改進(jìn)的遺傳算法

針對(duì)混流作業(yè)系統(tǒng)中物料配送AGV調(diào)度問(wèn)題，設(shè)計(jì)的改進(jìn)遺傳算法流程圖如圖1所示。

2.1編碼設(shè)計(jì)

遺傳算法有很多種編碼方式，為了清晰表達(dá)問(wèn)題的解，本文采用直接反映AGV配送路徑和任務(wù)分配的整數(shù)編碼方法[7]，每個(gè)染色體都代表一種物料配送計(jì)劃，由若干個(gè)AGV配送任務(wù)構(gòu)成，并且每個(gè)工作站在染色體中只能出現(xiàn)一次，這樣可以保證個(gè)體中包含所有需要補(bǔ)料的工作站。圖2所示為一個(gè)包含12個(gè)工作站的個(gè)體S1的編碼，其中0表示物料配送中心，數(shù)字1～12代表需要配料的工作站。圖中每一條支線代表一輛AGV執(zhí)行物料配送任務(wù)，支線的數(shù)量為系統(tǒng)中參與物料配送AGV的數(shù)量，工作站編號(hào)順序代表AGV執(zhí)行配送任務(wù)的先后順序，其序列表達(dá)方式為[0,1,2,6,7,0,5,4,9,12,0,3, 8,10,11]。

染色體編碼后，要按照編碼規(guī)則對(duì)染色體進(jìn)行解碼，按照個(gè)體基因信息解釋成AGV任務(wù)分配信息和物料配送路徑信息。通過(guò)模擬AGV調(diào)度過(guò)程，記錄每輛AGV完成任務(wù)的目標(biāo)值，進(jìn)而獲得個(gè)體的目標(biāo)值。個(gè)體Si適應(yīng)度函數(shù)F(Si)定義如下：

式中：Total表示當(dāng)前種群中所有個(gè)體目標(biāo)值的總和；Ps表示當(dāng)前種群的規(guī)模；f(Si)表示個(gè)體Si的目標(biāo)值。根據(jù)上述定義可知，個(gè)體適應(yīng)度值越大，目標(biāo)值越小。

選擇操作采用輪盤(pán)賭選擇法，將種群中所有個(gè)體按照適應(yīng)度升序排列，各個(gè)個(gè)體被選擇的概率與其適應(yīng)度成正比，然后每次從父代種群中選擇兩個(gè)個(gè)體進(jìn)入交叉變異操作[8]。

2.2種群初始化

對(duì)于算法的進(jìn)化和收斂效果來(lái)說(shuō)，結(jié)構(gòu)優(yōu)良的初始種群非常重要，本文算法取種群規(guī)模為100，算法初期采用強(qiáng)交叉變異(Pc=0.8，Pm=0.7)來(lái)增大搜索空間，后期采用弱交叉變異(Pc=0.8，Pm=0.2)來(lái)加快收斂速度。初始種群的創(chuàng)建步驟如下：

步驟1，根據(jù)系統(tǒng)中可調(diào)度AGV數(shù)量，確定個(gè)體支線數(shù)目V；根據(jù)工作站數(shù)量，確定基因編號(hào)范圍[1,N]。

步驟2，用創(chuàng)建任意離散隨機(jī)種群的方法對(duì)個(gè)體每個(gè)基因生成一個(gè)隨機(jī)數(shù)ri，ri∈[1,N]，基因數(shù)等于系統(tǒng)工作站數(shù)量。

步驟3，對(duì)生成的個(gè)體基因進(jìn)行調(diào)整，確?；蛑邪械墓ぷ髡?，修正完畢后將個(gè)體基因序列隨機(jī)分割為V段，每段基因均代表一條物料配送路徑。

步驟4，重復(fù)上述步驟100次，產(chǎn)生一個(gè)包含100個(gè)個(gè)體的初始種群。

2.3交叉操作

交叉是將兩父代個(gè)體的部分基因進(jìn)行替換或重組從而生成新的個(gè)體。由于染色體編碼規(guī)則的變化，常規(guī)的單點(diǎn)或雙點(diǎn)交叉模式容易產(chǎn)生不可行解，因此本文對(duì)交叉算子做出改進(jìn)，在綜合兩點(diǎn)交叉和BCBRC(BestCostBestRouteCrossover)[9]相結(jié)合的混合交叉模式基礎(chǔ)上，提出一種最好-最差交叉模式，其基本思想是保證優(yōu)秀基因在進(jìn)化過(guò)程中不被破壞。該交叉模式的過(guò)程如下：首先，根據(jù)目標(biāo)函數(shù)值從父代個(gè)體S1，S2中選擇最優(yōu)和最差的兩條配送路徑；然后，用S1中的最優(yōu)配送路徑替換S2中最差配送路徑，從而產(chǎn)生子代P2，S2中最優(yōu)配送路徑替換S1中最差配送路徑，從而產(chǎn)生子代P1；最后刪掉P1，P2中重復(fù)的工作站點(diǎn)，并同時(shí)將失去的工作站點(diǎn)重新修補(bǔ)插入到最佳位置。此方法的具體步驟如圖3所示。

2.4變異過(guò)程

變異算子影響種群的多樣性和局部搜索能力，由于采用實(shí)數(shù)制編碼方式，常規(guī)的變異方式容易產(chǎn)生含有相同節(jié)點(diǎn)的不可行解,因此本文采用基因段隨機(jī)交換的變異模式，其具體操作過(guò)程如下：從個(gè)體S1的兩個(gè)不同配送路徑中隨機(jī)取兩段基因，然后將兩段基因進(jìn)行交換形成新個(gè)體P1，如圖4所示。采用此種方法可以保證新個(gè)體中含有所有的工作站。

2.5精英保留策略

為了在進(jìn)化過(guò)程中能夠準(zhǔn)確選擇優(yōu)良個(gè)體，在算法中引入精英保留策略。父代種群經(jīng)過(guò)選擇、交叉和變異操作后形成子代種群，與父代種群合并得到2Ps個(gè)個(gè)體作為候選種群。計(jì)算候選種群中每個(gè)個(gè)體的目標(biāo)值和平均值，對(duì)其中目標(biāo)值相同而基因不同的個(gè)體，根據(jù)其平均值進(jìn)行篩選，對(duì)平均值高的個(gè)體處以罰函數(shù)，降低其適應(yīng)度。將調(diào)整后的2Ps個(gè)個(gè)體按其適應(yīng)度進(jìn)行降序排列，取其中適應(yīng)度高的Ps個(gè)個(gè)體作為下一代父代種群。此種方法能夠保證在種群進(jìn)化過(guò)程中保留優(yōu)良個(gè)體，避免偽優(yōu)良個(gè)體(目標(biāo)值低而平均值高的個(gè)體)大量充斥解空間。本文采用高斯罰函數(shù)：

式中：σ為常數(shù)，本文中σ2取0.4。

2.6迭代終止條件

通常遺傳算法迭代終止條件是連續(xù)數(shù)代目標(biāo)值或最優(yōu)解不發(fā)生變化，然而在迭代過(guò)程中往往個(gè)體目標(biāo)值雖沒(méi)有發(fā)生變化，種群均值卻不斷變化，種群仍在進(jìn)化。因此本文迭代終止條件是種群均值連續(xù)8代不發(fā)生變化則迭代停止，輸出最優(yōu)解。

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1實(shí)驗(yàn)相關(guān)數(shù)據(jù)

由于制造系統(tǒng)中物料配送種類(lèi)繁多，合理地調(diào)度AGV，使得物料能夠準(zhǔn)確及時(shí)地到達(dá)各個(gè)工作站就顯得十分重要。以某重型機(jī)械裝配系統(tǒng)為例，該裝配系統(tǒng)有12個(gè)工作站，分別將其編號(hào)為1，2,…，12，假定物料配送中心編號(hào)為0。系統(tǒng)中共有3臺(tái)AGV專(zhuān)門(mén)負(fù)責(zé)物料配送。該制造系統(tǒng)各工作站以及物料配送中心間距離見(jiàn)表1，物料的裝、卸載時(shí)間是固定的，并且相對(duì)于運(yùn)輸時(shí)間可以忽略不計(jì)。

本文利用上述所提方法對(duì)車(chē)間物料配送AGV調(diào)度進(jìn)行優(yōu)化，分別采用未改進(jìn)的遺傳算法(GA)、分支定界法(BBA)和改進(jìn)的遺傳算法(IGA)對(duì)建立的模型進(jìn)行求解，并且將3種算法優(yōu)化結(jié)果進(jìn)行了對(duì)比。

3.2實(shí)驗(yàn)結(jié)果分析

假定車(chē)間中12個(gè)工作站均需配送物料，配送過(guò)程仿真采用MATLAB軟件，通過(guò)實(shí)驗(yàn)仿真對(duì)本文所提IGA方法的有效性進(jìn)行驗(yàn)證，IGA算法迭代過(guò)程如圖5所示，算法在第16代開(kāi)始收斂，其目標(biāo)值為722，與GA、BBA運(yùn)行結(jié)果的對(duì)比見(jiàn)表2，本文所提方法得到的AGV完成物料配送時(shí)間和平均時(shí)間最短。表2中給出了最優(yōu)解對(duì)應(yīng)的AGV任務(wù)分配方案，3輛AGV的物料配送路徑分別為AGV1：0-2-5-9-10，配送時(shí)間為720s；AGV2：0-1-3-4-8-11，配送時(shí)間為722s；AGV3：0-7-12-6，配送時(shí)間為709s。物料配送平均時(shí)間為717s。為了進(jìn)一步驗(yàn)證本文所提方法的可靠性，采用多組不同數(shù)量工作站同時(shí)缺料情況作為算例，對(duì)IGA優(yōu)化效果進(jìn)行驗(yàn)證，與其他算法結(jié)果對(duì)比見(jiàn)表3，從表中可以看出本文所提IGA方法明顯優(yōu)于其他算法。

4 結(jié)束語(yǔ)

本文主要研究了混流作業(yè)車(chē)間物料配送多AGV多任務(wù)的調(diào)度優(yōu)化問(wèn)題，根據(jù)數(shù)學(xué)模型約束條件及求解參數(shù)的特點(diǎn)，提出了改進(jìn)的遺傳算法。針對(duì)某重型機(jī)械裝配車(chē)間物料配送實(shí)例，采用3種不同算法進(jìn)行求解，計(jì)算結(jié)果表明改進(jìn)的遺傳算法結(jié)果更優(yōu)，迭代次數(shù)更少，能夠提高裝配效率，降低生產(chǎn)成本。本文對(duì)實(shí)際車(chē)間物料配送進(jìn)行了簡(jiǎn)化，忽略了車(chē)輛沖突和物料到達(dá)工作站時(shí)間窗的限制，在今后研究中應(yīng)更多考慮不同工作站物料配送起止時(shí)間約束對(duì)AGV調(diào)度的影響。

[1]KooPH,JangJJ,SuhJD.Vehicledispatchingforhighlyloadedsemiconductorproductionconsideringbottleneckmachinesfirst[J].InternationalJournalofFlexibleManufacturingSystem，2005,17(1):23-38.

[2] 樊樹(shù)海，陳金龍，曹霞，等. 順序矩陣擴(kuò)展研究及其在流水車(chē)間布置中的應(yīng)用[J]. 工業(yè)工程與管理，2008,13(6): 51-54.

[3]VisIF.Surveyofresearchinthedesignandcontrolofautomatedguidedvehiclesystems[J].EuropeanJournalofOperationalResearch，2006，170(3):677-709.

[4] 王國(guó)新，寧汝新，王愛(ài)民，等. 仿真優(yōu)化在制造系統(tǒng)中的應(yīng)用現(xiàn)狀及發(fā)展趨勢(shì)[J]. 系統(tǒng)仿真學(xué)報(bào),2008, 20(1):1-6.

[5] 羅建，吳長(zhǎng)慶，李波，等.基于改進(jìn)量子微粒群的軌道導(dǎo)引小車(chē)系統(tǒng)建模與優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2011,17(2):321-328.

[6]TatsushiN，YuichiroH，IgnacioEG.Abileveldecompositionalgorithmforsimultaneousproductionschedulingandconflict-freeroutingforautomatedguidedvehicles[J].ComputersandOperationsResearch, 2011,38(5): 876-888.

[7]BakerBM,AyechewMA.Ageneticalgorithmforthevehicleroutingproblem[J].ComputersandOperationalResearch, 2003, 30(5):787-800.

[8] 韓瑞峰.遺傳算法原理與應(yīng)用實(shí)例[M].北京：兵器工業(yè)出版社，2010.

[9]GhoseiriK,GhannadpourSF.Multi-objectivevehicleroutingproblemwithtimewindowsusinggoalprogrammingandgeneticalgorithm[J].AppliedSoftComputing, 2010(10):1096-1107.

Scheduling of automated guided vehicles for material distribution based on improved genetic algorithm

LIU Xu, LOU Peihuang, QIAN Xiaoming, WU Xing

(Nanjing University of Aeronautics and Astronautics, Jiangsu Nanjing, 210016, China)

To solve multiple Automated Guided Vehicles (AGVs) scheduling problem for material distribution in hybrid flow job shop, it establishes an scheduling optimization model to minimize material handling time for AGVs of materials distribution, proposes an improved genetic algorithm for optimal solution. In the design process of algorithm, it uses integer coding to reflect directly AGV distribution routing and allocation of tasks. In order to face with illegal solutions due to the conventional crossovers and mutations, it applies best-worst route crossover and mutating method. The optimization process provides the multi-AGVs task allocation and scheduling. Finally, taking material distribution of heavy machine assembly workshop as the example, it compares this improved hybrid genetic algorithm with conventional genetic algorithm as well as branch and bound algorithm, proves the feasibility of the method.

automated guided vehicle; scheduling; mathematical optimization model; improved genetic algorithm

10.3969/j.issn.2095-509X.2015.03.004

2015-03-03

江蘇省物流自動(dòng)化裝備工程中心資助項(xiàng)目(JS-20130001/005)；江蘇省科技支撐資助項(xiàng)目 (BE2014137)

劉旭(1988—)，男，山東威海人，南京航空航天大學(xué)碩士研究生，主要研究方向?yàn)樽詣?dòng)導(dǎo)引車(chē)調(diào)度與控制。

TH24；TP278

A

2095-509X(2015)03-0016-06