基于時空網絡的自動化集裝箱碼頭自動化導引車路徑規劃

高一鷺，胡志華

（上海海事大學物流研究中心，上海201306）（*通信作者電子郵箱zhhu@shmtu.edu.cn）

0 引言

自動化導引車（Automated Guided Vehicle，AGV）是自動化集裝箱碼頭（Automated Container Terminal，ACT）水平運輸的主要設備［1］，承擔岸邊與堆場之間集裝箱的搬運任務，與岸橋和場橋互相協調共同完成碼頭的裝卸作業。AGV 路徑是指搬運任務作業過程中，AGV 從任務起點（Origin，O）到終點（Destination，D）的行駛軌跡，而ACT 連續作業下，多輛AGV同時共享道路網絡并行完成大量裝卸任務，因此AGV 行駛軌跡可能發生交叉或重疊從而導致AGV 發生碰撞、擁堵等沖突問題。AGV 路徑沖突若處理不當，則導致AGV 單次作業時間延長，作業成本增加，同時增加岸橋或場橋的等待時間，延長ACT 整體裝卸時間，從而降低其運作效率并大幅度增加碼頭作業成本。因此考慮沖突規避的多AGV 路徑規劃是ACT 運作管理的關鍵問題，相關的模型與算法研究為碼頭的運營和管理提供重要的理論依據［2-4］。

沖突規避的AGV 路徑規劃問題已成為當前研究的重點。Lyu 等［5］將帶時間窗的Dijkstra 算法嵌入遺傳算法中，搜索最短路徑同時檢測多車輛的碰撞情況；Fazlollahtabar等［6］建立混合整數規劃模型并提出兩階段優化方法（搜索解空間和尋找最優解）來規避AGV 之間的沖突；Nishi 等［7］提出動態環境中雙向AGV 系統調度和路徑沖突規避的Petri網分解方法，整個Petri 網分解為任務子網和AGV 子網并在AGV 子網中嵌入避免死鎖的方法；Miyamoto 等［8］建立混合整數規劃模型，并提出局部隨機搜索方法求解容量限制的AGV 系統調度和沖突規避的路徑規劃問題。以上研究同時考慮AGV 路徑規劃以及任務調度問題，通過調整AGV 任務作業序列以規避路徑沖突。然而，大部分情況下AGV任務執行順序是確定的。

在AGV 任務作業順序確定條件下，較多文獻關注于路徑搜索方法：Ma?opolski 等［9］用矩陣描述運輸系統布局，將AGV的運動視為以固定的平均速度從矩陣到矩陣的運動，進而提出一種防止AGV碰撞和死鎖的新方法；Antakly等［10］利用時間Petri 網進行建模并提出三階段的啟發式算法，通過對AGV 施加適當的延遲以避免與其他AGV 發生碰撞；Mohammadi 等［11］提出一種基于仿真的高級柔性工藝模型，通過預見機制以動態預防AGV的碰撞和死鎖；Fanti等［12］通過區域控制分散協議協調AGV 運動以規避碰撞；郭興海等［13］考慮動態環境下根據障礙物的運動情況，提出感應轉向算法使AGV 規避障礙物；Nishi 等［14］考慮AGV 加速或減速條件下沖突規避的路徑規劃問題，建立連續時間模型并提出基于列生成的啟發式算法；劉二輝等［15］提出路徑微調算子使路徑片段變短以避開障礙物，實現基于遺傳算法的動態路徑規劃；曹小華等［16］結合圖論提出一種基于頂點屬性和實時位置信息的沖突預測方法，建立混合整數規劃模型并提出一種適用于多AGV 系統避碰決策優化的改進粒子群優化算法；李軍軍等［17］通過分析路段與節點沖突問題建立混合整數規劃模型并提出一種誘導蟻群粒子群算法，在算法的狀態轉移規則中，增加誘導因子來引導AGV 規避沖突；鄭延斌等［18］針對多Agent 路徑規劃問題，提出一個基于蟻群算法及博弈論的兩階段路徑規劃算法，為解決多Agent 之間的碰撞，利用博弈論構建多Agent 之間的動態避障模型并利用虛擬行動法來求解多Nash 均衡的選擇問題。以上研究通過設計和調整AGV 行駛路線或者采取等待措施以規避路徑沖突，然而，大部分沖突規避的路徑規劃研究主要面向生產制造系統。

