基于動態平衡策略的自動化碼頭多 AGV路徑優化算法研究

摘 要： "對自動化集裝箱碼頭AGV（automatic guided vehicle）自動運輸系統路徑規劃算法和港口布局進行深入研究之后，針對岸橋與堆場之間路徑規劃中可能出現的沖突以及任務分配不均等問題，提出了基于動態平衡策略的自動化碼頭多AGV路徑優化算法。通過對Dijkstra算法進行改進，在考慮路徑距離的基礎上，同時引入該路徑上預計通過的AGV數量，實現了路徑分配的動態平衡；提出了改進速度控制策略和重新規劃路徑控制策略，有效減少了沖突次數，且減少了道路堵塞率。建立了基于動態平衡策略與基于MAS（multi-agent system，MAS）的控制方式對比實驗，結果表明該算法能有效求解500個任務以上的大規模任務分配問題，并且顯著降低平均堵塞率0.000 8～0.005 5。此算法亦可應用于其他類型的碼頭布局中，進一步提高了碼頭水平運輸效率。

關鍵詞： "自動化集裝箱碼頭； 多自動導引車路徑優化；動態平衡；堵塞率

中圖分類號： "U116.2 """文獻標志碼： A

文章編號： "1001-3695（2022）02-010-0385-06

doi：10.19734/j.issn.1001-3695.2021.06.0268

Research on optimal algorithm of multi-AGV paths for automated "terminals based on dynamic balance strategy

Niu Yaqian， Yu Fang， Liu Jingwen， Yang Yongsheng

（Institute of Logistics Science amp; Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract： "After in-depth research on the path planning algorithm of the AGV transportation system and the port layout of the automated container terminal， in view of the possible conflicts and unequal task allocation in the path planning between the quay crane and the yard， this paper proposed an automatic terminal multi-AGV path optimization algorithm based on a dynamic balance strategy. By improving the Dijkstra algorithm， considering the distance of the path， and at the same time introducing the number of AGVs expected to pass on the path， which realized the dynamic balance of path allocation. By proposing an improved speed control strategy and a re-planning path control strategy， which effectively reduced the number of conflicts and the road congestion rate. This paper also established adynamic balance strategy and a MAS-based control method comparison experiment. The results show that the algorithm can effectively solve large-scale task assignment problems with more than 500 tasks and significantly reduce the average blockage rate 0.000 8～0.005 5. This algorithm can also be applied to other types of terminal layouts to further improve the horizontal transportation efficiency of the container terminal.

Key words： "automated container terminal; multi-AGV path optimization; dynamic balance; congestion rate

0 引言

全球貿易的迅猛發展使得港口在進出口貿易中的地位愈發重要，而自動導引車（AGV）已成為自動化集裝箱碼頭岸橋與堆場之間水平運輸作業的重要工具，極大地便利了自動化貨物裝卸。然而，由于堵塞、沖突導致的AGV死鎖問題，嚴重制約了AGV水平運輸的效率，影響著碼頭整體調度任務。因此，本文主要針對AGV在自動化碼頭運輸作業時出現的堵塞碰撞問題，通過對AGV路徑進行合理規劃，從而減小作業過程中設備等待時間，并解決各條路徑上任務分配不均等問題，提高碼頭的作業效率。

