考慮沖突和擁堵的自動導引車調度與路徑規劃協同優化

范厚明，牟爽，岳麗君

考慮沖突和擁堵的自動導引車調度與路徑規劃協同優化

范厚明，牟爽，岳麗君*

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）（ ? 通信作者電子郵箱yuelj11@163.com）

針對自動化集裝箱碼頭自動導引車（AGV）調度與無沖突路徑規劃問題，提出了AGV沖突擁堵解決策略以生成無沖突路徑。首先，考慮堆場緩沖支架的容量，運行路徑無擁堵、節點無沖突約束，以最大完工時間最小、AGV總行駛時間最短為目標建立兩階段混合整數規劃模型；其次，設計改進的自適應遺傳算法、基于沖突擁堵解決策略的迪杰斯特拉算法求得AGV調度方案與無沖突路徑。算例分析結果表明：改進的自適應遺傳算法相較遺傳算法平均求解時間降低了13.56%，且目標函數平均差距率為9.01%；基于沖突擁堵解決策略相較停車等待策略使得水平運輸區擁堵度降低67.6%，AGV等待時間減少66.7%。可見，所提算法求解質量高且速度快，同時驗證了所提策略的有效性。

自適應遺傳算法；自動化集裝箱碼頭；自動導引車調度；無沖突路徑規劃；沖突和擁堵

0 引言

集裝箱吞吐量的不斷增長和集裝箱船舶大型化的快速發展對集裝箱碼頭裝卸作業效率提出了更高的要求。近年來，隨著自動化技術的不斷應用，我國集裝箱碼頭的智能化程度顯著提高，特別是自動化集裝箱碼頭的裝卸效率得到大幅度提高。自動導引車（Automated Guided Vehicle， AGV），是自動化集裝箱碼頭中關鍵的水平運輸工具，承擔著從岸橋到堆場的集裝箱卸船運輸和從堆場到岸橋的集裝箱裝船運輸的重要任務，其合理的調度以及高效穩定的運行對于提高碼頭的作業效率有非常重要的意義。在實際作業環境中，常配置充裕的AGV以避免岸橋和場橋等待，在多臺岸橋同時作業時，易發生AGV沖突和擁堵問題。因此，合理為各AGV分配作業任務的同時并優化各AGV行駛路徑，不僅能夠減少作業過程中設備間相互等待時間，而且能夠解決沖突、擁堵等問題，提高碼頭作業效率和AGV運輸效率，對碼頭的實際運營有著重要的指導作用。

目前，已有學者對AGV調度問題進行了大量研究，AGV通常與碼頭其他設備協同調度，如Bae等［1］首先提出作業面調度模式，以AGV總行駛距離最短為優化目標研究作業面調度模式，并設計啟發式算法求解；基于作業面調度模式，梁承姬等［2］提出了一種岸橋動態調度與AGV分組作業面的調度模式，建立了岸橋與AGV聯合調度優化的模型，并通過遺傳算法求解該模型；田宇等［3］針對自動化碼頭雙循環AGV和場橋集成調度問題，以船舶完工時間最小為優化目標建立數學模型，并設計了基于啟發式遺傳算法進行求解；范厚明等［4］考慮能耗因素，分別以岸橋能耗最小和AGV運輸過程中能耗最小為目標建立兩階段優化模型，分別設計了枚舉法和改進遺傳算法進行求解。以上將AGV與岸橋或者AGV與場橋協同調度研究，缺少對岸橋、AGV和場橋三者集成調度的研究。也有學者對不同策略下AGV調度進行研究，如Li等［5］研究了多標準調度策略下自動化集裝箱碼頭AGV調度，基于不同的場景對問題仿真模擬得到AGV的調度方案；韓曉龍等［6］通過eM-Plant建立了集裝箱碼頭的仿真模型，設計了不同AGV調度策略下和不同AGV數量配置下的模型并進行仿真實驗，驗證不同AGV調度策略對碼頭作業效率的影響。通過模擬碼頭真實作業環境，對比分析不同AGV調度策略對作業效率的影響，然而仿真模擬只能最大限度模擬真實作業環境，未能考慮實際作業其他相關因素對調度的影響。隨著研究的不斷深入，也有少量研究考慮實際作業過程中的相關因素對AGV調度的影響，如電池電量約束［7-8］、緩沖支架容量限制［9-10］等。

