劉敬一，孫維堂，劉 閩，董君陶

(1.中國(guó)科學(xué)院大學(xué)，北京 100049；2.中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所 智能控制與裝備部,沈陽(yáng) 110168；3.沈陽(yáng)市環(huán)境監(jiān)測(cè)中心站 沈陽(yáng) 110000；4沈陽(yáng)市第二十七中學(xué) 沈陽(yáng) 110011)

0 引言

隨著柔性制造系統(tǒng)的廣泛應(yīng)用，國(guó)內(nèi)對(duì)自動(dòng)導(dǎo)引車(chē)的需求量也漸漸增長(zhǎng)。在整個(gè)自動(dòng)化倉(cāng)儲(chǔ)物流中，AGV運(yùn)輸成本占總成本比重較高，倉(cāng)儲(chǔ)任務(wù)的精準(zhǔn)調(diào)度以及AGV良好的路徑規(guī)劃策略，對(duì)提高物流作業(yè)效率、降低運(yùn)輸成本有重要意義。

針對(duì)多AGV的路徑尋優(yōu)問(wèn)題，劉國(guó)棟等[1]提出了一種兩階段的交通控制方法來(lái)解決AGV路徑?jīng)_突問(wèn)題,王佳溶[2]提出改進(jìn)型的兩階段控制策略，他們針對(duì)任務(wù)的優(yōu)先級(jí)未做詳細(xì)描述，當(dāng)任務(wù)和車(chē)輛非常多時(shí)，容易產(chǎn)生任務(wù)饑餓；胡彬等[3]提出一種基于時(shí)間窗的動(dòng)態(tài)路徑規(guī)劃方法，先搜索出備選路徑，然后通過(guò)計(jì)算和排布時(shí)間窗來(lái)規(guī)避沖突，但提出的時(shí)間窗是基于邊的，也就是一條較長(zhǎng)車(chē)道只能被一臺(tái)AGV保留，效率比節(jié)點(diǎn)時(shí)間窗低。

對(duì)AGV路徑規(guī)劃中路徑成本最優(yōu)化以及調(diào)度效率問(wèn)題，提出一種基于優(yōu)先級(jí)隊(duì)列和時(shí)間窗動(dòng)態(tài)排序的路徑規(guī)劃方法。首先構(gòu)建任務(wù)優(yōu)先級(jí)隊(duì)列，然后用A-Star算法啟發(fā)式搜索路徑，通過(guò)對(duì)節(jié)點(diǎn)時(shí)間窗進(jìn)行精確計(jì)算和加鎖，實(shí)現(xiàn)了多AGV的路徑實(shí)時(shí)規(guī)劃和動(dòng)態(tài)調(diào)優(yōu)，在無(wú)碰撞沖突條件下保證了倉(cāng)儲(chǔ)物流路徑成本最低，而且提高了系統(tǒng)運(yùn)行效率。

1 問(wèn)題描述

1.1 環(huán)境地圖

本文所考慮的是自動(dòng)化倉(cāng)儲(chǔ)物流中AGV群體運(yùn)動(dòng)規(guī)則問(wèn)題，根據(jù)其所在的倉(cāng)儲(chǔ)環(huán)境采用拓?fù)浣７?gòu)建地圖，并作以下假設(shè)：

(1)相鄰節(jié)點(diǎn)間的路線為單行道可雙向行駛。

(2)AGV在4個(gè)方向上以同一速度勻速行駛，且轉(zhuǎn)向速度固定；

(3)AGV間安全制動(dòng)距離為0.8m；

(4)AGV共有4種狀態(tài)：無(wú)任務(wù)靜止?fàn)顟B(tài)(包括充電狀態(tài))，有任務(wù)待負(fù)載行駛狀態(tài)，負(fù)載搬運(yùn)狀態(tài)，臨時(shí)等待狀態(tài)。

圖1 倉(cāng)儲(chǔ)環(huán)境下拓?fù)涞貓D

1.2 目標(biāo)函數(shù)