目前，已經有很多學者針對自動化碼頭中的AGV路徑規劃問題進行了研究，如何解決AGV路徑規劃中的沖突問題成為當前研究中的關鍵要素。張中偉等人［1］通過時間窗檢測沖突類型并實時更新自身優先級，避免低優先級的車輛因長時間得不到調度而引發新的沖突，從而減少整體沖突，提高整體工作效率。張素云等人［2］提出一種將AGV路徑容量、安全距離、行駛時間及行駛速度等因素相結合的多參數優化控制模型，通過改進速度控制策略來進一步解決沖突問題。Saidi-Mehrabad等人［3］提出了一個由Job-Shop scheduling problem（JSSP）和conflict-free routing problem（CFRP）結合組成的數學模型，并提出一個兩階段蟻群算法，使整個模型的最大完工時間最小，為AGV規劃無沖突路徑，從而完成整體進程。Xin等人［4］提出了一種層次控制體系結構，以集成交互機器的調度和AGV的軌跡規劃，通過在自動集裝箱碼頭中生成AGV自由范圍的無碰撞軌跡來確定AGV的無沖突軌跡。Miyamoto等人［5］利用局部/隨機的方法，合理分派任務，解決了AGV無沖突路徑問題。Zhong等人［6］以最小化AGV的延遲時間為目標，建立了一種基于路徑優化、綜合調度、沖突和死鎖的混合整數規劃模型，但其計算時間相對較長，不適用于動態實時調度。Zhong等人［7］通過 對岸橋與堆場之間的最短距離建模，AGV可以通過測試重疊率和沖突時間，從預先計劃的路徑中選擇最佳路徑，最終實現AGV無沖突路徑規劃。經建峰［8］利用多智能體AGV建立一種分布式結構模型來控制整體調度，實現無沖突路徑規劃。鄭重［9］為了實現大規模任務運輸時行駛距離與時間調度最優，發現現有的方法在緩解交通擁堵方面與現實還有很大的差距，所以提出一種AGV路徑優化與調度的方法，有效縮減了AGV行駛時間和距離，進一步提高了AGV周轉率，但同時AGV配置規模的逐漸擴大也對路徑規劃提出了越來越大的挑戰。Guo等人［10］采用基于多智能體系統的控制方式，考慮岸橋等待時間與行駛距離，減少了AGV任務運輸的平均堵塞率及平均等待時間，有效解決了沖突問題。馮海雙［11］采用A*算法來考慮AGV路徑規劃中可能的沖突情況，將等待的安全距離考慮在內，實現了AGV路徑的合理規劃。現如今，對AGV路徑優化問題研究取得了較大的進步，但隨著AGV數量的增加，沖突問題越來越明顯，有時會造成到達某一路徑的AGV數量集中，而其余道路相對空閑的情況，使得碼頭道路使用率無法實現均衡，這大大影響了碼頭水平運輸工作效率。因此，如何提高碼頭AGV作業運輸效率，合理規劃每條路徑，減小沖突成為當前自動化碼頭中亟待解決的首要問題。然而，現階段的研究在解決沖突問題時，大多是根據AGV當前運行狀態，設計分布式控制模型，在速度方面作出調整或不斷更新低優先級順序，從而避免沖突，并沒有在同一時間發出改變其他路線的指令，使同一時間內任務分配實現均衡，即沒有針對碼頭貨物運輸路徑上AGV數量動態平衡問題進行深入研究。加之自動化碼頭本身也存在許多不確定因素，不同任務情況下工作效率也不同。鑒于此，本文提出了基于動態平衡策略的自動化碼頭多AGV路徑優化算法，對Dijkstra算法進行改進，同時提出了改進速度控制策略和重新規劃路徑控制策略，可以使當前路徑沖突時自動更新其他路徑，避免任務均集中于某一條路徑，以此提高作業效率和道路利用率，便于自動化碼頭運輸系統整體調控，實現碼頭任務分配的動態實時規劃。

1 問題描述

1.1 問題提出

目前，AGV運輸系統已經廣泛應用于港口物流自動化運輸生產，隨著現如今集裝箱任務運輸規模及吞吐量的不斷擴大，AGV運輸作業過程中常常存在任務復雜、信息不完全、 環境動態等問題，每輛AGV也會成為彼此運輸過程中的障礙物，從而造成擁堵現象的發生。因此，將自動化碼頭運輸布局中各路徑上通過的AGV數量考慮在內具有重要意義，能夠進一步提高道路利用率，實現任務在各條路徑上的均衡分配。因此，合理的路徑規劃成為排除這些因素，影響運輸過程的關鍵問題。

隨著AGV數量的增加以及碼頭任務規模的不斷擴大，沖突問題越來越明顯，多AGV在碼頭自主運輸作業過程中可能會出現以下幾種類型的沖突：

a）相向沖突。如圖1所示，當AGV1和AGV2從相反的方向向同一節點行駛時，它們可能發生相向沖突，但是本模型中不涉及相向沖突的情況。

b）節點沖突。如圖2所示，當AGV1和AGV2在碰撞范圍內檢測到對方會同時到達同一節點時，將會發生碰撞的沖突。當三輛AGV同時到達同一節點時也會造成節點沖突。這時，本文規定距離該節點較近的AGV優先通行。

c）占位沖突。如圖3所示，AGV2對AGV1的前進造成阻礙時，形成占位沖突；這時規定占位車輛優先通行，從而解除沖突。

