考慮AGV避碰的自動化碼頭多資源協同調度

楊雅潔，萇道方，余 芳

上海海事大學 物流科學與工程研究院，上海201306

1 引言

隨著經濟快速發展，海運貿易量不斷增大，如何提高效率是各個碼頭亟待解決的問題。新型自動化碼頭開始陸續建成，AGV 是連接岸橋和場橋的重要設備，其作業效率的高低對整個碼頭的運營效率起著關鍵性作用。另一方面，由于碼頭的特殊性，其各個環節之間是相互耦合的，如何實現各個資源間的合理調度，對提高自動化碼頭的作業效率有非常重要的意義。

目前，眾多國內外學者對碼頭資源中兩個資源的協同調度研究占了多數，一般有岸橋與集卡、泊位與岸橋、集卡與場橋的調度。岸橋與集卡的研究有：馬超等[1]針對集裝箱岸橋與集卡的協同調度問題，考慮集卡路徑約束和岸橋實際操作情況，構建邊裝邊卸的混合整數模型，用分層方法遺傳算法來求解模型；張笑等[2]針對集裝箱在碼頭堆場分區堆放的情況和碼頭泊位裝卸作業的狀態要求，以岸橋和集卡作業時間最小建立模型，通過Gurobi 實現集卡路徑優化；梁承姬等[3]考慮集裝箱裝卸作業順序和岸橋干涉等建立最大完工時間最小化目標的混合整數規劃模型，最后用遺傳算法和粒子群算法求解，并比較了其優劣性；余孟齊等[4]考慮集裝箱之間的優先關系和岸橋安全邊際的實際約束，建立混合整數規劃模型，并用改進粒子群算法對其進行求解；嚴南南等[5]針對環境污染和能源緊缺問題，建立了一個考慮能耗的岸橋和集卡調度的多目標數學模型，用遺傳算法采用MATLAB求解，使用多目標方法平衡能耗和時間這兩個目標。陳寧等[6]考慮集裝箱作業過程不交叉、優先級約束等因素，采用混合流水車間作業調度方法建立混合整數規劃模型，獲得集裝箱任務的岸橋和AGV 分配及集裝箱任務的處理順序。

雖然在兩兩協同調度方面的研究取得了很多成果，但是，單純的對局部某個模塊進行優化不一定能改善整個碼頭的生產效率。因此，三個及以上資源間的調度開始備受重視，比如：岸橋-集卡-場橋協同調度，集卡-場橋-堆場協同調度。馬越匯等[7]將自動化集裝箱碼頭的不確定因素考慮進去，建立AGV、岸橋、堆場、龍門吊四者最末結束任務時間最小化為目標函數的模型，判斷不確定因素對最末任務結束時間的影響；徐遠琴等[8]考慮裝卸不平衡問題，對集卡運輸時間與岸橋、場橋等待時間加入權重參數建立模型，用算例驗證模型的有效性和實用性；楊勇生等[9]考慮雙小車岸橋和雙軌道龍門起重機，以卸船作業最小完工時間為目標建立混合整數規劃模型，運用遺傳算法求解給出自動化碼頭的設備調度優化方案；添玉等[10]引入岸橋調度任務為主要約束，構建岸橋、頂升式自動導引車及自動軌道吊的協同調度模型，采用遺傳算法實現系統效率的提升下的作業序列的最優化；luo 等[11]考慮自動化集裝箱卸載過程，制定混合整數規劃模型，運用遺傳算法求解，有效減少船舶在港時間；Wang 等[12]同時考慮集裝箱碼頭裝載和卸載活動的問題，用MIP 模型描述車輛調度，堆場起重機調度和集裝箱存儲位置之間的相互關系，小規模用CPLEX 求解，大規模用遺傳算法求解，有效減少集裝箱任務的完成時間來縮短船舶周轉時間。Kaveshgar 等[13]考慮岸橋干擾，集裝箱之間的優先級關系建立綜合優化模型，運用遺傳算法和貪心算法相結合求解，能夠合理解決集裝箱碼頭出現的運營問題。上述文獻都在三個及以上資源的協同調度研究中做出了一定的貢獻，但是目前尚未有文獻在考慮多個資源協同調度的同時考慮了AGV 行駛過程中的碰撞問題。在自動化碼頭中，AGV 行駛路徑比較固定，不像傳統集卡行駛靈活，容易發生擁堵，對于多AGV 同時運行的碰撞問題亟待解決。因此，本文在考慮三個資源（岸橋、AGV、場橋）協同調度的同時考慮了AGV 間的碰撞問題。另一方面，現有的文獻，都是考慮在任意時間只能通過一輛AGV 來減少等待時間，如容芷君[14]在處理碰撞問題時，賦予小車優先級別，優先級最高的先通過，其余小車選擇等待；吳曉雨[15]在解決多AGV 路徑規劃時，提出等待避讓和更改路徑兩種選擇，凌忠奇[16]提出在AGV 節點間發生沖突時，采用等待策略，優先級高的AGV 先通過。而本文模擬實際交通的情況，通過對AGV 通過的路口設置相容和沖突相位，處于相容相位的AGV 能夠同時通過，可以使路口同時通過多輛AGV，以此來縮短整個作業流程時間。

