□ 齊 權(quán)，張新敏

(沈陽(yáng)工業(yè)大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽(yáng) 110870)

1 引言

隨著物流技術(shù)的廣泛應(yīng)用，自動(dòng)導(dǎo)引車(chē)(AGV)已經(jīng)被越來(lái)越多地應(yīng)用于柔性制造系統(tǒng)(FMS)中。AGV路徑規(guī)劃是多AGV系統(tǒng)設(shè)計(jì)的關(guān)鍵問(wèn)題之一，分配好配送任務(wù)之后，規(guī)劃出一條路徑，使AGV從起點(diǎn)無(wú)碰撞地到達(dá)終點(diǎn)并返回車(chē)場(chǎng)，且用時(shí)最短，路徑規(guī)劃的好壞直接影響物流系統(tǒng)的效率。自從AGV的路徑規(guī)劃問(wèn)題由Maxwell和Muekstady提出以來(lái)[1]，國(guó)內(nèi)外學(xué)者對(duì)多AGV系統(tǒng)路徑規(guī)劃問(wèn)題做了許多研究，Carl Adam Petr提出了Petri網(wǎng)理論，并利用該理論解決AGV路徑規(guī)劃問(wèn)題，該理論在AGV路徑規(guī)劃問(wèn)題中被廣泛應(yīng)用[2]；Reza選擇遺傳算法和禁忌搜索算法解決AGV路徑問(wèn)題；吉林大學(xué)的吳曉雨用基于優(yōu)先級(jí)的交通規(guī)則法解決沖突問(wèn)題[3]；廣東工業(yè)大學(xué)的李青欣設(shè)計(jì)不同類(lèi)型的遺傳算法來(lái)解決AGV在不同環(huán)境下的路徑規(guī)劃問(wèn)題[4]；Cai運(yùn)用遺傳算法原理給出了一種基于定長(zhǎng)十進(jìn)編碼方法的多個(gè)移動(dòng)機(jī)器人路徑規(guī)劃[5]。謝輝輝和鐘建琳等人對(duì)A*算法的論述中，介紹了A*算法中可以選取的常用啟發(fā)式函數(shù)[7-8]。研究工作對(duì)柔性生產(chǎn)環(huán)境多AGV路徑規(guī)劃問(wèn)題進(jìn)行了深入研究，在建立多AGV路徑優(yōu)化數(shù)學(xué)模型的基礎(chǔ)上，提出了一種改進(jìn)的克隆選擇算法進(jìn)行求解，并運(yùn)用離線-在線兩階段式控制策略解決AGV路徑空間沖突問(wèn)題。最后針對(duì)具體實(shí)例，給出了物料配送路徑的優(yōu)化結(jié)果，證明了所提方法的有效性和可行性。

2 問(wèn)題描述

在某柔性生產(chǎn)車(chē)間中，有多個(gè)AGV負(fù)責(zé)物料搬運(yùn)工作。AGV的任務(wù)是接受系統(tǒng)的調(diào)度，在不同站點(diǎn)之間以規(guī)劃好的路徑運(yùn)送物料，以完成對(duì)物料的搬運(yùn)。為更好的探討AGV作業(yè)調(diào)度問(wèn)題的本質(zhì)，對(duì)AGV工作做如下約束：

①AGV的數(shù)量、AGV的所要完成的物料搬運(yùn)任務(wù)是固定的；

②AGV運(yùn)行路徑可穩(wěn)定規(guī)劃且不沖突；

③AGV的運(yùn)行速度已知且恒定，AGV在路徑中的行駛時(shí)間與路徑長(zhǎng)度成正比；

④AGV完成運(yùn)輸任務(wù)后，返回車(chē)場(chǎng)；

⑤在同一路徑中，兩輛AGV不可相向行駛，并且以逆向行駛的方向超越對(duì)方。

3 優(yōu)化模型的建立