針對以上可能出現的沖突問題，需要對自動化碼頭中岸橋與堆場的整體結構布局進行深入分析考慮，熟悉AGV在整個運輸過程中的結構體系，進一步減少沖突，實現自動化碼頭中AGV運輸系統任務的合理分配及高效執行。另一方面，考慮AGV如何實現自身準確定位，并將自身坐標與狀態發送給計算機，系統判斷是否會發生沖突，在無沖突的情況下，將執行指令傳輸給AGV，既能減少碰撞的發生，也有助于解決各路徑任務分配不均的問題，有效適應碼頭復雜多變的工況，高效率地有序執行運輸任務。

本文針對以上可能出現的沖突類型，建立AGV路網模型進行動態規劃，在考慮路徑距離的基礎上，進一步考慮各路徑中預計通過的AGV數量，通過對各輛AGV速度與路徑等因素綜合考慮，最終解決沖突問題。

1.2 AGV路網模型建立

路徑規劃就是要從給定數字道路地圖中尋找出從起點到終點的最短路徑。應用到自動化碼頭環境中，則是讓AGV實時找到能夠完成任務的最優路線，從而實現整個運輸系統的最優控制。目前，最優路線問題已有許多成熟的算法，如Dijkstra算法等，它是一種解決路徑規劃問題的經典算法。將其基本思想應用于自動化碼頭環境中，能夠很好地解決碼頭任務運輸中存在的沖突問題。自動化碼頭中AGV路徑規劃系統是一個由岸橋、場橋等各個設備組成的復雜系統，各個設備之間相互關聯的連接點作為拓撲網絡的節點，各節點之間連線形成的邊作為可行路線，節點具有坐標的信息，各邊包含了距離和方向的信息，且所有邊的權值均為正值。因此，要建立帶權有向圖，計算出具有最小權值總和的路徑來完成任務。在此過程中，多AGV需要實時定位，將自身實時位置發送給系統，才能準確判斷當前路線是否合理。

本模型中設立了兩臺岸橋五個堆場的自動化碼頭布局進行模擬仿真。如圖4所示，為了減少車輛堵塞和死鎖發生的可能性，本文選擇了單向單車道路徑。這也是目前實際應用范圍最廣的一種路徑設置方式，即同一時間每條道路上多臺AGV的行駛方向是保持不變的。此種類型的系統有很強的擴展性，適用于各種規模的系統，實用性較強。

1.3 基本假設和符號規定

自動化碼頭環境下，一般有多輛AGV同時運行，為方便AGV無沖突路徑優化模型的建立，驗證實現路徑優化算法的優劣程度，展現其可實現性，提出以下假設：

a）每輛AGV型號規格相同；

b）一臺岸橋對應多個堆場箱區，可向不同堆場運輸集裝箱貨物；

c）環境對運輸作業造成的影響如天氣等不可抗拒因素不考慮在內，但路網中不同AGV之間成為彼此運輸中的障礙及構成某一道路沖突等因素必須考慮在內；

d）AGV在拿起和放下貨物的時間忽略不計；

e）碰撞點檢測，正常情況下，檢測到兩輛AGV到達同一節點而沖突時，計做一次碰撞，但當三輛AGV到達同一節點而沖突時，計做兩次碰撞；

f）所有AGV運行模式根據自動化碼頭實際模型而選擇直行或轉向，正常情況下AGV的速度保持恒定。

對AGV水平運輸作業進行路徑規劃時，構造賦權有向圖表示AGV路網布局，記做 G=（V，E， W ）。其中：V為路網中不同節點為元素的頂點集;E為邊的集合; W =（ω sk） n×n為鄰接矩 陣。若AGV在完成任 務s時未選擇第k條路徑，則ω sk=∞。決策變量為x smk，當x smk=1時，說明第m 臺AGV選擇第 k條路徑完成所分配的任務s，否則x smk=0。預 計通過的AGV數量動態顯示，當有車輛通過時自動加1，到達終點后自動減1，無通過數則為0。本文要解決的問題就是找出任意一條具有最小權的路，且達到路徑堵塞率最小化，從而進行最短路徑的實時規劃，為方便AGV路徑規劃問題分析及模型建立，引入以下基本符號，以便進一步表示： a 為檢測到沖突時AGV速度變化的加/減速度； c sk為完成任務s時路徑k中 多AGV發生沖突的次數； D tk為當前t時刻經過第k條路徑加權后得到的最終距離（k=1，2，3，4，…，K）；l 為AGV設備的自身長度； L 為AGV行駛過程中檢測碰撞的安全距離； L "為AGV行駛過程中檢測到沖 突之前預留減速的安全距離； M 為任務過程中AGV的數量， m= 1，2，3，4，…，M；M tk為當前t時刻第k條路 徑上預計通過的AGV數量； R 為AGV行駛過程中沖突距離檢測器的檢測范圍半徑長度； S 為AGV作業的總任務數， s=1，2，3，4，…，S；t sk 為AGV選擇第 k條路徑上完成任務s時因沖突而延遲的總時間；tm sk為第m 臺AGV選擇第 k條路徑完成任務s時因沖突造成的等待時間；t c1 為AGV作業過程中因發生沖突而減速的延遲時間； t c2 為AGV加速恢復到原速而延遲的時間； T 為AGV完成整個運輸任務所消耗的總時間； v 為AGV正常作業時的平均速度； v "0為AGV檢測到沖突時減速后的速度； β為 引入動態平衡量后影響實際路長的加權系數。

