自動化集裝箱碼頭AGV 配置與調度耦合問題研究

梁承姬，陳登川

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

2.西安外事學院，西安 710000

1 引言

自動化集裝箱碼頭作為綠色港口與智慧港口的象征，是未來大型港口發展的一個趨勢。自動化碼頭設備主要分為裝卸設備和水平運輸設備，所以自動化碼頭可以分為兩大系統：裝卸系統和水平運輸系統。裝卸系統主要由岸邊橋式起重機（以下簡稱岸橋）與堆場橋式起重機（以下簡稱場橋）構成；水平運輸系統主要由自動導引小車（Automated Guided Vehicle，AGV）構成。水平運輸系統作為連接自動化碼頭裝卸設備的樞紐，有著至關重要的作用。提高水平運輸系統的作業效率能夠直接提升裝卸設備的作業效率，進而提高整個自動化碼頭的作業效率。增加AGV的使用數量可以直接提升裝卸設備的作業效率，但是過多地投入AGV會造成AGV之間的互相等待，從而引起運輸區域的擁堵。所以在滿足任務時間的要求下盡量減少AGV使用數量能有效減少AGV的擁堵和互相等待。

在傳統集裝箱碼頭集卡協調調度研究領域，梁承姬等[1]以岸橋延遲時間、集卡空駛時間及任務對的時間差的加權和最小為目標，建立岸橋集卡協調調度模型，并分析了遍歷不同集卡數量時岸橋-集卡最佳的數量配比。趙金樓等[2]考慮空載率和集卡使用數量對集卡運輸效率的影響，構建了集裝箱碼頭的集卡兩階段路徑優化模型。張笑菊等[3]基于岸橋同貝同步裝卸作業的岸橋與集卡聯合調度問題，以船舶裝卸完工時間最短為目標，建立岸橋與集卡聯合調度優化模型，優化岸橋與集卡的任務分配及作業序列。梁承姬等[4]綜合考慮集裝箱順序及岸橋干涉、集卡作業面調度等約束，建立混合整數規劃模型，并使用遺傳算法進行求解。孫清臣等[5]針對雙循環集卡操作策略，建立了岸橋和集卡聯合優化混合整數規劃模型，并驗證了模型的有效性。嚴南南等[6]針對岸橋集卡協調調度，采用遺傳算法進行求解建立集卡能耗和岸橋集卡作業時間的多目標數學模型，最終驗證了模型和算法的有效性。Tang等[7]針對岸橋、集卡聯合角度問題，以最小化裝卸船完工時間為目標，建立混合整數規劃模型，并利用粒子群算法進行求解。在傳統碼頭集卡調度耦合優化方面，樊陸彬等[8]從不確定性角度出發，采用多學科變量耦合優化設計的方法，同時考慮集裝箱任務時間窗約束建立了岸橋和集卡協調調度耦合模型，并驗證了模型的有效性和實用性。在傳統碼頭集卡和岸橋的耦合調度問題方面已經有學者進行了研究，為自動化碼頭AGV調度問題研究提供了思路。

在自動化碼頭AGV調度的研究領域，楊雅潔等[9]考慮AGV避碰，建立了一個以所有任務最大完工時間最小化為目標的混合整數規劃模型，并對有無避碰規則下的實驗數據進行了比較和分析。楊勇生等[10]考慮AGV和RMG的任務分配約束，以最小化卸船作業最大完工時間為目標，建立混合整數規劃模型，并設計不同規模算例對模型進行驗證。添玉等[11]以最小化船舶在港時間和主要設備作業成本為目標，構建了新的裝卸混合模式下岸橋、AGV及自動化軌道吊協同調度的混合整數非線性規劃模型，并提出一種遺傳算法與啟發式策略結合的協同調度方法。Wang等[12]考慮邊裝邊卸模式中，用混合整數規劃模型描述車輛調度、堆場起重機調度和集裝箱存儲位置之間的相互關系，小規模用CPLEX求解，大規模用遺傳算法求解，有效減少集裝箱任務的完成時間來縮短船舶周轉時間。馬躍匯等[13]為研究不確定環境下自動化集裝箱碼頭AGV調度與配置問題，建立了以最末任務結束時間最小化為目標的基本模型。宗辰光等[14]采用多層編碼粒子群-遺傳算法融合，對成本優化問題進行了仿真研究，給出了成本變化曲線及AGV調度甘特圖。馬孫豫等[15]建立以卸船作業最末任務結束時間最小化為目標的混合整數規劃模型，采用多層編碼粒子群算法進行求解。在自動化碼頭AGV調度方面，國內外學者多以確定AGV數量的情況下對AGV調度問題展開研究，鮮有學者對AGV數量和AGV調度問題同時展開研究。