自動化碼頭與制造系統相比，運輸區域面積更大且無障礙物，交通規則更靈活，并且AGV 尺寸更大且數量更多，碼頭全自動連續作業要求AGV 與岸橋和場橋交互作業誤差盡可能小，因此對AGV 路徑進行合理規劃具有一定難度。Xin等［19］提出一種層次控制體系結構以滿足交互設備的集成調度，并且按照調度的總體圖序列，通過順序求解混合整數規劃問題以獲得滿足AGV沖突規避的軌跡規劃；Yang等［20］建立一個雙層編程模型并提出基于道路堵塞預防規則的雙層遺傳算法，以解決碼頭起重機、自動導引車和堆場起重機的集成調度問題；Xin 等［21］提出一種兩級能量感知方法，通過高級控制器解決控制問題以確定各個AGV 的碰撞規避軌跡；Li等［22］提出AGV 系統流量控制算法，通過減少每個區域的最小允許面積來提高工作區的利用率并設計一種緊急交通控制方案，以避免因車輛故障而導致的車輛碰撞和死鎖。然而目前，自動化碼頭AGV路徑規劃相關研究較少。

上述文獻提出的算法大多數在規劃路徑時設計沖突預測機制以檢測沖突，發現沖突后則返回路徑規劃或者調度問題求解中，然而算法并沒有實時檢測沖突路段進行一次路徑規劃，因此增加了計算的復雜性。本文研究自動化碼頭AGV 路徑規劃問題，在AGV 作業任務順序確定條件下，通過構造AGV 的時空網絡以實時反映AGV 狀態信息和檢測沖突路段，并以任務完工時間最小為目標，對實際路段擁堵情況建立模型和設計時空網絡算法，優先調整路線以規避路徑的碰撞和擁堵。

1 問題描述

ACT 由岸邊、AGV 和堆場三個作業區組成，布局如圖1所示。其中，AGV 作業區包括海陸兩側裝卸區、緩沖區和行駛區，海側裝卸區和行駛區下設有能控制小車轉彎方向的車道。AGV 作業可分為進口箱和出口箱作業。以進口箱作業為例說明其作業流程。1）在海側裝卸區的起始位置（O點），岸橋放置集裝箱到AGV 上，AGV 完成裝載；2）AGV 轉彎進入緩沖區進行排序，根據規劃的路徑進入指定的行駛區車道，行駛到陸側裝卸區的目標位置（D點）；3）場橋卸載AGV 上的集裝箱移至堆場箱區存儲，AGV 完成一次裝卸作業。對于出口箱作業任務，則反之。一輛AGV 同一時刻只能作業一個任務，只有完成當前的作業任務才可以執行下一個任務，同一個任務在作業過程中不能中斷。另外，AGV 行駛過程需遵守港區局部物流交通系統中的交通規則，例如轉彎、擁堵停車和讓道等，當某一道路擁堵時AGV可在緩沖區等待。

圖1 自動化集裝箱碼頭布局Fig.1 Layout of automated container terminal

通常，將一輛AGV 從任務的O點到D點的行駛路徑設為兩點之間的最短路徑，并且假定該最短路徑上的所有路段都是通暢可行的［23］，然而該做法沒有考慮AGV 在實際路段中的運行軌跡以及運行過程中的實時動態干涉，導致AGV 根據規劃路徑進行作業時產生沖突。路徑沖突情況包括碰撞和擁堵，在圖2中，舉例說明AGV 沖突問題。任務1 和任務2 同為進口箱作業，任務1和任務2的OD點分別為O1D1、O2D2，實線表示小車實際經過的路線，虛線表示計劃行駛但未行駛的路線。圖2（a）展示了碰撞的發生情況，執行任務1 的AGV 與執行任務2 的AGV 在不同時刻出發卻在同一時刻到達點A，發生碰撞導致任務執行失敗。圖2（b）展示了擁堵的發生情況，執行任務1和執行任務2的2輛AGV 會在同一時刻到達A點，但為避免碰撞，執行任務2 的AGV 行駛到緩沖區B點時停車等待，造成擁堵現象。AGV 發生碰撞將直接導致設備損壞，大幅度增加成本，設備停留在路段中占用路段資源，可能與即將行駛進路網的AGV 發生二次碰撞，并且處理碰撞事故所需時間和人力成本較高；等待是避免碰撞的常用手段，但AGV減速及加速過程所消耗的電力成本較高，并且AGV 等待減少了可用的道路資源，道路會因為AGV 的等待而出現擁堵，嚴重時會導致整個路網癱瘓導致ACT 被迫停止運作。所以，當路段本身成為臨界資源時，AGV 對路段具有獨占性，因此，考慮AGV 在不同時刻在路網上的狀態是判別碰撞和擁堵的前提條件。

