基于WebGL的多AGV物流調(diào)度仿真系統(tǒng)的研究與應(yīng)用

榮 燕，李 棟，曹先慶

(1.沈陽化工大學(xué) 信息工程學(xué)院，沈陽 110142；2.中國科學(xué)院 網(wǎng)絡(luò)化控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，沈陽 110016；3.中國科學(xué)院 沈陽自動(dòng)化所，沈陽 110016；4.中國科學(xué)院 機(jī)器人與智能制造創(chuàng)新研究院，沈陽 110169)

0 引言

目前生產(chǎn)型企業(yè)的數(shù)量眾多，每天都需要重復(fù)性搬運(yùn)物料和產(chǎn)品，耗時(shí)又耗力，尤其是當(dāng)比較忙碌時(shí)，還容易出現(xiàn)送料錯(cuò)誤的情況，這些問題導(dǎo)致了工廠工作效率低下，而且浪費(fèi)了大量的人力成本。AGV(automated guided vehicle)小車的出現(xiàn)，可以輕松解決這個(gè)問題。AGV不僅加速了生產(chǎn)進(jìn)度和效率，還可以節(jié)省大量的人力成本，有效地減少了送錯(cuò)料混料的情況。針對(duì)多AGV任務(wù)調(diào)度的仿真研究，很多研究考慮了多AGV執(zhí)行任務(wù)時(shí)影響任務(wù)效率的因素。如AGV的電池電量、AGV執(zhí)行任務(wù)時(shí)的路徑規(guī)劃、AGV數(shù)量配置等。文獻(xiàn)[1]考慮了AGV的充電策略，設(shè)計(jì)出4種充電方式，得出合理的充電方式可以提高AGV的工作效率。文獻(xiàn)[2]在集裝箱碼頭作業(yè)過程中將電池電量的問題考慮在內(nèi)，并基于Q學(xué)習(xí)算法建立出多AGV動(dòng)態(tài)調(diào)度模型：AGV在集裝箱碼頭作業(yè)時(shí)，執(zhí)行完一個(gè)任務(wù)時(shí)，可以動(dòng)態(tài)選擇下一個(gè)任務(wù)。文獻(xiàn)[3]針對(duì)AGV路徑優(yōu)化，闡述了一種新的方法-改進(jìn)人工勢(shì)場(chǎng)法，解決了傳統(tǒng)人工勢(shì)場(chǎng)法中存在的局部極小值問題。文獻(xiàn)[4]提出了用時(shí)間窗模型解決AGV路徑問題，能夠有效提高系統(tǒng)效率并且有良好的適應(yīng)性。文獻(xiàn)[5]以AGV完成任務(wù)的時(shí)間最短為目標(biāo)，建立了同步和異步兩種挑選模式下AGV的任務(wù)調(diào)度模型，最終驗(yàn)證了能夠有效將解決AGV調(diào)度問題。文獻(xiàn)[6]提出了路徑優(yōu)化速度較快的混合蟻群粒子群方法，提高了AGV運(yùn)行效率。文獻(xiàn)[7]研究了具有電池約束的AGV任務(wù)調(diào)度，以運(yùn)輸請(qǐng)求的延遲成本和AGV旅行成本的加權(quán)和最小為目標(biāo)，將充電和運(yùn)輸請(qǐng)求分配給AGV。文獻(xiàn)[8]主要研究了一種新型的多品種小批量生產(chǎn)的矩陣式制造車間中的自動(dòng)引導(dǎo)車輛調(diào)度問題。該問題的目的是確定一種解決方案，使客戶滿意度最大化，同時(shí)使分銷成本最小化。為此，建設(shè)一個(gè)多目標(biāo)混合整數(shù)線性規(guī)劃的模型。此外也有很多研究路徑?jīng)_突的文獻(xiàn)，文獻(xiàn)[9]針對(duì)傳統(tǒng)時(shí)間窗法的局限性，提出了更好的多AGV路徑?jīng)_突檢測(cè)方法-基因測(cè)序算法。文獻(xiàn)[10]針對(duì)AGV的沖突問題，提出模糊控制方法來優(yōu)化AGV路徑，證明了此方法可以有效提高運(yùn)輸效率。文獻(xiàn)[11]提出的基于沖突搜索的多AGV路徑算法最終驗(yàn)證能夠有效解決路徑?jīng)_突問題。文獻(xiàn)[12]針對(duì)自動(dòng)化碼頭動(dòng)態(tài)作業(yè)環(huán)境中多自動(dòng)引導(dǎo)車的路徑規(guī)劃問題，建立了AGV完成任務(wù)時(shí)間最小和路徑無沖突的兩階段模型，可以有效解決多AGV動(dòng)態(tài)沖突的規(guī)避。由上可見，大多數(shù)文獻(xiàn)研究了AGV任務(wù)調(diào)度系統(tǒng)的算法、路徑規(guī)劃的算法和AGV充電策略，在任務(wù)調(diào)度系統(tǒng)中，很少有在研究的同時(shí)把AGV充電問題和執(zhí)行任務(wù)時(shí)的路徑規(guī)劃問題考慮在內(nèi)，因此將AGV電池電量和路徑規(guī)劃問題同時(shí)作為約束條件，研究適配K公司汽車總裝生產(chǎn)線的實(shí)際場(chǎng)景需求是很有必要的，并利用webgl技術(shù)實(shí)現(xiàn)了三維AVG虛擬仿真[13-15]。

