自動化集裝箱碼頭多載AGV調度問題研究

霍 凱 歌，　張 亞 琦，　胡 志 華

( 上海海事大學 物流研究中心， 上海　201306 )

?

自動化集裝箱碼頭多載AGV調度問題研究

霍 凱 歌，張 亞 琦，胡 志 華*

( 上海海事大學 物流研究中心， 上海201306 )

摘要：多載AGV是一種自動化集裝箱碼頭水平作業設備，它可以同時搬運多個集裝箱，可縮小AGV流的規模，增大AGV的利用率．為了提高自動化集裝箱碼頭的作業效率，考慮了垂岸式集裝箱堆場布局，以最小化作業總費用為規劃目標，以作業限制、時間窗長度、負載平衡等為約束條件，以事件驅動的調度策略為研究方法，建立了多載AGV調度問題的混合整數規劃模型．同時利用GUROBI和遺傳算法求解多載AGV的作業總費用和空載率，并與相同條件下單載AGV的作業總費用和空載率對比，驗證了多載AGV的優越性．

關鍵詞：多載AGV；時間窗；事件驅動的AGV調度；混合整數規劃；遺傳算法

0引言

多載AGV(multi-load automated guided vehicle) 是一種自動化集裝箱碼頭水平作業設備，在自動化集裝箱碼頭應用前景巨大．伴隨著經濟全球化步伐的加快，越來越多的生產經營活動和資源配置活動趨于在全球范圍內進行．據統計，世界貿易的90%以上是通過海運方式實現的，集裝箱運輸隨之成為了一種重要的運輸方式，目前有超過一半的貨物采用集裝箱運輸．我國的集裝箱運輸發展尤其迅速，在2014年，我國的寧波-舟山港、上海港、天津港、唐山港、廣州港、蘇州港、青島港、大連港均躋身全球港口貨物吞吐量前十大港口，但是作為世界第一大集裝箱生產和運輸國，我國卻沒有技術成熟的、自動化程度高的自動化集裝箱碼頭．

自動化集裝箱碼頭就是將集裝箱碼頭岸邊與堆場之間的運輸、堆場內的作業、道口的進出等全過程實現自動化運作的碼頭．自動化集裝箱碼頭相對于普通集裝箱碼頭有以下優點：大幅度降低人工費用和總運行費用、降低員工勞動強度、提高碼頭的運行效率、可24 h連續作業等．在自動化集裝箱碼頭上，岸橋負責泊位部分的裝卸工作，龍門吊負責堆場區域的裝卸工作，而AGV負責碼頭范圍內的水平運輸．伴隨著自動化集裝箱碼頭吞吐量的增加，碼頭作業效率越來越受到碼頭管理者和船務公司的重視，越來越多的新技術被應用到岸橋和龍門吊等垂直作業設備上，自動化碼頭的垂直作業效率得到了質的提升，水平作業效率隨之成為了制約碼頭整體作業效率提升的瓶頸．

國外學者研究的重點主要集中在自動化集裝箱碼頭單載AGV調度的研究上，對多載AGV的研究相對較少．Azimi等[1]用仿真方法找出了多載AGV的最優調度策略．多載AGV調度面臨4個問題：(1)運輸任務的確定問題；(2)交付調度問題；(3)裝載調度問題；(4)負載選擇問題，Ho等[2-3]對前3個問題進行了研究，給出了不同的任務裝載策略和任務交付規則，并用仿真方法檢驗了其在不同環境中的作業效率．Grunow等[4]利用車輛的有效性，提出了一種求解多載AGV調度問題的基于優先權的調度算法，并且建立了MILP模型來驗證優先權調度算法的有效性．Homayouni等[5]提出了一種用遺傳算法求解自動化碼頭上岸橋、車輛和存儲平臺的綜合優化問題的方案．Fazlollahtabar等[6]提出了一種自動化碼頭最小化多載AGV的提前與延遲時間的綜合啟發算法．Luo等[7]提出了一種求解自動化集裝箱碼頭上的集裝箱存儲和車輛規劃問題的雙回路策略．Skinner等[8]針對自動化碼頭的優化問題，提出了一種基于改進型遺傳算法的優化策略．Ho等[9-10]提出了一種可以同時求解裝載調度和負載選擇的多屬性算法．Angeloudis等[11]提出了適用于AGV實時控制的調度方法，得出了優于啟發式算法的實驗結果．

