孟 沖，任 彧

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

自動導(dǎo)引運(yùn)輸車(Automated Guided Vehicle，AGV)作為一種靈活高效的運(yùn)輸設(shè)備，在工廠生產(chǎn)線、立體倉庫等的應(yīng)用日益廣泛。如何使進(jìn)行合理的路徑規(guī)劃，使AGV可以安全高效的運(yùn)行，是使用AGV時(shí)必然要考慮的問題。許多研究者也做了一些深入的研究。文獻(xiàn)[1]提出了用連續(xù)規(guī)劃方法和混合整數(shù)規(guī)劃求解調(diào)度和沖突問題的混合設(shè)計(jì)方法。文獻(xiàn)[2]闡述了多AGV動態(tài)路徑規(guī)劃和無碰撞路徑規(guī)劃。在文獻(xiàn)[3]中作者為降低多AGV系統(tǒng)調(diào)度過程的復(fù)雜性，提出了混合區(qū)域控制模型，采用分布式協(xié)調(diào)控制機(jī)制和任務(wù)等待時(shí)間最短的SWT調(diào)度策略，優(yōu)化系統(tǒng)效率。文獻(xiàn)[4]基于時(shí)間窗，通過改進(jìn)Dijkstra算法來減少AGV的路徑?jīng)_突并縮短AGV的行駛時(shí)間。文獻(xiàn)[5]中提出的基于兩階段動態(tài)路徑規(guī)劃策略的啟發(fā)式算法，在多AGV的路徑規(guī)劃中有不錯(cuò)的效果，但是由于路徑復(fù)雜度的問題, 隨著節(jié)點(diǎn)數(shù)增多和任務(wù)路徑長度的增大, 會帶來實(shí)時(shí)性的問題。本文研究利用兩階段調(diào)度策略對多AGV系統(tǒng)進(jìn)行實(shí)時(shí)調(diào)度的問題。

1 多AGV調(diào)度系統(tǒng)

圖1是本文實(shí)驗(yàn)所用的車間簡圖[6]。本文為AGV設(shè)定的工作流程是將物料從物料點(diǎn)送到加工點(diǎn)進(jìn)行加工，其中101、102、103、104為物料點(diǎn)，201、202、203、204、205、206、207為加工點(diǎn)。

AGV 執(zhí)行任務(wù)可描述為:位于起始節(jié)點(diǎn)的AGV, 派發(fā)到目標(biāo)節(jié)點(diǎn)。這里不考慮任務(wù)的性質(zhì)，而是由上層的任務(wù)模塊負(fù)責(zé)管理和細(xì)化任務(wù)，這樣可以使在AGV的路徑規(guī)劃模塊中只存在單一類型的任務(wù)，便于實(shí)現(xiàn)地圖配置的通用性，實(shí)現(xiàn)上層任務(wù)對下層路徑規(guī)劃的透明。在本文的多AGV系統(tǒng)中，假設(shè)每個(gè)AGV滿足以下操作條件：(1)AGV系統(tǒng)配置的路線圖是強(qiáng)聯(lián)通的；(2)AGV的數(shù)量少于節(jié)點(diǎn)數(shù)；(3)所有AGV勻速行駛，且速度相同；(4)AGV的負(fù)載為1，即一輛AGV在同一時(shí)刻只能執(zhí)行一個(gè)任務(wù)，只有在一個(gè)任務(wù)結(jié)束之后才能接收新的任務(wù)。

圖1 車間環(huán)境

2 兩階段控制策略

兩階段控制策略，又稱兩階段交通控制方案[7]，其先離線生成候選路徑集，再根據(jù)候選路徑集進(jìn)行總體路徑規(guī)劃的分階段路徑規(guī)劃策略，總體結(jié)構(gòu)如圖2所示。

離線階段：根據(jù)車間路線圖提取節(jié)點(diǎn)坐標(biāo)和節(jié)點(diǎn)間關(guān)系，建立以節(jié)點(diǎn)距離為權(quán)值的無向圖模型。用該模型和K-最短路徑算法,生成任意兩個(gè)節(jié)點(diǎn)間的K條候補(bǔ)路徑集, 并以路徑表的形式存儲起來, 構(gòu)成路徑庫。在線階段：