2 問題描述

本文研究自動化碼頭的范圍包含岸橋作業區、AGV水平作業區、堆場箱區。隨著港口業務量增多，自動化碼頭逐漸成為各個碼頭的建設的目標。AGV 作為自動化碼頭的象征性產物，為了滿足日益增長的業務需求，自動化碼頭AGV 的數量也隨之不斷增多。而其固定的行駛路線增加了沖突的概率，導致AGV 擁堵事件頻發，直接影響了整個碼頭的作業效率。因此，如何實現考慮AGV避碰情況下的多資源間的協同調度問題亟待解決。

圖1 集裝箱作業流程圖

本文針對岸橋-AGV-場橋三個資源協同調度情況下AGV 的避碰問題（主要考慮AGV 在十字路口的避碰）。整個作業流程如圖1 所示，AGV 從岸橋1 下的交接點等待岸橋將進口集裝箱從船上卸載到AGV 上，再由AGV 選擇最優路徑（如圖1 中路徑1 所示）將任務送到場橋前側交接點，AGV 便可自由返回碼頭處理下一集裝箱。本文結合岸橋、AGV、場橋三個資源，同時考慮路徑的分配及AGV 的避碰，建立一個所有任務的最大完工時間最小化為目標的混合整數規劃模型。

3 模型建立

3.1 模型假設

根據碼頭的一些實際情況，如在自動化碼頭中，隨著AGV 數量增多，在路口沖突問題最為顯著；場橋前設有AGV 伴侶，AGV 將任務放下即可返回[17]。為了便于問題求解分析以及集裝箱碼頭作業規則，對問題進行相應的假設：

（1）岸橋處理單個集裝箱任務的時間固定。

（2）AGV從岸橋取箱時間忽略不計。

（3）AGV 均勻速行駛，雙車道路徑，只考慮其在十字路口的碰撞。

（4）已知進口集裝箱任務在堆場的存放位置。

（5）場橋從AGV 伴侶取箱時間忽略不計，場橋處理集裝箱的時間固定。

（6）AGV 放置場橋前側等待區即可離開返回岸邊執行下一任務。

3.2 模型參數與決策變量

3.2.1 模型參數

I：所有任務的集合，i=1,2, ,Ι。

K：岸橋的集合，k=1,2, ,Κ。

B：箱區的集合。

V：AGV的集合，v=1,2, ,V。

Fi：任務i的結束時間。

QSi：岸橋開始任務i時刻。

YFi：場橋結束任務i時刻。

TUik：岸橋k開始處理任務i的時刻。

TSikv：AGVv開始執行岸橋k第i個任務的時刻。

Tkb：AGVv 從岸橋k 到箱區交接區b 所需要的時間。

TDiy：場橋Y 開始處理任務i的時刻。

T1：岸橋處理單個任務所需要的時間。