國內針對自動化集裝箱碼頭的研究相對較少，關于自動化集裝箱碼頭上多載AGV調度問題的研究則更少．張煜等[12]針對集裝箱碼頭交通特點, 提出了基于模糊控制的緩沖區策略．史飛等[13]針對港口未來期望平均24 h完成單只超巴拿馬型船舶的卸船作業，對該碼頭的卸船作業流程進行了模擬, 得到平均卸船作業時間約為17.75 h．溫智民等[14]以新型自動化集裝箱碼頭中間運輸系統為研究對象，利用仿真優化方法搜索AGV的優化調度方案，并以遺傳算法為研究方法，非枚舉地從所有可能的動態調度方案中找出了裝卸總時間最小的調度方案．鄭見粹等[15]介紹了自動化集裝箱碼頭裝卸工藝系統的發展、工作過程及應用情況，對不同類型的自動化集裝箱碼頭裝卸工藝系統方案的技術特點進行了全面的分析與對比．

目前，針對提高碼頭水平作業效率，主要從優化運輸任務和AGV之間的分配、優化AGV的作業路徑、控制交通及減輕交通擁堵三個方面入手．顯然后兩方面已經得到較充分的研究，涌現出了不少好的優化方案，但是關于第一方面的研究較少．本文從此入手，首先根據多載AGV作業的時間約束、負載約束，以及分配唯一性原則，建立多載AGV的調度模型；然后提出用混合整數規劃算法求解小規模問題，用遺傳算法求解大規模問題的求解策略；最后分別用兩種算法求解相應案例，并完成相關分析．

1問題描述

針對自動化集裝箱碼頭水平運輸問題，多數學者從單載AGV的路徑規劃入手，通過優化AGV的路徑方案來提升AGV的作業效率．AGV是自動化集裝箱碼頭上的水平運輸工具，為了達到對運輸任務的普適性，同時降低路徑規劃的復雜性，碼頭方面普遍采用可以裝載12 m集裝箱的大型AGV單載運輸碼頭上流動的6 m與12 m集裝箱．不難發現，在運輸6 m集裝箱時，一半的AGV荷載未被充分利用，隨之產生了資源的浪費，而且為了盡快完成裝卸任務，投入了大量的AGV，極大地增加了交通流的規模，留下了交通堵塞的隱患．本文從充分利用AGV的荷載入手，在加快作業效率的同時，減小交通流的規模，即考慮讓AGV每次運輸一個12 m集裝箱或者同時運輸兩個6 m集裝箱．

在傳統的單載模式下，可以將AGV調度問題看作m∶n的分配問題，其目標是最小化作業時間或最小化作業費用，可以比較容易地找出優化方案．但是對于多載AGV調度問題，復雜性就大大增加了，在調度中，除了需要給每輛AGV分配運輸任務，而且需要給每輛AGV安排好執行裝載和交付操作的具體順序，這就使得自動化集裝箱碼頭多載AGV調度問題的規劃難度大大增加了．

圖1為垂岸式集裝箱堆場布局的自動化集裝箱碼頭的俯瞰圖，在裝船或卸船中，AGV一旦收到運輸請求，即從停靠站出發，開始執行本時段的所有運輸任務．為了方便調度，本文定義所有AGV最多能裝載兩個集裝箱．圖2給出了具有兩個運輸任務的多載AGV作業運輸圖，AGV收到運輸請求后立即從停靠站出發，在QC1、QC2處完成集裝箱的裝載，滿載駛往堆場，然后在交付點SC1和SC2完成交付，最后駛回停靠站．在正常作業中，AGV完成一次運輸任務后，立即檢查是否還有運輸任務需要執行，如果有，就去執行下一個運輸任務，否則，就駛回停靠站，結束此次調度．

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

圖2　作業過程圖

2模型建立

2.1符號說明

以圖1所示的垂岸式自動化集裝箱碼頭為例，假設某時間段內共有n個運輸任務，由于該碼頭的平面布局已知，此時可以把裝船(或卸船)問題看作帶時間窗的車輛路徑規劃問題求解．通過運輸任務的裝載點和交付點來識別每個任務，例如，用i和n+i來識別任務i，其中i代表任務i的裝載點，n+i代表任務i的交付點，并且不同的任務點也可以表示相同的物理地址．在這里P={1,2,…,n}表示裝載點的集合，D={n+1,n+2,…,2n}表示交付點的集合，N=P∪D表示所有任務點的集合．如果任務i表示從i點運輸di個集裝箱到n+i點，那么li=di，ln+i=-di．