圖2 AGV在路網上的沖突情況Fig.2 Conflicts of AGVs in road network

在AGV 的行駛過程中，從當前時刻的位置出發，下一時刻可選的到達位置通常有多個；在各個不同位置上的下一個可能到達的位置又是不同的，因此，建立在道路網絡背景下隨時間演變的時空網絡。利用AGV 在不同時刻可能到達的不同位置，從而刻畫出AGV 從任務起點出發的一個可行的帶有時間和位置標簽的網絡，路徑規劃則是在該網絡中選擇一條完工時間最短的路徑。本文在ACT 背景下建立AGV時空網絡，在時空網絡中規劃AGV 最短路徑，以任務完工時間最短為目標，建立數學模型并設計時空網絡算法，使規劃路徑規避碰撞并緩解擁堵。

2 數學模型

路徑優化基礎模型如M1所示，其相關符號定義如表1所示。

模型M1的目標函數（1）為最小化時間成本；約束（2）和（3）表示任務作業的先后關系，AGV 從起始位置O開始作業，作業完成后回到終點位置D；約束（4）是網絡流量平衡約束，任意節點的出度等于節點的入度。

M1不考慮AGV 在實際路段中的運行軌跡，并假定路徑之間不會互相干涉。實際上，M1規劃出的當前路徑可能產生一些時刻下的不可行路段，若執行后續任務的AGV 占用不可行路段將產生沖突。為了規避沖突，保證AGV 在運行過程中路徑的暢通，根據上述界定的2 種沖突情況（碰撞和擁堵）進行建模。建模思想為：通過更新路網中新任務開始時刻下的可用節點集合實時規避該路徑可能出現的碰撞以及緩解路網的擁堵；更新方法為：在時空網絡下剔除當前任務規劃下的不可用路段。值得注意的是，每一次規劃新任務路徑前，由于當前任務的路徑產生了一些時刻下的新不可行路段，因此每個節點的碰撞和擁堵狀態是任務開始時刻計算出來的并且在每個新任務開始前會進行更新。對于執行某具體任務的AGV 而言，需要做出以下決策：1）經過的路段；2）經過該路段的時間；3）該路段是否可用（不存在沖突情況）。建立模型M2，其相關符號定義如表2所示。

表1 模型M1相關符號定義Tab.1 Related symbol definitions of model M1

表2 模型M2相關符號定義Tab.2 Related symbol definitions of model M2

建模的具體說明如下：1）定義道路網絡Net=(N，E)，其中，將道路網絡離散化為間隔是單位時間1 的網絡，即Tl=1，l∈E。2）定義離散時間集合T。擴 展Net定 義NetT=(NT，ET)，其中NT=，對于a∈NT，a[1]和a[2]分別取路網節點和時間；，對 于e∈ET，e[1]和e[2]分別表示第一個和第二個節點的狀態。3）考慮路網中部分節點在特定時間被占用的問題，引入表示不可用節點，據此得到不可達集合，，并更新擴展網絡為。

模型M2剔除了時空網絡中因路徑沖突而產生的不可行路段，在更新后的新時空網絡中規劃最優路徑，目標函數（5）為最小化時間成本；約束（6）和（7）表示在可行的路網中任務作業的先后關系，AGV從起始位置O開始作業，作業完成后回到終點位置D；約束（8）是可行路網流量平衡約束，任意節點的出度等于節點的入度。

3 算法設計

3.1 時空網絡求解算法

