倉儲物流中自動導引車的路徑規劃研究

隨著柔性制造系統的廣泛應用, 國內對自動導引車的需求量也漸漸增長。在整個自動化倉儲物流中, AGV運輸成本占總成本比重較高, 倉儲任務的精準調度以及AGV良好的路徑規劃策略, 對提高物流作業效率、降低運輸成本有重要意義。

針對多AGV的路徑尋優問題, 劉國棟等[1]提出了一種兩階段的交通控制方法來解決AGV路徑沖突問題, 王佳溶[2]提出改進型的兩階段控制策略, 他們針對任務的優先級未做詳細描述, 當任務和車輛非常多時, 容易產生任務饑餓;胡彬等[3]提出一種基于時間窗的動態路徑規劃方法, 先搜索出備選路徑, 然后通過計算和排布時間窗來規避沖突, 但提出的時間窗是基于邊的, 也就是一條較長車道只能被一臺AGV保留, 效率比節點時間窗低。

對AGV路徑規劃中路徑成本最優化以及調度效率問題, 提出一種基于優先級隊列和時間窗動態排序的路徑規劃方法。首先構建任務優先級隊列, 然后用A-Star算法啟發式搜索路徑, 通過對節點時間窗進行精確計算和加鎖, 實現了多AGV的路徑實時規劃和動態調優, 在無碰撞沖突條件下保證了倉儲物流路徑成本最低, 而且提高了系統運行效率。

本文所考慮的是自動化倉儲物流中AGV群體運動規則問題, 根據其所在的倉儲環境采用拓撲建模法構建地圖, 并作以下假設:

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

(2) AGV在4個方向上以同一速度勻速行駛, 且轉向速度固定;

(3) AGV間安全制動距離為0.8m;

(4) AGV共有4種狀態:無任務靜止狀態 (包括充電狀態) , 有任務待負載行駛狀態, 負載搬運狀態, 臨時等待狀態。

針對AGV倉儲物流環境, 建立拓撲地圖, 如圖1所示, 在有向連接網絡G=<V, E>中, V代表網絡中節點的集合V={v1, v2, …, vn}, E代表網絡中邊的集合E={e1, e2, …, em}, 且每條邊可以用相鄰節點有序對來表示:

多AGV路徑規劃的目的是規劃出一條時間代價最小的路徑。AGV在倉儲環境中的耗時分為到達裝載點時間, 搬運狀態時間和避障等待時間, 分別設為的tk、carrytk和Ωk。因此所有AGV的時間代價之和可由以下公式得到:

其中, k為倉儲任務的編號。

(1) 亟待充電且攜帶任務, 將已分配的任務作為高優先級重新分配, 然后將充電任務作為中優先級重新分配;

(2) 亟待充電且無任務無負載, 將充電任務作為中優先級重新分配;

(3) 一般性實時任務作為低優先級分配;

(4) 同一優先級按照FCFS方法分配。

(1) 相向相遇沖突。如圖2所示, 相向行駛的兩輛車相遇;

(2) 垂直相遇沖突。如圖3所示, 垂直方向的兩輛車在節點相遇;

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

(4) 占位沖突 (故障) 。如圖5所示, 前方因故障停車阻止了其他車的前進。

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

如圖1所示, 在有向連接網絡G= (V, E) 中, 假設有x輛車參與任務執行, 那么任務的AGV集合為A={a1, a2, …, ax}。所有任務的起點、終點都不同, 那么任務的起點集合和終點的集合分別記為S和D, 且SV, DV。那么自動導引車所經過節點的時間窗可以定義為:

式中, tiin表示自動導引車保留節點i的時間, tiout表示自動導引車釋放節點i的時間, i∈V。如圖7時間窗模型圖所示, 一個任務Wk的時間窗可以描述為Wk={w1, w2, w3, w4}={[t1, t2], [t3, t4], [t5, t6], [t7, t8]}。

為了保障倉儲物流過程的安全性, 需要對時間窗進行精準計算, 如圖7所示。設AGV到達節點i的時間為ti, 則有公式:

