時間窗約束下的AGV動態路徑規劃

張崢煒，陳波，陳衛東

時間窗約束下的AGV動態路徑規劃

張崢煒，陳波，陳衛東

針對自動化碼頭的多自動導引車系統（Automated Guided Vehicle，AGV）的路徑規劃問題，提出了一種基于時間窗的改進Dijkstra動態路徑規劃算法。算法按照任務優先級和地圖中的先驗信息順序規劃各AGV的行駛路徑，在已規劃路徑的基礎上，通過更新地圖中的時間窗信息，繼續規劃后續路徑，實現各AGV的無沖突且行駛時間最短的動態路徑規劃。結合實例及對比實驗表明該算法能夠有效減少多AGV之間的路徑沖突，降低AGV的路徑行駛時間，提高自動化碼頭運行效率。

自動導引車；時間窗；動態路徑規劃；Dijkstra算法；自動化碼頭

0 引言

自動導引車（Automated Guided Vehicle，AGV）系統是一種實現物料搬運的無人運輸系統，在倉儲物流、汽車裝配、煙草、電力等行業都有著廣泛應用。近年來隨著集裝箱自動化碼頭在國內的興起，AGV作為主要的水平運輸工具承擔重要任務，主要包括從岸橋到堆場的集裝箱卸船運輸、堆場到岸橋的裝船運輸以及堆場內的轉場運輸等。AGV水平運輸系統被業界公認為整個自動化碼頭的效率瓶頸，而 AGV路徑規劃問題又是AGV系統設計的核心，因此研究多AGV系統的高效無沖突、無死鎖路徑問題，對于提高整個自動化碼頭的裝卸效率具有重要意義。

世界上第一個集裝箱自動化碼頭荷蘭鹿特丹港ECT碼頭于1993年投入商業運營，此后德國漢堡港CTA碼頭、鹿特丹港Euromax等自動化碼頭相繼建成，國外學者圍繞自動化碼頭做了大量的研究工作，針對AGV的路徑問題的研究主要集中于在途AGV的相互間沖突[1,2]，死鎖的預防、檢測與控制[3-5]等方面，而針對AGV路徑搜索相關方面的研究相對較少。Klimm等[6]提出一種無沖突的靜態路徑規劃方法，首先以最小負載為目標規劃路徑，然后進行死鎖的預防與檢測。該方法僅適用于地圖中潛在死鎖數量較少的情況，隨著AGV數量的增加，地圖中潛在的死鎖數量增多，該方法無法獲得較優的結果。Jeon等[7]提出一種基于Q學習的路徑規劃算法，通過估計AGV在行駛中因沖突而產生的等待時間，為AGV規劃一條行駛時間最短的路徑，但是該算法求解耗時長，且無法避免死鎖的產生。

國內自動化碼頭起步相對較晚，針對自動化碼頭的AGV路徑規劃問題研究較少，且研究主要面向制造系統。劉國棟等[8]針對多AGV調度系統，提出兩階段動態路徑規劃方法，第一階段先離線生成任意兩點之間的候選路徑集，第二階段采用啟發式方法為所有任務分配各自的最優路徑。賀麗娜等[9]針對制造系統中的多AGV調度，提出一種基于先驗決策的無碰撞路徑規劃方法，該方法先根據Dijkstra算法對每個 AGV規劃出最短路徑，再結合時間窗原理進行AGV的無碰撞路徑規劃。胡彬等[10]提出一種基于時間窗的動態路徑規劃方法，該方法通過求出備選路徑，再在備選路

徑上排出理想情況下的時間窗，然后對有時間窗重疊部分的路徑進行計算與更新。喬巖等[11]提出通過實時改變自動導引車通過節點的優先級來調整自動導引車在相應節點的通過順序，從而實現多自動導引車動態環境下的路徑規劃。

上述文獻提出的AGV動態路徑規劃算法，均采用先為已分配任務的AGV規劃最短行駛路徑，再根據時間窗為各AGV調整路徑通過次序及時間，某種程度上避免了相互沖突，但由于路徑的規劃是以行駛距離最短為目標，規劃過程并未考慮行駛時間，無法充分利用路段的時間資源，因此AGV運行效率有限。基于以上原因，本文提出了一種適用于自動化碼頭的AGV動態路徑規劃方法，基于時間窗理論實現行駛時間最短的無沖突路徑。

1 問題描述

1.1 地圖描述

自動化碼頭的布局主要有兩種方式，循環式布局和交叉式布局，Duinkerken等[12]對兩種布局方式進行了對比，得出在岸橋裝卸船效率相同的情況下，交叉式布局需求的 AGV數量更少，即交叉式布局方式下AGV的運行效率更高。目前國內已建成的或在建的自動化碼頭，均采用交叉式布局，因此本文研究亦采用該方式。