時空網絡記錄AGV 在不同時刻能到達的多個位置及其可行的路段，故AGV 的時間狀態信息體現在網絡節點上。構造時空網絡的目的是讓AGV 在所有可行路段中選擇一條路徑，在規避沖突下完成從起點到終點的任務。對于時空網絡的結構而言，不同的道路交通規則下時空網絡表現出不同的形態，而同一道路交通規則下的時空網絡在更新時不改變其形態，每個網絡節點仍記錄AGV 的時間狀態信息。因此，時空網絡是空間網格在時間維度的迭代，而空間網格是港區道路網絡依據單位時間距離的離散化。具體而言，對每一個路段，依據單位時間距離進行近似等分得到路段上的節點，這些中間節點僅僅與相鄰節點以單位時間連通。依據模型M2的定義，離散后得到的道路網絡節點記為N，時空網絡的節點記為NT，在路段上單位時間連通的節點構成ET中的元素，不可用節點集合標記為-NT，并據此得到-ET。

基于以上的概念和模型，設計基于時空網絡的算法——TS-SP（Tempo-Spatial Shortest Path），TS-SP 算法由算法1 和算法2組成。其中，算法1通過生成時空網絡，更新時空網絡，以及調用M2計算最短路徑獲得給定一個OD的AGV 路徑；算法2調用算法1，通過迭代策略求解OD任務序列中的所有O和D配對的路徑。算法2 根據已獲得的路徑更新不可用節點集合-NT（步驟5）以實時檢測沖突，而算法1則利用不可用節點集合更新時空網絡（步驟2）以實時規避沖突并進行一次路徑規劃（步驟3），因此針對多個OD任務，在時空網絡上運用最短路徑算法，根據路徑結果更新時空網絡，并通過迭代最終獲得滿足避碰和緩解擁堵條件的路徑規劃，而M2的求解過程能夠通過拓展基本最短路徑算法（如Dijkstra 算法）實現。時空網絡算法流程如圖3 所示。算法開始，依據時間順序從任務集中選取任務執行。針對每一個當前任務，首先生成時空網絡，并依據當前的不可用節點集合更新時空網絡，接著在更新后的時空網絡中采用Dijkstra算法計算任務最短路徑，并依據當前任務的最短路徑結果更新不可用節點集合。判斷任務集是否為空：任務集不為空則選擇下一個任務執行；任務集為空則說明已完成所有任務，算法結束。

圖3 時空網絡算法流程Fig.3 Flowchart of tempo-spatial network algorithm

算法1 單個OD任務最短路徑優化算法（Single_OD_SP）。

輸入 任務的起點O和終點D、開始時間t0、調度周期總時長T；所有節點的集合N，不可用節點集合-NT；

步驟1 生成時空網絡NetT=(NT，ET)：NT={(i，t)|i∈N，t∈T}；

步驟2 更新時空網絡：

步驟3 采用M2計算最短路徑：

對Pe中的節點，取a[1]=O作為開始節點，依次順序插入后續節點得到Path

算法2 OD任務序列最短路徑優化算法。

輸入 任務集合OD={(O，D)}、開始時間t0、調度周期總時長T；所有節點的集合N，不可用節點集合；

輸出 路徑集合Paths={(O，D，Path)}。

步驟2 取(O，D) ←OD[i]。

步驟3 求最短路徑：

步驟4 更新路徑集合：Paths←Paths∪{(O，D，Path)}。

步驟6i←i+1，如果i＜|OD|，轉到步驟2；否則終止。

3.2 算法舉例

為了分析算法的機理，在圖4中，設計例證說明算法求解最優路徑及其更新過程。設節點集合N={1，2，…，9}，離散時間集合T={0，1，2，…}，任務集合I={i，j}，任務i，j的OD位置及出發時間分別為(1，9，0)，(2，9，1)。AGV行駛過程中從一個節點出發只能到達其右邊或其下邊相鄰的節點，如節點2 可到達節點3 或節點5，并且經過每一條短邊的時間成本記為1個單位時間。AGV 在時空網絡中行駛對應時間和空間位置要素，如執行任務i的AGV 在0時刻從節點1 出發，此時AGV狀態記為(1，0)。