T2：場橋處理單個任務所需要的時間。

dvt：AGVv在t 時刻的相位。

3.2.2 決策變量

3.3 基本模型

3.3.1 AGV路徑選擇與避碰模型

AGV 在行駛過程中，將會首先選擇一條路徑，如果選擇的路徑中AGV 會同時經過某個十字路口，則需要對AGV 進行路口相容還是沖突的判斷。傳統的模型大多假設只允許優先級最高的1 輛AGV 通過十字路口以避免沖突，而本文通過對路口的每個相位都設置相容和沖突的相位，處于相容相位的AGV 可以同時通過而不發生碰撞，而處于相沖突相位的AGV 則不能同時經過路口，以避免發生碰撞。例如，圖2 為t 時刻AGVv 到達雙車道十字路口時，12 種方位的情況。假設相位=1，可以從圖2中看出相位1的沖突相位為相位4，5，8，10，11，則Pdvt={4,5,8,10,11}。即在t 時刻，當AGVv 行駛到相位1 時，其他小車如處于4 相位，會發生碰撞沖突，則不能與其同時通過；如處于6 相位，則兩個AGV 相容，可以同時通過，節約路口等待時間。這樣可以使路口能同時通過多輛AGV 而不發生碰撞，大大提高了AGV 的運行效率，縮短了整個任務完成的時間。

圖2 十字路口AGV相位圖

3.3.2 協同調度模型

本文以總任務最大完工時間最小化為目標，考慮如何將任務分配給岸橋、AGV、場橋。首先，采用隨機方法將各集裝箱任務分配給各岸橋，考慮一個集裝箱任務在任意時刻只能分配給一個岸橋、一個AGV。然后由AGV 選擇最優線路，所謂最優線路，即使AGV 完成所有任務之后，已知各個岸橋到各箱區的距離，AGV 勻速行駛，方能計算出運行時間。將各集裝箱任務送至目標場橋，AGV 返回需要執行下個任務的岸橋（除AGV 完成最后一個任務外），算是一個任務真正完成的時間，直至最后一個任務完成為止。

結合3.3.1 小節所提出的避碰模型，將AGV 避碰加入岸橋、AGV、場橋協同調度模型中，建立一個總任務最大完工時間最小化的混合整數規劃模型。具體模型如下：

其中，式（1）為目標函數，表示最小化所有任務的最大完工時間；式（2）表示所有任務的完工時間；式（3）表示任務的結束時間；式（4）表示任務的開始時間；式（5）表示每個任務在任意時刻只能分配給一個岸橋；式（6）表示岸橋在任意時刻只能被分配一個任務；式（7）表示任意任務只能分配給一個箱區；式（8）表示每個集裝箱任務在任意時刻只能由一個AGV 完成；式（9）表示在任意時刻每輛AGV只能完成一個集裝箱任務；式（10）和式（11）是避免兩個處于沖突相位的AGV 同時經過十字路口；式（12）表示場橋只能在AGVv 將集裝箱運輸到指定工作點后才能開始處理集裝箱；式（13）表示只有在岸橋將集裝箱放到AGV 后，AGV 才能開始處理任務；式（14）表示任務i的完成時刻；式（15）是對參數的非負限制。

本模型中，AGV 服務任意岸橋，當AGV 開始運作后，將任務送至目標箱區即可返回。返回取任務的原則（優先級最高的先取），給集裝箱任務設置了優先級，數字越大，優先級越高，到最后一個任務完成，即所有任務完成的時間。在AGV 行進過程中，需要判斷路口是否存在沖突碰撞（選定目標點，各路口到目標點距離已知，若在同一時間點距離目標點路程相同，則會在該路口發生沖突）。傳統的模型并不考慮避碰規則，而是選擇運送任務優先級低的AGV 等待，優先級高的AGV 優先通過。而本文提出的模型考慮了避碰規則，當AGV 發生沖突時先判斷是否處于相容相位，如果處于相容相位，則可順利通過，如判斷處于沖突相位，則運送任務優先級低的任務等待，從而節約總任務等待時間。