1 需求分析

AGV是目前最受歡迎的自動(dòng)化搬運(yùn)設(shè)備，是實(shí)現(xiàn)智能物流的關(guān)鍵環(huán)節(jié)，從我國的AGV需求分析得知，AGV的應(yīng)用比較集中，主要分布在汽車工業(yè)和家電制造行業(yè)。AGV越來越受歡迎的原因有很多，首先AGV小車不需要人工駕駛，只需要在AGV的中央控制系統(tǒng)的控制下即可自動(dòng)接收和執(zhí)行搬運(yùn)任務(wù)，將需要搬運(yùn)的東西自動(dòng)搬運(yùn)到指定的地點(diǎn)，真正意義上實(shí)現(xiàn)了整個(gè)生產(chǎn)過程中無人化、自動(dòng)化地運(yùn)送產(chǎn)品，大大提高了企業(yè)生產(chǎn)線的物流效率。其次，如今很多的企業(yè)都存在招工難的現(xiàn)象，人工成本在不斷上升，因此很多企業(yè)都在向自動(dòng)化模式轉(zhuǎn)變，而AGV正好是可以代替普通工人的一種自動(dòng)化搬運(yùn)設(shè)備，降低成本，實(shí)現(xiàn)物流自動(dòng)化，靈活性和準(zhǔn)確性也都挺好，因而備受自動(dòng)化制造業(yè)的歡迎。此外，智能制造時(shí)代的3C大批量定制，生產(chǎn)的周期也明顯縮短，那么對(duì)于物流的速度也要求更高，因此企業(yè)對(duì)AGV小車的需求也會(huì)更加迫切[16-17]。

在AGV實(shí)際應(yīng)用中，還存在著很多需要解決的問題：

1)為了提高多AGV調(diào)度系統(tǒng)的效率，很多研究提出改進(jìn)算法來解決路徑優(yōu)化問題，卻很少有學(xué)者研究小車充電對(duì)調(diào)度系統(tǒng)的影響，AGV和電動(dòng)汽車相似，充電所需時(shí)間都比較長，因此根據(jù)AGV電量安排任務(wù)就尤為重要。將AGV充電需求考慮到調(diào)度系統(tǒng)中是比較復(fù)雜的，AGV每完成一次運(yùn)輸任務(wù)，都需要計(jì)算出小車此時(shí)剩余的電量，那么就需要知道小車行駛距離和所剩電量二者之間的關(guān)系，根據(jù)行駛距離計(jì)算出所剩電量，然后根據(jù)電量合理劃分AGV充電區(qū)間，從而判斷此AGV下一步是執(zhí)行新的任務(wù)還是行駛到充點(diǎn)電充電[18-19]。

2)當(dāng)越來越多的AGV被同時(shí)安排到倉庫里工作時(shí)，避免AGV之間相互碰撞也成了研究的重點(diǎn)，目前大多數(shù)文獻(xiàn)研究路徑?jīng)_突檢測(cè)的方法是時(shí)間窗法，但是時(shí)間窗法有一定的局限性，當(dāng)AGV行駛的距離遠(yuǎn)，經(jīng)過的路徑節(jié)點(diǎn)多，那存儲(chǔ)節(jié)點(diǎn)的時(shí)間窗就需要占據(jù)更大的內(nèi)存，那么沖突檢測(cè)的效率會(huì)降低，所以為了提高路徑?jīng)_突檢測(cè)的效率，本次研究利用基因測(cè)序算法來預(yù)測(cè)多AGV之間的路徑?jīng)_突問題，但是由于基因比對(duì)和AGV路徑問題的環(huán)境是不一樣的，因此在環(huán)境建立方面有難度，不能完全復(fù)制到路徑?jīng)_突檢測(cè)當(dāng)中[20-21]。