1.4 通信交互協議

AGV在整個運輸任務中處于不斷運動的狀態，且范圍較廣，加之其系統柔性較強，所以需要采用無線通信系統來實現AGV間的通信，如AGV與AGV之間、AGV與控制臺之間的通信交互協議。

通過考慮通信成本和任務運行的便捷性，最終選擇UDP無線網絡通信，此種通信在兩臺設備通信的時候，不需要建立邏輯連接就可以通行，效率很高。但需將它們的網絡IP地址設置在同一個IP網段內，使用無線Wi-Fi信號連接到路由器，從而實現不同AGV相互間的通信。

1.5 改進Dijkstra算法

Dijkstra算法是荷蘭數學家Dijkstra提出的適用于非負權值網絡的單源最短路算法，是目前求解最短路問題的理論上最完備、應用最廣的經典算法，在求解單AGV規劃問題時能快速找出最優路線，然而，多AGV路徑規劃算法復雜度較高。若在進行大規模任務時，只考慮路徑最短距離問題，而不考慮AGV實際運行情況，可能會造成大量擁堵現象的發生，比如多輛AGV同時進行任務時，均選擇第 k 條路徑而形成該條路徑任務擁堵，沖突頻繁，而其余路徑AGV運輸任務較少，另一方面也會使得道路利用率不高，運輸效率低下。因此，為了解決多AGV沖突問題，本文在Dijkstra算法的基礎上進行改進，在考慮路徑最短距離的同時，考慮當前路徑上預計通過的AGV數量，并不斷尋找最優的路徑，加權處理實現各條路徑AGV數量的均衡分配，即實現AGV運輸任務的合理管理與分配。使用本文設計好的路徑規劃算法進行路徑規劃，搜索路徑的算法流程如圖5所示，使其計算路程的方式與傳統算法相比發生改變，然后將合理的任務計劃命令下達給相應的AGV車輛完成運輸任務。同時接收AGV車輛上傳的實時信息，對AGV車輛進行實時監控，當檢測到沖突時，不同AGV之間進行協商，根據讓步策略規定距離沖突節點較近（若距離相同，優先掃描者優先）的AGV優先通行，從而避免沖突。

圖5所示搜索路徑算法流程的具體搜索步驟如下：

a）初始化剩余未找到距離最近路 徑集合B{}（即剩余路徑集合）、已找到最近路徑集合Y{}及最終路徑集合P{ }。

b）將所有路徑加入剩余未找到最近距離路徑集合 B {}。

c）將起點從剩余路徑集 合B{}中取出后加入集合Y{}，然后依次取出集合B{}中任意路徑k 1及已找到路徑集合Y{}中任意路徑k 2，將路徑k 1和k 2之間的距離（如果兩條 路徑不相連，則它們之間的距離為無窮大）加上兩者之間預通過AGV數與動態平衡量之積，找到加權計算后的最短距離。

d）判斷新計算的距離是否更小，若不是，則返回集 合Y{}中取下一條路徑k 。

e）判斷集 合Y{}與集合B{}是 否搜索完畢，若沒有，則分別返回集合中取出下一條路徑。

f）將 路徑k 2從剩余點集合B{}中移除并加入集合Y{}，記錄其距離。如果該路徑不是目標路徑，則繼續取出剩余路徑集合B{}中的路徑，重復以上流程尋找下一個最短距離；如果是目標路徑，則在已找到最近路徑集合Y{}中依次尋找出中間路徑，然后加入路徑集合P{}，結束 程序。