算法開始，在圖4（a）中，任務i的時空網絡如式（9）、（10）。此時不可用節點及邊集合，產生一條最優路徑Pathi，如式（11）。在圖4（b）中任務j的時空網絡如式（12），（13）。此時，若規劃任務j在時空網絡下的最優路徑Pathj，如式（14），則兩個任務所規劃的路徑在節點5存在沖突，即執行任務i的AGV 和執行任務j的AGV 在T=2時刻同時到達節點5，如圖4（c）。因此，為了任務i和任務j的路徑均可行，首先依據Pathi確定不可行節點與路段集合，如式（15）、（16），更新任務j的時空網絡，，如式（17）、（18），再規劃路徑，如式（19），以此消除沖突，如圖4（d）。然而，任務j更新后的路徑和任務i的路徑，在到達終點的時刻相等，即AGV 在執行卸載（或裝載）集裝箱操作時發生沖突。因此，使任務j在節點6 等待1 個單位時間，得到Path″j，如式（20）。至此，任務i和任務j的路徑規劃完成，在規避所有沖突的條件下得到最優路徑，Pathi，j，如式（21）。算法結束，其機理得以驗證。

圖4 算法優化路徑的過程Fig.4 Process of optimizing path planning by the algorithm

4 計算實驗與結果分析

4.1 算例設計

參照上海洋山四期自動化集裝箱碼頭的工藝布局設計算例，首先說明自動化碼頭的設計參數，如表3 所示，然后，設置規則并生成算例。考慮兩種類型的任務，即進口箱作業和出口箱作業。同一岸橋或同一堆場釋放一個待AGV運輸的進口箱或出口箱時間間隔分別服從均勻分布U(100，120)、U(40，60)。以進口箱作業為例，說明算例的生成規則。每個進口箱任務包括5 個參數：開始時間t0、作業岸橋Qi、裝卸車道Li、目標箱區Bi以及目標車位Pi，其中，依據表3的參數設置，Qi、Li、Bi、Pi分別服從均勻分布U(1，2)、U(1，4)、U(1，3)、U(1，5)。根據作業任務數量，分別產生5組不同規模的算例R10、R50、R100、R200、R400。其中，算例R10見表4。

表3 參數設置Tab.3 Parameter settings

表4 算例集R10Tab.4 Dataset R10

4.2 實驗設置

AGV時空網絡由Python3.7 平臺的NetworkX 工具包編譯實現，網格精度設置為6 m ×6 m。算例設計3 組實驗以驗證模型和算法的有效性。實驗假設：1）AGV 數量滿足裝卸任務需要；2）岸橋和場橋的裝卸效率足夠高，沒有出現延遲或等待現象。實驗中采用的基本最短路徑算法選取Dijkstra 算法。值得注意的是，AGV 路徑規劃問題有2個特征，分別為車輛碰撞和路網擁堵，時空網絡算法則是能夠避免路徑之間的碰撞并緩解路網擁堵，因此依據該問題特征，實驗對比了2 種不同路徑規劃求解策略，即基本最短路徑求解策略和停車等待求解策略，據此設計了2 個對比求解算法，分別為算法P、SP，算法特征如表5所示。P算法求解過程中不更新時空網絡，因此不能規避路徑中可能發生的沖突；SP 算法則更新時空網絡，檢測沖突路段，小車按原最短路徑行駛，在緩沖區停車等待以規避碰撞；TS-SP算法通過更新時空網絡，檢測沖突路段，并且在更新后的時空網絡中規劃路徑以緩解路網的擁堵。

表5 算法特征Tab.5 Algorithm features

實驗一 模型與算法的避碰效果驗證。分別考慮進口箱作業和出口箱作業下，采用P算法和TS-SP算法求解不同規模的算例，計算兩種算法規劃出的路徑下小車發生的碰撞次數。依據AGV 實際尺寸，實驗設置AGV 之間的安全距離為12 m，計算不同規模算例下執行每一個任務的AGV 與路網中其他執行任務的AGV 之間的最小相對距離，其中任務數量用N表示。