3)將充電需求和路徑規(guī)劃分別考慮到調(diào)度系統(tǒng)之后，最重要的是還需要將二者結(jié)合起來同時(shí)考慮到調(diào)度系統(tǒng)中，以最小路徑為目標(biāo)，建立多AGV模型也是一大難點(diǎn)。綜上分析，本次研究以AGV充電需求算法、路徑規(guī)劃算法、調(diào)度系統(tǒng)模型為重點(diǎn)，分析了多AGV調(diào)度系統(tǒng)中問題的解決方法[22]。

2 AGV充電需求算法分析

在物流運(yùn)輸行業(yè)，安全可靠的無人AGV廣泛應(yīng)用于工廠加工系統(tǒng)，具有低噪音、低污染、智能程控、高效搬運(yùn)等諸多優(yōu)點(diǎn)。驅(qū)動(dòng)結(jié)構(gòu)是AGV的重要組成部分，目前大多采用電池供電作為運(yùn)行動(dòng)力源。那么多AGV調(diào)度系統(tǒng)中電池的供電、放電和充電就顯得尤為重要。本文主要研究調(diào)度系統(tǒng)中AGV的充電問題，以K公司汽車生產(chǎn)總裝生產(chǎn)線為背景，共有十一輛AGV小車。小車負(fù)責(zé)把不同的汽車零件運(yùn)送到終點(diǎn)進(jìn)行組裝，執(zhí)行完任務(wù)后回到原點(diǎn)。當(dāng)AGV一直處于工作狀態(tài)，不停的在運(yùn)輸物料，AGV的電量就會(huì)處于直線下降的狀態(tài)，當(dāng)AGV的電量不能夠完成系統(tǒng)分配的運(yùn)輸物料任務(wù)時(shí)，此時(shí)AGV就要進(jìn)入設(shè)定的充點(diǎn)電進(jìn)行充電。等小車電量足夠時(shí)，就停止充電，以保證運(yùn)輸任務(wù)的正常進(jìn)行，從而減少任務(wù)等待的時(shí)間，提高AGV任務(wù)調(diào)度的效率。當(dāng)AGV在完成運(yùn)輸任務(wù)時(shí)，存在兩種狀態(tài)，一種是空載，另一種是重載，AGV同樣的速度下，重載時(shí)的輸出功率是要大于空載時(shí)的，相同的距離重載和空載的耗電量也有所不同，傅正堂等人提出了AGV電量消耗和距離的關(guān)系[23]。

根據(jù)圖1得出，AGV消耗的電量和路程的關(guān)系可以用一元二次函數(shù)描述，AGV的電量記為x，AGV行駛的距離記為R，二者關(guān)系記為：R(x)=Ax2 +Bx+C，因此根據(jù)AGV行駛的距離就可以知道小車所剩的電量。然后將AGV的電量分為3個(gè)區(qū)間：x1設(shè)為AGV從起點(diǎn)到終點(diǎn)最短距離所對(duì)應(yīng)的電量，x2設(shè)為AGV能夠從起點(diǎn)到達(dá)終點(diǎn)，再從終點(diǎn)到起點(diǎn)所行駛的總路程所對(duì)應(yīng)的電量。

圖1 AGV電量消耗圖

1)低電量區(qū)間：[0 ～x1)，當(dāng)AGV電量在這個(gè)區(qū)間時(shí)，說明AGV已經(jīng)不能從起點(diǎn)到達(dá)終點(diǎn)了，此時(shí)AGV必須駛?cè)氤潆婞c(diǎn)進(jìn)行充電。

2)中電量區(qū)間：[x1 ～x2)，當(dāng)AGV電量處于此區(qū)間時(shí)，AGV可以執(zhí)行任務(wù)，但是在執(zhí)行任務(wù)之前，需要考慮任務(wù)距離的遠(yuǎn)近，執(zhí)行太遠(yuǎn)的任務(wù)中途可能會(huì)電量不足，從而導(dǎo)致小車停在半路，造成擁堵。所以在此區(qū)間的AGV盡量執(zhí)行距離較近的任務(wù)。

3)高電量區(qū)間：[x2 ～ 1)，當(dāng)AGV電量處于高電量區(qū)間時(shí)，可以執(zhí)行任何一個(gè)任務(wù)。

通過劃分AGV的電量區(qū)間，可以更加合理的給小車安排任務(wù)，提高系統(tǒng)調(diào)度的效率。小車執(zhí)行任務(wù)的流程如圖2所示。

圖2 AGV充電需求分析

3 AGV路徑規(guī)劃

3.1 AGV最短路徑算法

在AGV路徑規(guī)劃的研究中，都以AGV路徑最短為目標(biāo)，完成這個(gè)目標(biāo)一般使用的是A*算法。A*算法的公式表示為：

f(n)=g(n)+h(n)