目前關于AGV路徑規劃的研究大部分針對柔性制造系統［11-13］，自動化集裝箱碼頭與柔性制造系統相比，AGV數量多且運輸行駛區無障礙，碼頭連續作業要求AGV在運輸過程中盡可能減少岸橋和場橋的相互等待時間，因此對AGV路徑規劃具有一定難度。高一鷺等［14］以任務完工時間最短為目標，提出了一種基于時空網路的路徑優化方法。由于自動化集裝箱碼頭AGV數量多，AGV行駛過程中不可避免產生碰撞，在AGV路徑規劃中沖突問題一直是研究的熱點，卻較少研究AGV在行駛中產生的擁堵問題，曾慶成等［15］提出了AGV動態路徑規劃策略，建立考慮擁堵的多AGV路徑優化模型，設計了基于動態路徑規劃策略的多種群蟻群算法求解。當產生沖突擁堵時，如何解決AGV沖突問題已經成為當前研究AGV路徑規劃的重點，仲美穌等［16］提出了交通虛擬環島策略，建立了集裝箱碼頭的仿真模型；Xin等［17］提出了一種分層控制方法用于生成AGV行駛路徑，以碼頭設備作業時間最短為目標構建了混合整數規劃模型。

也有少量的文獻研究AGV調度與路徑規劃問題，絕大部分是針對柔性制造系統進行的研究［18-21］，僅有少數針對自動化碼頭進行研究，Yang等［22］以總任務最大完工時間最小為目標構建了雙層規劃模型，設計了基于避碰規則的雙層遺傳算法進行求解；Zhong等［23］考慮了自動化碼頭集成調度、路徑優化、沖突和死鎖等問題，以AGV延遲時間最小為目標建立了混合整數規劃模型，并設計了啟發式遺傳粒子群（Heuristic Genetic Algorithm-Particle Swam Optimization， HGA-PSO）混合算法進行求解。

通過對現有研究分析發現：1）現有研究較少考慮岸橋、AGV和場橋三個不同設備之間的相互關聯和制約協同關系，大多數是對碼頭一種或者兩種設備進行研究和優化調度，對AGV調度與路徑規劃的研究較少；2）現有對AGV調度的研究較少考慮實際作業過程中緩沖支架對各個設備之間的影響，現有對AGV路徑規劃的研究較少考慮路徑擁堵問題；3）目前所采用的算法大多數在解決AGV沖突時又重新回到任務調度和路徑規劃，解決沖突的策略主要有停車等待和重新規劃路徑，重新規劃路徑不僅會增加了計算時間而且會產生新的沖突，增加了研究的復雜性。

因此，本文針對AGV調度與路徑規劃問題，考慮堆場緩沖支架容量，AGV運行路徑無擁堵、節點無沖突約束，建立了兩階段混合整數規劃模型，并設計兩階段混合優化算法分階段對其求解。

1 問題描述

在靠港船舶裝卸作業過程中，AGV調度的核心目標是每輛AGV按時到達岸橋和堆場作業區，若AGV到達岸橋或場橋作業區的時刻早于計劃作業時刻，那么AGV等待；否則，岸橋或場橋等待。作業面調度模式下AGV的調度過程如圖1所示，岸橋1將卸船箱放至空載AGV，AGV沿著線路1將卸船箱運送到箱區2，作業完的空載AGV可以沿著線路3到達岸橋3作業下一卸船箱，也可以沿著線路2到達箱區3作業下一裝船箱，將裝船箱從箱區3運送到岸橋2。通過優化AGV的空載時間降低AGV的配置數量，有利于減小AGV路徑沖突和擁堵的概率。

圖1　碼頭布局和AGV運輸流程示意圖

與傳統碼頭不同，自動化碼頭堆場前設置緩存區，緩沖支架安裝在箱區前，用于裝卸集裝箱，當作業進口箱時，若AGV到達場橋下的時刻早于場橋計劃作業時刻，AGV無需等待場橋作業完上一個集裝箱，AGV直接將進口集裝箱卸到緩沖支架，待場橋作業完上一集裝箱后直接從緩沖支架提取進口箱；作業出口箱時，若AGV到達場橋下的時刻晚于場橋計劃作業時刻，場橋無需等待AGV到達作業，場橋直接將出口集裝箱卸到緩沖支架上，待AGV到達箱區后直接從緩沖支架提取出口箱。考慮緩沖支架容量優化AGV調度，有利于降低各AGV在箱區的等待時間，也可進一步降低岸橋延遲時間。

不同集裝箱所屬船舶貝位和堆場存放位置不同，不同AGV運輸集裝箱的行駛路徑也可能不同。在實際作業過程中，多AGV間沖突和擁堵會增加其運輸時間，若因沖突和擁堵導致AGV晚到達岸橋或場橋，可能會導致集裝箱實際裝卸完工時間晚于裝卸時間要求，船舶無法按時離港。因此，AGV路徑規劃的核心目標是為每一輛AGV規劃出一條無沖突擁堵的最短行駛路徑。

