基于遺傳算法的自動化集裝箱碼頭多載AGV調(diào)度

霍凱歌++胡志華

摘要：

為提升自動化集裝箱碼頭的作業(yè)效率，減輕碼頭吞吐量增大帶來的交通問題，降低自動化導(dǎo)引小車

（Automated Guided Vehicle， AGV）

的空載率，在自動化集裝箱碼頭應(yīng)用可以同時搬運(yùn)不止一個集裝箱的多載AGV，建立多載AGV調(diào)度問題的混合整數(shù)線性規(guī)劃（MixedInteger Linear Programming， MILP）模型，應(yīng)用遺傳算法進(jìn)行求解.借助算例，對比遺傳算法與MILP算法的求解效果，分析交叉概率和變異概率對遺傳算法的影響，比較多載AGV與單載AGV的作業(yè)時間，驗證遺傳算法的可靠性.該方法表明，遺傳算法不僅求解效率高，而且對MILP算法不適用的大、中型多載AGV調(diào)度問題，也能給出值得信賴的近似最優(yōu)解.

關(guān)鍵詞：

自動化集裝箱碼頭； 多載自動化引導(dǎo)小車（AGV）； 混合整數(shù)線性規(guī)劃（MILP）； 遺傳算法

中圖分類號： U691.3

文獻(xiàn)標(biāo)志碼： A

0引言

隨著經(jīng)濟(jì)全球化進(jìn)程的加快，集裝箱碼頭得到了迅猛發(fā)展.為提高碼頭作業(yè)效率和增大效益，自動化技術(shù)開始被引進(jìn).上海自貿(mào)區(qū)政策的出臺，標(biāo)志著上海國際航運(yùn)中心建設(shè)轉(zhuǎn)入以現(xiàn)代航運(yùn)服務(wù)業(yè)發(fā)展為重心的新階段.2013—2015年出臺的

《關(guān)于落實(shí)〈中國（上海）自由貿(mào)易試驗區(qū)總體方案〉加快推進(jìn)上海國際航運(yùn)中心建設(shè)的實(shí)施意見》《關(guān)于金融支持中國（上海）自由貿(mào)易試驗區(qū)建設(shè)的意見》和《全國海洋經(jīng)濟(jì)發(fā)展十二五規(guī)劃》極大地推動了航運(yùn)業(yè)的發(fā)展，使得越來越多的目光聚焦到航運(yùn)業(yè)發(fā)展上來.作為集裝箱進(jìn)出口大國，中國上海洋山港、廈門港和青島港也已經(jīng)在建造屬于中國的自動化集裝箱碼頭了.

集裝箱岸邊與堆場之間的運(yùn)輸、堆場內(nèi)的作業(yè)、道口進(jìn)出等全過程實(shí)現(xiàn)自動化的集裝箱碼頭就是自動化集裝箱碼頭.自動化集裝箱碼頭能夠大幅度降低人工費(fèi)用，提高碼頭的運(yùn)作效率，24 h連續(xù)作業(yè)，滿足船舶的大型化、高速化等需求.圖1是自動化集裝箱碼頭俯瞰圖.自動化導(dǎo)引小車（Automated Guided Vehicle， AGV）負(fù)責(zé)岸邊與堆場之間的水平運(yùn)輸，本文中統(tǒng)一采用可以同時搬運(yùn)2個20英尺小箱或者1個40英尺大箱的多載AGV負(fù)責(zé)整個碼頭的水平運(yùn)輸.

圖1自動化集裝箱碼頭俯瞰圖