在研究AGV路徑規(guī)劃問題時(shí)，f(n)表示AGV從初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)n再到目標(biāo)節(jié)點(diǎn)的最小行駛距離，g(n)表示從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小距離，h(n)表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的路徑的最小行駛距離，也稱為A*算法的啟發(fā)函數(shù)。如果啟發(fā)函數(shù)h(n)一直為零的話，此時(shí)就由g(n)決定路徑節(jié)點(diǎn)的優(yōu)先級(jí)。如果h(n)始終小于等于節(jié)點(diǎn)n到終點(diǎn)的距離，那么A*算法一定能夠?yàn)锳GV找到最短路徑，但是當(dāng)h(n)的值越小，算法將遍歷更多的路徑節(jié)點(diǎn)，從而導(dǎo)致A*算法速度變慢。如果h(n)完全等于路徑節(jié)點(diǎn)n到終點(diǎn)的距離，則A*算法將找到最佳路徑，并且速度很快。如果h(n)的值比節(jié)點(diǎn)n到終點(diǎn)的距離要大，那么A*算法就不能保證可以為小車找到最短路徑。由此可以得出，A*算法找到最短路徑的條件是：h(n)≤h(n)具實(shí)距離。A*算法(F=G+H)的具體步驟如下：

1)首先創(chuàng)建兩個(gè)集合openList和closeList(openList用于存放可以走的路，closeList存放已經(jīng)走過的路(即不能走的路，包含障礙物))。

2)將起點(diǎn)加入openList中，使用一個(gè)workCell變量用于開拓道路。首先取出openList中的第一個(gè)元素存放到workCell中。此時(shí)進(jìn)行判斷，若workCell等于終點(diǎn)，流程結(jié)束。否則進(jìn)行3)。

3)將openList中的第一個(gè)元素即workCell從openList中刪除，并加入到closeList中，表示這是走過的路。

4)找到workCell的所有鄰點(diǎn)，用一個(gè)臨時(shí)變量neighboursList存放，對(duì)neighboursList[i]進(jìn)行判斷，若該鄰點(diǎn)在closeList集合中，表示該鄰點(diǎn)是走過的，直接跳過，否則進(jìn)行5)。

5)若neighboursList[i]不在openList中，表示沒有計(jì)算過F，計(jì)算F，并將neighboursList[i]的父節(jié)點(diǎn)設(shè)置為workCell，然后將該鄰居加入到openList中，加入的時(shí)候進(jìn)行判斷，當(dāng)F最小時(shí)放在openList首位(保證最短路徑)；否則，neighboursList[i]在openList中(表示曾經(jīng)計(jì)算過F)，執(zhí)行6)。

6)重新計(jì)算F，若重新計(jì)算的值比之前計(jì)算的值小，則更新F和G以及父節(jié)點(diǎn)。

7)重復(fù)執(zhí)行2)～6)，直到openList中沒有元素(表示沒有通路)。

8)若成功找到通路，則用終點(diǎn)來回溯尋找父節(jié)點(diǎn)，將每個(gè)父節(jié)點(diǎn)存到pathList集合中，最終該集合就是通路。

通過A*尋路算法可以算出AGV小車行駛的路徑距離，下一步通過距離計(jì)算出小車到達(dá)節(jié)點(diǎn)的時(shí)間。AGV在小車運(yùn)動(dòng)過程中，不會(huì)一直處于勻速狀態(tài)，所以不能直接利用小車行駛的距離除以速度得出時(shí)間，需要考慮小車速度的變化從而求出時(shí)間。時(shí)間的計(jì)算方式主要如下：規(guī)定AGV的加速度為a，最大速度為Vmax，勻加速運(yùn)動(dòng)和勻減速運(yùn)動(dòng)距離如式(1)和(2)所示：

(1)

(2)

當(dāng)AGV小車從起點(diǎn)開始運(yùn)動(dòng)時(shí)，初始速度為0，即V0為0，然后進(jìn)行勻加速運(yùn)動(dòng)，加速到最大速度Vmax，此時(shí)能夠求出從起點(diǎn)到達(dá)最大速度這段路程所需要的時(shí)間t1為：

(3)

將式(3)代入式(1)，可得出從初始速度0加速至最大速度Vmax時(shí)所行駛的距離Smax：

(4)

AGV到達(dá)節(jié)點(diǎn)時(shí)間的求解主要分為4種情況：