對(duì)于傳統(tǒng)的車(chē)輛路徑問(wèn)題，實(shí)際應(yīng)用中可以選擇的目標(biāo)函數(shù)主要包括物流配送成本最少、配送車(chē)輛行駛總路程最短、使用的車(chē)輛數(shù)最少、配送的準(zhǔn)時(shí)性最高等幾個(gè)目標(biāo)，大多數(shù)車(chē)輛路徑問(wèn)題都是單目標(biāo)問(wèn)題。

針對(duì)執(zhí)行運(yùn)輸任務(wù)的AGV來(lái)說(shuō)，執(zhí)行配送任務(wù)的AGV總行駛路程最低是為了節(jié)省車(chē)間內(nèi)寶貴的運(yùn)輸路徑資源。減少AGV與AGV在路徑中迎面相遇的次數(shù)，可以減少AGV與AGV在避障的過(guò)程中由于自身性能的缺陷導(dǎo)致死鎖現(xiàn)象的出現(xiàn)。此外，由于AGV在轉(zhuǎn)彎過(guò)程中行駛較慢，因此要盡量減少AGV在路徑中轉(zhuǎn)彎的次數(shù)，在規(guī)劃階段即需要規(guī)劃合理路線，以徑直的行駛路線代替轉(zhuǎn)彎的規(guī)劃路線。

綜上，所研究問(wèn)題為多目標(biāo)優(yōu)化問(wèn)題，因此，目標(biāo)函數(shù)的確定需要綜合考慮多種因素對(duì)配送工作的影響，并將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，構(gòu)建目標(biāo)函數(shù)的表達(dá)式如下：

(1)

式中，m表示規(guī)劃的AGV的數(shù)量，Si表示編號(hào)為i的AGV在路徑中行駛的距離，Ri表示編號(hào)為i的AGV在路徑中轉(zhuǎn)彎的次數(shù)，Ta表示AGV在路徑中以相反方向行駛并相遇的次數(shù)，Cs表示路徑長(zhǎng)度的時(shí)間成本系數(shù)，Cr表示由于AGV轉(zhuǎn)彎路程的時(shí)間成本系數(shù)。

為方便研究工作的進(jìn)行，設(shè)置如下決策變量：

Xijkp表示完成編號(hào)為i任務(wù)過(guò)程中，編號(hào)為p的AGV由節(jié)點(diǎn)j向節(jié)點(diǎn)k行駛的次數(shù)。Yij表示任務(wù)i由于編號(hào)為j的AGV完成，Soijk表示實(shí)時(shí)狀態(tài)下，編號(hào)為i的AGV從j向k已行駛的路徑長(zhǎng)度。

模型受到如下條件約束：

①每個(gè)運(yùn)輸任務(wù)由一臺(tái)AGV完成，其中m表示模型中AGV的數(shù)量。

(2)

②AGV完成運(yùn)輸任務(wù)之后返回車(chē)場(chǎng)，其中Bp表示，編號(hào)為p的AGV車(chē)場(chǎng)所在節(jié)點(diǎn)編號(hào)。

XijBpp>1

(3)

③路徑只能容納一臺(tái)AGV行駛，AGV在路徑中與其他AGV相遇，其中一臺(tái)改變行駛方向，djk能表示節(jié)點(diǎn)j、k之間的空間距離。

Soijk+Soukj

(4)

4 基于改進(jìn)克隆選擇算法的多AGV路徑規(guī)劃

4.1 抗體編碼設(shè)計(jì)

克隆選擇算法有很多種編碼方式，編碼不但決定了抗體內(nèi)數(shù)字的排列形式，還決定了從抗體數(shù)字變換到解空間的解碼方法，同時(shí)也影響到變異算子、克隆算子等操作，合適的編碼方法能夠讓算子運(yùn)算的操作見(jiàn)到實(shí)現(xiàn)和執(zhí)行。在抗體中，以十進(jìn)制自然數(shù)表達(dá)AGV對(duì)于路徑的選擇。以數(shù)字串表示AGV從出發(fā)點(diǎn)到目的地的一條完整路徑，每個(gè)數(shù)字表達(dá)AGV的路徑選擇決策。例如圖1所示，當(dāng)AGV運(yùn)行到黑色節(jié)點(diǎn)時(shí)，編碼1、2、3、4分別代表規(guī)劃路徑中的后繼節(jié)點(diǎn)分別為1、4、7、8。

