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

霍凱歌++胡志華

摘要：

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

（Automated Guided Vehicle， AGV）

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

關鍵詞：

自動化集裝箱碼頭； 多載自動化引導小車（AGV）； 混合整數線性規劃（MILP）； 遺傳算法

中圖分類號： U691.3

文獻標志碼： A

0引言

隨著經濟全球化進程的加快，集裝箱碼頭得到了迅猛發展.為提高碼頭作業效率和增大效益，自動化技術開始被引進.上海自貿區政策的出臺，標志著上海國際航運中心建設轉入以現代航運服務業發展為重心的新階段.2013—2015年出臺的

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

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

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

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

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

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

1問題描述

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

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

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

2模型建立

2.1符號說明

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

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

2.2調度模型

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

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

3遺傳算法

VRP問題是數學上的組合優化問題，Golden等證明了該問題是NP難問題，隨著問題規模的擴大，計算復雜度將呈指數增長，因此不妨用遺傳算法來求解VRP問題的近似最優解.

3.1編碼與解碼

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

圖3染色體編碼示意圖

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

3.2交叉

3.3變異

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

4數學實驗

4.1實驗設置

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

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

4.2性能指標

實驗中共引入兩個性能指標：（1）最優性.小規模問題用MILP算法求出問題最優解的下界，大規模問題通過重復實驗求出問題最優解的上下界.（2）計算時間.現實問題對實時性的要求較高，對計算時間有硬性要求，所以在這里把計算時間作為算法性能的另一指標.

4.3實驗場景

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

4.4實驗結果

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

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

實驗1分別用MILP算法與遺傳算法求解該問題，并完成相應對比按照實驗設置，重復實驗；

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

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

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

實驗4驗證遺傳算法所得結果的可靠性設置交叉概率和變異概率為最優交叉概率和最優變異概率；

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

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

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

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

需要，因此圖6中的等高線示意圖就相當于每對組合的優先性示意圖.不難發現，rc=0.7，rm=0.3組合和rc=

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

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

4.5實驗總結

通過上述4組實驗，容易得出：

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

（2）用遺傳算法求出的結果與交叉概率和變異概率的賦值有關，如果交叉概率rc和變異概率rm賦值不當，調度結果的可靠性將受到影響.多次重復實驗，得出該遺傳算法交叉概率與變異概率的最優組合為rc=0.7，rm=0.3.

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

（4）重復實驗50次，并分析利用遺傳算法求出的運輸時間和平均誤差率，可以得出：對小規模問題，遺傳算法可以給出接近于精確解的調度方案，對于中大規模的問題，遺傳算法可以給出穩定的近似最優調度方案.

5結論

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

參考文獻：

[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.