由于碼頭水平運輸區各車道的長度和容量固定，需同時作業任務量較多時，多輛AGV可能會在同一時間在同一路段向同一方向行駛而產生相向沖突，如圖2（a）所示；可能會在同一時間經過同一節點而產生節點沖突，如圖2（b）所示；也可能會在同一路徑上出現擁堵的情況，如圖3所示。本文研究單向導引路徑，即不考慮圖2（a）所示的相向沖突，僅針對圖2（b）所示的節點沖突和圖3所示的路徑擁堵情況進行研究。

圖2　沖突示意圖

圖3　路徑擁堵示意圖

2 模型建立

2.1　模型假設

本文研究基于以下假設：

1）岸橋和場橋作業單個集裝箱的時間服從均勻分布；

2）待作業集裝箱位置及裝卸順序已知，岸橋、箱區的位置已知，AGV運輸起點為出口箱所屬堆場和作業進口箱的卸船岸橋，終點為存儲進口箱的堆場和作業出口箱的裝船岸橋；

3）所有待作業集裝箱箱型一致，所有的進口箱運送至指定堆場，所有出口箱運送至船上指定箱位。

2.2　第一階段AGV調度優化模型

1） 集合、參數及狀態變量如下。

2） 決策變量如下。

3） 數學模型如下。

第一階段模型目標函數為：

約束條件為：

式（1）為目標函數，表示最大完工時間最小化，即岸橋提起最后一個裝船集裝箱或放下最后一個卸船集裝箱的時刻；式（2）表示在每輛AGV只能完成一個集裝箱任務；式（3）和式（4）表示一個集裝箱由且僅由一輛AGV運輸；式（5）和式（6）表示一個集裝箱由一臺岸橋或場橋作業；式（7）表示更新后的岸橋計劃作業時間；式（8）表示作業卸船箱的岸橋的實際作業時間；式（9）表示作業裝船箱的岸橋的實際作業時間；式（10）表示岸橋實際作業時間與計劃作業時間之間的關系；式（11）表示同一岸橋處理的相鄰兩個任務的實際作業時間的間隔要滿足計劃作業時間的間隔；式（12）表示AGV運輸裝船箱時在緩沖支架的實際作業時刻滿足時間窗約束；式（13）表示AGV運輸卸船箱時在緩沖支架的實際作業時刻滿足時間窗約束；式（14）表示AGV在場橋下取裝船箱時滿足時間窗約束；式（15）表示AGV在場橋下取卸船箱時滿足時間窗約束；式（16）表示AGV提取卸船集裝箱時在岸橋下的等待時間；式（17）表示AGV交付裝船集裝箱時在岸橋下的等待時間；式（18）表示AGV交付卸船集裝箱時在場橋下的等待時間；式（19）表示AGV提取裝船集裝箱時在場橋下的等待時間；式（20）和式（21）表示AGV送完裝船集裝箱后，開始作業下一個裝船集裝箱或卸船集裝箱的時間約束；式（22）和式（23）表示AGV送完卸船集裝箱后，作業下一個裝船集裝箱或卸船集裝箱的時間約束；式（24）和式（25）分別表示變量類型和取值范圍。

2.3　第二階段AGV調度優化模型

1） 集合、參數及狀態變量。

2）決策變量。

x為第輛AGV從節點到節點時為1，否則為0。

第二階段模型目標函數為：

約束條件為：

式（26）為目標函數，表示最小化AGV的總行駛時間；式（27）和式（28）表示完成每個任務的AGV在每個節點至多行駛一次，避免AGV路徑重疊，造成道路死鎖；式（29）表示一個集裝箱由且僅由一輛AGV運輸；式（30）表示路徑網絡為單向導引路徑。

兩輛AGV通過同一節點，如圖5所示。

圖4　AGV路段示意圖

圖5　AGV節點沖突示意圖

式（33）表示AGV在路徑1和2中存在的相同節點；式（34）和式（35）表示AGV在相同節點的時間檢測，若兩臺AGV通過相同節點的時間差小于AGV1順利通過并與AGV2保持安全距離的時間，則說明發生沖突。

式（36）表示AGV路徑中重疊路段的檢測；式（37）表示路段e可容納AGV的數量，Round（）為向下取整函數；式（38）表示AGV在路段e上任意時刻的車輛數不能超過路段容量。

3 模型求解

