霍 凱 歌，　張 亞 琦，　胡 志 華

( 上海海事大學(xué) 物流研究中心， 上?！?01306 )

?

自動(dòng)化集裝箱碼頭多載AGV調(diào)度問(wèn)題研究

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

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

摘要：多載AGV是一種自動(dòng)化集裝箱碼頭水平作業(yè)設(shè)備，它可以同時(shí)搬運(yùn)多個(gè)集裝箱，可縮小AGV流的規(guī)模，增大AGV的利用率．為了提高自動(dòng)化集裝箱碼頭的作業(yè)效率，考慮了垂岸式集裝箱堆場(chǎng)布局，以最小化作業(yè)總費(fèi)用為規(guī)劃目標(biāo)，以作業(yè)限制、時(shí)間窗長(zhǎng)度、負(fù)載平衡等為約束條件，以事件驅(qū)動(dòng)的調(diào)度策略為研究方法，建立了多載AGV調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型．同時(shí)利用GUROBI和遺傳算法求解多載AGV的作業(yè)總費(fèi)用和空載率，并與相同條件下單載AGV的作業(yè)總費(fèi)用和空載率對(duì)比，驗(yàn)證了多載AGV的優(yōu)越性．

關(guān)鍵詞：多載AGV；時(shí)間窗；事件驅(qū)動(dòng)的AGV調(diào)度；混合整數(shù)規(guī)劃；遺傳算法

0引言

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

自動(dòng)化集裝箱碼頭就是將集裝箱碼頭岸邊與堆場(chǎng)之間的運(yùn)輸、堆場(chǎng)內(nèi)的作業(yè)、道口的進(jìn)出等全過(guò)程實(shí)現(xiàn)自動(dòng)化運(yùn)作的碼頭．自動(dòng)化集裝箱碼頭相對(duì)于普通集裝箱碼頭有以下優(yōu)點(diǎn)：大幅度降低人工費(fèi)用和總運(yùn)行費(fèi)用、降低員工勞動(dòng)強(qiáng)度、提高碼頭的運(yùn)行效率、可24 h連續(xù)作業(yè)等．在自動(dòng)化集裝箱碼頭上，岸橋負(fù)責(zé)泊位部分的裝卸工作，龍門吊負(fù)責(zé)堆場(chǎng)區(qū)域的裝卸工作，而AGV負(fù)責(zé)碼頭范圍內(nèi)的水平運(yùn)輸．伴隨著自動(dòng)化集裝箱碼頭吞吐量的增加，碼頭作業(yè)效率越來(lái)越受到碼頭管理者和船務(wù)公司的重視，越來(lái)越多的新技術(shù)被應(yīng)用到岸橋和龍門吊等垂直作業(yè)設(shè)備上，自動(dòng)化碼頭的垂直作業(yè)效率得到了質(zhì)的提升，水平作業(yè)效率隨之成為了制約碼頭整體作業(yè)效率提升的瓶頸．

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

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

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

1問(wèn)題描述

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

在傳統(tǒng)的單載模式下，可以將AGV調(diào)度問(wèn)題看作m∶n的分配問(wèn)題，其目標(biāo)是最小化作業(yè)時(shí)間或最小化作業(yè)費(fèi)用，可以比較容易地找出優(yōu)化方案．但是對(duì)于多載AGV調(diào)度問(wèn)題，復(fù)雜性就大大增加了，在調(diào)度中，除了需要給每輛AGV分配運(yùn)輸任務(wù)，而且需要給每輛AGV安排好執(zhí)行裝載和交付操作的具體順序，這就使得自動(dòng)化集裝箱碼頭多載AGV調(diào)度問(wèn)題的規(guī)劃難度大大增加了．