如果程 序運行結束仍未找到目標路徑，則表明路徑k 1和k 2間無法形成通路，路徑集合P{} 為空。

1.6 多AGV沖突協商策略

多AGV的協商策略主要是根據AGV與沖突節點的距離進行判斷，然后確定讓步次序，進一步來解決沖突。本文以減少沖突為原則，采用基于改進速度控制以及重新規劃路徑的方式作為多AGV的沖突協商策略。

1）基于改進速度控制的沖突協商策略 如圖6所示，每輛AGV設置一個以車身幾何中心為圓心，半徑為 R 的圓形臨界圈。臨界圈會隨著AGV的不斷移動而發生位移。在圖6（a）中，AGV1和AGV2同時向路口行駛，以 R 為半徑的臨界圈均在安全距離以外，所以兩車并不會檢測到沖突，可以保持正常速度繼續運行；當兩輛AGV同時保持正常速度，直到出現圖6（b）的情形時，兩個臨界圈相交，表明AGV1和AGV2將會發生沖突，兩者需要協商確定某一臺優先通行或者改變行駛速度繼續前進。

以檢測安全距離為標準，檢測到沖突的某臺AGV為例介紹解決沖突的過程：

a）當AGV檢測到自身安全距離與其余任務AGV相交時，AGV首先準確定位自身位置并記錄當前位置，以此作為彼此的協商對象。

b）AGV彼此向自身的協商對象發送位置信息，請求通過當前可能沖突的節點。

c）雙方根據自身位置協商處理，分別判斷與沖突節點的距離，確定距離較近的一臺AGV勻速通過當前沖突路段。

d）其他距離相對較遠的AGV檢測到檢測圈后開始減速，等到對方的AGV通過該節點，若減速到0還未解除沖突，則需要停車等待，之后再恢復原速通過該節點，從而解決沖突問題。

2）基于重新規劃路徑控制的沖突協商策略 自動化碼頭下多AGV協同作業是實現碼頭高效運輸的重要因素。當多AGV同時處理任務時，常常會發生多輛AGV搜索到同一最短路徑，造成某一條路徑任務頻繁，其他路徑使用率低，甚至發生死鎖的現象。為了解決這一沖突，本文引入動態平衡量，通過引入加權系數以及當前道路預計通過的車輛數加權處理，當遇到任務規模大且AGV數量密集的情況時，各條路徑能夠實現均勻分配，減少了不必要的沖突，提高了運輸效率。同時當某條路徑因沖突或其他環境因素造成堵塞而無法正常運行時，可屏蔽當前路段，使正在完成任務的其他AGV選擇其他最為合理的路徑完成任務。實現自動化集裝箱碼頭整個運輸系統的合理規劃，能夠有效應對碼頭任務復雜多變的狀況。

2 基于動態平衡策略的路徑優化模型

為了使多AGV運輸任務在不同時刻達到路徑分配的動態平衡，本文引入了動態平衡量，給AGV實時傳送合理的路徑信號。例如檢測到該條道路預計通過的AGV數量較多時，綜合考慮所完成任務量，若通過等待前面AGV依次通行后再行駛所消耗的時間大于直接選擇其他路徑行駛所用時間，則通過加權計算后發送改變其他路徑的信號；若等待時間相對選擇其他路徑所用時間較少，則不改變路徑，等待后再通行。這樣既減少了不必要的等待時間，也可以使到達堆場的各條路徑上AGV數量均衡分配。因此，以任務總完工堵塞率最小為目標函數，不斷減少AGV行駛過程中的沖突次數，提高碼頭自動化運輸效率。當AGV從岸橋出發到堆場選擇第 k 條路徑完成一次任務時，其最終的加權距離根據預計 通過AGV數的動態變化而發生改變，根據掃描順序，多AGV依次執行任務。在行駛過程中，若檢測到兩輛甚至三輛AGV同時到達某一節點時，則會檢測到碰撞，從而造成沖突，這時兩車之間的絕對距離小于兩者行駛過程中沖突距離檢測器的檢測范圍半徑之和，多輛AGV之間需要協商僅允許其中一輛通過。為了避免這一現象的發生，在監控管理系統中加一層控制，通過更改預計通過的車輛數，可以改變其余沖突AGV的行駛路徑，有利于實現各路徑動態平衡分配，減少沖突。因此，將AGV路徑規劃模型構建如下：