針對(duì)AGV倉(cāng)儲(chǔ)物流環(huán)境，建立拓?fù)涞貓D，如圖1所示，在有向連接網(wǎng)絡(luò)G=中，V代表網(wǎng)絡(luò)中節(jié)點(diǎn)的集合V={v1,v2,…,vn},E代表網(wǎng)絡(luò)中邊的集合E={e1,e2,…,em}， 且每條邊可以用相鄰節(jié)點(diǎn)有序?qū)?lái)表示：

ey={vp→vq：vp，vq∈V}

(1)

多AGV路徑規(guī)劃的目的是規(guī)劃出一條時(shí)間代價(jià)最小的路徑。AGV在倉(cāng)儲(chǔ)環(huán)境中的耗時(shí)分為到達(dá)裝載點(diǎn)時(shí)間，搬運(yùn)狀態(tài)時(shí)間和避障等待時(shí)間，分別設(shè)為的tk、carrytk和Ωk。因此所有AGV的時(shí)間代價(jià)之和可由以下公式得到：

(2)

其中，k為倉(cāng)儲(chǔ)任務(wù)的編號(hào)。

1.3 任務(wù)調(diào)度

(1)亟待充電且攜帶任務(wù)，將已分配的任務(wù)作為高優(yōu)先級(jí)重新分配，然后將充電任務(wù)作為中優(yōu)先級(jí)重新分配；

(2)亟待充電且無(wú)任務(wù)無(wú)負(fù)載，將充電任務(wù)作為中優(yōu)先級(jí)重新分配；

(3)一般性實(shí)時(shí)任務(wù)作為低優(yōu)先級(jí)分配；

(4)同一優(yōu)先級(jí)按照FCFS方法分配。

1.4 避障要素

(1)相向相遇沖突。如圖2所示，相向行駛的兩輛車(chē)相遇；

圖2 相向沖突示意圖

(2)垂直相遇沖突。如圖3所示，垂直方向的兩輛車(chē)在節(jié)點(diǎn)相遇；

圖3 垂直相遇沖突示意圖

(3)占位沖突(車(chē)輛空閑)。如圖4所示，前方因AGV空閑停車(chē)阻止了其他車(chē)的前進(jìn)。

圖4 占位沖突1示意圖

(4)占位沖突(故障)。如圖5所示，前方因故障停車(chē)阻止了其他車(chē)的前進(jìn)。

圖5 占位沖突2示意圖

(5)追尾沖突(超速)。如圖6所示,即將趕超。

圖6 追尾沖突示意圖

2 基于時(shí)間窗的避障路線規(guī)劃法

2.1 時(shí)間窗定義

如圖1所示，在有向連接網(wǎng)絡(luò)G=(V，E)中，假設(shè)有x輛車(chē)參與任務(wù)執(zhí)行，那么任務(wù)的AGV集合為A={a1，a2,…，ax}。所有任務(wù)的起點(diǎn)、終點(diǎn)都不同，那么任務(wù)的起點(diǎn)集合和終點(diǎn)的集合分別記為S和D,且S?V，D?V。那么自動(dòng)導(dǎo)引車(chē)所經(jīng)過(guò)節(jié)點(diǎn)的時(shí)間窗可以定義為：

(3)

圖7 節(jié)點(diǎn)保留時(shí)間窗模型圖

2.2 時(shí)間窗計(jì)算

為了保障倉(cāng)儲(chǔ)物流過(guò)程的安全性，需要對(duì)時(shí)間窗進(jìn)行精準(zhǔn)計(jì)算，如圖7所示。設(shè)AGV到達(dá)節(jié)點(diǎn)i的時(shí)間為ti,則有公式：

(4)

其中，tb為車(chē)輛安全制動(dòng)時(shí)間，te為允許最大誤差時(shí)間，包括在節(jié)點(diǎn)處突發(fā)斷電及故障引起的制動(dòng)誤差。

如圖8所示，設(shè)AGV車(chē)身的長(zhǎng)度為l，AGV直行通過(guò)節(jié)點(diǎn)時(shí)，則有公式：

(5)

其中，vst是小車(chē)統(tǒng)一默認(rèn)的直行速度。