圖1為垂岸式集裝箱堆場(chǎng)布局的自動(dòng)化集裝箱碼頭的俯瞰圖，在裝船或卸船中，AGV一旦收到運(yùn)輸請(qǐng)求，即從?？空境霭l(fā)，開(kāi)始執(zhí)行本時(shí)段的所有運(yùn)輸任務(wù)．為了方便調(diào)度，本文定義所有AGV最多能裝載兩個(gè)集裝箱．圖2給出了具有兩個(gè)運(yùn)輸任務(wù)的多載AGV作業(yè)運(yùn)輸圖，AGV收到運(yùn)輸請(qǐng)求后立即從停靠站出發(fā)，在QC1、QC2處完成集裝箱的裝載，滿載駛往堆場(chǎng)，然后在交付點(diǎn)SC1和SC2完成交付，最后駛回停靠站．在正常作業(yè)中，AGV完成一次運(yùn)輸任務(wù)后，立即檢查是否還有運(yùn)輸任務(wù)需要執(zhí)行，如果有，就去執(zhí)行下一個(gè)運(yùn)輸任務(wù)，否則，就駛回?？空荆Y(jié)束此次調(diào)度．

圖1　自動(dòng)化集裝箱碼頭俯瞰圖

圖2　作業(yè)過(guò)程圖

2模型建立

2.1符號(hào)說(shuō)明

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

假設(shè)AGV的集合為K，由于并不是所有AGV都可以負(fù)責(zé)任意的運(yùn)輸任務(wù)，AGVk擁有唯一的集合Nk=Pk∪Dk，其中Nk、Pk、Dk分別為集合N、P、D的子集．對(duì)于任意AGVk，定義網(wǎng)絡(luò)Gk=(Vk,Ak)，其中Vk=Nk∪{o(k),d(k)}表示AGVk的所有任務(wù)點(diǎn)與AGVk的出發(fā)點(diǎn)和?？奎c(diǎn)的集合，Vk×Vk子集Ak表示AGVk所有可行的?。瓵GVk的最大負(fù)載能力為Ck，由于文中采用統(tǒng)一的AGV，也可用固定值C表示．ti,j,k和ci,j,k分別表示AGVk從端點(diǎn)i到端點(diǎn)j的時(shí)間和費(fèi)用，其中i,j∈Vk．

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

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

圖3　作業(yè)路徑圖

2.2調(diào)度模型

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

(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)描繪了一個(gè)多物流網(wǎng)絡(luò)結(jié)構(gòu)，限定任意AGVk必須從出發(fā)點(diǎn)o(k)出發(fā)，完成所有任務(wù)后抵達(dá)?？奎c(diǎn)d(k)，并且保證途中經(jīng)過(guò)的各端點(diǎn)的出度等于其入度．式(5)、(6)限定每個(gè)運(yùn)輸任務(wù)能且僅能被執(zhí)行一次，同一任務(wù)的裝載和交付必須由同一AGV完成．式(7)～(9)給出了關(guān)于執(zhí)行時(shí)間的約束，如果xi,j,k=1，即AGVk完成操作i后，去執(zhí)行操作j時(shí)，AGV開(kāi)始執(zhí)行操作j的時(shí)間Tj,k一定不小于AGVk開(kāi)始執(zhí)行任務(wù)i的時(shí)間Ti,k、任務(wù)i的執(zhí)行時(shí)間si與AGVk從執(zhí)行點(diǎn)i到執(zhí)行點(diǎn)j的時(shí)間之和，由于xi,j,k是0-1變量，式(7)也可以表示為Ti,k+si+ti,j,k-Tj,k≤Mi,j(1-xi,j,k)，其中Mi,j表示一個(gè)足夠大的常數(shù)，而且Mi,j可以用max{bi+si+ti,j,k-aj,0},(i,j)∈Ak表示，AGVk開(kāi)始執(zhí)行任意裝卸操作i的時(shí)間Ti,k必須在相應(yīng)的時(shí)間窗內(nèi)，AGVk開(kāi)始執(zhí)行交付操作的時(shí)間一定不小于它開(kāi)始執(zhí)行裝載操作的時(shí)間Ti,k與AGVk從裝載點(diǎn)到交付點(diǎn)的行駛時(shí)間ti,n+i,k的和．式(10)～(13)給出了負(fù)載平衡的約束，如果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執(zhí)行裝載操作的負(fù)載約束，式(12)給出了執(zhí)行交付操作的負(fù)載約束．式(13)、(14)給出了任意AGVk在起始點(diǎn)o(k)和停靠點(diǎn)d(k)的負(fù)載情況．式(15)限定xi,j,k為0-1變量，對(duì)于Ti,k,k∈K,i∈Vk，可以從式(8)和(9)看出，Ti,k≥0恒成立，對(duì)于Li,k,k∈K,i∈Vk，可以從式(11)～(14)看出，0≤Li,k≤Ck恒成立，且Li,k為整數(shù)．

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