(1)新任務(wù)下達(dá)時(shí)，首先檢驗(yàn)路徑庫中是否存在一條能在當(dāng)前空閑時(shí)間窗內(nèi)運(yùn)行路徑。若存在，更新時(shí)間窗。若路徑庫內(nèi)的K條路徑均不可行, 對正在執(zhí)行任務(wù)的所有AGV重新規(guī)劃路徑；

(2)監(jiān)控AGV的運(yùn)行，將AGV的運(yùn)行信息，與注冊時(shí)間窗進(jìn)行對比，若某臺AGV實(shí)際運(yùn)行情況與注冊時(shí)間窗不符，則對其重新規(guī)劃路徑，處理過程與新任務(wù)下達(dá)相同。

圖2 兩階段控制策略的總體結(jié)構(gòu)

3 路徑庫的生成

本文先通過多次調(diào)用Dijkstra算法生成任意兩個(gè)節(jié)點(diǎn)間的最短距離，再將最短距離作為從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)值,運(yùn)用到A*算法中[8]，通過多次調(diào)用A*算法生成任意兩點(diǎn)間的K條最短路徑。

由于AGV在行駛過程中，轉(zhuǎn)彎會比直線行駛消耗更多的時(shí)間和電量，在通過Dijkstra和A*算法計(jì)算路徑時(shí)，對轉(zhuǎn)彎增加懲罰因子。

根據(jù)持續(xù)時(shí)間，AGV的阻塞分為兩種情況：被正在運(yùn)行的AGV阻塞和被故障或等待任務(wù)的AGV阻塞。由于后一種情況時(shí)間較長，無法通過短暫等待解決，所以生成K條路徑后，對路徑集進(jìn)行檢測：檢測K條路徑中是否同時(shí)包括某一條(或多條) 路段。若存在，檢測該條(或多條)路段是否是必經(jīng)路段。若不是，用A*算法生成兩條路徑用來替換第K-1和第K條路徑(若K=2，只替換第K條)。重復(fù)檢查，直到生成K條符合要求的最短路徑。

生成任意兩個(gè)節(jié)點(diǎn)的K條最短路徑后，將相應(yīng)路徑信息儲存于數(shù)據(jù)庫中，路徑信息包括路徑起止節(jié)點(diǎn)、路徑、路徑索引、路徑長度，哈希值，存儲形式為Path(f,t,i,s,h)，表示從節(jié)點(diǎn)f到節(jié)點(diǎn)t的第i條最短路徑，長度為s，哈希值為h。

4 時(shí)間窗

時(shí)間窗描述了AGV對路段的占用情況，是路段、時(shí)間和AGV進(jìn)入的路段方向的集合：

Ti(section,dir,t_enter,t_exit,pre,next)

其中，section表示從一個(gè)岔路口節(jié)點(diǎn)按照一個(gè)固定方向到達(dá)相鄰岔路口節(jié)點(diǎn)所經(jīng)過的所有節(jié)點(diǎn)集合；dir∈{1,-1}表示AGV在路段上的行駛方向；t_enter和t_exit分別表示進(jìn)、出路段的時(shí)間；pre和next表示Ti的前驅(qū)和后繼時(shí)間窗。時(shí)間窗包含的AGV使用某路段的時(shí)間，稱為注冊時(shí)間，即在這個(gè)時(shí)間段，其它AGV不能以相反的方向進(jìn)入該路段，但可以在滿足安全距離Ls的前提下與該AGV同向行駛。注冊時(shí)間之間的空閑時(shí)間構(gòu)成空閑時(shí)間窗。本文通過生成時(shí)間窗來衡量不同的調(diào)度方案，并依據(jù)時(shí)間窗對AGV進(jìn)行實(shí)時(shí)調(diào)度和監(jiān)控。為了簡化問題，本文忽略了AGV在各個(gè)節(jié)點(diǎn)裝卸貨的時(shí)間。在多AGV運(yùn)行的過程中，存在3種沖突類型[9]：

(1)相向沖突：兩輛車在同一路段沿相反方向運(yùn)行。發(fā)生相向沖突時(shí)，后到達(dá)車輛在前驅(qū)路段等待，若無可?？康那膀?qū)路段，方案不可行；

(2)趕超沖突：趕超沖突是因同向運(yùn)行的AGV速度不同、前車故障停車、避讓停車或等待任務(wù)導(dǎo)致的沖突。本文研究的內(nèi)容不包括故障處理，并且設(shè)定AGV速度相等，所以趕超沖突只包括后3種情況。由避讓停車導(dǎo)致的趕超沖突時(shí)間較短，后到達(dá)的AGV按照順序等待的方式調(diào)整時(shí)間窗。由故障停車和等待任務(wù)導(dǎo)致的，則時(shí)間窗調(diào)整失?。?/p>

