梁承姬，陳登川

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

2.西安外事學(xué)院，西安 710000

1 引言

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

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

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

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

2 問題描述

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

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

本文考慮AGV的雙循環(huán)作業(yè)，即有四種運輸方式：（a）只卸，岸橋卸箱后滿車運輸?shù)竭M口箱區(qū)，場橋提箱后，空車回岸邊；（b）只裝，從堆場的出口箱區(qū)滿車運輸?shù)桨哆叺却稑蜓b船，再空車回堆場；（c）先裝后卸，從堆場的出口箱區(qū)滿車運輸?shù)桨哆叺却稑蜓b船，空車去另一臺岸橋處等待岸橋卸箱，再滿車運輸?shù)竭M口箱區(qū)；（d）先卸后裝，從岸橋處滿車運輸?shù)竭M口箱區(qū)，場橋提箱后，空車去出口箱區(qū)，此箱區(qū)場橋裝箱后，滿車運輸?shù)桨哆叺却稑蜓b船。

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

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

圖2 多學(xué)科變量耦合優(yōu)化設(shè)計方法

3 數(shù)學(xué)模型

3.1 Model I：AGV調(diào)度模型

符號：

i,j：集裝箱任務(wù)。

I,F：虛擬的初始和結(jié)束任務(wù)。

P：集裝箱任務(wù)總和。

J+：裝箱任務(wù)集。

J-：卸箱任務(wù)集，且有J=J+?J-。

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

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

參數(shù)：

ti,j：AGV在作業(yè)任務(wù)i與任務(wù) j之間的時間間隔。

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

hqi：岸橋處理各任務(wù)的時間。

hyi：場橋處理各任務(wù)的時間。

ωi,j：AGV完成任務(wù)i緊接著去完成任務(wù) j產(chǎn)生的時間延誤成本。

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

圖3 AGV作業(yè)系統(tǒng)耦合模型框架

決策變量：

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

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

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

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

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

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

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

3.2 Model II：AGV配置模型

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

圖4 AGV配置模型的網(wǎng)絡(luò)示意圖

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

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

符號：

i,j：表示集裝箱任務(wù)；

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

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

n：時間窗的等分量。

參數(shù)：

ei：任務(wù)i的最早完成時刻；

ri：岸橋?qū)嶋H完成其所屬的集裝箱任務(wù)的時刻；

ti,j：表示運輸時間。

決策變量：

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

v表示AGV的數(shù)量。

建立模型：

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

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

3.3 AGV協(xié)調(diào)調(diào)度耦合模型

在上述AGV調(diào)度和AGV配置子模型的基礎(chǔ)上協(xié)調(diào)調(diào)度和配置問題，實現(xiàn)AGV協(xié)調(diào)調(diào)度的最優(yōu)。這需要將調(diào)度和配置子模型進行多次的循環(huán)迭代計算，不斷更新公用設(shè)計變量的值，并設(shè)定相應(yīng)迭代計算判斷條件來控制協(xié)調(diào)子模型的耦合計算。

迭代計算條件：

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

迭代計算流程如下：

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

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

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

圖5 迭代計算流程圖

按照上述流程不斷地循環(huán)迭代，直到不再符合迭代條件，或者所求的目標(biāo)函數(shù)值不再變動，則停止循環(huán)迭代計算，最終將得到最優(yōu)的AGV配置數(shù)量和調(diào)度方案。

4 算法設(shè)計

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

4.1 Model I算法設(shè)計

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

（1）染色體編碼

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

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

具體步驟：

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

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

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

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

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

（2）適應(yīng)度函數(shù)

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

（3）選擇、交叉

選擇操作為輪盤賭法。

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

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

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

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

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

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

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

（4）變異

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

步驟2若s為其所在任務(wù)片段的第一個任務(wù)，發(fā)現(xiàn)s的繼后任務(wù)為z，隨機選出任務(wù)z的非s可行先前任務(wù)s′。

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

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

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

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

（5）循環(huán)終止條件

達(dá)到設(shè)定最大迭代次數(shù)即終止循環(huán)。

4.2 Model II算法設(shè)計

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

（1）染色體編碼

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

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

具體步驟：

步驟1根據(jù)4.1節(jié)染色體生成方式生成Model II算法染色體的整數(shù)部分。

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

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

（2）適應(yīng)度函數(shù)

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

（3）選擇、變異操作

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

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

（4）循環(huán)終止條件

達(dá)到設(shè)定最大迭代次數(shù)即終止循環(huán)。

5 算例分析及算法比較

5.1 設(shè)計算例

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

表1 岸橋作業(yè)順序表

表2 岸橋與箱區(qū)之間的距離

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

表3 箱區(qū)之間的距離

表4 岸橋之間的距離

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

5.2 結(jié)果分析

5.2.1 模型有效性驗證

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

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

圖10 Model I第1代迭代過程

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

圖11 Model II第1代迭代過程

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

表5 11臺AGV不同任務(wù)時間窗下計算結(jié)果對比

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

5.2.2 數(shù)值計算結(jié)果

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

表6 AGV耦合調(diào)度計算結(jié)果

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

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

根據(jù)最優(yōu)解對應(yīng)的AGV調(diào)度方案，畫出甘特圖如圖13所示。

圖13 AGV最優(yōu)調(diào)度方案甘特圖

在圖13中，AGV1對應(yīng)的任務(wù)編號依次為：12，26，36，40，52，18，即AGV1依次執(zhí)行第12號，26號，36號，40號，52號，18任務(wù)。

5.3 算法比較

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

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

表7 不同算例規(guī)模下GA與各算法求解結(jié)果比較

6 結(jié)語

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

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