3遺傳算法

VRP問(wèn)題是數(shù)學(xué)上的組合優(yōu)化問(wèn)題，Golden等證明了該問(wèn)題是NP-hard問(wèn)題，因此，不妨用遺傳算法求解該VRP問(wèn)題的近似最優(yōu)解．

3.1編碼

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

圖4染色體編碼示意圖

Fig.4The diagram of chromosome encoding

3.2解碼

圖5　第i個(gè)染色體片段的解碼過(guò)程

3.3交叉

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

輸入兩個(gè)父代染色體P1、P2

輸出子代染色體child

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

第2步通過(guò)復(fù)制P1所選位置上的基因生成一個(gè)子代染色體原型．

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

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

3.4變異

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

圖6　倒置變異示意圖

4案例分析

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

4.1實(shí)驗(yàn)假設(shè)

文中假設(shè)：(1)參與運(yùn)輸?shù)募b箱全為小箱，即每個(gè)運(yùn)輸任務(wù)能且只能占用一半的AGV荷載；(2)實(shí)驗(yàn)中運(yùn)輸任務(wù)數(shù)據(jù)由計(jì)算機(jī)隨機(jī)產(chǎn)生；(3)岸橋和龍門吊裝卸效率足夠高，其作業(yè)效率對(duì)AGV運(yùn)輸時(shí)間的影響忽略不計(jì)．

4.2評(píng)價(jià)指標(biāo)

該部分共引入兩個(gè)評(píng)價(jià)指標(biāo)：(1) 作業(yè)費(fèi)用．自動(dòng)化集裝箱碼頭是一家企業(yè)，企業(yè)都關(guān)心成本，因此作業(yè)費(fèi)用可以作為第一個(gè)評(píng)價(jià)指標(biāo)，假設(shè)作業(yè)費(fèi)用和運(yùn)輸時(shí)間成線性關(guān)系，為了便于計(jì)算，不妨直接令作業(yè)費(fèi)用等于運(yùn)輸時(shí)間大?。?2) 空載率．空載率反映了對(duì)AGV負(fù)荷的利用情況，空載率越低，AGV利用率就越高，資源浪費(fèi)就越少，這正是碼頭方面愿意看到的，因此空載率可以作為第二個(gè)評(píng)價(jià)指標(biāo)．

4.3實(shí)驗(yàn)設(shè)置

該部分共做了4組實(shí)驗(yàn)，具體實(shí)驗(yàn)設(shè)置如表1所示．

4.4實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1 按照表1中實(shí)驗(yàn)1的要求配置實(shí)驗(yàn)，然后代入GUROBI計(jì)算，得出多載AGV和單載AGV的作業(yè)過(guò)程圖如圖7和8所示．多載AGV的總運(yùn)輸成本為187元，單載AGV的總運(yùn)輸成本為238元，容易得出：多載AGV的空載次數(shù)和空載時(shí)間明顯比單載AGV低，應(yīng)用多載AGV可以達(dá)到降低運(yùn)輸費(fèi)用、縮短運(yùn)輸時(shí)間的目的．

表1　實(shí)驗(yàn)場(chǎng)景設(shè)置

圖7　多載AGV作業(yè)圖

圖8　單載AGV作業(yè)圖