在自動化碼頭中，AGV沿著鋪在地面上的導引磁釘行駛，磁釘及AGV在磁釘之間的運動方向構成地圖，如圖1所示：

圖1 自動化碼頭中部分地圖布局

布局中所有的磁釘抽象為圖論中的點，根據點在地圖中的不同位置以及AGV在點之間的運動方向構成圖論中的有向邊。所有的點以及點與點之間的線路抽象為一個有向強連通圖 。其中為點的集合，為邊的集合，為邊上權重的集合。

動態路徑規劃算法的目標是搜索出一條能連通、無沖突的且行駛時間最短的路徑，所以有向邊的權重定義為 AGV通過該邊的行駛時間。AGV在邊上的權重為邊的長度與邊上行駛速度的比值為式（1）：

式（1）中為邊的物理長度，為AGV在邊上的平均行駛速度。

1.2 模型描述

本文模型描述如下：在一個強連通圖中，給定一個任務，其中表示任務編號，表示任務的起點，表示任務的終點，表示任務的開始時間，規劃一條從任務起點到任務終點能夠連通、無沖突的且行駛時間最短的路徑。

一個簡化的地圖模型如圖2所示：

圖2 簡化的地圖模型

與其相對應的時間窗如圖3所示：

圖3 對應的時間窗

為簡化模型，本文在建模時做如下規定：

（1）對于有k個任務需要規劃路徑，按照任務優先級依次對k個任務進行路徑規劃，任務優先級在任務下發時給出。

（2）在所有運行區域，AGV的行駛速度設定為常值。

（3）為保障AGV行車安全，本文定義一個安全時間：

（4）為便于研究，本文假設所有任務均統一下發，對于實際工程中可能出現的分批下發情況，本文暫不做討論。

2 時間窗約束下的路徑規劃算法

2.1 算法實現步驟

針對動態路徑規劃算法的求解，本文采用類似求解Dijkstra算法的以點為基礎的標號法，Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題[13]，該算法要求所有邊的權重均為非負值。在本文研究中，邊的權重為時間，均為非負值滿足算法要求。算法的實現分為以下幾個步驟：

2.2 時間窗的計算（1）計算AGV通過點的時間如圖4所示：

圖4 AGV通行示意圖

（2）計算最早達到時間及占用時間窗

在執行帶時間窗約束的路徑搜索時，如圖5所示：

圖5 相鄰點

如1.2節所示的模型，運用上述算法規劃AGV的行駛路徑，主要計算過程及結果如圖6所示：

圖6 路徑規劃結果

3 算法仿真驗證

本文使用MATLAB R2012a軟件進行時間窗約束下的動態路徑規劃仿真驗證。選取國內某自動化碼頭水平運輸區部分區域，長287米，寬94米，包含45個堆場作業車道，40個岸橋緩沖區車道以及6個高速車道。AGV行駛速度設定為3m/s。本文設計了兩組對比實驗，一組是任務數量相同時的路徑規劃，另一組是任務數量逐漸遞增時的路徑規劃，從兩個維度對比本文提出的算法與先路徑規劃后進行無沖突的時間窗排布算法[8-11]（后文簡稱對比算法）的結果差異。其中每個任務定義為一輛AGV從岸橋緩沖區車道運輸集裝箱到堆場作業車道，或者從堆場作業車道運輸集裝箱到岸橋緩沖區車道，AGV數量等于任務數量。

（1）任務數量相同

實驗設定一批任務包含40個子任務，即需要規劃40輛AGV分別從不同的堆場作業車道生成路徑至不同的岸橋緩沖區車道。隨機生成500萬批任務，根據每批任務中40個子任務的起點和終點位置計算路線的潛在沖突次數，采用聚類方法將每批任務的潛在沖突次數分成3類，得到的潛在沖突次數分類如表1所示：

表1 每批任務潛在沖突次數分類

根據表1中所述的潛在沖突次數的分類，每個類別分別取樣200批任務，計算每批任務中40個子任務的平均完成時間，實驗結果如圖7和圖8所示：

圖7 平均完成時間對比

圖8 平均等待次數對比

由圖7和圖8可以看出，任務數量相同，即AGV數量相同時，隨著潛在沖突數量的增加，子任務的平均完成時間和平均等待時間均逐漸增加。同時，本文算法的子任務平均完成時間和平均等待次數均小于對比算法，并且潛在沖突越多，效率提升越明顯。

（2）任務數量不同

針對每批任務分別包含10、20、30、40個子任務進行分類分析，每個類別分別取樣200批任務，計算每批任務的平均完成時間和平均等待次數，實驗結果如圖9和圖10所示：

圖9 不同任務數量平均完成時間對比

圖10 不同任務數量平均等待次數對比

由兩圖可以看出，當任務數量較少即AGV數量較少時，兩種算法的結果沒有明顯的差異，但是隨著任務數量的增加，本文算法相較于對比算法，任務的平均完成時間和等待次數均大幅減少，效率提升明顯。