min "Z= ∑ S s=1 "∑ K k=1 t sk T """（1）

x smk= 1 第m臺 AGV選 擇第k條路徑完成接收的任務s 0 其他 """""（2）

ω sk= 弧e sk的權值 "e sk∈E ∞ 其他 """"（3）

∑ M m=1 x smk=1" s∈S ""（4）

∑ K k=1 x smk=1" s∈S ""（5）

D tk=ω sk+M tkβ ""（6）

T= ∑ S s=1 ∑ M m=1 ∑ K k=1 D tkx smk v """（7）

L≤2R ""（8）

L =（R+ v2－v2 0 2a ）× 2 """（9）

t c1= v－v 0 a － L "v """（10）

t c1≤t c2 ""（11）

t sk=∑ M m=1 tm skx smk+c sk（t c1+t c2） ""（12）

其中：式（1）為目標函數，即AGV完成總任務時延遲時間總和與總完成時間的比值；式（2）表示決策變 量x smk在不同情況下的取值，鄰接矩陣 W "的分量為式（3），即AGV行駛時所選擇的各路徑的權值;式（4）表明一個任務只能分配給一輛AGV;式（2）～（6）確定了AGV行駛過程中的距離估計函數，分別由基礎路徑和引入動態平衡量后的加權路徑兩部分求和共同構成，后部分表示加權路 徑，即為t時刻第k條路 徑上預計通過的AGV數與動態平衡量的乘積、任務的總完成時間即為完成所有任務時在狀態 t 時刻加權后的總距離與平均速度的比值，如式（7）所示；式（8）為檢測到碰撞沖突的安全距離，若不同AGV之間的距離小于 2R ，將會發生沖突；式（9）為AGV即將檢測到沖突時開始從 v減速到v 0的安全距離，那么延遲時間t c1即為加 減速行駛消耗的時間減去AGV以正常速度行駛所花費的總時間；在距離相同的情況下，AGV從減速到最終停止等待所消耗的時間與解決沖突后加速恢復到原速的時間相同，若AGV在速度減為0之前解決沖突，則減速所用時間相對較小，如式（10）（11）所示；式（12）為AGV完成總任務過程中在各條路徑上因等待、碰撞等沖突而延遲的時間總和，其中等待時間為AGV停止時刻與沖突解除之后AGV開始從0恢復到正常速度時兩者之間間隔的時間差。

3 算例分析

參照自動化碼頭實際運行模型，設計如圖7所示的單向單車道的路網結構；路網布局中，Q1、Q2為自動化碼頭中岸橋位置，Ⅰ～Ⅳ為堆場箱區，其余1～60為可通過的節點，節點連線形成可行路徑。AGV在此路網模型中模擬完成預定的運輸任務。采用C+ +語言編程，在Intel CoreTMi7-8550U CPU @ 1.80 GHz、8 GB內存的Windows 10計算機上實現。

3.1 多任務下AGV實驗與分析

一臺岸橋可作業于多個堆場箱區，本實驗以Q1、Q2兩個岸橋為起點，向Ⅰ、Ⅱ兩個堆場運輸集裝箱。設定基本參數，其中 v "0=4 m/s， a =2 m/s2，實驗規定總任務數為50個集裝箱，在 M=20、M=25、M=30三種車輛數情況下，分別分析改變動態平衡系數β后碰撞次數和完成時間的變化情況，從而得出影響路徑分配的最佳系 數，驗證AGV高密度運行情況下各條路徑如何達到動態均衡分配，并使得道路堵塞率呈現減小趨勢。

研究AGV數量分別 為M=20、M=25、M=30時，不斷改變動態平衡系數β 分別進行100次實驗求其平均，每輛AGV依次執行任務，且完成當前任務后可再次返回執行下一次任務，即每輛AGV可能進行多次任務，但每個任務只由一輛AGV完成，直到完成規定任務量為止。每次任務過程中AGV沖突時，根據沖突檢測距離確定讓步規則，當行駛過程中產生沖突且AGV在速度減為0之前沖突解除時，可以繼續加速恢復到原來的速度。最終實現多AGV高效運行。

通過編寫自動化集裝箱碼頭多AGV運輸系統的控制程序，使用Qt軟件進行仿真實驗驗證，其碰撞次數和完成時間的實驗結果如圖8、9所示。