實(shí)驗(yàn)2 為了進(jìn)一步增加實(shí)驗(yàn)1所得結(jié)論的說(shuō)服力，驗(yàn)證模型的適應(yīng)性，在擴(kuò)大作業(yè)規(guī)模以及在裝船和卸船同步進(jìn)行的情況下，求解出AGV在多載和單載模式下的作業(yè)費(fèi)用，如表2所示．不難發(fā)現(xiàn)，裝船卸船同步進(jìn)行時(shí)，AGV的費(fèi)用明顯降低，并且對(duì)單載AGV的優(yōu)化效果更加顯著，但這依然沒(méi)有影響到多載AGV的優(yōu)越性．

表2　總運(yùn)輸費(fèi)用對(duì)比

實(shí)驗(yàn)3 為了研究應(yīng)用多載AGV后，水平運(yùn)輸工具的利用率情況，設(shè)定空載率=空載時(shí)間/運(yùn)輸總時(shí)間，然后計(jì)算實(shí)驗(yàn)2中各實(shí)驗(yàn)場(chǎng)景對(duì)應(yīng)的空載率情況，得出如表3的空載率統(tǒng)計(jì)表．顯然，任務(wù)量相同時(shí)，裝船與卸船同步進(jìn)行時(shí)，多載AGV與單載AGV空載率都更低，而且，每種實(shí)驗(yàn)場(chǎng)景中，多載AGV的空載率都比單載AGV低．

表3　空載率對(duì)比

表4　大規(guī)模問(wèn)題費(fèi)用對(duì)比

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

圖9　優(yōu)先性等高線示意圖

4.5實(shí)驗(yàn)總結(jié)

通過(guò)上述4組實(shí)驗(yàn)，容易得出：

(1)多載AGV比單載AGV運(yùn)輸費(fèi)用更低，而且在完成全部運(yùn)輸任務(wù)的過(guò)程中空載次數(shù)與空載率都更低；

(2)擴(kuò)大問(wèn)題規(guī)模，增加問(wèn)題的復(fù)雜性，依然沒(méi)有影響多載AGV的優(yōu)越性，在實(shí)驗(yàn)2的場(chǎng)景中，多載AGV都比單載AGV節(jié)省運(yùn)輸費(fèi)用；

(3)實(shí)驗(yàn)3統(tǒng)計(jì)了整個(gè)運(yùn)輸過(guò)程中AGV的利用情況，由表3可以得出：在每種實(shí)驗(yàn)場(chǎng)景中，多載AGV的空載率都比單載AGV低；

(4)前3組實(shí)驗(yàn)都是建立在小規(guī)模問(wèn)題的基礎(chǔ)上的，至于大規(guī)模問(wèn)題，已經(jīng)超出了GUROBI的求解范圍，實(shí)驗(yàn)4中用遺傳算法求解不同規(guī)模多載AGV調(diào)度問(wèn)題，正好驗(yàn)證了多載AGV在大規(guī)模問(wèn)題中的優(yōu)越性．

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]張 煜,王少梅. 自動(dòng)化集裝箱碼頭中自動(dòng)導(dǎo)引小車的交通策略研究[J]. 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 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]史 飛,張新艷,趙啟元. 新型自動(dòng)化集裝箱碼頭的仿真分析[J]. 機(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]溫智民,陸志強(qiáng),孫小明. 自動(dòng)化集裝箱碼頭運(yùn)輸系統(tǒng)配置的仿真優(yōu)化[J]. 工業(yè)工程與管理, 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]鄭見(jiàn)粹,李海波,謝文寧,等. 自動(dòng)化集裝箱碼頭裝卸工藝系統(tǒng)比較研究[J]. 水運(yùn)科學(xué)研究, 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

中圖分類號(hào)：U691.3

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.7511/dllgxb201603004

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

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(71471109)；上海市曙光計(jì)劃資助項(xiàng)目(13SG48)；上海市教委科研創(chuàng)新項(xiàng)目(14YZ100)；交通運(yùn)輸部科技計(jì)劃應(yīng)用基礎(chǔ)研究資助項(xiàng)目(2015329810260).

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