綜上述可知，目前文獻在集卡調度或者AGV調度的研究上多是確定設備數量后再對整體調度方案進行求解。但在自動化集裝箱碼頭的實際生產活動中，裝卸設備與運輸設備之間為耦合關系，設備的調度方案和設備使用數量之間是相互影響的，所以不應該采用單向協調的方法。本文基于此，綜合設備數量和調度方案，采用多學科變量耦合優化設計的思想，建立耦合模型，來獲得最優的整體最優調度方案。

2 問題描述

自動化集裝箱碼頭的作業模式分為裝船作業和卸船作業，裝船作業是出口集裝箱（以下簡稱出口箱）從堆場出發被運輸至目標岸橋，再由岸橋抓取集裝箱放至船舶目標貝位的過程，卸船作業則與裝船作業相反。AGV作為連接岸橋和場橋的運輸設備，需要根據集裝箱任務的要求選擇不同的運輸方式，運輸方式如圖1所示。

圖1 自動化集裝箱碼頭AGV運輸方式

本文考慮AGV的雙循環作業，即有四種運輸方式：（a）只卸，岸橋卸箱后滿車運輸到進口箱區，場橋提箱后，空車回岸邊；（b）只裝，從堆場的出口箱區滿車運輸到岸邊等待岸橋裝船，再空車回堆場；（c）先裝后卸，從堆場的出口箱區滿車運輸到岸邊等待岸橋裝船，空車去另一臺岸橋處等待岸橋卸箱，再滿車運輸到進口箱區；（d）先卸后裝，從岸橋處滿車運輸到進口箱區，場橋提箱后，空車去出口箱區，此箱區場橋裝箱后，滿車運輸到岸邊等待岸橋裝船。

在作業過程中，AGV與岸橋之間會產生互相等待的時間，因此需要盡可能縮短互相等待的時間。增加AGV數量能直接減少設備間互相等待的時間，但是一味地增加AGV數量會造成AGV資源浪費、碼頭前沿交通擁堵等問題。自動化碼頭AGV作業系統是個復雜的系統，其不僅包括AGV本身，而且還涉及到岸橋和場橋的大型設備，需要采用多設備協調調度的方法來求得復雜系統的最優運行狀態。

本文就以此為出發點，根據多學科變量耦合優化設計方法（如圖2），將AGV作業系統分解為兩個同層級的子系統，即AGV調度子系統和AGV配置子系統，并建立AGV調度模型、AGV配置模型和AGV協調調度耦合模型。AGV調度模型要解決的是AGV具體的任務作業順序，即每輛AGV以何種順序運輸哪一個集裝箱，使得AGV與岸橋的互相等待時間最小；AGV配置模型要解決的是在滿足集裝箱任務完成情況下需要配置至少幾輛AGV的問題；AGV協調調度耦合模型是為了判斷上述兩個模型計算結果是否符合要求。并將岸橋完成集裝箱任務的時刻和AGV的數量作為公用設計變量連接兩個子系統，形成耦合關系，并通過迭代的方法不斷更新公用設計變量。給出本文的AGV作業系統耦合模型框架，如圖3所示。在圖3中，AGV調度子模型的輸入為AGV數量與岸橋完成集裝箱任務的子時刻，輸出為岸橋完成集裝箱任務的時刻，將該AGV調度子模型的輸出輸入到協調調度模型中進行運算，若符合迭代計算條件，則將岸橋完成集裝箱任務的時刻作為輸入條件輸入AGV配置子模型。AGV配置模型的輸入為岸橋完成集裝箱任務的時刻，輸出為AGV數量與岸橋完成集裝箱任務的子時刻，將AGV配置子模型的輸出輸入到協調調度模型中進行運算，若符合迭代條件，則將AGV數量和岸橋完成集裝箱任務的子時刻作為輸入條件輸入AGV調度子模型。如此循環求解，形成了兩個子模型之間的耦合關系。