圖1 抗體基因編碼解碼示意圖

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

基于改進(jìn)克隆算法求解AGV路徑規(guī)劃的過(guò)程中，需要根據(jù)抗體解的質(zhì)量進(jìn)行排序，選取解質(zhì)量較優(yōu)秀的抗體進(jìn)行克隆，在對(duì)克隆抗體執(zhí)行變異操作的基礎(chǔ)上，選取解質(zhì)量最優(yōu)的變異抗體替代原抗體。

解的評(píng)價(jià)方法一般是根據(jù)目標(biāo)函數(shù)設(shè)計(jì)適應(yīng)度函數(shù)，研究工作考慮路徑長(zhǎng)度、AGV在路徑中相遇的可能性、路徑的光滑程度3個(gè)因素，采取加權(quán)的方式先建立目標(biāo)函數(shù)，再轉(zhuǎn)化為適應(yīng)度函數(shù)。其中，路徑長(zhǎng)度與AGV完成任務(wù)的時(shí)間有關(guān)，長(zhǎng)度越短AGV運(yùn)行時(shí)間越少；如果AGV在路徑中與其他AGV相遇，可能由于AGV爭(zhēng)奪運(yùn)輸空間導(dǎo)致死鎖現(xiàn)象的發(fā)生，延誤物料運(yùn)輸任務(wù)的進(jìn)行；路徑的光滑程度也與運(yùn)輸時(shí)間有關(guān)，AGV轉(zhuǎn)彎時(shí)速度需要減小，若優(yōu)化路徑時(shí)不考慮AGV的轉(zhuǎn)彎問(wèn)題，則規(guī)劃出的最優(yōu)路徑不一定能使AGV以最快最安全的狀態(tài)到達(dá)目標(biāo)點(diǎn)，且轉(zhuǎn)彎處的加減速能耗隨之增加，為此AGV的轉(zhuǎn)彎因素也是研究工作考慮的因素。

設(shè)計(jì)如式(5)所示的適應(yīng)度函數(shù)，用于迭代過(guò)程中評(píng)估抗體的優(yōu)劣，f1、f2和f3越小，表示路徑長(zhǎng)度越短、AGV在路徑中相遇的概率越低和路徑越平滑，實(shí)際應(yīng)用中根據(jù)f1、f2和f3的重要程度選擇合適的α、β和γ。

Fit=N-αf1-βf2-γf3

(5)

式中：N為足夠大的正數(shù)，F(xiàn)it為適應(yīng)度函數(shù)，α、β和γ分別是f1、f2和f3的權(quán)重系數(shù)。

4.3 兩階段式控制策略

兩階段控制策略，又稱(chēng)兩階段交通控制方案[6]，是將多AGV系統(tǒng)的控制系統(tǒng)分為兩個(gè)模塊：離線路徑規(guī)劃模塊和在線交通控制模塊。兩個(gè)模塊分別對(duì)AGV進(jìn)行離線式任務(wù)調(diào)度和在線式任務(wù)調(diào)度。

在離線式任務(wù)調(diào)度中，所有的運(yùn)輸需求都是已知的。所有AGV的行駛路徑在出發(fā)之前得以?xún)?yōu)化。但是一個(gè)小的改變例如：任務(wù)延遲、道路擁堵、車(chē)輛故障或物料不足等可以使整個(gè)調(diào)度計(jì)劃難以繼續(xù)執(zhí)行。多AGV系統(tǒng)必須能夠合理應(yīng)對(duì)各種不確定因素引起的變化，當(dāng)AGV所在的環(huán)境發(fā)生變化后，在線交通控制模塊根據(jù)工作的AGV信息，生成無(wú)碰撞的AGV運(yùn)行路徑。

4.4 改進(jìn)克隆選擇算法流程

為解決多AGV系統(tǒng)的路徑優(yōu)化問(wèn)題，設(shè)計(jì)了改進(jìn)克隆選擇算法對(duì)路徑進(jìn)行規(guī)劃設(shè)計(jì)。