從圖8、9中可以看出，在 β 不斷改變的前提下，不同實驗下AGV數量雖然不同，但總體碰撞次數以及完成時間曲線呈現相同的趨勢。引入動態平衡量后，雖然總的完成時間可能會有所增加，呈現逐漸上升后趨于平穩的趨勢，但綜合考慮碰撞次數和總完成時間可以看出，在 β=10時，該算法的實現效果最為理想，碰撞次數為最少，總完成時間相對穩定。衡量指標在β=10時的運行結果 如表1所示。

表1展現了不同數量AGV運行時， β =10時各參數數據，隨著AGV數量的增多，完成時間呈現總體減小趨勢，沖突相對較少，說明該算法模型在引入動態平衡量后完成自動化碼頭作業任務時的實用性相對較強。

本文以任務總完工堵塞率最小為目標，為了證明該算法模型對大規模任務情況下的實用性，分別 分析M=20、M=25、M=30三種情況在動態平衡系數β =10時向Ⅰ、Ⅱ、Ⅲ、Ⅳ四個堆場運輸500個集裝箱時堵塞率變化的情況，AGV作業過程中遇到的沖突根據1.6節提出的協商策略解決。因此，實驗仿真結果如圖10所示。

從圖10中可以看出，設置AGV數量為20時，平均堵塞率為0.018 2；AGV數量為25時，平均堵塞率為0.025 3；AGV數量為30時，平均堵塞率為0.032 3；隨著AGV數量的逐漸增多，堵塞率逐漸變大；但與任務數相對較小的情況相比，堵塞率是有所降低的，任務規模越大，堵塞率降低的程度越大。同時， "M=20、M=25、M=30時，任 務平均完成時間分別為2 330.91 s、 1 942.698 s、1 707.546 s，符合碼頭實際任務要求的完成時間，說明此模型亦適用于大規模任務運輸的情況，實現效果較為理想。

3.2 不同控制方式實驗對比及分析

基于動態平衡策略和基于多智能體系統（multi-agent system，MAS）的控制方式在不同車數情況下的堵塞率分布情況如圖11～13所示。基于MAS的控制方式主要是為一定數量的AGV分配起始點和終點后，根據每臺AGV的優先級確定避碰決策，優先級高的正常作業，否則需要等待讓行。文獻［10，12］采用基于MAS的控制方式，在減少AGV平均等待時間以及完成時間方面取得了明顯效果，但這種控制方式在進行大規模任務時經常發生沖突，甚至死鎖。針對AGV此種沖突情況，本文提出動態平衡策略，分別采用改進速度控制策略和重新規劃路徑控制策略解決，分析不同控制策略對AGV整體作業的影響。為了進一步說明此模型對大規模任務的實用性，選擇規模較大的任務數進行對比實驗，規定任務數為500，以20、25、30輛AGV分別進行仿真實驗100次為例，比較不同控制方式下堵塞率的變化情況。

從圖11～13中可以看出，隨著AGV數量的增多，實驗結果對比效果越來越明顯，本文所提出的基于動態平衡策略的控制方式在高密度任務運輸時堵塞率明顯降低。為了更加直觀地突出結果的優越性，表2顯示了兩種控制方式的平均完成時間對比情況。

從表2可以看出，在任務數為500的規模下，將兩種控制方式的堵塞率進行對比，基于動態平衡策略的控制方式明顯低于基于MAS控制方式，平均降低了0.000 8～0.005 5，隨著AGV數量的增多，實驗效果越來越明顯。同時從兩者平均完成時間的數據可以看出，當AGV數量增多時，基于動態平衡策略的完成時間明顯減少，且低于基于MAS控制方式。說明本文所建立的算法優化模型對于自動化集裝箱碼頭大規模任務運輸的情況具有較強的適用性。

4 結束語

本文分析了自動化碼頭集裝箱任務運輸中路徑規劃的沖突問題，以最小化堵塞率為目標，考慮任務碰撞次數、完成時間、運行速度以及沖突距離，設計了自動化碼頭多AGV路徑優化控制模型。通過考慮每條路徑中預計通過的AGV數量，實現了碼頭中各路徑分配的動態平衡，當某一道路因各種不確定因素而無法繼續執行任務時，可屏蔽當前路徑，AGV自動接收信號采用其他更優的路徑完成任務，有利于實現碼頭運輸系統整體動態調控；其次，采用改進速度控制策略，有效減少了AGV運輸過程中可能出現的沖突問題，減少了等待時間，重新規劃路徑控制策略有效減少了道路堵塞率。仿真結果表明，與基于MAS的控制方式相比，道路堵塞率明顯降低。在有效減少沖突的同時，使總任務的完成時間達到最小，并且隨著任務規模的擴大，路徑分配實時保持較優的狀態。另外，隨著AGV數量增多，平均完成時間逐漸減小，實驗效果較為理想，說明該模型對于解決港口大規模運輸任務情況下的路徑規劃問題也是適用的。