圖2 多學科變量耦合優化設計方法

3 數學模型

3.1 Model I：AGV調度模型

符號：

i,j：集裝箱任務。

I,F：虛擬的初始和結束任務。

P：集裝箱任務總和。

J+：裝箱任務集。

J-：卸箱任務集，且有J=J+?J-。

k：AGV的集， ||k=K，有k輛AGV完成運輸任務，則有k條直接路徑。

Jˉ ：所有任務，Jˉ={ }I,F ?J。

參數：

ti,j：AGV在作業任務i與任務 j之間的時間間隔。

si,j：AGV在任務間的空車行駛時間。

hqi：岸橋處理各任務的時間。

hyi：場橋處理各任務的時間。

ωi,j：AGV完成任務i緊接著去完成任務 j產生的時間延誤成本。

qsi：岸橋可處理集裝箱任務i的時刻。

圖3 AGV作業系統耦合模型框架

決策變量：

xijk：0-1變量，1表示AGVk完成任務i后去完成任務 j。

ωi,j分為兩種情況：AGV晚到，即qsi+ti,j-qsj≥0，此時岸橋需要等待AGV；AGV早到，即qsj-qsi-ti,j≥0,此時AGV需要等待岸橋。所以：

其中，a是AGV早到引起延誤的時間成本系數，b是AGV晚到的引起延誤的時間成本系數，a和b均為不大于1的正隨機數。由于岸橋的是自動化碼頭唯一與船舶直接接觸的設備，岸橋誤工會引起船期的延誤，所以應當調節系數的大小，盡量避免岸橋等待AGV。

ti,j表示AGV在作業任務i與任務 j之間的時間間隔，根據AGV運輸方式確定ti,j的計算方式為：

由于船舶裝卸集裝箱對船舶平穩性有嚴格的要求，所以本文假設每臺岸橋有著嚴格的裝卸作業順序，相應地計算ti,j不能違反岸橋的裝卸順序，例如對于岸橋k，若i>j，則規定ti,j=M,M趨向于正無窮，表示岸橋k的i任務不能在 j任務之前完成。

方程（2）為Model I的目標函數，表示各集裝箱任務作業過程中總延誤時間成本最小；約束（3）表示每個任務的繼后任務只能由同一輛AGV完成；約束（4）表示對于每個任務的先前任務只能由同一輛AGV完成；約束（5）表示對于中間任務，需要運輸平衡，即輸入等于輸出；約束（6）表示k輛AGV都必須完成起始任務，即共有k輛AGV參與調度；約束（7）表示k輛AGV完成結束任務，即共有k輛AGV結束調度；約束（8）表示決策變量AGV的作業順序為0-1變量，1表示AGVk完成任務i之后完成任務 j。

通過上述模型求解出AGV的作業任務順序，即調度方案。通過實際的AGV任務作業順序，可以計算出每個集裝箱任務的實際被操作時刻ri,ri分為卸船時刻和裝船時刻。卸船時刻即為吊具接觸集裝箱的時刻，裝船時刻即為吊具離開集裝箱的時刻，ri的計算公式如下：

3.2 Model II：AGV配置模型

岸橋裝卸每個任務都有作業時間窗，本文由ei和ri這兩個值構成時間窗[ei,ri]，其中ei為任務i的最早可處理時刻，ri為岸橋實際處理其所屬集裝箱的任務完成時刻。將每個任務的時間窗等分成n段，則每個任務可在這n個時刻中選擇一個時刻完成，當選擇的任務完成子時刻點越來越接近ei時，表示單個任務的延誤時間越來越小，從而使所有任務的延誤時間最小化。以5個任務為例，每個任務的作業時間窗4等分，可得到如圖4所示的網絡圖。在圖4中，第一臺AGV從起點s點出發依次經過任務1、4、6、22，最后到達終點 t。第二臺AGV從起點s點出發，只經過任務9后直接到達終點t點。所以從起始點s點出發到達結束點t點并經過所有時間窗，至少需要2條直接路徑，所以完成5個任務至少需要2臺AGV。其中s點表示虛擬起始任務完工時刻，t點表示虛擬結束任務完工時刻，圖中的AGV必須滿足車輛約束和時間窗約束。