國外關(guān)于自動化碼頭AGV調(diào)度的研究相對較多，但多數(shù)是關(guān)于單載AGV的.FAZLOLLAHTABAR等[1]和LUO等[2]為縮短自動化集裝箱碼頭AGV提前到達(dá)和延遲到達(dá)的時間，提出了兩階段優(yōu)化算法，并指出可以用混合整數(shù)線性規(guī)劃（MixedInteger Linear Programming， MILP）算法求解小規(guī)模問題，用啟發(fā)式算法求解大規(guī)模問題.HOMAYOUNI等[3]和CAI[4]等提出用遺傳算法求解自動化集裝箱碼頭岸橋、車輛和存儲平臺的綜合優(yōu)化問題，并考慮了包含不確定性的大規(guī)模規(guī)劃問題的求解.GELAREH等[5]擴(kuò)展了適用于AGV調(diào)度的MILP模型，并且通過引入基于拉格朗日松弛的分解策略與啟發(fā)式算法，找出了高效的智能自主車（Intelligent and Autonomous Vehicle， IAV）調(diào)度策略.SKINNER等[6]提出了基于改進(jìn)型遺傳算法的優(yōu)化策略，并用仿真方法驗證了方案的有效性.HO等[7]和HAMZHEEL等[8]提出了同時求解多載AGV的負(fù)載選擇和裝載調(diào)度問題的多屬性方法，并提出了用蟻群算法求解自動化集裝箱碼頭的AGV調(diào)度問題的方法.PJEVCEVIC等[9]提出了一種適用于自動化集裝箱碼頭作業(yè)環(huán)境的、基于數(shù)據(jù)包絡(luò)分析的、高效的集裝箱處理策略.AZIMI等[10]和ANGELOUDIS等[11]用仿真方法找出了多載AGV的最優(yōu)調(diào)度策略，提出了適用于AGV實(shí)時控制的調(diào)度方法.

國內(nèi)關(guān)于集裝箱碼頭水平運(yùn)輸系統(tǒng)的研究主要還集中在集卡上，很少有關(guān)于AGV的研究.趙悅瓊等[12]提出了改變調(diào)度計劃中的集卡配備數(shù)量，計算卸載船舶停留和集卡使用的最小總成本的數(shù)學(xué)模型，同時引入了蒙特卡洛算法和窮舉法進(jìn)行仿真.楊華龍等[13]建立了以最小化船舶在港時間和最大化岸橋利用率為目標(biāo)的模型，并針對該模型設(shè)計了擠壓算法，將泊位岸橋聯(lián)合調(diào)度看作二維裝箱問題求解.嚴(yán)偉等[14]利用聚類分析方法，給出了集裝箱碼頭出口箱的堆存策略.鄭見粹等[15]介紹了自動化集裝箱碼頭裝卸工藝系統(tǒng)的發(fā)展、工作過程及應(yīng)用情況，對不同類型的自動化集裝箱碼頭裝卸工藝系統(tǒng)方案的技術(shù)特點(diǎn)進(jìn)行了全面的分析.馬再洲等[16]提出了適用于自動化集裝箱碼頭的集中式調(diào)度算法，并用案例驗證了算法的可行性和有效性.

提高自動化集裝箱碼頭的工作效率，可以從提高岸橋的工作效率、龍門吊的工作效率和水平運(yùn)輸AGV的工作效率等3個方面入手，但是伴隨著自動化水平的提高，龍門吊和岸橋的工作效率得到了不斷提升，水平運(yùn)輸系統(tǒng)隨之成為了自動化碼頭的瓶頸.因此，本文從提高水平運(yùn)輸系統(tǒng)的效率入手，以自動化集裝箱碼頭同時運(yùn)輸不同尺寸集裝箱為背景，建立多載AGV的調(diào)度模型，并提出用遺傳算法求解多載AGV調(diào)度問題的求解策略，最后用真實(shí)案例驗證多載AGV的優(yōu)越性.

1問題描述

AGV是自動化集裝箱碼頭的水平運(yùn)輸工具，一般分為裝載20英尺集裝箱的小型AGV和裝載40英尺集裝箱的大型AGV兩種.在多數(shù)自動化集裝箱碼頭，為滿足運(yùn)輸工具對運(yùn)輸任務(wù)的普適性，同時降低路徑規(guī)劃的復(fù)雜性，普遍采用統(tǒng)一規(guī)格的大型AGV單載完成所有的運(yùn)輸任務(wù).不難發(fā)現(xiàn)，在運(yùn)輸20英尺集裝箱時，AGV有一半的容量未被充分利用，而且隨著碼頭吞吐量的增大，投入運(yùn)輸?shù)腁GV越來越多，這不僅產(chǎn)生了巨大的資源浪費(fèi)，而且極大地增加了交通負(fù)擔(dān).因此，本文從增大AGV的運(yùn)輸能力，減小投入運(yùn)輸?shù)腁GV數(shù)量入手，提出多載AGV的調(diào)度策略.