圖8 自動(dòng)導(dǎo)引車(chē)通過(guò)節(jié)點(diǎn)i示意圖

如圖9所示，當(dāng)AGV在節(jié)點(diǎn)處轉(zhuǎn)彎時(shí)，則有：

(6)

其中，vtu是小車(chē)轉(zhuǎn)彎通過(guò)節(jié)點(diǎn)的速度。

圖9 自動(dòng)導(dǎo)引車(chē)轉(zhuǎn)彎通過(guò)節(jié)點(diǎn)i示意圖

2.3 AGV最優(yōu)路徑規(guī)劃算法

在進(jìn)行多AGV路徑尋優(yōu)時(shí)，采用拓?fù)浣７?gòu)建倉(cāng)儲(chǔ)電子地圖，且攜帶任務(wù)的AGV在運(yùn)行過(guò)程中可雙向行駛。將一個(gè)倉(cāng)儲(chǔ)搬運(yùn)任務(wù)定義為：

carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}

(7)

其中，PQk表示第k個(gè)任務(wù)的實(shí)時(shí)優(yōu)先級(jí)，參數(shù)越大優(yōu)先級(jí)越低；btk表示第k個(gè)任務(wù)的開(kāi)始時(shí)間；Sk和Dk分別表示第k個(gè)任務(wù)的裝載點(diǎn)和卸載點(diǎn)，且Sk∈V、Dk∈V；枚舉類型的參數(shù)LBk(t)表示第k個(gè)任務(wù)的搬運(yùn)狀態(tài),如公式(8)所示。

(8)

給任務(wù)分配不同的優(yōu)先級(jí)PQ：如圖10所示，將任務(wù)隊(duì)列劃分為高中低三個(gè)優(yōu)先級(jí)隊(duì)列，分別用PQh、PQm和PQl來(lái)表示。

(1)當(dāng)LBk(t)=0時(shí)，小車(chē)正在去裝載點(diǎn)的路途中，即當(dāng)有任務(wù)無(wú)負(fù)載的AGV小車(chē)亟待充電或突發(fā)斷電等故障時(shí)，已安排的任務(wù)的需要重新分配，將該任務(wù)carryk(t)放入高優(yōu)先級(jí)隊(duì)列，將充電或維修任務(wù)放入中優(yōu)先級(jí)隊(duì)列；

(2)當(dāng)LBk(t)=1時(shí)，AGV在裝載點(diǎn)Sk和目的地Dk之間，即有任務(wù)有負(fù)載的AGV亟待充電或突發(fā)斷電等故障時(shí)，已安排的任務(wù)的需要重新初始化，因?yàn)檠b載點(diǎn)Sk已經(jīng)改變，然后將新任務(wù)carryk(t)放入高優(yōu)先級(jí)隊(duì)列，將充電或維修任務(wù)放入中優(yōu)先級(jí)隊(duì)列；

(3) 把一般性實(shí)時(shí)任務(wù)放入低優(yōu)先級(jí)隊(duì)列。

圖10 三叉堆優(yōu)先級(jí)隊(duì)列示意圖

體現(xiàn)在沖突一：后續(xù)的長(zhǎng)任務(wù)需要不斷地尋找次優(yōu)路線；體現(xiàn)在沖突二：后續(xù)的長(zhǎng)任務(wù)需要不斷地負(fù)載等待。二者都容易造成任務(wù)饑餓，會(huì)降低調(diào)度系統(tǒng)的效率。

我們有了任務(wù)的優(yōu)先級(jí)分配和時(shí)間窗的計(jì)算，下面來(lái)介紹路徑規(guī)劃算法的具體實(shí)現(xiàn)步驟，如圖11所示。

(1)根據(jù)上位機(jī)系統(tǒng)管理員輸入倉(cāng)儲(chǔ)物流參數(shù)，將任務(wù)劃分優(yōu)先級(jí)，插入優(yōu)先級(jí)隊(duì)列，并初始化多個(gè)運(yùn)輸任務(wù)，carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}。

(2)按照任務(wù)的優(yōu)先級(jí)順序進(jìn)行車(chē)輛調(diào)度：選用離裝載點(diǎn)[6]最近的空閑AGV來(lái)執(zhí)行任務(wù)。