假設AGV的集合為K，由于并不是所有AGV都可以負責任意的運輸任務，AGVk擁有唯一的集合Nk=Pk∪Dk，其中Nk、Pk、Dk分別為集合N、P、D的子集．對于任意AGVk，定義網絡Gk=(Vk,Ak)，其中Vk=Nk∪{o(k),d(k)}表示AGVk的所有任務點與AGVk的出發點和停靠點的集合，Vk×Vk子集Ak表示AGVk所有可行的弧．AGVk的最大負載能力為Ck，由于文中采用統一的AGV，也可用固定值C表示．ti,j,k和ci,j,k分別表示AGVk從端點i到端點j的時間和費用，其中i,j∈Vk．

如圖3所示，對于任意AGVk，可行的裝載與交付路線是：從起始點o(k)出發，途經網絡Gk中可行的路徑，訪問且只訪問一次Vk中的所有節點，然后到達停靠點d(k)的線路．如果某AGV訪問端點i∈N，則必須在時間窗[ai,bi]內完成，屆時服務時間si開始；如果AGV提前到達，則必須等待．

文中的多載AGV并非一直采用多載運輸模式，只有當多載運輸模式能夠滿足預定的時間與負載約束，并能達到縮短運輸路程與降低空載率的目標時，多載AGV才采用多載運輸模式，其他情況下，多載AGV往往被當作單載AGV應用．因此在模型中，僅限定任意AGVk完成任意操作i后的負載Li,k服從約束0≤Li,k≤Ck，而非賦予其定值．

圖3　作業路徑圖

2.2調度模型

在模型中，共包含3類變量：二進制變量xi,j,k，如果弧(i,j)∈Ak且由AGVk訪問，則xi,j,k=1，否則xi,j,k=0；時間變量Ti,k表示AGVk在端點i∈Vk開始服務的時間；變量Li,k表示AGV在端點i∈Vk完成操作后的荷載，因此目標函數可以定義為

(1)

約束條件

(2)

?k∈K,j∈Nk

(3)

(4)

(5)

(6)

xi,j,k(Ti,k+si+ti,j,k-Tj,k)≤0；

?k∈K,(i,j)∈Ak

(7)

ai≤Ti,k≤bi； ?k∈K,i∈Vk

(8)

Ti,k+tj,n+i,k≤Tn+i,k； ?k∈K,i∈Pk

(9)

xi,j,k(Li,k+dj-Lj,k)=0；

?k∈K,(i,j)∈Ak

(10)

di≤Li,k≤Ck； ?k∈K,i∈Pk

(11)

0≤Ln+i,k≤Ck+dn+i； ?k∈K,n+i∈Dk

(12)

Lo(k),k=0； ?k∈K

(13)

Ld(k),k=0； ?k∈K

(14)

xi,j,k∈{0,1}； ?k∈K,(i,j)∈Ak

(15)

模型的約束如式(2)～(15)．式(2)～(4)描繪了一個多物流網絡結構，限定任意AGVk必須從出發點o(k)出發，完成所有任務后抵達停靠點d(k)，并且保證途中經過的各端點的出度等于其入度．式(5)、(6)限定每個運輸任務能且僅能被執行一次，同一任務的裝載和交付必須由同一AGV完成．式(7)～(9)給出了關于執行時間的約束，如果xi,j,k=1，即AGVk完成操作i后，去執行操作j時，AGV開始執行操作j的時間Tj,k一定不小于AGVk開始執行任務i的時間Ti,k、任務i的執行時間si與AGVk從執行點i到執行點j的時間之和，由于xi,j,k是0-1變量，式(7)也可以表示為Ti,k+si+ti,j,k-Tj,k≤Mi,j(1-xi,j,k)，其中Mi,j表示一個足夠大的常數，而且Mi,j可以用max{bi+si+ti,j,k-aj,0},(i,j)∈Ak表示，AGVk開始執行任意裝卸操作i的時間Ti,k必須在相應的時間窗內，AGVk開始執行交付操作的時間一定不小于它開始執行裝載操作的時間Ti,k與AGVk從裝載點到交付點的行駛時間ti,n+i,k的和．式(10)～(13)給出了負載平衡的約束，如果xi,j,k=1，則Li,k+dj-Lj,k=0恒成立，因此，式(10)也可以表示為-M2(1-xi,j,k)≤Li,k+dj-Lj,k≤M2(1-xi,j,k)，其中M2取Ck．式(11)給出了AGV執行裝載操作的負載約束，式(12)給出了執行交付操作的負載約束．式(13)、(14)給出了任意AGVk在起始點o(k)和停靠點d(k)的負載情況．式(15)限定xi,j,k為0-1變量，對于Ti,k,k∈K,i∈Vk，可以從式(8)和(9)看出，Ti,k≥0恒成立，對于Li,k,k∈K,i∈Vk，可以從式(11)～(14)看出，0≤Li,k≤Ck恒成立，且Li,k為整數．