其中, tb為車輛安全制動時間, te為允許最大誤差時間, 包括在節點處突發斷電及故障引起的制動誤差。

如圖8所示, 設AGV車身的長度為l, AGV直行通過節點時, 則有公式:

其中, vst是小車統一默認的直行速度。

如圖9所示, 當AGV在節點處轉彎時, 則有:

其中, vtu是小車轉彎通過節點的速度。

在進行多AGV路徑尋優時, 采用拓撲建模法構建倉儲電子地圖, 且攜帶任務的AGV在運行過程中可雙向行駛。將一個倉儲搬運任務定義為:

其中, PQk表示第k個任務的實時優先級, 參數越大優先級越低;btk表示第k個任務的開始時間;Sk和Dk分別表示第k個任務的裝載點和卸載點, 且Sk∈V、Dk∈V;枚舉類型的參數LBk (t) 表示第k個任務的搬運狀態, 如公式 (8) 所示。

給任務分配不同的優先級PQ:如圖10所示, 將任務隊列劃分為高中低三個優先級隊列, 分別用PQh、PQm和PQl來表示。

(1) 當LBk (t) =0時, 小車正在去裝載點的路途中, 即當有任務無負載的AGV小車亟待充電或突發斷電等故障時, 已安排的任務的需要重新分配, 將該任務carryk (t) 放入高優先級隊列, 將充電或維修任務放入中優先級隊列;

(2) 當LBk (t) =1時, AGV在裝載點Sk和目的地Dk之間, 即有任務有負載的AGV亟待充電或突發斷電等故障時, 已安排的任務的需要重新初始化, 因為裝載點Sk已經改變, 然后將新任務carryk (t) 放入高優先級隊列, 將充電或維修任務放入中優先級隊列;

(3) 把一般性實時任務放入低優先級隊列。

首先我們用A-Star算法[4,5]給每個AGV搜索路徑, 得到臨時路徑p={e1, e2, …, en}。如圖7所示, 我們根據臨時路徑來計算時間窗, 節點的時間窗被定義為W={wi=[tiin, tout]}。在任意時刻, 只要節點被保留, 就不允許其他AiGV進入該窗口。倉儲運輸環境中, 上位機系統分發的任務都是按需求多次動態分發, 為了提高效率, 這里需要預判任務耗時長短, 將比較復雜或裝載點[6]Sk距離卸載點Dk比較遠的任務優先插入優先級隊列以及優先排布時間窗, 這樣做是為了減少后續的長任務在規避和等待節點時間窗上大量的耗時:

體現在沖突一:后續的長任務需要不斷地尋找次優路線;體現在沖突二:后續的長任務需要不斷地負載等待。二者都容易造成任務饑餓, 會降低調度系統的效率。

我們有了任務的優先級分配和時間窗的計算, 下面來介紹路徑規劃算法的具體實現步驟, 如圖11所示。

(1) 根據上位機系統管理員輸入倉儲物流參數, 將任務劃分優先級, 插入優先級隊列, 并初始化多個運輸任務, carryk (t) ={PQk (t) , btk, Sk, Dk, LBk (t) }。

(2) 按照任務的優先級順序進行車輛調度:選用離裝載點[6]最近的空閑AGV來執行任務。

(3) 用A-Star算法對路徑進行啟發式搜索, 得到臨時的最短行駛路徑。

(4) 計算小車到達每個路徑節點的時間ti, 然后根據公式 (4) ~式 (6) 計算出自動導引車保留節點i的時間tiin和自動導引車釋放節點i的時間tiout。

(5) 初始化節點時間窗Wk, 如果存在任務p和q使Wp∩Wq≠?, 說明節點時間窗因尚未加鎖而出現重疊現象, 即在的某個保留時間窗內出現了其他車輛[[7]]。