(3)用A-Star算法對(duì)路徑進(jìn)行啟發(fā)式搜索，得到臨時(shí)的最短行駛路徑。

(5)初始化節(jié)點(diǎn)時(shí)間窗Wk，如果存在任務(wù)p和q使Wp∩Wq≠?，說(shuō)明節(jié)點(diǎn)時(shí)間窗因尚未加鎖而出現(xiàn)重疊現(xiàn)象，即在的某個(gè)保留時(shí)間窗內(nèi)出現(xiàn)了其他車(chē)輛[7]。

(6)根據(jù)重疊時(shí)間窗和拓?fù)涞貓D，來(lái)確定將會(huì)發(fā)生哪種節(jié)點(diǎn)沖突，然后對(duì)每個(gè)節(jié)點(diǎn)的時(shí)間窗加鎖。如果存在如圖2所示的沖突一相向相遇沖突[8]，選擇PQk(t)較大的任務(wù)重新調(diào)度，由于根據(jù)啟發(fā)式算法規(guī)劃的臨時(shí)最優(yōu)路線會(huì)出現(xiàn)碰撞[9]，因此需要繼續(xù)搜索次優(yōu)路徑，返回執(zhí)行步驟(3)，若最后所有路線都會(huì)出現(xiàn)沖突一，那么返回執(zhí)行步驟(2)更換AGV車(chē)輛；如果沖突類型只剩沖突二垂直相遇沖突[10]，那么攜帶低優(yōu)先級(jí)任務(wù)的AGV原地等待一個(gè)節(jié)點(diǎn)時(shí)間窗的時(shí)間，直到重疊窗口消失；如果兩種沖突都存在，則先按照相向相遇沖突處理。

(7)生成可執(zhí)行任務(wù)(指定AGV，明確路線)，AGV執(zhí)行完任務(wù)空閑后，由于該AGV可能成為其他任務(wù)的障礙，所以要優(yōu)先派發(fā)該車(chē)輛。重復(fù)執(zhí)行步驟(1)等待管理員動(dòng)態(tài)分發(fā)新需求。

圖11 AGV路徑規(guī)劃算法流程圖

考慮其他三種沖突，任務(wù)執(zhí)行過(guò)程中，對(duì)于沖突三,那么將更改此空閑AGV所占有的節(jié)點(diǎn)周?chē)臈l邊的權(quán)重為無(wú)窮大,修改任務(wù)的起始點(diǎn)，執(zhí)行算法中的步驟(3)；對(duì)于沖突四，可能為突發(fā)斷電(非亟待充電提醒)或機(jī)械老化等故障，需要人工維修或清除，然后更新可用AGV信息；對(duì)于沖突五，由于環(huán)境中假設(shè)AGV速度相同，所以不會(huì)出現(xiàn)趕超沖突，即使在前面的AGV制動(dòng)減速的時(shí)候也不會(huì)出現(xiàn)趕超沖突，因?yàn)樵谟?jì)算時(shí)間窗時(shí)，AGV制動(dòng)時(shí)間tb已經(jīng)被保留在時(shí)間窗內(nèi)。

3 算法仿真驗(yàn)證

使用 Visual Studio 2015作為仿真開(kāi)發(fā)平臺(tái)，編寫(xiě)調(diào)度程序?qū)μ岢龅穆窂綄?yōu)算法進(jìn)行驗(yàn)證。選取某倉(cāng)儲(chǔ)物流中心如圖1拓?fù)涞貓D所示，倉(cāng)儲(chǔ)區(qū)域長(zhǎng)30m，寬30m，倉(cāng)儲(chǔ)節(jié)點(diǎn)36(不包括充電區(qū)域)，144個(gè)貨架，14條車(chē)道縱橫交錯(cuò),AGV直行速度為0.5m/s。轉(zhuǎn)向時(shí)間固定為2s。