本文針對建立的兩階段優化模型，設計改進的自適應遺傳算法（Improved Adaptive Genetic Algorithm，IAGA）求解AGV調度問題，設計基于沖突擁堵解決策略的迪杰斯特拉（Dijkstra）算法求解AGV的無沖突路徑規劃問題。將Dijkstra算法與IAGA相結合，設計滿足約束條件的編碼規則和符合優化目標的適應度函數，求得各AGV的調度方案和無沖突最短路徑，如圖6所示。

圖6　改進的自適應遺傳算法與迪杰斯特拉算法流程

3.1　第一階段模型求解

第一階段模型是研究AGV調度問題為NP-hard問題，在現有研究中，遺傳算法廣泛應用于AGV的調度研究中。傳統的遺傳算法收斂速度慢且容易陷入局部最優，因此本文根據問題特點設計IAGA對模型求解，具體步驟如下：

1） 染色體編碼。

本文算法采用實數編碼方式，以便于解碼操作和基因操作。染色體長度為待卸集裝箱數量，即作業任務數，因此編碼長度由集裝箱數量決定，染色體生產中每條染色體長度均為。初始化時在染色體每個基因位上設置為［1，］（為AGV數量）的隨機數，代表AGV編號。如圖7所示的染色體，假設待卸集裝箱數量為10，由3輛AGV運輸集裝箱，AGV1按3-6-7的作業順序，AGV2按5-8的作業順序，AGV3按1-2-4-9-10的作業順序。

圖7　染色體編碼示意圖

2） 修復。

為滿足種群多樣性，通過隨機方式產生初始種群。由于每個AGV至少分配到一個任務的約束，隨機方式產生初始解會存在不滿足約束的情況，需要對不合理基因位上的解進行修復，如圖8所示，使其滿足約束。在式（2）～（6）的約束條件下生成一定數量的個體，其中染色體每個基因位上隨機生成［1，］的AGV編號，所有個體構成初始種群。

圖8　染色體修復示意圖

3） 適應度函數。

目標函數的計算流程如圖9所示。

圖9　目標函數求解流程

鑒于本文模型以總任務最大完工時間最小化為目標，算法中取目標函數的倒數為適應度函數，適應度值高的個體直接進入下一代，具體適應度函數如下：

其中：f為個體的適應度；（）為個體的目標函數值。

4）選擇操作。

在遺傳算法運行中，如果只使用輪盤賭選擇算子而不用精英保留策略，交叉、變異會破壞適應度好的染色體，有可能會失去優良的染色體。精英保留策略能夠將適應度最大的染色體保留下來，防止被交叉、變異破壞，使得整個種群向全局最優解方向進化。

5）交叉與變異。

遺傳算法收斂速度和搜索能力受到交叉概率和變異概率的影響，二者的取值至關重要。為提高算法的性能，本文借鑒文獻［24］的交叉概率和變異概率公式，引入自適應交叉概率和自適應變異概率，具體表達如式（40）～（41）：

本文采用兩點交叉的方式如圖10所示，在染色體中設置兩個交叉點，相互兩個交叉點之間的部分，產生新的染色體，同時結合自適應交叉概率，既能保證交叉操作的全局搜索能力，又能保證優良染色體最大概率地保留到子代中。

變異與交叉類似，如圖11所示，在染色體中設置兩個不同基因位置，交換這兩個位置上的基因，即能變異得到新染色體，同時結合自適應變異概率，既能充分發揮變異操作的局部搜索能力，又能避免遺傳算法陷入局部最優。

圖10　染色體交叉操作示意圖

圖11　染色體變異操作示意圖

3.2　第二階段模型求解

第二階段模型是AGV路徑規劃模型，模型求解主要分為三個部分：

1）利用Dijkstra算法計算各AGV完成任務所遍歷的節點，得到各AGV的最短行駛路徑，在最短路徑有數條的情況下，依據路徑轉折數確定優先級來生成最短路徑。

2）檢測各AGV是否發生沖突和擁堵，檢測流程如圖12、13所示。

圖12　節點沖突檢測流程

圖13　路徑擁堵檢測流程

具體步驟如下：

步驟1 輸入每輛AGV的路徑，中包含節點集合和路段集合，根據式（31）～（32）計算AGV經過每個節點和路段的時間。

3）基于沖突擁堵解決策略為各AGV規劃出一條無沖突最短行駛路徑，有效解決AGV沖突擁堵，減小沖突和擁堵概率。

4 算例分析