圖4 AGV配置模型的網絡示意圖

通過Model II計算得到的結果有：AGV數量和任務完成子時刻。AGV數量為Model I輸入條件，任務完成子時刻作為新的qsi的值。

集合：E表示所有任務完成子時刻的集合。

符號：

i,j：表示集裝箱任務；

g,h：表示集裝箱任務處理的子時刻；

s,t：表示虛擬的起始時刻和結束時刻；

n：時間窗的等分量。

參數：

ei：任務i的最早完成時刻；

ri：岸橋實際完成其所屬的集裝箱任務的時刻；

ti,j：表示運輸時間。

決策變量：

Zgh=1表示AGV在g時刻完成某一任務后在h時刻完成下一個任務；

v表示AGV的數量。

建立模型：

方程（10）為Model II的目標函數，表示最小AGV數量；約束（11）表示起始點有v輛AGV；約束（12）表示終止點有v輛AGV；約束（13）表示中間點輸入輸出平衡；約束（14）表示對于每個任務，其繼后任務時間窗內的子時刻只能選擇一個；約束（15）表示對于每個任務，其先前任務時間窗內的子時刻也只能選擇一個；約束（16）表示同一AGV完成的先后任務的子時刻的時間間隔不能小于任務間的運輸時間；約束（17）表示作業順序中繼后任務的時刻不能小于先前任務；約束（18）表示決策變量為0-1變量，AGV數量為整數。

將Model II得到的AGV數量和任務完成子時刻輸入AGV協調調度耦合模型，判斷是否符合迭代條件，若是，則將新的AGV數量作為輸入條件入Model I中計算。

3.3 AGV協調調度耦合模型

在上述AGV調度和AGV配置子模型的基礎上協調調度和配置問題，實現AGV協調調度的最優。這需要將調度和配置子模型進行多次的循環迭代計算，不斷更新公用設計變量的值，并設定相應迭代計算判斷條件來控制協調子模型的耦合計算。

迭代計算條件：

式（19）約束了任務的最早處理時刻和實際處理時刻差的容許范圍不得超過ε；式（20）約束了AGV的數量，nqc表示岸橋數量，nb表示箱區數量；式（21）表示同一岸橋的先后集裝箱任務處理時刻差不能小于其最早處理時刻差；式（22）表示同一岸橋的先后集裝箱任務在任務時間窗內處理的子時刻差不能小于其最早處理時刻差。

迭代計算流程如下：

將Model I中求得的 ri代入式（19）和式（21）判斷是否符合，如符合，則將ri代入Model II中；若不符合則跳回Model I重新計算，直到滿足式（19）和（21）。

將Model II中得出的AGV數量與任務處理子時刻g,h值分別代入式（20）和式（22）進行判斷，若符合，則將AGV數量與更新后的qsi輸入Model I進行第二次迭代；否則，重新計算Model II，直到滿足式（20）和（22）。

為了更直觀地表示迭代計算流程，給出如圖5所示的迭代計算流程圖。

圖5 迭代計算流程圖

按照上述流程不斷地循環迭代，直到不再符合迭代條件，或者所求的目標函數值不再變動，則停止循環迭代計算，最終將得到最優的AGV配置數量和調度方案。

4 算法設計

根據上述建模思路，本文提出一種循環求解算法，分為Model I算法和Model II算法，并將耦合迭代條件融入兩個算法中。

4.1 Model I算法設計

本文中的AGV調度問題為NP-hard問題，在現有的研究中，遺傳算法廣泛應用于AGV的調度研究中。Model I為AGV調度模型，決策變量為AGV作業集裝箱任務的順序，求解算法采用遺傳算法來設計，設計的內容主要為如下5個部分。

（1）染色體編碼

染色體采用實數編碼的形式，染色體長度等于m（集裝箱任務總數）+n（AGV數量）+1，即染色體長度=m+n+1，基因值為任務編號，其中不同AGV之間的任務用0元素隔開。把同一臺AGV任務所在的基因片段稱為任務片段。如圖6所示的染色體，從第二個基因位開始基因值依次為4，9，23，14，3，37，表示第1臺AGV的作業編號，依次為4，9，23，14，3，37。