4 算例分析

為了評估模型的準確性，首先對參數進行初步設定，采用JAVA編程語言進行精確求解，對各算例進行分析。本文考慮了兩種情況：（1）不考慮避碰規則下岸橋-AGV-場橋的協同調度；（2）考慮避碰規則情況下的岸橋-AGV-場橋的協同調度，然后分別對兩種情況下不同卸箱任務數量、不同岸橋-AGV-場橋配比時的結果進行了分析，以此來驗證所提出模型的優越性。

4.1 參數設定

針對兩種情況下的實驗1與實驗2的模型參數采用相同的設置（詳見表1～3）。其中，表1 為集裝箱碼頭的各設備實驗參數，岸橋處理一個集裝箱任務的時間為50 s，場橋處理一個集裝箱任務的時間為55 s，AGV 行駛的速度為5 m/s；表2 為各集裝箱任務的目標堆場箱區；表3為岸橋到各箱區的距離。

表1 集裝箱碼頭設備試驗參數

表2 集裝箱目標堆場

4.2 結果分析

（1）未考慮避碰規則情況下

表3 岸橋與各箱區的距離 m

分別考慮了11 種不同參數設置下的實驗：算例1～3考慮了卸箱數量均為60、岸橋均為3、箱區均為6 情況下，AGV 數量分別為12、15、18 的情況；算例4～6 跟算例1 保持相同的岸橋-AGV-場橋配比情況下分別將卸箱數量增加為80、120、180 的情況；算例7、8 跟算例2 保持相同的岸橋-AGV-場橋配比情況下分別將卸箱數量增加為250、330的情況；算例9～11跟算例3保持相同的岸橋-AGV-場橋配比情況下分別將卸箱數量增加為420、550、700 的情況。實驗結果如表4 所示，可以看出在相同卸箱數量情況下，AGV 數量越多，總任務完成的時間越少；在岸橋、AGV、箱區數量相同的情況下，卸箱數量越多，總任務完成時間越長。

表4 未考慮避碰下的實驗結果

以算例1為例，可得AGV的最優調度方案如下：

AGV1 的調度方案為（2，37）→6，（1，4）→1，（1，49）→1，（3，43）→3，（3，10）→2

AGV2 的調度方案為（3，28）→1，（2，59）→6，（1，55）→6，（1，44）→4，（3，51）→5

AGV3 的調度方案為（1，11）→4，（3，13）→5，（3，53）→4，（2，39）→2，（1，31）→6

AGV4 的調度方案為（3，47）→2，（2，48）→3，（2，5）→5，（3，8）→6，（2，24）→4

AGV5 的調度方案為（2，30）→3，（3，29）→2，（2，57）→3，（1，45）→1，（1，32）→1

AGV6 的調度方案為（1，20）→5，（1，23）→4，（3，15）→2，（2，34）→5，（2，22）→2

AGV7 的調度方案為（3，50）→1，（2，16）→4，（2，26）→4，（2，12）→5，（1，3）→3

AGV8 的調度方案為（1，17）→4，（3，56）→5，（1，40）→3，（3，38）→6，（2，7）→3

AGV9 的調度方案為（2，14）→6，（1，21）→6，（2，36）→6，（2，25）→1，（1，60）→5

AGV10 的調度方案為（2，52）→2，（2，58）→3，（3，33）→2，（1，18）→2，（3，2）→1

AGV11 的調度方案為（3，41）→3，（1，42）→1，（3，46）→1，（3，35）→3，（2，54）→4

AGV12 的調度方案為（1，19）→5，（3，27）→2，（1，9）→5，（1，6）→4，（3，1）→6

以AGV1 為例，代表含義為AGV1 執行岸橋2 的37號集裝箱任務到達箱區6，執行岸橋1的4號集裝箱任務到達箱區1，執行岸橋1 的49 號集裝箱任務到達箱區1，執行岸橋3 的43 號集裝箱任務到達箱區3，執行岸橋3的10號集裝箱到達箱區2。

