張崢煒，陳波，陳衛(wèi)東

時間窗約束下的AGV動態(tài)路徑規(guī)劃

張崢煒，陳波，陳衛(wèi)東

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

自動導引車；時間窗；動態(tài)路徑規(guī)劃；Dijkstra算法；自動化碼頭

0 引言

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

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

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

徑上排出理想情況下的時間窗，然后對有時間窗重疊部分的路徑進行計算與更新。喬巖等[11]提出通過實時改變自動導引車通過節(jié)點的優(yōu)先級來調(diào)整自動導引車在相應節(jié)點的通過順序，從而實現(xiàn)多自動導引車動態(tài)環(huán)境下的路徑規(guī)劃。

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

1 問題描述

1.1 地圖描述

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

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

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

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

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

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

1.2 模型描述

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

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

圖2 簡化的地圖模型

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

圖3 對應的時間窗

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

（1）對于有k個任務需要規(guī)劃路徑，按照任務優(yōu)先級依次對k個任務進行路徑規(guī)劃，任務優(yōu)先級在任務下發(fā)時給出。

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

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

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

2 時間窗約束下的路徑規(guī)劃算法

2.1 算法實現(xiàn)步驟

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

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

圖4 AGV通行示意圖

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

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

圖5 相鄰點

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

圖6 路徑規(guī)劃結(jié)果

3 算法仿真驗證

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

（1）任務數(shù)量相同

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

表1 每批任務潛在沖突次數(shù)分類

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

圖7 平均完成時間對比

圖8 平均等待次數(shù)對比

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

（2）任務數(shù)量不同

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

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

圖10 不同任務數(shù)量平均等待次數(shù)對比

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

4 總結(jié)

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

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

[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調(diào)度系統(tǒng)中的兩階段動態(tài)路徑規(guī)劃[J]. 機器人, 2005, 27(3)： 210-214.

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

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

[11] 胡彬,王冰,王春香,等.一種基于時間窗的自動導引車動態(tài)路徑規(guī)劃方法[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

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