2)AGV到達(dá)節(jié)點(diǎn)時(shí)處于勻速狀態(tài)。如果AGV到達(dá)節(jié)點(diǎn)時(shí)處于勻速的話，說明AGV從起點(diǎn)開始行駛，先開始勻加速，然后加速到了最大速度Vmax之后，AGV就保持Vmax進(jìn)行勻速運(yùn)動(dòng)，所以這種情況下，AGV到達(dá)節(jié)點(diǎn)的時(shí)間就是勻加速運(yùn)動(dòng)和勻速運(yùn)動(dòng)時(shí)間的總和，首先當(dāng)AGV小車從起點(diǎn)開始運(yùn)動(dòng)時(shí)，初始速度為0，即V0為0，然后進(jìn)行勻加速運(yùn)動(dòng)，由于AGV到達(dá)下一節(jié)點(diǎn)時(shí)不需要轉(zhuǎn)彎，行駛距離大于Smax′所以能夠加速到最大速度Vmax，此時(shí)根據(jù)式3)就能求出AGV從起點(diǎn)到達(dá)最大速度時(shí)這一段路程的時(shí)間t1為Vmax/a，下一步當(dāng)AGV進(jìn)行勻速運(yùn)動(dòng)時(shí)，一直以Vmax的速度行駛，這一段勻速行駛的距離記為S2，那么這一段路程所需要的時(shí)間為t2=S2/Vmax。最后得出AGV到達(dá)節(jié)點(diǎn)處于勻速狀態(tài)時(shí)的時(shí)間為t1+t2。

3)AGV到達(dá)節(jié)點(diǎn)之前沒有加速至最大速度，到達(dá)節(jié)點(diǎn)時(shí)處于勻減速狀態(tài)。當(dāng)AGV從起點(diǎn)開始運(yùn)動(dòng)，然后進(jìn)行勻加速運(yùn)動(dòng)，由于AGV到達(dá)下一節(jié)點(diǎn)的距離較短，距離小于Smax時(shí)就需要轉(zhuǎn)彎，所以無法加速至最大速度就需要進(jìn)行勻減速運(yùn)動(dòng)。當(dāng)AGV從起點(diǎn)開始勻加速時(shí)，起始速度為0，最終達(dá)到的速度Vg

4)AGV到達(dá)節(jié)點(diǎn)之前加速至最大速度，到達(dá)節(jié)點(diǎn)時(shí)處于勻減速狀態(tài)。當(dāng)AGV小車從起點(diǎn)開始運(yùn)動(dòng)時(shí)，初始速度為0，即V0為0，然后進(jìn)行勻加速運(yùn)動(dòng)，由于AGV到達(dá)下一節(jié)點(diǎn)時(shí)不需要轉(zhuǎn)彎，行駛距離大于Smax′所以能夠加速到最大速度Vmax，此時(shí)根據(jù)式(3)就能求出AGV從起點(diǎn)到達(dá)最大速度時(shí)這一段路程的時(shí)間t1。到達(dá)最大速度以后，AGV就進(jìn)行勻速運(yùn)動(dòng)，一直以Vmax的速度行駛，這一段勻速行駛的距離記為S2，那么這一段路程所需要的時(shí)間為t2=S2/Vmax，最后當(dāng)AGV在下一節(jié)點(diǎn)需要轉(zhuǎn)彎時(shí)，那么AGV的狀態(tài)就會(huì)從最大速度開始減速進(jìn)行勻減速運(yùn)動(dòng)，直到速度減為0，這一段勻減速的路程記為S3，初始速度為Vmax′那么這一段的時(shí)間t3=Vmax/a。最終到達(dá)節(jié)點(diǎn)的時(shí)間t即為t1+t2+t3。

3.2 多AGV路徑?jīng)_突檢測(cè)算法

在AGV小車實(shí)際應(yīng)用中，往往不是只有一臺(tái) AGV在工作，而是同時(shí)有多臺(tái)AGV在共同工作，并且物流運(yùn)輸系統(tǒng)中的各個(gè)任務(wù)都是交叉同時(shí)進(jìn)行的。為了使多AGV系統(tǒng)能夠高效有序的運(yùn)行，需要為每個(gè)AGV規(guī)劃出無沖突的路徑，以免出現(xiàn)AGV之間發(fā)生碰撞或出現(xiàn)時(shí)間沖突。多AGV系統(tǒng)就是不但是一輛AGV，而是很多輛同時(shí)工作，需要在保證AGV之間不發(fā)生碰撞的情況下完成系統(tǒng)分配好的任務(wù)。針對(duì)多AGV系統(tǒng)調(diào)度，我們首先要解決的問題是各個(gè)AGV之間碰撞問題和時(shí)間沖突問題，主要的沖突有3種類型，路口沖突、追趕沖突和相向沖突，分別如圖3～5所示。

圖3 路口沖突

圖4 相向沖突

圖5 追趕沖突

圖6 地圖編號(hào)