本文采用改進的Dijkstra算法，在實現自動化碼頭路徑規劃堵塞率最小化方面取得了明顯進展，且任務完成時間相差較小甚至不斷減小。今后，可以考慮將此模型應用于U型碼頭，合理規劃碼頭布局，進一步提高運輸效率，實現碼頭實時動態調度；亦可在算法層面提供其他的啟發式算法，如人工智能和強化學習等，可能會產生更好的結果;還可結合考慮AGV電量問題，綜合減小能耗排放，從而更符合當今綠色發展的時代要求。

參考文獻：

[1] "張中偉，張博暉，代爭爭，等.基于動態優先級策略的多AGV無沖突路徑規劃［J］.計算機應用研究，2021， 38 （7）：2108-2111.（Zhang Zhongwei， Zhang Bohui， Dai Zhengzheng， "et al . Multiple AGV conflict-free path planning based on dynamic priority strategy［J］. Application Research of Computers ，2021， 38 （7）：2108-2111.）

［2] 張素云，楊勇生，梁承姬，等.自動化碼頭多AGV路徑沖突的優化控制研究［J］.交通運輸系統工程與信息，2017， 17 （2）：83-89.（Zhang Suyun， Yang Yongsheng， Liang Chengji， "et al . Research on optimal control of multi-AGV path conflict in automated terminal［J］. Transportation System Engineering and Information ，2017， 17 （2）：83-89.）

［3] Saidi-Mehrabad M， Dehnavi-Arani S， Evazabadian F， "et al . An ant colony algorithm （ACA） for solving the new integrated model of Job-Shop scheduling and conflict-free routing of AGVs［J］. Computers amp; Industrial Engineering ，2015， 86 ：2-13.

［4] Xin Jianbin， Negenborn R R， Corman F， "et al . Control of interacting machines in automated container terminals using a sequential planning approach for collision avoidance［J］. Transportation Research， Part C： Emerging Technologies ，2015， 60 ：377-396.

［5] Miyamoto T， Inoue K. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems［J］. Computers amp; Industrial Engineering ，2016， 91 ：1-9.

［6] Zhong Meisu， Yang Yongsheng， Dessouky Y， "et al . Multi-AGV scheduling for conflict-free path planning in automated container terminals［J］. Computers amp; Industrial Engineering ，2020， 142 ：106371.

［7] Zhong Meisu， Yang Yongsheng， Sun Shu， "et al . Priority-based speed control strategy for automated guided vehicle path planning in automated container terminals［J］. Trans of the Institute of Measurement and Control ，2020， 42 （16）：3079-3090.

［8] "經建峰.基于智能體的多AGV自主控制系統研發［D］.南京：南京航空航天大學，2014.（Jing Jianfeng. Research and development of multi-AGV autonomous control system based on intelligent body［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2014.）

［9] 鄭重.自動化集裝箱碼頭AGV調度及路徑優化［J］.中國港口，2021（3）：34-36.（Zheng Zhong. Automated container terminal AGV scheduling and route optimization［J］. China Ports ，2021（3）：34-36.）

［10] Guo Kunlun， Zhu Jin， Shen Lei. An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals［J］. IEEE Access ，2020， 9 ：3326-3338.

［11] 馮海雙.AGV自動運輸系統調度及路徑規劃的研究［D］.哈爾濱：哈爾濱工業大學，2013.（Feng Haishuang. Research on AGV automatic transportation system scheduling and route planning［D］.Harbin：Harbin Institute of Technology，2013.）

［12] 陳曉利，韓鋒斌.基于多智能體的城市環道交通信號控制算法［J］.重慶大學學報，2021， 44 （1）：37-45，118.（Chen Xiaoli， Han Fengbin. Urban ring road traffic signal control algorithm based on multi-agent［J］. Journal of Chongqing University ，2021， 44 （1）：37-45，118.