該多載AGV調度模型是一個考慮裝載和交付操作的帶時間窗的車輛路徑規劃模型，其決策變量X是一個1×KN2的列向量，并且在模型中，規劃精確到每一個操作，不再局限于完整的運輸任務．該多載AGV調度模型比一般的調度模型要復雜得多，規劃中不僅要進行運輸任務與AGV之間的分配，而且要安排好每輛AGV裝卸操作的具體順序，其復雜度為O(K(3N2+6N+4)+N)，其中K表示AGV數，N表示任務數．

3遺傳算法

VRP問題是數學上的組合優化問題，Golden等證明了該問題是NP-hard問題，因此，不妨用遺傳算法求解該VRP問題的近似最優解．

3.1編碼

本文采用將運輸任務分配給相應多載AGV的方式進行編碼，如果第i個位置的編碼為k，則表示第i個任務由AGVk完成，因此長度為N的染色體可由N個1到NVAR之間整數的排列表示，其中NVAR表示多載AGV的數量，圖4是一條長度為19，共有3輛多載AGV參與運輸的染色體編碼示意圖．

圖4染色體編碼示意圖

Fig.4The diagram of chromosome encoding

3.2解碼

圖5　第i個染色體片段的解碼過程

3.3交叉

本文采用1990年Syswerda提出的基于位置的交叉方法(position-based crossover)，這種交叉方法尤其適用于排列形式的染色體，如下所示：

輸入兩個父代染色體P1、P2

輸出子代染色體child

第1步從父代染色體P1中隨機選擇一些位置．

第2步通過復制P1所選位置上的基因生成一個子代染色體原型．

第3步刪除染色體P2上選定位置的基因，剩下的部分就是子代染色體child需要的．

第4步將P2上的基因從左到右依次放入子代染色體child上未確定基因的位置上，這樣就成功地生成了一個子代染色體．

3.4變異

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

圖6　倒置變異示意圖

4案例分析

多載AGV調度問題是一個VRPPDTW(考慮裝載和交付操作的帶時間窗的車輛路徑規劃)問題，本文分別采用MATLAB中YALMIP工具箱中的GUROBI6.0求解器和遺傳算法對該問題進行了求解．

4.1實驗假設

文中假設：(1)參與運輸的集裝箱全為小箱，即每個運輸任務能且只能占用一半的AGV荷載；(2)實驗中運輸任務數據由計算機隨機產生；(3)岸橋和龍門吊裝卸效率足夠高，其作業效率對AGV運輸時間的影響忽略不計．

4.2評價指標

該部分共引入兩個評價指標：(1) 作業費用．自動化集裝箱碼頭是一家企業，企業都關心成本，因此作業費用可以作為第一個評價指標，假設作業費用和運輸時間成線性關系，為了便于計算，不妨直接令作業費用等于運輸時間大小．(2) 空載率．空載率反映了對AGV負荷的利用情況，空載率越低，AGV利用率就越高，資源浪費就越少，這正是碼頭方面愿意看到的，因此空載率可以作為第二個評價指標．

4.3實驗設置

該部分共做了4組實驗，具體實驗設置如表1所示．

4.4實驗結果

實驗1 按照表1中實驗1的要求配置實驗，然后代入GUROBI計算，得出多載AGV和單載AGV的作業過程圖如圖7和8所示．多載AGV的總運輸成本為187元，單載AGV的總運輸成本為238元，容易得出：多載AGV的空載次數和空載時間明顯比單載AGV低，應用多載AGV可以達到降低運輸費用、縮短運輸時間的目的．

表1　實驗場景設置

圖7　多載AGV作業圖

圖8　單載AGV作業圖