由于時(shí)間窗法(就是使沖突路段和行駛時(shí)間窗口化，通常使用坐標(biāo)軸進(jìn)行表示。也就是說時(shí)間窗描述了每一輛 AGV在地圖模型中每個(gè)路段的駛?cè)牒婉偝鰰r(shí)間。)無法根據(jù)AGV沖突的類型調(diào)整預(yù)檢測(cè)的精度，所以利用基因測(cè)序沖突檢測(cè)方法[9]來解決路徑?jīng)_突問題，能夠有效彌補(bǔ)時(shí)間窗法的不足。算法的具體步驟如下：

1)對(duì)地圖中的每一個(gè)節(jié)點(diǎn)和節(jié)點(diǎn)之間的路段進(jìn)行編號(hào)。地圖構(gòu)成記為m×n，第一步對(duì)地圖中的節(jié)點(diǎn)進(jìn)行編號(hào)，表示為0，1，2，…，m×n-1；水平路段編號(hào)：左節(jié)點(diǎn)為i，右節(jié)點(diǎn)為j，那么該路徑的編號(hào)即為(i+j)/2；垂直路徑編號(hào)的方法和水平編號(hào)類似，路徑上節(jié)點(diǎn)為a，下節(jié)點(diǎn)為b，則此路徑的編號(hào)為(a+b)/2+ 0.01。不同是垂直路徑需要在后面加上0.01，由于工廠倉庫的規(guī)模一般都很大，水平垂直兩個(gè)方向的路徑編號(hào)很有可能會(huì)重復(fù)，因此垂直路徑編號(hào)時(shí)多加0.01的數(shù)值，以便區(qū)分水平和垂直兩個(gè)路段。

2)建立AGV的路徑和時(shí)間得分矩陣。

路徑得分矩陣：路徑得分矩陣記為Mr，矩陣Mr的行是一臺(tái)AGV的路徑，列是另一臺(tái)AGV的路徑，在基因序列比對(duì)中，相似性是指兩個(gè)序列在同一位置具有相同的基因片段。和基因比對(duì)方法不同的是，AGV行駛的路徑是有方向的，所以就需要將兩臺(tái)AGV中的一臺(tái)AGV的路徑進(jìn)行逆轉(zhuǎn)。如果AGV1經(jīng)過的節(jié)點(diǎn)為[a1，…，ai，aj，…，an]；AGV2經(jīng)過的節(jié)點(diǎn)為[b1，…，bk，bl，…，bm]；那么可得出AGV之間的沖突發(fā)生在[ai，aj]或者[bk，bl]段。具體如圖7所示：由于AGV1和AGV2的行駛的方向相反，所以AGV1路線從左往右為a1 ～an，而AGV2的路線從右往左為b1～bm。

假設(shè)AGV1的路徑信息為R1，路徑節(jié)點(diǎn)為P1，路徑長度為L1；AGV2的路徑信息為R2，路徑節(jié)點(diǎn)為則P2T，路徑長度為L2。Mr表示以(0，P2T)為行，以(0，P1)為列的(L1+1)(L2+1)的矩陣。

時(shí)間得分矩陣：時(shí)間得分矩陣記為Mt。由于時(shí)間沒有方向性，所以不需要像路徑那樣做逆轉(zhuǎn)處理。其余過程和Mr矩陣類似。假設(shè)AGV1的路徑信息為R1，時(shí)間序列為T1，長度為L1；AGV2的路徑信息為R2，時(shí)間序列則為T2，長度為L2。Mt為以(0，T2)為行，以(0，T1)為列的矩陣。

3)回溯上面路徑和時(shí)間得分矩陣，得到?jīng)_突發(fā)生的區(qū)域。

在基因里面，回溯是要找到相似性最高的片段，那么在AGV中，就是找到矩陣中的最大值。如圖8所示，因此首先計(jì)算此元素上面、對(duì)角線方向、左面3個(gè)方向的得分，得分的數(shù)值為該方向上的得分+移動(dòng)過程得分；然后計(jì)算出的3個(gè)方向的得分與0的最大值。根據(jù)式(5)計(jì)算矩陣中每個(gè)元素的得分以此填充整個(gè)矩陣。

(5)

其中：(1 ≤i≤L1，1 ≤j≤L2)

Mi，j為第i行第j列元素得分，Mi-1，j-1為對(duì)角線方向元素得分，Mi-1，j為上面元素得分，Mi，j-1為左邊元素得分。s(a，b)和W為移動(dòng)過程得分，L1和L2表示AGV1和AGV2路徑長度。

回溯的步驟：首先根據(jù)上面的計(jì)算方法得到矩陣中的最大值。下一步得到路徑對(duì)比數(shù)組MAH_r[]和時(shí)間對(duì)比數(shù)組MAH_t[]，路徑最大值數(shù)組MAX_r[]和時(shí)間最大值數(shù)組MAX_t[]。最后通過比對(duì)4個(gè)數(shù)組，得到路徑比對(duì)結(jié)果和時(shí)間比對(duì)結(jié)果。