設(shè)計(jì)兩組仿真對(duì)比實(shí)驗(yàn)：一組是無(wú)時(shí)間窗加鎖和有時(shí)間窗加鎖的路徑尋優(yōu)結(jié)果，另一組是不含優(yōu)先級(jí)隊(duì)列和含優(yōu)先級(jí)隊(duì)列的路徑尋優(yōu)結(jié)果。從兩個(gè)維度來(lái)驗(yàn)證所提出算法的可行性和高效性。

(1)針對(duì)第一種仿真對(duì)比實(shí)驗(yàn)，我們分別初始化三個(gè)任務(wù)：

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={2,0,g3,b3, -1}。

carry3(t)={3,0,e1,b2, -1}。

首先根據(jù)任務(wù)的預(yù)估時(shí)間來(lái)初始化優(yōu)先級(jí)，時(shí)間越長(zhǎng)，PQk(t)數(shù)字越小，優(yōu)先級(jí)越高。

無(wú)時(shí)間窗加鎖的情況如圖12所示，執(zhí)行任務(wù)carry1(t)的車(chē)輛將會(huì)與執(zhí)行carry3(t)的車(chē)輛在b1到c1路段發(fā)生相向相遇沖突，執(zhí)行任務(wù)carry1(t)的車(chē)輛將會(huì)與執(zhí)行carry2(t)的車(chē)輛在c3節(jié)點(diǎn)發(fā)生垂直相遇沖突[11]；

圖12 無(wú)時(shí)間窗加鎖含優(yōu)先級(jí)路徑尋優(yōu)結(jié)果

含時(shí)間窗加鎖的情況如圖13所示，由于經(jīng)過(guò)時(shí)間窗的重新排布，任務(wù)carry3(t)已經(jīng)重新規(guī)劃路線，有效避免與任務(wù)carry1(t)相向相遇沖突，且在節(jié)點(diǎn)c2進(jìn)行等待規(guī)避，避免垂直相遇沖突，任務(wù)carry3(t)將會(huì)在節(jié)點(diǎn)c3處進(jìn)行規(guī)避等待，有效避免死鎖和碰撞[12]。

圖13 含時(shí)間窗加鎖含優(yōu)先級(jí)路徑尋優(yōu)結(jié)果

(2)針對(duì)第二種仿真對(duì)比實(shí)驗(yàn)，在不含優(yōu)先級(jí)的算法中我們分別初始化三個(gè)任務(wù)，這里PQk(t)均為1，即：

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={1,0,g3,b3, -1}。

carry3(t)={1,0,e1,b2, -1}。

算法執(zhí)行過(guò)程如圖14所示。

圖14 含時(shí)間窗加鎖不含優(yōu)先級(jí)路徑尋優(yōu)結(jié)果

考慮圖13和圖14所示的兩種仿真執(zhí)行過(guò)程，對(duì)不含優(yōu)先級(jí)和含優(yōu)先級(jí)的兩種調(diào)度算法進(jìn)行路徑代價(jià)對(duì)比，如表1和表2所示。根據(jù)目標(biāo)函數(shù)公式計(jì)算出：含優(yōu)先級(jí)的調(diào)度算法路徑成本Cost小于不含優(yōu)先級(jí)的調(diào)度算法。

表1 不含優(yōu)先級(jí)隊(duì)列的調(diào)度算法執(zhí)行分析

表2 含優(yōu)先級(jí)隊(duì)列的調(diào)度算法執(zhí)行分析

4 結(jié)論

對(duì)多AGV路徑尋優(yōu)和調(diào)度效率問(wèn)題，提出基于優(yōu)先級(jí)隊(duì)列和時(shí)間窗模型的調(diào)度算法。在多AGV動(dòng)態(tài)路徑尋優(yōu)中，解決了多AGV的碰撞沖突問(wèn)題，而且通過(guò)構(gòu)建任務(wù)優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)優(yōu)化了調(diào)度順序，不僅保證了路徑最優(yōu)，而且可以避免任務(wù)饑餓與死鎖。最后通過(guò)仿真實(shí)驗(yàn)得出，算法在保證車(chē)輛無(wú)碰撞的條件下可使AGV路徑成本最低，同時(shí)提高了任務(wù)和車(chē)輛調(diào)度的效率。