本文選取不同規模算例，將IAGA與遺傳算法（GA）進行比較驗證本文算法的有效性。對比考慮沖突、擁堵解決策略和不考慮沖突、擁堵解決策略的AGV路徑規劃的效果，驗證了本文基于沖突、擁堵解決策略的有效性。本文算法編程采用Matlab R2018b，操作系統為Windows 10，電腦內存為8 GB，CPU為Intel i7-7700M，主頻3.60 GHz。

4.1　參數設置

1）以圖1的碼頭布局為模型，參考文獻［25］中的AGV路網布局，如圖14所示。圖中一共有69個節點以模擬磁釘點，線段為有向線段，車道長200 m，岸橋作業區寬10 m，緩沖行駛區寬60 m，堆場行駛區車道寬為10 m。

圖14　自動化集裝箱碼頭路徑網絡布局示意圖

Q1～Q3是岸橋所在位置，B1～B6是箱區所在位置。其中B1～B2為進口箱區，B3～B6為出口箱區，占據的節點編號如表1所示。

表1　岸橋及箱區的節點編號對照

2）模型參數取值為：=21～300；=3～6；=3；=6；=6；=6；=5 m/s；=5 m；H=5 m。

3）岸橋作業完上一個出口箱繼續作業下一個出口箱的作業時間為α=U（40，60） s；岸橋作業完進口箱作業下一個進口箱的作業時間為α=U（40，60） s；岸橋作業完出口箱作業下一個進口箱的作業時間為α=U（60，80） s；岸橋作業完進口箱作業下一個出口箱的作業時間為α=U（20，40） s。

4）場橋作業時間為β=U（80，120） s。

5）本文算法參數設置如下：種群規模=100，最大迭代次數=200；自適應參數設置P1=0.6，P2=0.01，P1=0.01，P2=0.002。

4.2　算法驗證與結果分析

表2　算例對比結果

此外，由算例1、2、4和6，算例3、5、7、9、11和13，算例8、10、12和14可知，在相同設備配置的情況下，增加集裝箱任務數量會導致目標函數值增加，即最大完工時間增加；由算例2和3，算例4和5，算例6、7和8，算例8和9，算例9和10，算例11和12，算例，13和14可知，增加AGV的數量會導致目標函數值減小。由此可知，合理配置AGV的數量能夠提高碼頭的裝卸效率。

4.3　策略有效性驗證

為驗證本文第二階段沖突、擁堵解決策略的有效性，以算例3為例，對42個集裝箱任務、6輛AGV進行實驗，任務分配如表3所示。

表3　任務分配

1）AGV調度結果。

采用Matlab進行編程求解，求得最大完工時間為988 s，AGV調度方案如表4所示。

表4　AGV調度結果

2）路徑規劃結果分析與對比。

本算例根據圖15自動化集裝箱碼頭路網，通過Dijkstra算法得出AGV總行駛時間為2 438 s，完成任務的行駛路徑如表5～10所示。

表5　AGV1完成任務的路徑

表6　AGV2完成任務的路徑

表7　AGV3完成任務的路徑

表8　AGV4完成任務的路徑

表9　AGV5完成任務的路徑

表10　AGV6完成任務的路徑

圖15顯示了不考慮沖突、擁堵解決策略的各AGV行駛路徑和作業時間，如AGV2開始作業第1個時間段是0 s～28 s，將裝船箱8從箱區B4送至岸橋Q3，在自動化集裝箱碼頭路網從節點64運送至節點13；第2個時間段是147 s～197 s，AGV2完成上一裝船箱8直接在岸橋Q3作業下一卸船箱10，將卸船箱從岸橋Q3送至箱區B2，從節點13運送至節點60；第3個時間段是197 s～227 s，AGV2完成卸船箱10后前往下一卸船箱13所在岸橋Q1，從節點60到節點3；第4個時間段是285 s～307 s，AGV2作業卸船箱13從岸橋Q1送至箱區B2，從節點3到節點60；第5個時間段是307 s～335 s，AGV2作業完卸船箱13從箱區B2作業下一卸船箱18所在岸橋Q2，從節點60到節點8；第6個時間段是340 s～376 s，AGV2作業卸船箱18從岸橋Q2到箱區B2，從節點8到節點60；第7個時間段是376 s～394 s，AGV2作業完卸船箱18從箱區B2作業下一裝船箱28所在的箱區B4，從節點60到節點64；第8個時間段是410 s～440 s，AGV2作業裝船箱28從箱區B4到岸橋Q2，從節點64到節點8；第9個時間段是568 s～596 s，AGV2作業完裝船箱28從岸橋Q2開始作業下一裝船箱33所在的箱區B5，從節點8到節點67；第10個時間段是596 s～646 s，AGV2作業裝船箱33從箱區B5到岸橋Q1，從節點67到節點3。