實驗二 模型與算法的緩解擁堵效果驗證。分別考慮進口箱作業和出口箱作業下，采用SP 算法和TS-SP 算法求解不同規模的算例，計算小車總行駛路程、小車總行駛時間、最小完工時間、小車總延誤時間、延誤任務數量以及延誤任務數量占比，分別表示為S、T、M、W、K和G。以算例R400為例，與P 算法求解得的最小任務完成時間相比，計算SP 算法和TS-SP 算法求解下執行每個任務的AGV 到達時間差。又因路網中的擁堵現象表現為小車在行駛過程中因避免碰撞而發生等待行為，故以任務延誤時間比上最小任務完成時間表示路網平均擁堵度［24］，其中，N為任務數量。

實驗三 算法性能驗證。分別考慮進口箱作業和出口箱作業下，采用P 算法、SP 算法和TS-SP 算法求解不同規模的算例，在Win10-PC、i7CPU、內存8 GB 的計算環境下各算法的計算時間，保留4位有效數字。

4.3 結果分析

1）實驗一結果與分析。用P 算法和TS-SP 算法求解的碰撞次數以及AGV最小相對距離分別如表6、圖5所示。

表6 P和TS-SP算法求解下碰撞次數Tab.6 Number of collisions in P and TS-SP algorithms

圖5 AGV最小相對距離圖Fig.5 The minimum relative distances of AGVs

由表6可知，P算法求解下小車在任務規模較大時碰撞次數較多，如進口箱作業N=400時，并且碰撞次數隨著任務規模的增加而增加，如出口箱作業。而在時空網絡算法下，無論任務的規模多大，AGV 之間碰撞次數均為0。該結果說明時空網絡算法規劃的路徑互不干涉，AGV 之間無碰撞從而保證AGV安全作業。

由圖5 可知，P 算法求解下部分執行任務的AGV 發生碰撞，AGV 最小相對距離則為0，在未發生碰撞的情形下，仍有部分執行任務的AGV 最小相對距離小于安全距離，如出口箱作業算例R100時。TS-SP 算法求解下，無論任務的規模多大，執行每個任務的AGV 最小相對距離都大于或等于安全距離。AGV 在實際行駛時由于車身長度因素會對不止一個路段具有獨占性，從而對路網中其他AGV 行駛產生影響，時空網絡算法充分考慮到AGV 車身長度因素使得AGV 最小相對距離始終大于安全距離，結果說明該算法下AGV 行駛過程中是安全的，提高了AGV運行效率。

2）實驗二結果與分析。用SP算法與TS-SP算法求解任務集結果、AGV 到達時間差以及路網平均擁堵度分別如表7、圖6、7所示。

由表7 可知，1）進口箱作業下，SP 算法和TS-SP 算法求解同一規模算例下AGV 總行駛時間與最小完工時間均相同，任務總延誤時間隨著任務規模的增加而增加。同等規模下，因TS-SP 算法為避免小車發生碰撞而選擇規劃新路徑，故TS-SP算法求解得總行駛路程大于SP 算法求解得總路程，但TS-SP算法求解得總延誤時間小于SP 算法求解得總延誤時間，在較大規模下，TS-SP 算法求解得延誤任務占比數值較小，如N=400時。2）出口箱作業下，兩種算法求解同一規模算例下AGV最小完工時間相同。TS-SP算法求解得總路程大于SP算法下的總路程，但SP 算法下AGV 總行駛時間則較大，如N=200時。任務總延誤時間隨著任務規模的增加而增加，同等規模下，TS-SP 算法求得任務總延誤時間小于SP 算法求得總延誤時間；并且當任務規模較大時，TS-SP 算法能有效地縮短總延誤時間，如N=400時。TS-SP 算法能有效減少延誤任務數量，降低延誤任務占比數值，如N=200時。

表7 SP和TS-SP算法求解結果比較分析Tab.7 Comparison of SP and TS-SP solving results