傳統(tǒng)情況下，可以將AGV調(diào)度問題看作m∶n的分配問題，其目標(biāo)為運(yùn)輸時間或者運(yùn)輸費(fèi)用最少，這很容易找出最優(yōu)調(diào)度策略.但對于多載AGV的調(diào)度問題，已經(jīng)超出了簡單分配問題的范疇，調(diào)度中不僅需要分配運(yùn)輸任務(wù)給相應(yīng)的AGV，而且需要安排好具體的裝載和交付順序，因為只有這樣才能確保AGV的利用率盡可能高，運(yùn)輸時間、運(yùn)輸費(fèi)用盡可能低，船舶停泊時間盡可能短等.

本文從單輛多載AGV的調(diào)度入手，假設(shè)各集裝箱的裝載順序不受時間限制，AGV可以從任意任務(wù)的起點(diǎn)開始運(yùn)輸，其規(guī)劃目標(biāo)為運(yùn)輸時間最短.假設(shè)共有N個任務(wù)，每個任務(wù)有相應(yīng)的裝載點(diǎn)和交付點(diǎn)，所以可以用集合I={1，2，3，…，2N-1，2N}表示N個任務(wù)的全部裝卸點(diǎn).本文還引入虛擬端點(diǎn)2N+1和2N+2，用來表示起點(diǎn)和終點(diǎn)，于是任務(wù)點(diǎn)總數(shù)為2N+2，其中不同任務(wù)點(diǎn)可以代表相同的物理位置.現(xiàn)假設(shè)有3個運(yùn)輸任務(wù)，任務(wù)c1和c2為20英尺集裝箱，任務(wù)c3為40英尺集裝箱，于是多載AGV的調(diào)度方案見圖2.

2模型建立

2.1符號說明

假設(shè)某自動化碼頭某時刻共有N個運(yùn)輸任務(wù)，P表示任務(wù)裝載點(diǎn)的集合，D表示交付點(diǎn)的集合，I=P∪D表示裝載點(diǎn)與交付點(diǎn)的總集合，并且I+=I∪{S，E}表示增加了虛擬起點(diǎn)和虛擬終點(diǎn)的任務(wù)點(diǎn)集合.運(yùn)輸任務(wù)的裝載點(diǎn)坐標(biāo)Pm，交付點(diǎn)坐標(biāo)Dm和AGV運(yùn)行速度θ已經(jīng)給出，并且用Tm，n表示AGV從任務(wù)點(diǎn)m到任務(wù)點(diǎn)n的運(yùn)行時間，dm表示AGV在任務(wù)點(diǎn)m的容量改變情況，Cm表示在任務(wù)點(diǎn)m完成操作后AGV容量的占用情況，C表示AGV的最大負(fù)荷能力.

如果AGV相繼訪問任務(wù)點(diǎn)m和n，則決策變量xm，n=1，否則xm，n=0；決策變量zm表示AGV在任務(wù)點(diǎn)m完成相應(yīng)操作的時間.

2.2調(diào)度模型

以最小化最末任務(wù)完成時間f為目標(biāo)，建立自動化集裝箱碼頭多載AGV調(diào)度模型.該模型的目標(biāo)函數(shù)與約束條件如下：

目標(biāo)函數(shù)（1）是最小化最末任務(wù)完成時間，它服從式（2）～（16）的約束.式（2）限定最末任務(wù)完成時間不小于任何裝載和交付操作的完成的時間.式（3）和（4）是對操作完成時間的限制：式（3）指出，如果xm，n=1，則zn≥zm+Tm，n恒成立，其中m，n∈I，m≠n；式（4）限定任何任務(wù)的交付時間一定不小于該任務(wù)的裝載時間.式（5）限定任何運(yùn)輸任務(wù)的裝載和交付操作一定不是孤立存在的，即一定有且僅有一個前驅(qū)和一個后繼.式（6）限定任務(wù)序列中的任何操作能且只能被執(zhí)行一次.式（7）和（8）限定虛擬起點(diǎn)有且僅有一個后繼，虛擬終點(diǎn)有且僅有一個前驅(qū).式（9）指出，如果AGV在任務(wù)點(diǎn)m完成操作后，立即去任務(wù)點(diǎn)n執(zhí)行操作，那么在任務(wù)點(diǎn)n完成操作后AGV的負(fù)載Cm等于在任務(wù)點(diǎn)m完成操作后AGV的負(fù)載Cm加上AGV在任務(wù)點(diǎn)n的負(fù)載變化dn.式（10）～（12）是對AGV負(fù)載的約束.式（13）限定任意任務(wù)點(diǎn)m的操作不能作自己的前驅(qū)或后繼，任何操作不能在虛擬開始前開始，任何任務(wù)不能在虛擬結(jié)束后開始.式（14）給出最小化最終完成時間f，任意操作的完成時間zm和從任務(wù)點(diǎn)m到任務(wù)點(diǎn)n的時間間隔Tm，n的下界.式（15）限定決策變量xm，n為01變量.式（16）給出了無窮大量M1的取值.