圖6 Model I算法染色體編碼示意圖

具體步驟：

步驟1在染色體第一位生成第一個0元素。

步驟2若第i位基因值為0，那么隨機選取nqc個最小qsi值所對應的任務編號作為第i+1位基因值。否則，轉步驟3。

步驟3根據第i位基因值選取滿足車輛約束與時間窗約束的繼后任務編號，若繼后任務數量為0，則選取0元素作為第i+1為基因值，并轉步驟2；若繼后任務數量等于1，則選擇唯一任務號作為第i+1為基因值；若繼后任務數量大于1，則轉步驟4。

步驟4在若干可行繼后任務號中，計算各個繼后任務與先前任務的ri值，規定每個繼后任務的都有適應度值 f=1/(ri-ri-1)，應用輪盤賭法選擇出繼后任務號作為第i+1位基因值。轉步驟3。

步驟5重復步驟2，直至所有任務選取完畢。其中繼后任務編號滿足迭代約束條件（19）和約束（21）。

（2）適應度函數

Model I為最小化問題，適應度越大的染色體對應的目標函數應該越小，其中f1(x)為適應度值，y1(x)為目標函數值。

（3）選擇、交叉

選擇操作為輪盤賭法。

由于染色體中含有0元素，不能直接進行交叉，在這里采用線性交叉的方法，具體步驟如下：

步驟1隨機選擇一個不與0元素相鄰的基因作為交叉片段1的起點 p，交叉片段1為：從 p開始至任務片段最后一個基因為止。

步驟2尋找是否存在允許任務p作為繼后任務的不與0元素相鄰的任務q。若存在，標記q的繼后任務為 p′，生成交叉片段2：從 p′開始至其所在任務片段最后一個基因為止；若不存在，則轉步驟1。

步驟3交換交叉片段1與交叉片段2在染色體中的位置。

步驟4重新計算各個任務的ri，若使ri滿足約束（19）和（21），則結束變異過程；若不滿足，則轉到步驟1，重新開始。

為更清楚地展示交叉過程，給出交叉過程示意圖，如圖7所示。

圖7 Model I算法交叉過程示意圖

（4）變異

步驟1隨機選擇一個非0元素基因作為變異點s。

步驟2若s為其所在任務片段的第一個任務，發現s的繼后任務為z，隨機選出任務z的非s可行先前任務s′。

步驟3檢查s′替換為s后染色體的可行性，若可行，則交換s與s′的位置；若不可行，則返回步驟1。

步驟4重新計算各個任務的ri，若使ri滿足約束（19）和（21），則結束變異過程；若不滿足，則轉到步驟1，重新開始。

為了更清楚地展示交叉過程，給出交叉過程示意圖，如圖8所示。

圖8 Model I算法變異過程示意圖

（5）循環終止條件

達到設定最大迭代次數即終止循環。

4.2 Model II算法設計

Model II模型目標函數為最小化AGV的使用數量。通過對Model II模型的特點進行分析，考慮AGV配置模型的特殊性，采用單親遺傳算法。給出的Model II算法如下：

（1）染色體編碼

采用浮點數編碼方式，染色體長度等于m（集裝箱任務總數）+n（AGV數量）+1，即染色體長度=m+n+1。基因值的整數部分為任務編號，小數部分為整數部分任務的任務完成子時刻在時間窗中的具體等分點，AGV的數量為0元素數量總和減1。如圖9所示，第二個基因值為1.4，表示1號任務的完成子時刻為第4個等分點，其染色體基因值順序滿足車輛約束與時間窗約束。

圖9 Model II算法染色體編碼示意圖

具體步驟：

步驟1根據4.1節染色體生成方式生成Model II算法染色體的整數部分。

步驟2根據已生成的整數部分為每個整數值添加小數部分，小數部分滿足約束（21）與（22）。

步驟3檢查AGV數量是否滿足約束（20）。若是，則結束編碼過程；否則，重新開始步驟1。

（2）適應度函數

f2(x)=1/(c(x)+y2(x))，其中f2(x)為適應度函數值，c(x)為AGV數量的最大估計值，y2(x)為Model II的目標函數值。