(6) 根據重疊時間窗和拓撲地圖, 來確定將會發生哪種節點沖突, 然后對每個節點的時間窗加鎖。如果存在如圖2所示的沖突一相向相遇沖突[8], 選擇PQk (t) 較大的任務重新調度, 由于根據啟發式算法規劃的臨時最優路線會出現碰撞[9], 因此需要繼續搜索次優路徑, 返回執行步驟 (3) , 若最后所有路線都會出現沖突一, 那么返回執行步驟 (2) 更換AGV車輛;如果沖突類型只剩沖突二垂直相遇沖突[10], 那么攜帶低優先級任務的AGV原地等待一個節點時間窗的時間, 直到重疊窗口消失;如果兩種沖突都存在, 則先按照相向相遇沖突處理。

(7) 生成可執行任務 (指定AGV, 明確路線) , AGV執行完任務空閑后, 由于該AGV可能成為其他任務的障礙, 所以要優先派發該車輛。重復執行步驟 (1) 等待管理員動態分發新需求。

考慮其他三種沖突, 任務執行過程中, 對于沖突三, 那么將更改此空閑AGV所占有的節點周圍四條邊的權重為無窮大, 修改任務的起始點, 執行算法中的步驟 (3) ;對于沖突四, 可能為突發斷電 (非亟待充電提醒) 或機械老化等故障, 需要人工維修或清除, 然后更新可用AGV信息;對于沖突五, 由于環境中假設AGV速度相同, 所以不會出現趕超沖突, 即使在前面的AGV制動減速的時候也不會出現趕超沖突, 因為在計算時間窗時, AGV制動時間tb已經被保留在時間窗內。

使用Visual Studio 2015作為仿真開發平臺, 編寫調度程序對提出的路徑尋優算法進行驗證。選取某倉儲物流中心如圖1拓撲地圖所示, 倉儲區域長30m, 寬30m, 倉儲節點36 (不包括充電區域) , 144個貨架, 14條車道縱橫交錯, AGV直行速度為0.5m/s。轉向時間固定為2s。

設計兩組仿真對比實驗:一組是無時間窗加鎖和有時間窗加鎖的路徑尋優結果, 另一組是不含優先級隊列和含優先級隊列的路徑尋優結果。從兩個維度來驗證所提出算法的可行性和高效性。

(1) 針對第一種仿真對比實驗, 我們分別初始化三個任務:

首先根據任務的預估時間來初始化優先級, 時間越長, PQk (t) 數字越小, 優先級越高。

無時間窗加鎖的情況如圖12所示, 執行任務carry1 (t) 的車輛將會與執行carry3 (t) 的車輛在b1到c1路段發生相向相遇沖突, 執行任務carry1 (t) 的車輛將會與執行carry2 (t) 的車輛在c3節點發生垂直相遇沖突[11];

含時間窗加鎖的情況如圖13所示, 由于經過時間窗的重新排布, 任務carry3 (t) 已經重新規劃路線, 有效避免與任務carry1 (t) 相向相遇沖突, 且在節點c2進行等待規避, 避免垂直相遇沖突, 任務carry3 (t) 將會在節點c3處進行規避等待, 有效避免死鎖和碰撞[12]。

(2) 針對第二種仿真對比實驗, 在不含優先級的算法中我們分別初始化三個任務, 這里PQk (t) 均為1, 即:

算法執行過程如圖14所示。

考慮圖13和圖14所示的兩種仿真執行過程, 對不含優先級和含優先級的兩種調度算法進行路徑代價對比, 如表1和表2所示。根據目標函數公式計算出:含優先級的調度算法路徑成本Cost小于不含優先級的調度算法。

對多AGV路徑尋優和調度效率問題, 提出基于優先級隊列和時間窗模型的調度算法。在多AGV動態路徑尋優中, 解決了多AGV的碰撞沖突問題, 而且通過構建任務優先級隊列優先級優化了調度順序, 不僅保證了路徑最優, 而且可以避免任務饑餓與死鎖。最后通過仿真實驗得出, 算法在保證車輛無碰撞的條件下可使AGV路徑成本最低, 同時提高了任務和車輛調度的效率。