3遺傳算法

VRP問題是數(shù)學(xué)上的組合優(yōu)化問題，Golden等證明了該問題是NP難問題，隨著問題規(guī)模的擴(kuò)大，計算復(fù)雜度將呈指數(shù)增長，因此不妨用遺傳算法來求解VRP問題的近似最優(yōu)解.

3.1編碼與解碼

采用集裝箱運(yùn)輸任務(wù)的序號進(jìn)行染色體編碼，用i表示第i個運(yùn)輸任務(wù)，則染色體序列可以表示為{1，2，3，…，N}，其中N是運(yùn)輸任務(wù)的數(shù)量，而且這些運(yùn)輸任務(wù)中既有小箱也有大箱.隨機(jī)生成n個染色體的全排列，就構(gòu)成了初始種群.圖3就是一條長度為16的染色體.

圖3染色體編碼示意圖

為清晰形象地表示解碼的過程，給出解碼示意圖，見圖4.圖中Ci，j表示從任務(wù)i的裝載點(diǎn)到任務(wù)j的裝載點(diǎn)的最短運(yùn)行時間，于是可以用從虛擬起點(diǎn)到虛擬終點(diǎn)的最短距離表示整個任務(wù)序列的最早完成時間.

3.2交叉

3.3變異

本文中的變異方法采用倒置變異，也就是在染色體上隨機(jī)選擇兩個位置，然后顛倒兩個位置間的基因序列，見圖5.

4數(shù)學(xué)實(shí)驗

4.1實(shí)驗設(shè)置

將從自動化集裝箱碼頭收集到的實(shí)驗數(shù)據(jù)存放于data.xlsx中，其中多載AGV的行駛速度AGVSpeed取值5 km/h，作業(yè)點(diǎn)個數(shù)ODnum取值100.作業(yè)點(diǎn)的物理坐標(biāo)存放于元胞矩陣XY中，運(yùn)輸任務(wù)的序號、裝載點(diǎn)、交付點(diǎn)和任務(wù)大小等數(shù)據(jù)存放于元胞矩陣ODL中.

為評估算法的性能，用MATLAB編寫該遺傳算法，并用其求解一系列自動化碼頭的真實(shí)問題，并且在實(shí)驗中作如下設(shè)置：設(shè)定小規(guī)模問題包含的任務(wù)量為1～15，中等規(guī)模問題包含的任務(wù)量為15～40，大規(guī)模問題包含的任務(wù)量為40～100.

4.2性能指標(biāo)

實(shí)驗中共引入兩個性能指標(biāo)：（1）最優(yōu)性.小規(guī)模問題用MILP算法求出問題最優(yōu)解的下界，大規(guī)模問題通過重復(fù)實(shí)驗求出問題最優(yōu)解的上下界.（2）計算時間.現(xiàn)實(shí)問題對實(shí)時性的要求較高，對計算時間有硬性要求，所以在這里把計算時間作為算法性能的另一指標(biāo).

4.3實(shí)驗場景

在本文算例分析部分共做4組實(shí)驗，具體場景設(shè)置見表1，其中：rc為交叉概率；rm為變異概率；ngen為遺傳算法迭代次數(shù).

4.4實(shí)驗結(jié)果