實驗2 為了進一步增加實驗1所得結論的說服力，驗證模型的適應性，在擴大作業規模以及在裝船和卸船同步進行的情況下，求解出AGV在多載和單載模式下的作業費用，如表2所示．不難發現，裝船卸船同步進行時，AGV的費用明顯降低，并且對單載AGV的優化效果更加顯著，但這依然沒有影響到多載AGV的優越性．

表2　總運輸費用對比

實驗3 為了研究應用多載AGV后，水平運輸工具的利用率情況，設定空載率=空載時間/運輸總時間，然后計算實驗2中各實驗場景對應的空載率情況，得出如表3的空載率統計表．顯然，任務量相同時，裝船與卸船同步進行時，多載AGV與單載AGV空載率都更低，而且，每種實驗場景中，多載AGV的空載率都比單載AGV低．

表3　空載率對比

表4　大規模問題費用對比

實驗4 GUROBI只能對小規模調度問題進行求解，對于大規模調度問題，必須用遺傳算法進行求解，于是分別設置不同的交叉概率rc與變異概率rm，并將它們一一組合，然后運用遺傳算法，求出rc與rm組合對應的運輸費用后，令z(i，j)=5 000/T(i，j)，然后做出z的等高線示意圖，如圖9所示．容易看出，rc=0.7，rm=0.3組合與rc=0.7，rm=0.5組合的優越性明顯高于其他組合，由于變異概率一般較小，給定最佳交叉概率與變異概率組合為rc=0.7，rm=0.3．分別對總任務量N=40，60，80，100，120的情況進行實驗，得出表4所示的實驗結果，在每一個實驗場景中多載AGV都比單載AGV節省運輸費用，這充分證明了實驗1猜想的正確性．

圖9　優先性等高線示意圖

4.5實驗總結

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

(1)多載AGV比單載AGV運輸費用更低，而且在完成全部運輸任務的過程中空載次數與空載率都更低；

(2)擴大問題規模，增加問題的復雜性，依然沒有影響多載AGV的優越性，在實驗2的場景中，多載AGV都比單載AGV節省運輸費用；

(3)實驗3統計了整個運輸過程中AGV的利用情況，由表3可以得出：在每種實驗場景中，多載AGV的空載率都比單載AGV低；

(4)前3組實驗都是建立在小規模問題的基礎上的，至于大規模問題，已經超出了GUROBI的求解范圍，實驗4中用遺傳算法求解不同規模多載AGV調度問題，正好驗證了多載AGV在大規模問題中的優越性．

5結語

多載AGV的調度屬于NP-hard問題，國內外很多文獻指出，GUROBI在混合整數規劃模型和二次規劃模型求解方面具有較好的性能，而且GUROBI常用于調度問題求解，因此，作為多載AGV調度問題的研究，本文首先使用GUROBI求解小規模調度問題．但是，僅僅依靠小規模調度問題的求解，不足以判定多載AGV能夠提升自動化集裝箱碼頭水平運輸效率，于是，本文增加了用遺傳算法求解大規模調度問題的研究，這豐富了多載AGV的適用范圍，并能有力地支持本文結論：多載AGV比單載AGV更節省運輸費用，且空載率更低，其應用有助于解決自動化集裝箱碼頭水平運輸效率低的問題．實際上，自動化集裝箱碼頭上大箱與小箱往往同時參與運輸，而文中只考慮了全是小箱的情況，這與現實作業環境有一定差距，因此，大箱與小箱同時參與運輸的多載AGV調度問題值得進一步研究．

參考文獻：

[1] Azimi P, Haleh H, Alidoost M. The selection of the best control rule for a multiple-load AGV system using simulation and fuzzy MADM in a flexible manufacturing system [J]. Modelling and Simulation in Engineering, 2010, 2010:821701.

[2]Ho Y-C, Chien S-H. A simulation study on the performance of task-determination rules and delivery-dispatching rules for multiple-load AGVs [J]. International Journal of Production Research, 2006, 44(20):4193-4222.

[3]Ho Y-C, Liu H-C. A simulation study on the performance of pickup-dispatching rules for multiple-load AGVs [J]. Computers and Industrial Engineering, 2006, 51(3):445-463.

[4]Grunow M, Gunther H-O, Lehmann M. Dispatching multi-load AGVs in highly automated seaport container terminals [J]. OR Spectrum, 2004, 26(2):211-235.