(3)路口沖突：兩輛AGV以垂直方向經(jīng)過路口時(shí)發(fā)生側(cè)面沖撞。路口沖突可以視作一種特殊的趕超沖突，按照趕超沖突處理。

5 基于多種群遺傳算法的在線路徑規(guī)劃

兩階段控制策略通過生成K-最短路徑庫，節(jié)省了在線搜索路徑的開銷，但也排除了大量的可行解，導(dǎo)致在線路徑規(guī)劃時(shí)，可能無法僅僅依賴路徑庫生成比較優(yōu)秀的，甚至可行的方案。而過度提高K的取值，又會增加路徑選擇的成本[10]。本文通過引入多種群遺傳算法[11]，來達(dá)到枚舉路徑庫中路徑組合和生成新路徑的作用。通過使用多種群遺傳算法：將標(biāo)準(zhǔn)遺傳算法中的一個(gè)大的種群分割成多個(gè)小的種群，用來避免早熟現(xiàn)象[12]，并提高并行性進(jìn)而提升效率。

本文所使用的多種群遺傳算法分為m個(gè)輔助種群和1個(gè)主種群，種群的進(jìn)化過程分為3個(gè)階段：第一階段，分別為m個(gè)輔助種群生成n個(gè)不同的個(gè)體；第二階段，m個(gè)輔助種群按照同樣的規(guī)則，獨(dú)立進(jìn)化，滿足條件后將最優(yōu)個(gè)體注入主種群；第三階段，當(dāng)主種群中的個(gè)體數(shù)達(dá)到n個(gè)后，主種群開始進(jìn)化，同時(shí)接收輔助種群注入的新個(gè)體來替換其最差個(gè)體，滿足結(jié)束條件，輸入結(jié)果。種群進(jìn)化設(shè)計(jì)如下：

(1)基因編碼。遺傳算法的編碼方式有很多，為了使問題更加簡單直觀，解碼操作和基因操作更為方便，本文采用直接反映AGV 配送路徑和任務(wù)分配的自然編碼方法[13]，每條染色體表示一種路徑規(guī)劃方案，由若干個(gè)AGV 配送路徑構(gòu)成；

(2)種群初始化。每個(gè)輔助種群的染色體中的路徑都來自于路徑庫：path(f,t,i,s,h)，f和t通過任務(wù)的起止節(jié)點(diǎn)確定，i隨機(jī)生成。生成完n個(gè)個(gè)體后，檢測各路徑的哈希值，如果存在重復(fù)的個(gè)體，重新生成個(gè)體進(jìn)行替換。重復(fù)上述過程組成m個(gè)輔助種群；

(3)交叉算子?；蚪徊妫前褍蓚€(gè)父體部分結(jié)構(gòu)加以替換，生成新的個(gè)體的操作。隨機(jī)選取要交叉的任務(wù)路徑，并隨機(jī)截取一段以ri、rj為首尾節(jié)點(diǎn)的路徑，在其他個(gè)體的任務(wù)路徑中尋找包括ri、rj節(jié)點(diǎn)的路徑，若存在，截取并交換，不存在，則重新選取交叉的路徑；

(5)選擇算子。為了在進(jìn)化過程中能夠準(zhǔn)確選擇優(yōu)良個(gè)體，在算法中引入精英保留策略：父代種群經(jīng)過選擇、交叉和變異操作后形成子代種群，與父代種群合并作為候選種群。計(jì)算候選種群中每個(gè)個(gè)體的適應(yīng)度,選取適應(yīng)度最高的n個(gè)個(gè)體作為下一代種群。

(6)適用度函數(shù)。 適應(yīng)度函數(shù)用于評價(jià)個(gè)體的優(yōu)劣程度。在AGV路徑規(guī)劃中，優(yōu)秀個(gè)體的衡量考慮3個(gè)方面：運(yùn)行時(shí)間、停車等待次數(shù)、轉(zhuǎn)彎次數(shù)。其中以最短運(yùn)行時(shí)間為主，同時(shí)通過增加停車懲罰因子、轉(zhuǎn)彎懲罰因子，兼顧停車和轉(zhuǎn)彎對系統(tǒng)性能的影響。適應(yīng)度函數(shù)的計(jì)算如圖3所示。