（3）選擇、變異操作

選擇操作為輪盤賭法。適應度較大的染色體被選擇的概率會比較大。

在此算法設計的染色體中，隨意變異某個基因值的整數部分會引起一連串基因值的變化，且對AGV數量的變化不會起到明顯的作用。所以變異方法為：在每個任務片段中隨機選取一個基因值，將其小數部分變為滿足約束（21）與（22）的值。

（4）循環終止條件

達到設定最大迭代次數即終止循環。

5 算例分析及算法比較

5.1 設計算例

結合上述數學模型，設計算例，岸橋數量nqc=6，箱區數量nb=6，任務數量P=60。各岸橋的作業順序、處理各任務的時間及完成各任務的最早時刻見表1。M25為QC1與QC2的卸船箱區，M26為QC3、QC4的卸船箱區，M27為QC5、QC6的卸船箱區。QC1與QC2為M24的裝船岸橋，QC3與QC4為M28的裝船岸橋，QC5與QC6為M29的裝船岸橋。岸橋與箱區間距離、岸橋間距離與箱區間距離分別見表2～4。

表1 岸橋作業順序表

表2 岸橋與箱區之間的距離

在Model I算法中：交叉過程能夠以增加解的多樣性的方式提高GA的全局搜索能力，交叉系數不可過小，過小的變異系數會導致GA的全局搜索能力大大下降；變異過程能提高GA的局部搜索能力，變異系數不宜過大，過大的變異系數容易使GA陷入局部最優解。故設置Model I中交叉系數Pc=0.7，變異系數Pm=0.1，經試算，Model I算法迭代次數為1 000得出的結果較好。在Model II算法中：由于Model II算法采用單親遺傳算法，只有變異過程能提高GA的搜索能力，使用過小的變異系數對GA的搜索能力的提高收益甚微，故設置Model II中變異系數Pm=0.3。理論上時間窗等分點越多，所求得的集裝箱任務完成子時刻的值就越精確，但過多的等分點數量會影響GA的計算速度，故n取值為8。若ε取值過小，會影響模型計算速度，若ε取值過大，則會影響模型求解的精度，所以迭代計算條件中ε取15。經試算Model I算法在迭代次數小于100時就多次收斂，故設置Model I算法迭代次數為100。

表3 箱區之間的距離

表4 岸橋之間的距離

由表1～4可得出ti,j和si,j，再根據Model I中所述的計算ti,j的規則進而得出各任務間的ti,j。通過對上海港洋山四期自動化集裝箱碼頭的實地調研獲得以下數據：hqi的值93%以上落在0.630 1～1.411 7 min，且基本服從N(1,0.04)的正態分布；在不考慮場橋對AGV和岸橋的影響的前提下，場橋的作業時間hyi均勻分布在0.8～1.6之間；AGV的運動參數：全速6 m/s，轉彎2 m/s，最小轉彎半徑9 m。

5.2 結果分析

5.2.1 模型有效性驗證

基于上述數據，利用MATLAB2018a編寫算法對上述模型進行迭代計算。

以12輛AGV作為Model I的初始輸入條件，設定最大遺傳代數為1 000代，得到總延誤時間和初始任務調度方案，總延誤時間迭代過程如圖10所示，當AGV數量為12時，總延誤時間在Model I算法迭代至522次的時候收斂，最小總延誤時間為59.2 min。

圖10 Model I第1代迭代過程

將Model I求出的任務時間窗輸入Model II AGV配置模型中，設定最大遺傳代數為100代。執行計算后得到AGV數量、任務作業子時刻以及更新后的任務時間窗，AGV數量迭代過程如圖11所示，在Model II算法迭代至第24次時收斂至11臺，且符合AGV數量約束。各個任務完成子時刻等分點的選取結果如圖12所示，任務總數為60，任務完成子時刻等分點的數值越小，表示其實際任務完成時刻越接近ei。其中，任務完成子時刻等分點大于等于5的任務數量占比65%，所以初次運算所得任務時間窗仍有優化的空間；但選取任務子時刻等分點小于等于5的任務數量占比35%。以上結果表明Model II的優化效果明顯，驗證了Model II的有效性。

圖11 Model II第1代迭代過程