[5]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:545-556.

[6]Fazlollahtabar H, Saidi-Mehrabad 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:131-138.

[7]LUO Jia-bin, WU Yue. Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals [J]. Transportation Research Part E:Logistics and Transportation Review, 2015, 79:49-64.

[8]Skinner B, YUAN Shuai, HUANG Shou-dong,etal. Optimisation for job scheduling at automated container terminals using genetic algorithm [J]. Computers and Industrial Engineering, 2013, 64(1):511-523.

[9]Ho Y-C, Liu H-C, Yih Y. A multiple-attribute method for concurrently solving the pickup-dispatching problem and the load-selection problem of multiple-load AGVs [J]. Journal of Manufacturing Systems, 2012, 31(3):288-300.

[10]Ho Y-C, Liu H-C. The performance of load-selection rules and pickup-dispatching rules for multiple-load AGVs [J]. Journal of Manufacturing Systems, 2009, 28(1):1-10.

[11]Angeloudis P, Bell M G H. An uncertainty-aware AGV assignment algorithm for automated container terminals [J]. Transportation Research Part E:Logistics and Transportation Review, 2010, 46(3):354-366.

[12]張 煜,王少梅. 自動化集裝箱碼頭中自動導引小車的交通策略研究[J]. 武漢理工大學學報(交通科學與工程版), 2007, 31(4):641-644.

ZHANG Yu, WANG Shao-mei. Research on traffic strategy for the application of AGVs in automated container terminals [J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2007, 31(4):641-644. (in Chinese)

[13]史 飛,張新艷,趙啟元. 新型自動化集裝箱碼頭的仿真分析[J]. 機械與電子, 2008, 12(1):56-60.

SHI Fei, ZHANG Xin-yan, ZHAO Qi-yuan. Simulation and analysis of a new type of automated container terminal [J]. Machinery & Electronics, 2008, 12(1):56-60. (in Chinese)

[14]溫智民,陸志強,孫小明. 自動化集裝箱碼頭運輸系統配置的仿真優化[J]. 工業工程與管理, 2009, 36(1):36-39,43.

WEN Zhi-min, LU Zhi-qiang, SUN Xiao-ming. Research of simulation optimization technique on equipment allocation of transportation system in automatic container terminals [J]. Industrial Engineering and Management, 2009, 36(1):36-39,43. (in Chinese)

[15]鄭見粹,李海波,謝文寧,等. 自動化集裝箱碼頭裝卸工藝系統比較研究[J]. 水運科學研究, 2011, 7(2):26-33.

ZHENG Jian-cui, LI Hai-bo, XIE Wen-ning,etal. A study on automation for container terminal operation systems [J]. Research on Waterborne Transportation, 2011, 7(2):26-33. (in Chinese)

Research on scheduling problem of multi-load AGV at automated container terminal

HUOKai-ge,ZHANGYa-qi,HUZhi-hua*

( Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China )

Abstract：Multi-load AGV (automated guided vehicle) is a kind of level work equipment for automated container terminals. It can carry multiple containers at the same time and is capable of reducing the scale of AGV flow, while increasing utilization rate of AGV. In order to improve the operation efficiency of automated container terminal, layouts of vertical shore-type container yards are taken into account, minimal total operational cost is regarded as planning target, operational restrictions, length of time window and load balance are viewed as constraint conditions, and scheduling policy driven by events is applied as research method to establish a mixed-integer programming model for the scheduling of multi-load AGV. Meanwhile, GUROBI and genetic algorithm are applied to solve the total operational costs and empty-loading ratio of multi-load AGV. Furthermore, a comparison with the total operational cost and empty-loading ratio of single-load AGV is made to verify the superiority of multi-load AGV.

Key words：multi-load AGV; time window; event-driven AGV scheduling; mixed-integer programming; genetic algorithm

中圖分類號：U691.3

文獻標識碼：A

doi:10.7511/dllgxb201603004

作者簡介:霍凱歌(1990-)，男，研究生，E-mail:283478770@qq.com；胡志華*(1977-)，男，博士，教授，E-mail:zhhu@shmtu.edu.cn.

基金項目:國家自然科學基金資助項目(71471109)；上海市曙光計劃資助項目(13SG48)；上海市教委科研創新項目(14YZ100)；交通運輸部科技計劃應用基礎研究資助項目(2015329810260).

收稿日期：2015-10-29；修回日期: 2016-03-28．