4.4.1 種群初始化

對(duì)于算法的進(jìn)化和收斂效果，結(jié)構(gòu)優(yōu)良的初始種群非常重要，隨機(jī)生成一組長(zhǎng)度為n的整數(shù)數(shù)組，表達(dá)抗體的路徑選擇策略，整數(shù)的取值范圍介于1和與圖的度(即圖中單個(gè)節(jié)點(diǎn)的最大連接數(shù))之間，數(shù)組長(zhǎng)度取決于圖的復(fù)雜程度。初始種群創(chuàng)建的步驟如下：

步驟1，根據(jù)系統(tǒng)中需要調(diào)度的AGV數(shù)量，確定個(gè)體支線數(shù)目M；根據(jù)圖中度確定抗體基因取值范圍[1，N]。

步驟2，用創(chuàng)建任意離散隨機(jī)種群的方法對(duì)個(gè)體每個(gè)基因生成一個(gè)隨機(jī)數(shù)ri，抗體的基因數(shù)n=M×節(jié)點(diǎn)數(shù)。

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

4.4.2 解碼

根據(jù)4.1中所述的解碼規(guī)則，對(duì)抗體基因進(jìn)行解碼，轉(zhuǎn)碼為AGV的規(guī)劃運(yùn)行路線。

4.4.3 抗體適應(yīng)度評(píng)價(jià)

抗體適應(yīng)度評(píng)價(jià)的目的是選取解的質(zhì)量較為優(yōu)秀的抗體進(jìn)行克隆，并選擇解質(zhì)量?jī)?yōu)秀的抗體代替原有抗體，增強(qiáng)算法的收斂性，抗體的適應(yīng)度評(píng)價(jià)依據(jù)4.2設(shè)計(jì)的抗體適應(yīng)度函數(shù)評(píng)價(jià)公式進(jìn)行。

4.4.4 克隆操作

對(duì)于適應(yīng)度較高的抗體，克隆規(guī)模越大；反之適應(yīng)度越低，則克隆出的個(gè)體越少?？寺〔僮髂苡行U(kuò)大搜索范圍。實(shí)現(xiàn)了個(gè)體的高適應(yīng)度的要求，并且有助于避免種群過(guò)早收斂和陷入局部最優(yōu)?？贵w克隆規(guī)模為：

(6)

其中，α為克隆系數(shù)，f(i)為抗體適應(yīng)度，ceil()表示向上取整。式(6)表示克隆個(gè)數(shù)與抗體適應(yīng)度成正比。

4.4.5 變異操作

變異操作可以實(shí)現(xiàn)種群的多樣性，搜索到更優(yōu)秀的抗體。當(dāng)克隆增殖操作之后，對(duì)產(chǎn)生的個(gè)體獨(dú)立地進(jìn)行變異操作。采用基因突變算子，根據(jù)設(shè)定好的變異概率Pm，對(duì)克隆抗體種群中的一個(gè)或幾個(gè)基因進(jìn)行變異操作，變異的形式為，抗體基因片段整數(shù)的修改。

4.4.6 選擇替代操作

從克隆抗體中選出適應(yīng)度較好的抗體，使它按一定規(guī)則保留，替代原抗體，提高收斂速度和計(jì)算效率。組成子種群，代替對(duì)應(yīng)的原抗體。在研究工作中，為保留抗體基因多樣性，同源克隆抗體只保留一個(gè)抗體。為增強(qiáng)算法的收斂性，選擇出的抗體將原抗體集合中適應(yīng)度較低的抗體替代，保留原抗體集合中適應(yīng)度較好的抗體，為此修改原抗體集合與克隆抗體集合的映射關(guān)系，抗體的替代操作依據(jù)重新建立的抗體映射關(guān)系進(jìn)行替代操作。

圖2 抗體集合映射的修改

4.4.7 終止判斷

如果算法迭代一定次數(shù)之后，適應(yīng)度最優(yōu)i的抗體適應(yīng)值不發(fā)生改變，或者達(dá)到最高迭代次數(shù)，算法終止運(yùn)行，否則返回步驟(2)。

5 實(shí)例分析