4 總結

針對自動化碼頭的多AGV路徑規劃問題，本文結合時間窗理論和Dijkstra算法，提出一種動態路徑規劃算法，該算法旨在為AGV規劃一條連通任務起點和任務終點、無沖突且行駛時間最短的路徑。通過仿真實驗，將本文算法與先進行路徑規劃再進行時間窗排布的算法進行對比分析，結果驗證了本文算法能夠有效減少AGV的行駛時間，提升自動化碼頭的運行效率。

本文主要針對給定任務起點和終點，規劃一條可連通、無沖突且行駛時間最短的路徑，然而在實際工程中，載有集裝箱的AGV在與其他設備進行交互操作時對集裝箱的箱門方向有嚴格規定，因此如何在本文提出的算法的基礎上進一步規劃出一條滿足倒箱門策略的路徑將是今后的研究方向。

[1] Duinkerken M B, Evers J J M, Ottjes J A. Traces： Teaffic Control Engineering System A case-study on container terminal automation[J]. signal, 1999, 3(2)：

[2] Cheng Y L, Sen H C, Natarajan K, et al. Dispatching automated guided vehicles in a container terminal[M]// Supply chain optimization.New York Springer US, 2005, 355 -389.

[3] Moorthy R L, Hock-Guan W, Wing-Cheong N, et al. Cyclic deadlock prediction and avoidance for zone-controlled AGV system[J]. International Journal of Production Economics, 2003, 83(3)： 309-324.

[4] Lehmann M, Grunow M, Günther H O. Deadlock handling for real-time control of AGVs at automated container terminals[J]. Or Spectrum, 2006, 28(4)： 631-657.

[5] Kim K H, Jeon S M, Ryu K R. Deadlock prevention for automated guided vehicles in automated container terminals[M]//Container Terminals and Cargo Systems： Berlin Springer, 2007： 243-263.

[6] Klimm M, Gawrilow E, M?hring R H, et al. Conflict-free vehicle routing： load balancing and deadlock prevention[ROL].[2007-10-31] Technical Report, 2007. http：//w ww.matheon. de/preprints/5137_preprint- staticrouting. pdf, 2007.

[7] Jeon S M, Kim K H, Kopfer H. Routing automated guided vehicles in container terminals through the Q-learning technique[J]. Logistics Research, 2011, 3(1)： 19-27.

[8] 劉國棟,曲道奎,張雷. 多AGV調度系統中的兩階段動態路徑規劃[J]. 機器人, 2005, 27(3)： 210-214.

[9] 賀麗娜,樓佩煌,錢曉明,等.基于時間窗的自動導引車無碰撞路徑規劃[J]. 計算機集成制造系統, 2010, 16(12)：2630-2634.

[10] 喬巖,錢曉明,樓佩煌.基于改進時間窗的AGVs避碰路徑規劃[J].計算機集成制造系統,2012,18(12)：2683-2688.

[11] 胡彬,王冰,王春香,等.一種基于時間窗的自動導引車動態路徑規劃方法[J]. 上海交通大學學報, 2012, 46(6)：59-63.

[12] Duinkerken M B, Evers J J M, Ottjes J A. Improving quay transport on automated container terminals[C]//Proceedings of the IASTED International Conference Applied Simulation and Modelling (ASM 2002), Crete. 2002.

[13] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1)： 269-271.

Dynamic Routing of Automated Guided Vehicles with Time Window

Zhang Zhengwei1, Chen Bo1, Chen Weidong2
(1.Shanghai Zhenhua Heavy Industries Electric Co., Ltd, Shanghai 200125, China；2. Institute of Automation, Shanghai Jiaotong University, Shanghai 200240, China)

To solve the routing problem for the multiple Automated Guided Vehicles (AGV) in automated container terminals, an improved Dijkstra dynamic routing algorithm based on time window is proposed. Every AGV route is scheduled in order according to the priorities of the tasks and prior information of the map. Based on the planned routes, conflict-free, shortest-time and dynamic routing are achieved by updating the time window information for the planned routes. In comparison with the traditional method, the proposed algorithm can effectively decrease the conflicts between AGV routes and reduce their travel time, thereby the operating efficiency of the terminal can be enhanced.

Automated guided vehicles； Time window； Dynamic routing； Dijkstra algorithm； Automated terminal

TP391

A

1007-757X(2016)11-0046-04

20 16.09.27）

張崢煒（1983-），男，上海振華重工電氣有限公司，工程師，博士，研究方向：agv路徑問題等，上海 200125

陳 波（1988-），男，上海振華重工電氣有限公司，工程師，碩士，研究方向：agv路徑問題等，上海 200125

陳衛東（1968-），男，上海交通大學自動化系，教授，研究方向：移動機器人，多機器人學等，上海 200240