以11臺AGV作為Model I的初始輸入條件，并分別將更新后的任務時間窗與原任務時間窗輸入Model I，得到的結果見表5。

表5 11臺AGV不同任務時間窗下計算結果對比

表5顯示，當AGV數量為11臺時，求解Model I得出的總延誤時間要比AGV數量為12臺時降低34.63%，且輸入更新后的任務時間窗得到的總延誤時間比輸入原任務時間窗得到的總延誤時間少7.8 min。這一結果證明了Model II的有效性。

5.2.2 數值計算結果

基于上述第1代耦合迭代，繼續進行后續迭代，得到的結果見表6，并將結果與利用YALMIP調用CPLEX12.8計算得出的結果進行比較。

表6 AGV耦合調度計算結果

從表6可以看出，從第3代開始，由GA求得的AGV數量保持不變，總延誤時間波動范圍為不超過0.4 min；從第5代開始，由CPLEX求解的AGV數量和總延誤時間保持不變。從收斂速度上看，GA的收斂速度明顯優于CPLEX；從求解精度上看，GA與CPLEX求解結果精度一致。上述結果符合耦合迭代流程終止條件，求得了最優AGV數量為10臺，最小總延誤時間為12.2 min。

從計算結果上看，本文所提出的算法與CPLEX在求解耦合模型上比較具有以下優點：（1）收斂速度快，在第3代就已經收斂；（2）在計算大規模AGV調度問題上有潛在優勢。

根據最優解對應的AGV調度方案，畫出甘特圖如圖13所示。

圖13 AGV最優調度方案甘特圖

在圖13中，AGV1對應的任務編號依次為：12，26，36，40，52，18，即AGV1依次執行第12號，26號，36號，40號，52號，18任務。

5.3 算法比較

本文擴大算例規模，設計9組實驗，每組實驗用GA與不同算法進行求解，并對求解結果進行對比。表7為不同算例規模下PSO、ACO和GA的求解結果，每組實驗每個算法分別運算5次，結算結果均取平均值。

實驗1、2、3顯示：在計算AGV數量上，GAP2到達16.7%，ACO在求解AGV數量上性能較弱；在計算總延誤時間上，GAP3與GAP4均小于5%，PSO、ACO與GA求得的總延誤時間幾乎相近。實驗4，5，6顯示：在計算AGV數量上，GAP1與GAP2最大均達到7.7%，表明GA求解AGV數量的精度均要高于PSO與ACO；在計算總延誤時間上，GAP3最大達到14.74%，GAP4最大達到30.22%，表明GA求得的總延誤時間最優。直到實驗6為止，實驗規模的增加對PSO與ACO求解精度都帶來了不小的困難，而GA由于其強大的全局搜索能力，在求解精度上始終保持領先。實驗7，8，9顯示：GAP1與GAP2最大均達到20%，GAP3最大達到31.99%，GAP4最大為59.19%，不管是AGV數量還是總延誤時間，GA均表現出了優于PSO與ACO的求解能力。以上9組實驗進一步證明了GA在求解大規模算例上的優勢。經研究表明，本文提出的模型，通過遺傳算法的求解，可以很大程度降低AGV與岸橋之間相互等待時間，并能有效減少AGV的使用數量。

表7 不同算例規模下GA與各算法求解結果比較

6 結語

本文運用多學科變量耦合優化設計的方法，將AGV調度系統解構為AGV調度和配置兩個子系統，分別建立AGV調度和AGV配置的數學模型，并建立AGV協調調度耦合模型來協調AGV調度模型和AGV配置模型。設計算例，采用GA進行求解，并給出了最優AGV數量與最優AGV調度方案。為了更適應碼頭實際生產情況，本文擴大算例規模，用GA與PSO和ACO算法進行對比，實驗表明GA在求解大規模算例時性能優于PSO與ACO。由此可見，本文提出的模型與算法對于解決實際問題有一定的效用，并能大大減少船舶的在港時間，減少碼頭前沿AGV的擁堵。

本文尚未考慮場橋對AGV調度的影響，因此在今后的自動化碼頭AGV調度與配置耦合問題研究中，同時考慮岸橋、AGV和場橋這三者的影響來尋求最佳決策將更加具有現實意義。