圖15　不考慮沖突、擁堵因素的AGV行駛路徑

AGV在行駛過程中發生的路徑擁堵已在圖15中用黑圈示出，節點沖突用黑框示出，時間表如表11、12所示。

由表11、12可知：AGV2與AGV5分別在節點67、66、65、64、63發生沖突，AGV2與AGV6在節點3發生沖突，AGV4與AGV6在節點60發生沖突，AGV1與AGV4分別在節點64、63、51、37、22、7、8發生沖突，AGV1與AGV6分別在節點64、63發生沖突；AGV4與AGV6分別在路段67-66、66-65、65-64發生擁堵，AGV2與AGV5分別在路段67-66、66-65、65-64發生擁堵。通過停車等待策略解決沖突擁堵，AGV等待時間為27 s，水平運輸區擁堵度為1.11%。

基于本文沖突擁堵解決策略，AGV2與AGV5分別在177 s、176 s通過節點67開始發生沖突，AGV2在節點67停車等待1 s；AGV2與AGV6在285 s通過節點3發生沖突，AGV2在節點3停車等待2 s；AGV4與AGV6在353 s通過節點60發生沖突，AGV4在節點60等待2 s；AGV4與AGV6在393 s通過路段67-66開始發生沖突、擁堵，AGV4在節點67停車等待2 s；AGV1與AGV4和AGV6分別在400 s、399 s通過節點64開始發生沖突，AGV1在節點64停車等待2 s，AGV總停車等待9 s，水平運輸區擁堵度為0.36%。

本文沖突擁堵解決策略比停車等待策略解決沖突擁堵所用時間更短，采用本文沖突擁堵解決策略水平運輸區擁堵度降低67.6%，AGV等待時間減少66.7%。

考慮沖突、擁堵因素，基于沖突擁堵解決策略下AGV行駛路徑如圖16所示。

對比圖15、16可知，基于沖突擁堵解決策略能為各AGV規劃出一條無沖突最短行駛路徑，采用本文基于沖突擁堵解決策略能有效解決節點沖突，降低了擁堵程度，避免重新進行任務調度和路徑規劃而產生的新沖突和擁堵。

圖16　考慮沖突、擁堵因素的AGV行駛路徑

表11　AGV節點沖突時間表

表12　AGV路段擁堵時間表

5 結語

本文針對自動化碼頭多AGV調度和路徑規劃問題展開研究，分析自動化集裝箱碼頭實際作業流程并結合自動化碼頭路徑網路空間布局結構，考慮緩沖支架容量約束以及沖突和擁堵等，以最大完工時間最小為第一階段優化目標、AGV總行駛時間最短為第二階段優化目標建立兩階段混合整數規劃模型。針對該模型，設計了IAGA求解第一階段模型的AGV調度方案，采用精英保留和輪盤賭相結合的選擇操作，保證了算法的有效收斂，同時結合自適應交叉概率和自適應變異概率，既能保證遺傳算法的全局搜索能力，又能避免遺傳算法陷入局部最優；設計了基于沖突擁堵解決策略的Dijkstra算法求解第二階段模型，可得調度方案下各AGV的無沖突路徑。算例分析結果表明，IAGA比GA求解速度快且質量高；與停車等待策略相比，本文策略能降低水平運輸區擁堵度，降低程度為67.6%。

本文的研究較符合實際自動化集裝箱碼頭船舶裝卸過程，但還存在一些不足，在實際作業過程中未考慮不確定因素，在實際作業過程中岸橋和AGV的故障、AGV電量不足等不確定情況也會影響裝卸作業時間，這些都有待于未來進一步的研究。

[1] BAE J W， KIM K H. A pooled dispatching strategy for automated guided vehicles in port container terminals［J］. Management Science and Financial Engineering， 2000， 6（2）：47-67.

[2] 梁承姬，申哲，張悅. 干擾約束下考慮分組作業面的岸橋AGV聯合調度［J］. 計算機工程與應用， 2020， 56（18）：254-261.（LIANG C J， SHEN Z， ZHANG Y. Quay crane and AGV joint scheduling with grouping work surface under interference constraints［J］. Computer Engineering and Applications， 2020， 56（18）：254-261.）

[3] 田宇，周強，朱本飛. 自動化集裝箱碼頭雙循環AGV與場橋的集成調度研究［J］. 交通運輸系統工程與信息， 2020， 20（4）：216-223， 243.（TIAN Y， ZHOU Q， ZHU B F. Integrated scheduling of dual-cycle AGV and yard crane at automated container terminal［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（4）：216-223， 243.）