實(shí)驗1.根據(jù)調(diào)度模型在MATLAB中編寫MILP算法，并用YALMIP工具箱中的GUROBI6.0求解器求解.容易得出：隨著任務(wù)量的增大，MILP算法的計算時間呈指數(shù)增長趨勢，而且當(dāng)任務(wù)量大于8時，短時間內(nèi)不能求出精確解.用遺傳算法再次求解上述

各問題，并將兩種算法求出的運(yùn)輸時間和所用計算

實(shí)驗1分別用MILP算法與遺傳算法求解該問題，并完成相應(yīng)對比按照實(shí)驗設(shè)置，重復(fù)實(shí)驗；

限定ngen=100，Npep=50，rc=0.7，rm=0.4，rpareto=0.65

實(shí)驗2設(shè)置不同的rc和rm，研究交叉概率與變異概率對實(shí)驗結(jié)果的影響令rc=0.1，0.2，…，0.9，rm=0.1，0.2，…，0.9；其他設(shè)置與實(shí)驗1相同；運(yùn)行遺傳算法，求出不同的交叉概率與變異概率組合對應(yīng)的實(shí)驗結(jié)果；根據(jù)實(shí)驗結(jié)果，用等高線示意圖法找出最優(yōu)交叉概率與變異概率的組合

實(shí)驗3對比單載AGV與多載AGV的運(yùn)輸效率令rc與rm分別等于最優(yōu)交叉概率與最優(yōu)變異概率，其他設(shè)置與實(shí)驗1相同；求出用單載AGV完成指定運(yùn)輸任務(wù)的時間；求出用多載AGV完成相同運(yùn)輸任務(wù)的時間

實(shí)驗4驗證遺傳算法所得結(jié)果的可靠性設(shè)置交叉概率和變異概率為最優(yōu)交叉概率和最優(yōu)變異概率；

重復(fù)實(shí)驗，求出最短作業(yè)時間和平均誤差率；平均誤差率Dev=（Ni=1（（Vi-Vmin）/Vmin）/N）×100%，其中Vi是第i次實(shí)驗得到的結(jié)果，Vmin表示N次實(shí)驗中的最小實(shí)驗結(jié)果

時間記入表2.不難發(fā)現(xiàn)，兩種算法給出的調(diào)度方案的運(yùn)輸時間相差不大，但隨著問題規(guī)模的擴(kuò)大，遺傳算法的計算時間改變很小，但是MILP算法的計算時間卻飛速增長.由于自動化集裝箱碼頭任務(wù)量通常較大，且對實(shí)時性要求較高，因此，遺傳算法更適用于求解該多載AGV調(diào)度問題.

實(shí)驗2.將遺傳算法的交叉概率和變異概率分別取0.1，0.2，…，0.9，并將它們一一配對，生成81種不同的組合；分別將這81對交叉概率與變異概率的組合作為遺傳算法的交叉概率和變異概率進(jìn)行運(yùn)算；為增加可信度，每組實(shí)驗重復(fù)進(jìn)行5次，取最優(yōu)結(jié)果作為每組實(shí)驗的結(jié)果.

令z（i，j）=100 000/T（i，j），其中T（i，j）為每組實(shí)驗的實(shí)驗結(jié)果，然后作出如圖6所示的關(guān)于z的等高線示意圖.利用遺傳算法求出的運(yùn)輸時間越短，越符合碼頭方面的

需要，因此圖6中的等高線示意圖就相當(dāng)于每對組合的優(yōu)先性示意圖.不難發(fā)現(xiàn)，rc=0.7，rm=0.3組合和rc=

0.7，rm=0.5組合的優(yōu)越性明顯高于其他組合，因為變異概率一般較小，所以該遺傳算法的最優(yōu)交叉概率和最優(yōu)變異概率分別取rc=0.7，rm=0.3.

實(shí)驗3.分別在不同任務(wù)量下進(jìn)行實(shí)驗，并對比單載AGV與多載AGV完成相應(yīng)運(yùn)輸任務(wù)所需的時間，見圖7和表3.顯然，除了任務(wù)量為5個的情況，多載AGV都能在更短的時間內(nèi)完成給定運(yùn)輸任務(wù).

4.5實(shí)驗總結(jié)

通過上述4組實(shí)驗，容易得出：