圖3 為算例1 集裝箱任務調度結果的甘特圖，綠色表示岸橋處理時間，紅色代表AGV 的碰撞時間，藍色代表AGV 處理集裝箱任務的時間（包括返回時間），橙色代表場橋處理的時間。從圖3 中可以明顯地看到AGV存在碰撞的時間。

圖3 集裝箱調度結果甘特圖（未考慮避碰規則）

在AGV 進行任務作業時，會發生碰撞，下面就卸箱數量均為60，岸橋-AGV-箱區的作業情況下，各AGV 之間的路口碰撞情況進行說明。如圖4 與圖5 所示，在任務進行至209 s時，4號AGV和10號AGV在路口發生沖突，10 號AGV 等待1 s，此時，5 號AGV 和11 號AGV 在路口發生沖突，11 號AGV 等待1 s，由于兩輛AGV 在路口發生沖突，必有一輛AGV 要等待，才能使另一方順利通過，增加了總任務的完成時間。如圖6，在任務進行至221 s時，6號AGV 和12號AGV 發生碰撞，12號AGV 等待1 s，使6號AGV順利通過，增加了總任務的完成時間。

（2）考慮避碰規則情況下

在考慮避碰規則的情況下，采取了與不考慮避碰規則相同的設置下的11 個算例進行比較分析。實驗結果如表5所示。

下面舉例就卸箱任務數量為60，岸橋-AGV-場橋配比為3-12-6的運行情況進行說明。

圖4 AGV4與AGV10離碰撞路口距離圖

圖5 AGV5與AGV11碰撞路口距離圖

圖6 AGV6與AGV12碰撞路口距離圖

表5 考慮避碰規則下的實驗結果

AGV1 首先在岸橋下等待就緒，岸橋開始AGV1 首次運送37 號任務至6 號場橋，AGV2 運送28 號任務至1號場橋，AGV3 運送11 號任務至4 號場橋；AGV4 運送47 號任務至2 號場橋，AGV5 運送30 號任務至3 號場橋，AGV6 運送20 號任務至5 號場橋；AGV7 運送50 號任務至1 號場橋，AGV8 運送17 號任務至4 號場橋，AGV9運送14號任務至6號場橋。

AGV2 將任務送至目標箱區，判斷下一任務為2 號岸橋的59 號任務優先級最高，AGV2 從1 號場橋返回至2 號岸橋取59 號任務，AGV3 從4 號場橋返回至3 號岸橋取13 號任務，AGV1 從6 號場橋返回至1 號岸橋取4 號任務。

AGV10 從岸橋2 出發運送52 號任務至2 號場橋，AGV11 從岸橋3 出發運送41 號任務至3 號場橋，AGV12從岸橋1出發運送19號任務至5號場橋。

AGV4從2號場橋返回至2號岸橋取任務，AGV5從3號場橋返回至3岸橋取任務，AGV6從5號場橋返回至1號岸橋取任務。

在AGV10 從岸橋2 至場橋2 運送任務，AGV4 從場橋2 返回過程中，在如圖7 位置點b1 發生沖突。若在考慮避碰規則后，則節約本次等待時間。

圖7 沖突位置圖

此外，從實驗結果可知當卸箱數量相同時（算例1，2，3），隨著AGV 數量增多，總任務完成時間減少；當岸橋、AGV、場橋數量相同時（算例4，5，6），隨著卸箱數量增多時，總任務完成時間增加。

在任務進行至第209 s 時，4 號和10 號AGV 發生碰撞，此時10 號AGV 處于如圖8 的8 號相位，4 號AGV 處于如圖8 的3 號相位，由于避碰規則的設置，8 號相位與3號相位屬于相容相位，可以順利通過，節約了在路口的等待時間；5 號和11 號AGV 發生碰撞，同樣，此時11 號AGV處于如圖8的8號相位，5號AGV處于如圖8的3號相位，由于避碰規則的設置，8號相位與3號相位屬于相容相位，可以順利通過，節約了在路口的等待時間。

圖8 AGV4與AGV10、AGV5與AGV11路口相位圖