由圖6（a）可知，進口箱作業下，TS-SP算法與SP算法求解400 個任務時，大部分執行任務的AGV 到達時間差為0，少部分AGV到達時間差大于0且集中出現在任務規模較大時。在求解第227 個任務時，TS-SP 算法下AGV 到達時間差較大，其他情況下AGV 到達時間差數值相等。SP 算法下平均時間差為3.56 s，TS-SP 算法下平均時間差為3.67 s。由圖6（b）可知，出口箱作業下，TS-SP算法與SP算法求解結果中有較多執行任務的AGV 到達時間差大于0 且分布較為均勻。其中，大部分AGV 到達時間差數值相等，少部分到達時間差數值不等，SP 算法求解得AGV 到達時間差較大的任務個數為9，TSSP 算法求解得AGV 到達時間差較大的任務數量為3。SP 算法下平均時間差為3.3 s，TS-SP 算法下平均時間差為3.18 s。值得注意的是，TS-SP算法下AGV到達時間差大于0是由于新規劃的路徑長度較長，AGV 行駛時間長且行駛過程中也可能出現等待行為；而SP 算法下的時間差大于0是由于AGV 在原路徑行駛過程中發生等待行為。該結果表明，大部分任務下，時空網絡算法下AGV 依據新規劃的路徑行駛的時間與停車等待策略下依據原路徑行駛的時間相等；少部分任務下，時空網絡算法減少了任務完成時間。

由圖7 可知，同一作業模式下TS-SP 算法比SP 算法求解得路網平均擁堵度低，當任務規模較大時，路網平均擁堵度較低，如出口箱作業N=400時。由于出口箱作業數量多且間隔時間短，出口箱作業下路網平均擁堵度比進口箱作業下路網平均擁堵度高，如N=200時，進口箱作業下擁堵度為0.089%，而出口箱作業下擁堵度則為0.630%。該結果說明時空網絡算法能有效緩解路網的擁堵，減少AGV 停車等待成本，AGV的暢通行駛提高了碼頭運作效率。

圖6 AGV到達時間差Fig.6 AGV arrival time difference

3）實驗三結果與分析。用P 算法、SP 算法和TS-SP 算法求解不同規模的算例的計算時間如圖8所示。

由圖8 可知，進口箱作業和出口箱作業下P 算法、SP 算法和TS-SP 算法求解不同規模算例的計算時間趨勢相同，以進口箱作業模式為例，說明計算時間增長趨勢。如圖8（a）所示，進口箱作業下，計算時間隨任務規模的增大而增大，在任務數量小于等于200時，隨任務數量增大，計算時間平穩增長；當任務數量為400時，計算時間大幅增長，尤其表現為SP 和TSSP 算法，增長幅度分別為319.86%和347.31%；當任務數量大于等于100時，TS-SP 算法計算時間比SP 算法計算時間長，這是因為TS-SP算法考慮了問題的2個特征（碰撞及擁堵），而SP 算法僅考慮了車輛避碰條件。同等任務規模下，完成出口箱作業的計算時間比完成進口箱作業的計算時間要長，如當N=400時，出口箱作業下TS-SP 算法計算時間為71.870 1 s，而進口箱作業下的計算時間為52.842 s。計算結果說明，TSSP 算法可以在有效的計算時間內完成較大規模任務集計算。

圖7 路網平均擁堵度Fig.7 Average congestion rate of road network

圖8 3種算法求解不同規模的算例的計算時間對比Fig 8 Calculating time comparison of three algorithms for sloving different scale examples

以上實驗結果表明，時空網絡算法能有效求解沖突規避的大規模路徑規劃問題，減少任務延誤時間，使進出口集裝箱滿足岸邊或堆場堆存計劃安排，大幅度降低自動化碼頭運營的時間成本以及其他人力、物力成本，并且算法可以考慮AGV 車身長度對路網的影響，更加符合自動化碼頭實際規劃情況。

5 結語

本文針對自動化集裝箱碼頭AGV 行駛過程中路網實際可用路段資源有限的特征，以任務完工時間最短為目標，建立了路徑優化的整數規劃模型，為求解模型，設計了基于時空網絡的啟發式算法。算例分析結果表明，該算法能完全避免路徑之間的碰撞，與停車等待策略下的路徑優化算法相比，該算法能降低路網平均擁堵度，最大降低程度為0.68%。與已有研究相比，本文主要工作包括：1）所建模型考慮了路網中路段的時變沖突并以沖突規避為約束優化AGV 作業路徑；2）提出基于時空網絡的迭代求解策略，提高ACT 作業系統優化的精細化程度。本文考慮了沖突規避的AGV 作業路徑優化問題，而對AGV 能耗約束、任務送達時間窗約束沒有考慮，進一步研究還可以考慮基于時空網絡的AGV 調度問題，拓展時空網絡算法的研究方向。