（1）該自動化集裝箱碼頭上的多載AGV調(diào)度問題是NP難問題.對小規(guī)模問題，可以利用YALMIP工具箱中的GUROBI求解器得出精確解，但中大規(guī)模問題已經(jīng)超出精確算法的計算適用范圍，只能用遺傳算法等智能算法求出近似最優(yōu)解.

（2）用遺傳算法求出的結(jié)果與交叉概率和變異概率的賦值有關(guān)，如果交叉概率rc和變異概率rm賦值不當(dāng)，調(diào)度結(jié)果的可靠性將受到影響.多次重復(fù)實(shí)驗，得出該遺傳算法交叉概率與變異概率的最優(yōu)組合為rc=0.7，rm=0.3.

（3）通過實(shí)驗3中的多載AGV與單載AGV的運(yùn)輸時間對比可以看出，多載AGV的效率更高，更能滿足自動化集裝箱碼頭對工作效率的要求，且在碼頭運(yùn)作中小箱越多，越能發(fā)揮出多載AGV的作用.

（4）重復(fù)實(shí)驗50次，并分析利用遺傳算法求出的運(yùn)輸時間和平均誤差率，可以得出：對小規(guī)模問題，遺傳算法可以給出接近于精確解的調(diào)度方案，對于中大規(guī)模的問題，遺傳算法可以給出穩(wěn)定的近似最優(yōu)調(diào)度方案.

5結(jié)論

為進(jìn)一步提升自動化集裝箱碼頭的作業(yè)效率，減輕碼頭吞吐量增大帶來的交通負(fù)擔(dān)，降低AGV的空載率，本文從增大AGV的運(yùn)輸能力，減少投入運(yùn)輸?shù)腁GV的數(shù)量入手，提出在自動化集裝箱碼頭應(yīng)用多載AGV的構(gòu)想，并給出多載AGV調(diào)度問題的混合整數(shù)線性規(guī)劃（MILP）模型.顯然，該多載AGV調(diào)度問題屬于NP難問題，MILP算法只能用來驗證模型的正確性或求解小規(guī)模問題，對于中大規(guī)模的調(diào)度問題，需要用遺傳算法等智能算法求解.進(jìn)行多組實(shí)驗后，得出結(jié)論：多載AGV的應(yīng)用能夠提升自動化集裝箱碼頭的作業(yè)效率，減輕交通擁堵負(fù)擔(dān)，且遺傳算法能夠快速給出可信度高的多載AGV調(diào)度方案.實(shí)際上，在自動化集裝箱碼頭，每次參與運(yùn)輸?shù)腁GV數(shù)量對調(diào)度也有一定影響，而文中缺乏對該影響的考慮，因此，多載AGV的配置問題值得進(jìn)一步研究.

參考文獻(xiàn)：

[1]FAZLOLLAHTABAR H， SAIDIMEHRABAD M， BALAKRISHNAN J. Mathematical optimization for earliness /tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms[J]. Robotics and Autonomous Systems， 2015， 72（C）： 131138.

[2]LUO J B， WU J. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E： Logistics and Transportation Review， 2015， 79： 4964.

[3]HOMAYOUNI S M， TANG S H， MOTLAGH O. A genetic algorithm for optimization of integrated scheduling of cranes， vehicles， and storage platforms at automated container terminals[J]. Journal of Computational and Applied Mathematics， 2014， 270： 545556.

[4]CAI B H， HUANG S D， DISSANAYAKE G， et al. Rescheduling policies for largescale task allocation of autonomous straddle carriers under uncertainty at automated container terminals[J]. Robotics and Autonomous Systems， 2014， 62（4）： 506514.

[5]GELAREH S， MERZOUKI S， MCGINLEY K， et al. Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J]. Transportation Research Part C： Emerging Technologies， 2013， 33（33）： 121.

[6]SKINNER B， YUAN S， HUANG S D， et al. Optimisation for job scheduling at automated container terminals using genetic algorithm[J]. Computers & Industrial Engineering， 2013， 64（1）： 511523.

[7]HO Y C， LIU H C， YIH Y. A multipleattribute method for concurrently solving the pickupdispatching problem and the loadselection problem of multipleload AGVs[J]. Journal of Manufacturing Systems， 2012， 31（3）： 288300.