為驗(yàn)證改進(jìn)克隆選擇算法的有效性，以某柔性生產(chǎn)車(chē)間為例，以實(shí)際應(yīng)用的場(chǎng)地布局為參照，設(shè)計(jì)了一組模擬實(shí)驗(yàn)。以圖3所示的車(chē)間為例，車(chē)間內(nèi)有3臺(tái)AGV，在柔性車(chē)間中存在3個(gè)加工區(qū)，在圖中位置分別為結(jié)點(diǎn)10、結(jié)點(diǎn)22和結(jié)點(diǎn)23，還有2個(gè)倉(cāng)庫(kù)，在圖中位置為結(jié)點(diǎn)4和結(jié)點(diǎn)5，AGV的車(chē)場(chǎng)位置為結(jié)點(diǎn)9，由AGV將倉(cāng)庫(kù)內(nèi)的物料運(yùn)送至加工區(qū)。模型中AGV穿越路徑的時(shí)間與長(zhǎng)度成正比，在結(jié)點(diǎn)處轉(zhuǎn)彎的時(shí)間取定值。

圖3 車(chē)間平面示意圖

通過(guò)Matlab進(jìn)行實(shí)驗(yàn)仿真，使用傳統(tǒng)遺傳算法、經(jīng)典克隆選擇算法和所設(shè)計(jì)的改進(jìn)克隆選擇算法對(duì)多AGV路徑規(guī)劃模型進(jìn)行求解，得出AGV完成配送任務(wù)的總時(shí)間，參數(shù)設(shè)置如下：

種群大?。?0；

克隆因子：0.3；

抗體變異因子：0.2；

最大迭代次數(shù)：90。

解的列表分別表示采用遺傳算法和改進(jìn)克隆選擇算法進(jìn)行任務(wù)調(diào)度和路徑規(guī)劃后AGV完成配送任務(wù)的總時(shí)間、AGV在路徑中相遇的次數(shù)。

由表1可看出，當(dāng)任務(wù)數(shù)小于等于19時(shí)，兩種算法都能得到相同的最優(yōu)解；但是隨著任務(wù)數(shù)的增加，當(dāng)任務(wù)數(shù)等于20時(shí)，相對(duì)于改進(jìn)克隆算法，遺傳算法的AGV相遇概率更大；當(dāng)任務(wù)數(shù)增加到21時(shí)，改進(jìn)克隆選擇算法的物料配送時(shí)間小于遺傳算法的物料配送時(shí)間。這說(shuō)明改進(jìn)克隆選擇算法具有優(yōu)秀的魯棒性，可以跳出局部最優(yōu)。

表1 算法運(yùn)行結(jié)果對(duì)比

圖4顯示了克隆選擇算法與改進(jìn)克隆選擇算法的收斂曲線，根據(jù)曲線可以看出，克隆選擇算法與改進(jìn)克隆選擇算法都可以收斂得到可靠解，而克隆選擇算法收斂較慢，改進(jìn)克隆選擇算法魯棒性較強(qiáng)，收斂速度較快，經(jīng)典克隆選擇算法與改進(jìn)克隆選擇算法都可以得到路徑優(yōu)化問(wèn)題的最優(yōu)解。

圖4 仿真結(jié)果

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

研究工作以柔性生產(chǎn)車(chē)間的多AGV路徑優(yōu)化問(wèn)題作為研究對(duì)象，分析了對(duì)AGV運(yùn)輸時(shí)間構(gòu)成影響的因素，并建立了數(shù)學(xué)模型，提出了兩階段策略，解決AGV在路徑中的沖突問(wèn)題，為解決問(wèn)題，提出了改進(jìn)克隆選擇算法，為驗(yàn)證算法的有效性和優(yōu)越性，利用編程軟件完成了模擬試驗(yàn)，實(shí)驗(yàn)結(jié)果證明，改進(jìn)克隆選擇算法相對(duì)于經(jīng)典克隆選擇算法的求解質(zhì)量相同，但求解速度大大加快，可以更少的迭代次數(shù)得到最優(yōu)解，收斂性能大大提高。