由于AGV小車一般不會(huì)出發(fā)點(diǎn)發(fā)生沖突，所以可以去除MAX_r[]和MAX_t[]第一個(gè)位置的元素，然后得到數(shù)組MAX_r’[]和MAX_t’[]，下一步計(jì)算出平均值，記MAX_r_a和MAX_t_a。由于AGV行駛時(shí)會(huì)有延遲，所以設(shè)置了一個(gè)檢測(cè)裕度ε，然后在MAX_r’[]和MAX_t’[]中選擇符合式(6)和(7)的元素并且存到mah_r[]和mah_t[]里面，具體如式(8)和(9)：

MAX_r_a-ε≤MAX_r′[]≤MAX_r_a+ε

(6)

MAX_t_a-ε≤MAX_t[]≤MAX_t_a+ε

(7)

mah_r[i]←MAX_r′[i]，1≤i≤min(L1，L2)

(8)

mah_t[i]←MAX_t′[i]，1≤i≤min(L1，L2)

(9)

然后取mah_r[]和mah_t[]的交集，就是兩臺(tái)AGV發(fā)生沖突的位置，如式(10)所示：

mah_r[j]∩mah_t[k]

(10)

其中：j和k的取值范圍都為[1，min(L1，L2)]。

多AGV沖突檢測(cè)的偽代碼如下所示：

沖突預(yù)檢測(cè):

定義:空列表存儲(chǔ)有潛在路徑?jīng)_突的AGV的數(shù)量:number[ ].

1:For i in range [1,n-1]

2: For j in range [i+1,n]

3:If Si ?Sj≠ Ф

4: number[ ] ←(i,j)

5:End For

6:End

沖突預(yù)檢測(cè)之后確定路徑?jīng)_突路段：如果不同的AGV行駛路徑中包含相同的節(jié)點(diǎn)，比較AGV到達(dá)相同節(jié)點(diǎn)的時(shí)間，判斷AGV是否在這路徑中發(fā)生沖突。沖突路段的偽代碼如下所示：沖突關(guān)鍵段:

定義:空列表存儲(chǔ)存在路徑?jīng)_突的AGV編號(hào):section[ ]

空列表存儲(chǔ)路徑?jīng)_突關(guān)鍵段的長度:length[ ]

1: For i in range [ 1,k-1]

3: [T] ←[Ti]

4: For j in range [ 1,2×(n-1)]

5:For k in range [ j+1,2×n]

6: If [Ti] ∩[Tk] ≠ Φ

7: section[ ] ←arg( [Ti]或 [Tk] )

8: length[ ] ←length[ ]( section[ ])

9: End For

10: End For

11: End For

12: End

3.3 AGV最終路徑規(guī)劃

上面兩節(jié)介紹了A*算法求解最短路徑，然后根據(jù)規(guī)劃的路徑進(jìn)行沖突檢測(cè)，檢測(cè)完沖突以后再利用A*算法為沖突的AGV重新規(guī)劃路徑或者原地等待。具體實(shí)現(xiàn)過程如圖9所示：圖中有三輛AGV，三輛AGV的路徑具體經(jīng)過哪些節(jié)點(diǎn)如表3所示。

表3 AGV路徑節(jié)點(diǎn)

圖9 AGV運(yùn)行路徑

AGV小車時(shí)間節(jié)點(diǎn)如表4所示。

表4 AGV時(shí)間節(jié)點(diǎn)

由表4可知，AGV1和AGV2在節(jié)點(diǎn)7處的沖突屬于相向沖突，此時(shí)就為AGV2用A*算法重新規(guī)劃一條路徑，重新規(guī)劃的路線為8→9→10→11→30→29→28→27→26。由表3可知，AGV1和AGV3在節(jié)點(diǎn)14處的沖突屬于路口沖突，那么就讓AGV3等待AGV1走完節(jié)點(diǎn)14再繼續(xù)前行，從而避免沖突。

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

4.1 仿真原型系統(tǒng)搭建步驟

實(shí)現(xiàn)AGV三維模型利用3 ds MAX建立模型，3 ds MAX(3D Studio Max)是3D建模渲染和制作軟件。首先建立三維工廠AGV模型。第二步是材質(zhì)的設(shè)置，材質(zhì)是指物體表面的特性，反應(yīng)物體表面的質(zhì)感。下一步是貼圖的制作，貼圖是材質(zhì)的一種圖像屬性，為材質(zhì)提供可視化的圖像信息。然后是燈光的設(shè)置，燈光來源于觀察和對(duì)畫面的整體把握。全部設(shè)置好之后將建立好的模型以gltf格式導(dǎo)出。導(dǎo)出以后，再利用WebGL(Web Graphics Library)將三維模型加載出來，WebGL技術(shù)是可以在網(wǎng)頁上繪制和渲染三維圖形以及允許用戶與之進(jìn)行交互。渲染出來的效果如圖10所示。