圖3 適應(yīng)度函數(shù)的計(jì)算

1)通過染色體描述的路徑信息結(jié)合各AGV的初始位置和車速，生成表示AGV對路段占用情況的時(shí)間窗；

2)比較不同路徑的各個(gè)時(shí)間窗的路段和節(jié)點(diǎn)，得到重疊時(shí)間窗集。按照重疊的路段或節(jié)點(diǎn)的不同進(jìn)行分組。對路段重疊的時(shí)間窗按照t_enter排序，對節(jié)點(diǎn)沖突的時(shí)間窗按照到達(dá)節(jié)點(diǎn)的時(shí)間排序。對每組重疊時(shí)間窗按照上文描述處理，并統(tǒng)計(jì)停車次數(shù)Cstop；

3)通過路徑對應(yīng)的最后一個(gè)時(shí)間窗的駛出路段時(shí)間得到路徑的運(yùn)行時(shí)間trunningtime；通過路徑直接獲得轉(zhuǎn)彎次數(shù)Ctrun。將運(yùn)行時(shí)間、停車次數(shù)、轉(zhuǎn)彎次數(shù)應(yīng)用到適應(yīng)度公式[14]

6 實(shí)例分析

在以上算法的基礎(chǔ)上，通過Java代碼進(jìn)行了實(shí)驗(yàn)分析。實(shí)驗(yàn)參數(shù)如表1所示。最初4輛AGV分別停在101、102、103、104共4個(gè)物料點(diǎn)等待調(diào)度，通過隨機(jī)的方式為4輛AGV派發(fā)從物料點(diǎn)到加工點(diǎn)的任務(wù)。當(dāng)AGV到達(dá)加工點(diǎn)時(shí)自動下發(fā)返回物料點(diǎn)的任務(wù)，當(dāng)AGV返回物料點(diǎn)時(shí)自動隨機(jī)下發(fā)到加工點(diǎn)的任務(wù)，按照這種方式，實(shí)驗(yàn)對算法進(jìn)行持續(xù)的測試。

表1 實(shí)驗(yàn)參數(shù)

表2 截取了部分實(shí)驗(yàn)數(shù)據(jù)。其中“++”表示需要停車等待。在t=0 s、185 s、305 s時(shí)，直接使用了路徑庫的路徑。在3 221 s和3 225 s，通過遺傳算法生成了新任務(wù)的路徑。在3 386 s，生成了AGV3的路徑并更改了AGV2的路徑。

表3是與兩種路徑規(guī)劃方案的比較數(shù)據(jù)：GA是標(biāo)準(zhǔn)的遺傳算法[15]，因?yàn)閮烧呙看蔚?guī)模不同，比較迭代次數(shù)缺少意義，而MPGA和GA中計(jì)算適應(yīng)度耗時(shí)最多，所以比較了兩者每次被調(diào)用時(shí)計(jì)算適應(yīng)度的次數(shù)。

圖4和圖5是在MPGA算法運(yùn)行過程中總的運(yùn)行時(shí)間、停車次數(shù)、轉(zhuǎn)彎次數(shù)的變化。

表2 任務(wù)路線

圖4 迭代過程中AGV總運(yùn)行時(shí)間的變化(MPGA)

圖5 迭代過程中總停車次數(shù)和轉(zhuǎn)彎次數(shù)的變化(MPGA)

方案運(yùn)行時(shí)間停車次數(shù)轉(zhuǎn)彎次數(shù)適應(yīng)度計(jì)算次數(shù)MPGA636.230.256.25258.19GA672.150.396.71237.32other713.620.937.41-

7 結(jié)束語

本文主要研究了多AGV調(diào)度系統(tǒng)的路徑規(guī)劃問題。通過將多種群遺傳算法引入到兩階段控制策略中，減少了在線路徑搜索帶來的運(yùn)算負(fù)擔(dān)，有效提高了系統(tǒng)效率和適用性，可以有效解決目前多AGV系統(tǒng)路徑規(guī)劃不靈活、容易出現(xiàn)沖突的問題。通過仿真測試，驗(yàn)證了本文提出的策略能夠比較快速地規(guī)劃出全局較優(yōu)的路徑，為實(shí)際系統(tǒng)應(yīng)用提供了參考。