[4] 范厚明，郭振峰，岳麗君，等. 考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化［J］. 自動化學報， 2021， 47（10）： 2412-2426.（FAN H M， GUO Z F， YUE L J， et al. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving［J］. Acta Automatica Sinica， 2021， 47（10）： 2412-2426.）

[5] LI Z H， YU T， CHEN Y X， et al. Multi-objective optimization dispatching strategy for wind-thermal-storage generation system incorporating temporal and spatial distribution control of air pollutant dispersion［J］. IEEE Access， 2020， 8： 44263-44275.

[6] 韓曉龍，樊加偉. 自動化港口AGV調度配置仿真分析［J］. 重慶交通大學學報（自然科學版）， 2016， 35（5）：151-154， 164.（HAN X L， FAN J W. Analysis of AGV dispatching and configuration simulation of automated container terminals［J］. Journal of Chongqing Jiaotong University （Natural Science）， 2016， 35（5）：151-154， 164.）

[7] 吳洪明，鄒夢艷. 考慮電池電量約束的自動化碼頭AGV調度［J］. 起重運輸機械， 2021（3）：47-52.（WU H M， ZOU M Y. AGV scheduling of automated terminal considering battery power constraints［J］. Hoisting and Conveying Machinery， 2021（3）：47-52.）

[8] 鄭亞紅，徐玖龍，謝淳. 自動化集裝箱碼頭AGV換電管理與調度優化［J］. 武漢理工大學學報（交通科學與工程版） ，2021， 45（1）：1-6.（ZHENG Y H， XU J L， XIE C. Electricity exchange management and scheduling optimization of AGV in automated container terminal［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2021， 45（1）：1-6.）

[9] 文家獻，魏晨，尹宇起，等. 考慮堆場緩沖區容量的ASC與AGV集成調度［J］. 計算機工程與應用， 2020， 56（11）：238-245.（WEN J X， WEI C， YIN Y Q， et al. Integrated scheduling of ASC and AGV considering block buffer capacity［J］. Computer Engineering and Applications， 2020， 56（11）：238-245.）

[10] 程聰聰，梁承姬，李曄. 自動化集裝箱港口考慮AGV伴侶的AGV調度優化問題研究［J］. 計算機應用研究， 2019， 36（8）：2349-2354.（CHENG C C， LIANG C J， LI Y. Study on AGV scheduling with considering AGV partner in automated container ports［J］. Application Research of Computers， 2019， 36（8）：2349-2354.）

[11] 鄒裕吉，宋豫川，王馨坤，等. 多目標自適應聚類遺傳算法求解無路徑沖突的AGV與加工設備集成調度問題［J/OL］. 中國機械工程. （2021-04-28） ［2021-05-10］.http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.1022.002.html.（ZOU Y J， SONG Y C， WANG X K， et al. Multi-objective adaptive clustering genetic algorithm to solve the AGVs and machine integrated scheduling problem without path conflict［J/OL］. China Mechanical Engineering. （2021-04-28） ［2021-05-10］.http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.1022.002.html.）

[12] 鄧希，胡曉兵，江代渝，等. 基于混合遺傳算法的柔性作業車間機器和AGV規劃［J］. 四川大學學報（自然科學版）， 2021， 58（2）：73-82.（DENG X， HU X B， JIANG D Y， et al. A hybrid GA approach to the scheduling of machines and automated guided vehicles in flexible job shops［J］. Journal of Sichuan University （Natural Science Edition）， 2021， 58（2）：73-82.）

[13] FANTI M P， MANGINI A M， PEDRONCELLI G， et al. A decentralized control strategy for the coordination of AGV systems［J］. Control Engineering Practice， 2018， 70：86-97.

[14] 高一鷺，胡志華. 基于時空網絡的自動化集裝箱碼頭自動化導引車路徑規劃［J］. 計算機應用， 2020， 40（7）：2155-2163.（GAO Y L， HU Z H. Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal［J］. Journal of Computer Applications， 2020， 40（7）：2155-2163.）

[15] 曾慶成，李明澤，薛廣順. 考慮擁堵因素的自動化碼頭多AGV無沖突動態路徑規劃模型［J］. 大連海事大學學報， 2019， 45（4）：35-44.（ZENG Q C， LI M Z， XUE G S. Multiple AGV conflict-free dynamic routing model in automated terminals considering congestion factors［J］. Journal of Dalian Maritime University， 2019， 45（4）：35-44.）