圖10 三維模型圖

最終得到的多AGV模型如下：目標(biāo)函數(shù)有兩個(gè)條件，任務(wù)路徑最短為r1，當(dāng)存在充電需求的AGV的時(shí)候，目標(biāo)函數(shù)r為任務(wù)路徑最短r1和有充電需求的AGV路徑最短r2之和。目標(biāo)函數(shù)如下：

r=r1 +r2

(11)

(12)

(13)

約束條件如下：

任務(wù)調(diào)度車約束：

(14)

一輛AGV一個(gè)時(shí)間只能完成一個(gè)任務(wù)：

(15)

如果第m輛AGV有充電需求，可以表現(xiàn)為當(dāng)前電量處于低電量區(qū)間：

ei≤x1

(16)

一輛AGV只能在一個(gè)充電樁內(nèi)充電：

(17)

式中，i表示AGV需要完成的運(yùn)輸任務(wù)，i= 1，2，3，…，I。j表示AGV小車，j=1，2，3，…，J。表示任務(wù)i由第j輛小車執(zhí)行，那么Xij=1，否則為0。dij表示第j輛AGV小車在完成運(yùn)輸任務(wù)i過程中行駛的距離。

AGV物流調(diào)度系統(tǒng)仿真實(shí)現(xiàn)如下所示：圖11為調(diào)度系統(tǒng)的首頁，記錄了AGV的數(shù)量以及離線和在線的情況。圖12為公司訂單的一些信息統(tǒng)計(jì)，可以對(duì)訂單信息進(jìn)行增刪改的操作。

圖11 系統(tǒng)首頁

圖12 訂單信息

4.2 結(jié)果分析

對(duì)于多AGV物流調(diào)度仿真系統(tǒng)的研究，都是為了提高系統(tǒng)中AGV的利用率、AGV負(fù)載率等。但是不能單用上面一種指標(biāo)來評(píng)價(jià)系統(tǒng)整體效率，不同的系統(tǒng)對(duì)于AGV的要求也是不一樣的，所以評(píng)價(jià)多AGV調(diào)度系統(tǒng)的效率需要對(duì)系統(tǒng)進(jìn)行全面的分析。

本文設(shè)計(jì)的系統(tǒng)以一天的工作時(shí)間進(jìn)行仿真，在初始狀態(tài)，所以AGV都在原點(diǎn)處，處于空閑狀態(tài)。根據(jù)仿真時(shí)間，計(jì)算出AGV的利用率、負(fù)載率、平均電量等信息，原有調(diào)度系統(tǒng)和本文設(shè)計(jì)的系統(tǒng)數(shù)據(jù)對(duì)比如表5所示。

表5 仿真結(jié)果對(duì)比 %

其中，一天中AGV的電量變化如圖13所示。

圖13 AGV電量變化

通過表5可以得出，本文設(shè)計(jì)的調(diào)度系統(tǒng)由于考慮了AGV電量和AGV路徑?jīng)_突，調(diào)度系統(tǒng)的任務(wù)分配更加合理，從而提高了AGV的利用率和負(fù)載率，提高了系統(tǒng)的總體效率。

5 結(jié)束語

本文主要以K公司汽車總裝生產(chǎn)線為應(yīng)用背景進(jìn)行了研究，為了解決多AGV調(diào)度系統(tǒng)中電量分配不均、路徑?jīng)_突等問題，利用WebGL技術(shù)建立了整個(gè)生產(chǎn)線場(chǎng)景的三維模型，并且建立了三維AGV模型，使得汽車生產(chǎn)線的場(chǎng)景和AGV小車更加可視化。此外，設(shè)計(jì)出了多AGV物流調(diào)度的仿真系統(tǒng)，系統(tǒng)可以自動(dòng)給AGV分配任務(wù)，然后AGV按照系統(tǒng)里面派發(fā)的任務(wù)去完成。在AGV執(zhí)行任務(wù)過程中，為了提高系統(tǒng)效率，設(shè)定了AGV電池電量的閾值，能夠合理分配電量，并利用A*算法為AGV尋找最短路徑，然后再利用基因序列比對(duì)算法找到存在路徑?jīng)_突的AGV，并為它們重新規(guī)劃路徑。最終經(jīng)過調(diào)度系統(tǒng)仿真驗(yàn)證，綜合考慮電池電量和路徑規(guī)劃問題提高了多AGV物流調(diào)度系統(tǒng)的效率。