基于改進克隆選擇算法的多AGV路徑規(guī)劃研究

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

(沈陽工業(yè)大學 機械工程學院，遼寧 沈陽 110870)

1 引言

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

2 問題描述

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

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

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

③AGV的運行速度已知且恒定，AGV在路徑中的行駛時間與路徑長度成正比；

④AGV完成運輸任務(wù)后，返回車場；

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

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

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

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

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

(1)

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

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

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

模型受到如下條件約束：

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

(2)

②AGV完成運輸任務(wù)之后返回車場，其中Bp表示，編號為p的AGV車場所在節(jié)點編號。

XijBpp>1

(3)

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

Soijk+Soukj

(4)

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

4.1 抗體編碼設(shè)計

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

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

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

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

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

設(shè)計如式(5)所示的適應(yīng)度函數(shù)，用于迭代過程中評估抗體的優(yōu)劣，f1、f2和f3越小，表示路徑長度越短、AGV在路徑中相遇的概率越低和路徑越平滑，實際應(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 兩階段式控制策略

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

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

4.4 改進克隆選擇算法流程

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

4.4.1 種群初始化

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

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

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

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

4.4.2 解碼

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

4.4.3 抗體適應(yīng)度評價

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

4.4.4 克隆操作

對于適應(yīng)度較高的抗體，克隆規(guī)模越大；反之適應(yīng)度越低，則克隆出的個體越少。克隆操作能有效擴大搜索范圍。實現(xiàn)了個體的高適應(yīng)度的要求，并且有助于避免種群過早收斂和陷入局部最優(yōu)?？贵w克隆規(guī)模為：

(6)

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

4.4.5 變異操作

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

4.4.6 選擇替代操作

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

圖2 抗體集合映射的修改

4.4.7 終止判斷

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

5 實例分析

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

圖3 車間平面示意圖

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

種群大?。?0；

克隆因子：0.3；

抗體變異因子：0.2；

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

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

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

表1 算法運行結(jié)果對比

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

圖4 仿真結(jié)果

6 結(jié)束語

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