任務進行至221 s 時，6 號和12 號AGV 發生碰撞，此時12 號AGV 處于如圖9 的7 號相位，6 號AGV 處于如圖9 的5 號相位，為相沖突的相位，12 號AGV 仍需等待1 s。

圖9 AGV6與AGV12路口相位圖

圖10 為考慮避碰規則情況下算例1 集裝箱任務調度結果的甘特圖，綠色表示岸橋處理時間，紅色代表AGV 的碰撞時間，藍色代表AGV 處理集裝箱任務的時間（包括返回時間），橙色代表場橋處理的時間。由圖可見，在考慮避碰規則情況下的碰撞等待時間減少。

圖10 集裝箱調度結果甘特圖（考慮避碰規則）

4.3 實驗結果比較

為了更直觀地看出模型的優越性，對相同卸箱數量、不同AGV 數量以及相同AGV 數量、不同卸箱數量在考慮與未考慮避碰規則的情況下進行了比較。

岸橋數量為3，場橋數量為6，固定卸箱數量為60，AGV數量分別為12、15、18下的未考慮避碰規則和考慮避碰規則的對比圖如圖11。可以看出，未考慮避碰規則的總任務完成時間多于考慮避碰規則的總任務完成時間。

岸橋-AGV-場橋數量固定為3-15-6 情況下，箱區數量為60、250、330 時考慮避碰規則和未考慮避碰規則下的對比結果如圖12 所示。同樣可以看出，未考慮避碰規則的總任務完成時間多于考慮避碰規則的總任務完成時間。

圖11 AGV數量不同、卸箱任務相同情況下的對比

圖12 AGV數量相同、卸箱任務不同情況下的對比

同時，如圖13 與圖14 所示，分別卸箱數量為60，岸橋、箱區數量為3和6情況下不同AGV 數量的碰撞耗時圖與岸橋-AGV-箱區數量為3-15-6，不同卸箱數量的碰撞耗時圖。實驗結果表明，在卸箱數量，AGV 數量增多情況下，發生碰撞的幾率就越大，在考慮設置的避碰之后，節約了AGV在路口的等待時間，從而使調度結果更優化。

圖13 卸箱任務相同、AGV數量不同碰撞耗時圖

圖14 AGV數量相同、卸箱任務不同碰撞耗時圖

在11 個算例中，考慮避碰規則后平均任務完成總時間減少率如表6 所示，提升了整個卸船作業流程的效率，算例結果表明，考慮避碰規則下的解要優于未考慮避碰規則下的解。

表6 考慮避碰規則后總任務完成時間減少率

通過上述分析最終能得出以下結論：

（1）在AGV 數量、岸橋和箱區數量一致時，隨著卸箱任務增多，AGV 碰撞等待時間越長，即發生沖突概率增加，總任務時間增加。

（2）在卸箱數量、岸橋和箱區數量一致時，AGV 數量增多，AGV 碰撞等待時間越長，發生沖突概率增加，總任務時間增加。

（3）考慮避碰規則下的碰撞耗時明顯少于不考慮避碰規則下的耗時。

（4）考慮避碰規則下總任務完成時間小于不考慮避碰規則下的總任務完成時間。

（5）考慮避碰規則的總的碼頭操作效率明顯高于不考慮避碰的情況。

5 結束語

本文針對AGV 小車路口碰撞問題，考慮任務分配、路口避碰等約束，建立以最大完工時間最小化為目標的自動化集裝箱碼頭協同調度模型。并對任務數量、岸橋、AGV、箱區數量進行不同配比情況下的模型進行驗證和比較。實驗結果表明在考慮AGV 避碰規則之后，平均任務總完成時間減少。

但本文只考慮了路口的碰撞問題，其他碰撞問題還有待深入研究。另外，實際情況下，不同的集裝箱在不同堆場的存放順序也對總任務處理時間有影響，未來的研究可考慮在裝卸并行的情況下，考慮集裝箱在堆場的存放順序等因素，使其更符合集裝箱碼頭的實際情況。