[16] 仲美穌，楊勇生. 卸船作業模式下自動化碼頭AGV路徑仿真優化［J］.水運工程， 2018（4）：122-127.（ZHONG M S， YANG Y S. Based on discharging operation mode automation terminal of AGV path simulation optimization［J］. Port and Waterway Engineering， 2018（4）：122-127.）

[17] XIN J B， NEGENBORN R R， LODEWIJKS G. Trajectory planning for AGVs in automated container terminals using avoidance constraints： a case study［J］. IFAC Proceedings Volumes， 2014， 47（3）：9828-9833.

[18] NISHI T， HIRANAKA Y， GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles［J］. Computers and Operations Research， 2011， 38（5）： 876-888.

[19] FAZLOLLAHTABAR H， SAIDI-MEHRABAD M， MASEHIAN E. Mathematical model for deadlock resolution in multiple AGV scheduling and routing network： a case study［J］. Industrial Robot， 2015， 42（3）： 252-263.

[20] 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 and Industrial Engineering， 2015， 86：2-13.

[21] MIYAMOTO T， INOUE K. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems［J］. Computers and Industrial Engineering， 2016， 91：1-9.

[22] YANG Y S， ZHONG M S， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals［J］. Computers and Industrial Engineering， 2018， 126：482-493.

[23] ZHONG M S， YANG Y S， DESSOUKY Y， et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals［J］. Computers and Industrial Engineering， 2020， 142： No.106371.

[24] 吳聰，陳侃松，姚靜. 基于改進自適應遺傳算法的物流配送路徑優化研究［J］. 計算機測量與控制， 2018， 26（2）：236-240.（WU C， CHEN K S， YAO J. Study on optimization of logistics distribution route based on improved adaptive genetic algorithm［J］. Computer Measurement and Control， 2018， 26（2）：236-240.）

[25] 張素云，楊勇生，梁承姬，等. 自動化碼頭多AGV路徑沖突的優化控制研究［J］. 交通運輸系統工程與信息， 2017， 17（2）：83-89.（ZHANG S Y， YANG Y S， LIANG C J， et al. Optimal control of multiple AGV path conflict in automated terminals［J］. Journal of Transportation Systems Engineering and Information Technology， 2017， 17（2）：83-89.）

FAN Houming， born in 1962， Ph. D.， professor. His research interests include transportation system planning and design.

MU Shuang， born in 1995， M. S. candidate. Her research interests include transportation engineering.

YUE Lijun， born in 1995， Ph. D. candidate. Her research interests include transportation planning and management.

Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion

FAN Houming， MU Shuang， YUE Lijun*

（，，116026，）

In order to solve the problems of Automated Guided Vehicle （AGV） scheduling and conflict-free path planning in automated container terminals， an AGV conflict and congestion resolution strategy was proposed to generate conflict-free paths. Firstly， considering the capacity of the buffer bracket in the container yard as well as the constraints of no congestion on the operation paths and no conflict on the nodes， a two-stage mixed integer programming model was established based on the goal of the smallest maximum completion time and the shortest AGV transportation time. Then， an improved adaptive genetic algorithm and Dijkstra algorithm based on conflict and congestion resolution strategy were designed to obtain the AGV scheduling scheme and conflict-free paths. The results of numerical examples show that the improved adaptive genetic algorithm has the average solution time reduced by 13.56%， and the average gap rate of the objective function reduced by 9.01% compared to the genetic algorithm. Compared with the parking to wait strategy， the conflict and congestion resolution strategy has the congestion rate of the horizontal transportation area reduced by 67.6%， and the AGV waiting time reduced by 66.7%. It can be seen that the proposed algorithm has higher solving quality and faster speed， at the same time， the effectiveness of the proposed strategy is verified.

adaptive genetic algorithm; automated container terminal; Automated Guided Vehicle (AGV) scheduling; conflict-free path planning; conflict and congestion

This work is partially supported by Project of Dalian Science and Technology Innovation Fund （2020JJ26GX033）.

1001-9081（2022）07-2281-11

10.11772/j.issn.1001-9081.2021050819

2021?05?19；

2022?02?21；

2022?05?25。

大連市科技創新基金資助項目（2020JJ26GX033）。

TP18

A

范厚明（1962—），男，山東蓬萊人，教授，博士生導師，博士，主要研究方向：交通運輸系統規劃與設計； 牟爽（1995—），女，山東煙臺人，碩士研究生，主要研究方向：交通運輸工程； 岳麗君（1995—），女，河南濮陽人，博士研究生，主要研究方向：交通運輸規劃與管理。