不確定環(huán)境下自動化集裝箱碼頭AGV調(diào)度與配置問題

馬越匯,胡志華

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

?

不確定環(huán)境下自動化集裝箱碼頭AGV調(diào)度與配置問題

馬越匯,胡志華

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

摘要：為研究不確定環(huán)境下自動化集裝箱碼頭AGV調(diào)度與配置問題，建立了以最末任務(wù)結(jié)束時間最小化為目標(biāo)的基本模型，將裝卸集裝箱任務(wù)的帶箱作業(yè)時間，完成一個任務(wù)后到執(zhí)行下一個任務(wù)之前空箱行駛的時間這兩個決策變量在合理的范圍內(nèi)生成了5 000個數(shù)據(jù)，選取其中有代表性的數(shù)據(jù)進(jìn)行分析?？紤]了不確定因素,例如集裝箱碼頭堆場內(nèi)的交通控制、交通擁堵情況等。結(jié)果表明：外界不確定因素對于最末任務(wù)結(jié)束時間最小值的影響是有限的，在一定程度上增加了工作時間，但不是時間增加的決定性因素；自動化集裝箱碼頭實(shí)際運(yùn)行過程中，并不是AGV數(shù)量越多，整個運(yùn)作效率就會越高；隨著AGV數(shù)量增加時，外界不確定因素對最末任務(wù)結(jié)束時間最小值的影響就會越來越小，直到幾乎沒有影響。算例證明了模型的有效性和實(shí)用性。

關(guān)鍵詞：自動化集裝箱碼頭；自動引導(dǎo)車；隨機(jī)規(guī)劃模型；調(diào)度與配置

0引言

AGV(automated guided vehicle)，指裝備有電磁或光學(xué)等自動導(dǎo)引裝置，能夠沿規(guī)定的導(dǎo)引路徑行駛，具有安全保護(hù)以及各種移載功能的運(yùn)輸車，工業(yè)應(yīng)用中不需要駕駛員的搬運(yùn)車，可充電的蓄電池為其動力來源。集裝箱運(yùn)輸作為國際貨物運(yùn)輸物流系統(tǒng)的一個重要節(jié)點(diǎn),集裝箱運(yùn)輸效率的高低會直接影響經(jīng)濟(jì)的發(fā)展，由于AGV具有自動化、智能化、并行作業(yè)的特點(diǎn)，能夠很好地滿足自動化集裝箱碼頭的運(yùn)輸要求，因此在自動化集裝箱碼頭得到了廣泛的應(yīng)用。

在集裝箱卸船作業(yè)中，首先碼頭為船舶分配泊位，岸吊將集裝箱放置在AGV上，AGV按照規(guī)定路徑將集裝箱運(yùn)載至指定箱區(qū)，再由龍門吊將集裝箱卸載至指定箱區(qū)的指定位置。集裝箱裝船作業(yè)的順序與卸船作業(yè)相反。一般可通過電腦來控制AGV的行進(jìn)路線以及行為，或利用電磁軌道來設(shè)立其行進(jìn)路線，電磁軌道粘貼在地板上，AGV依循電磁軌道所帶來的信息進(jìn)行移動與動作。

Lee等[1]考慮了在集卡資源限制下的調(diào)度模型，建立了以集卡等待時間和運(yùn)輸時間加權(quán)和最小為目標(biāo)函數(shù)的模型，設(shè)計(jì)了新的混合算法來求解模型。Cao等[2]針對集裝箱碼頭在堆場卡車和堆場橋吊的裝載作業(yè)的調(diào)度問題，建立了混合整數(shù)規(guī)劃模型。Elmekkawy等[3]針對自動化集裝箱碼頭研究了一種新的方法，結(jié)合了遺傳算法開發(fā)了一種MA算法，提高AGV系統(tǒng)工作效率。Giuseppe等[4]將AGV的調(diào)度問題轉(zhuǎn)化成最小流問題，并且建立了最小流模型，使用了貪婪算法和單純形算法進(jìn)行求解，將結(jié)果進(jìn)行對比?？抵久鬧5]闡述了兩種不同的AGV調(diào)度方式，提出了基于成本的AGV路線調(diào)度方法，在作業(yè)面動態(tài)調(diào)度模型下，建立了等待時間最少為目標(biāo)的車輛調(diào)度模型，利用遺傳算法來求解。徐遠(yuǎn)琴等[6]考慮了集卡運(yùn)輸時間與等待岸橋、場橋時間之間的權(quán)重系數(shù)，建立了以等待岸橋、場橋作業(yè)時間與集卡運(yùn)輸時間之和最小為目標(biāo)的聯(lián)合調(diào)度優(yōu)化模型。張遠(yuǎn)春等[7]以生產(chǎn)線產(chǎn)能最大化為目標(biāo),以生產(chǎn)工藝、AGV路徑、調(diào)度規(guī)則等為約束條件,建立了以AGV的數(shù)量為決策變量的數(shù)學(xué)模型，利用仿真得到優(yōu)化方法。計(jì)明軍等[8]提出了集卡與岸橋協(xié)同調(diào)度模型，并設(shè)計(jì)了進(jìn)化規(guī)劃算法求解該模型，以達(dá)到任務(wù)完成時間最少的目標(biāo)。曾慶成等[9]考慮了等待時間問題，提出了綜合考慮岸橋和場橋等待集卡的時間最小的集卡調(diào)度方法，采用Q-學(xué)習(xí)法對模型進(jìn)行求解。秦天保等[10]以完工時間最小為目標(biāo)，構(gòu)建帶有任務(wù)順序約束的岸橋與集卡集成調(diào)度的 MIP 模型和約束規(guī)劃模型。馬超等[11]針對集裝箱碼頭岸橋和集卡的協(xié)同調(diào)度問題，以進(jìn)口箱和出口箱的總完工時間最短為目的，考慮了集卡路徑約束和岸橋?qū)嶋H操作情況等實(shí)際約束，構(gòu)建了邊裝邊卸的混合整數(shù)規(guī)劃模型。梁承姬等[12]針對集裝箱碼頭集卡調(diào)度問題，建立基于岸橋作業(yè)并考慮時間窗約束的集卡協(xié)調(diào)調(diào)度耦合模型，目的為使集卡數(shù)最小且延誤時間最短。

已有的文獻(xiàn)中幾乎都忽略自動化集裝箱碼頭實(shí)際作業(yè)中不確定因素的，例如集裝箱運(yùn)輸過程中堆場交通擁堵情況, 并且所建立的模型假設(shè)條件太多,與自動化集裝箱碼頭實(shí)際作業(yè)相差不少,調(diào)度模型的研究也僅僅局限在理論層面,很難有實(shí)際意義。本文的創(chuàng)新之處就在于將這些不確定性因素考慮進(jìn)去，使得模型更具現(xiàn)實(shí)意義。

本文首先結(jié)合AGV、岸橋、堆場、龍門吊四者建立了最末任務(wù)結(jié)束時間最小化為目標(biāo)函數(shù)的模型。其次設(shè)計(jì)了算法來計(jì)算AGV任務(wù)作業(yè)完成時間、兩個任務(wù)之間的空箱行駛時間。因?yàn)榭紤]到實(shí)際運(yùn)行過程中，自動化集裝箱碼頭不確定性因素，不確定因素包括堆場內(nèi)的交通控制、交通擁堵情況等，因此在合理范圍內(nèi)對前述兩個時間生成5 000組數(shù)據(jù)。采用數(shù)學(xué)建模和數(shù)據(jù)分析的方法研究AGV的調(diào)度問題，AGV一定時，最末任務(wù)結(jié)束時間是否受不確定因素影響；任務(wù)一定時，AGV的數(shù)量與最末任務(wù)結(jié)束時間、不確定性因素的關(guān)系,最后通過算例驗(yàn)證了模型的有效性和實(shí)用性。

1模型建立

圖1為一個自動化集裝箱碼頭的俯視圖，共有5岸橋，6個箱區(qū)，每輛AGV按圖1中所示箭頭規(guī)定路徑進(jìn)行運(yùn)作，在集裝箱卸船作業(yè)中，首先碼頭為船舶分配泊位，岸吊將集裝箱放置在AGV上，AGV按照規(guī)定路徑將集裝箱運(yùn)載至箱區(qū)，再由龍門吊將集裝箱卸載至所需要存放箱區(qū)的位置。集裝箱裝船作業(yè)的順序與卸船作業(yè)相反。AGV的作業(yè)軌跡跟裝船作業(yè)與卸船作業(yè)有關(guān)，根據(jù)集裝箱卸下的位置和裝載的位置確定其路徑。本文使用參數(shù)1計(jì)算裝卸集裝箱任務(wù)的帶箱作業(yè)時間為Ti，使用參數(shù)2計(jì)算在完成一個任務(wù)后到執(zhí)行下一個任務(wù)之前空箱行駛的時間為Tij。

圖1　自動化集裝箱碼頭的俯視圖示例

1.1符號

本文建立AGV的裝卸作業(yè)任務(wù)調(diào)度模型，相關(guān)符號的定義如下：

I:N項(xiàng)任務(wù)的集合,I={1,2,…,N}，其中1和N表示起止兩個虛擬任務(wù)；

V: AGV的集合,V={1,2,…,|V|}；

k:k=∑ijTij+∑iiTi，一個足夠大的數(shù)；

Tij: 在完成任務(wù)i(i∈I)后去執(zhí)行任務(wù)j,(j∈I)AGV空箱行駛的時間；

xijv:xijv∈{0,1},若v∈V在完成任務(wù)i∈I后執(zhí)行下一個任務(wù)j∈I,則xijv為1; 否則xijv為 0；

yiv:yiv∈{0,1}，如果車輛v∈V執(zhí)行任務(wù)i∈I，則yiv為1;否則yiv為0；

zi: 任務(wù)i∈I工作的開始時間；

f: 所有工作的完工時間，即最后一個任務(wù)完成時的時間；

Rv: AGV,v∈V最早有效使用的時間；

Ti: 任務(wù)i∈I的工作時間；

Ai: 任務(wù)i∈I的最早有效開始工作時間。

1.2基本模型

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

minf,

(1)

s.t.f≥zi+Ti,?i∈I,

(2)

zj+(1-xijv)K≥zi+Ti+Tij,?i≠j,v∈V,

(3)

zi≥Ai,?i∈I,

(4)

Zi≥Ri+T1,i+(yi,v-1)K,?i∈I,v∈V,

(5)

∑j∈I+{i}xjiv=∑j∈I+{i}xijv=yiv,?i∈I,v∈V,

(6)

∑vyiv=1,?i∈I,

(7)

xijv+xjiv≤1,?i,j∈I,i≠j,v∈V,

(8)

∑i∈I+{1}x1,i,v=1,?v∈V,

(9)

∑i∈I+{N}xi,N,v=1,?v∈V,

(10)

f≥0,zi≥0,?i∈I,

(11)

式(2)是最末任務(wù)結(jié)束時間的最小值f；式(3)表示f是由每個任務(wù)的開始工作時間和完成任務(wù)的時間決定的；在分配每輛AGV的任務(wù)順序時，需要考慮每個任務(wù)的開始時間，以免任務(wù)分配發(fā)生時間重疊；式(4)對任意AGV (v)安排的作業(yè)任務(wù)序列，如果完成任務(wù)i后又執(zhí)行任務(wù)j，則xijv=1，那么要求滿足zi≥zi+Tij+T，即zi≥xijv(zi+Tij+T);式(5)表示任務(wù)i∈I的開始時間在其可執(zhí)行的最早開始時間后進(jìn)行；式(6)表示車輛v∈V所要完成的任務(wù)i∈I在AGV的有效工作時間內(nèi)進(jìn)行；式(7)對任意AGV，對任意非虛擬任務(wù)，滿足該任務(wù)在任務(wù)網(wǎng)絡(luò)中的流約束；式(8)每個任務(wù)只可以由一輛AGV完成運(yùn)輸;式(9)對于任意AGV，從虛擬任務(wù)出發(fā)，到虛擬任務(wù)完成運(yùn)輸，僅負(fù)責(zé)一個作業(yè)流程;式(10)和式(11)對于每輛AGV都是從虛擬任務(wù)開始，到虛擬任務(wù)后結(jié)束。

2參數(shù)估計(jì)

圖2　岸橋與箱區(qū)的位置坐標(biāo)

Lui,Luj:i∈I,j∈I，若Lui,Luj為1是卸船任務(wù)；否則是裝船任務(wù)；

S: AGV的行駛速度；

Lu1: 岸橋裝載和卸載一個集裝箱的時間；

Lu2: 龍門吊裝載和卸載一個集裝箱的時間；

Di: 裝卸集裝箱任務(wù)i的帶箱行駛距離;

Dij: 完成任務(wù)裝卸作業(yè)i后去執(zhí)行任務(wù)j之前空箱行駛距離。

①參數(shù)估計(jì)1：裝卸集裝箱任務(wù)i的帶箱行駛時間。

輸出:Di,Ti

步驟:

Step 1: 根據(jù)Lui,Luj計(jì)算距離Di,若Lui,Luj=1,則轉(zhuǎn)step 2;否則轉(zhuǎn)step 3;

Step 4: 根據(jù)距離Di,計(jì)算時間Ti=Di/S+Lu1+Lu2。

②參數(shù)估計(jì)2：AGV完成一個任務(wù)i后到執(zhí)行下一個任務(wù)j之前空箱行駛的時間。

輸出:Dij,Tij

步驟:

Step 1: 根據(jù)Lui,Luj,i∈I,j∈J的值計(jì)算距離Dij,

如果Lui=1,Luj=1,轉(zhuǎn)step 2,

如果Lui=0,Luj=0,轉(zhuǎn)step 3,

如果Lui=0,Luj=1,轉(zhuǎn)step 4,

如果Lui=1,Luj=0,轉(zhuǎn)step 5;

Step 6:Tij=Dij/S。

3算例

本文對AGV=2、3、4、5、6、7、8情況下的最末任務(wù)結(jié)束時間最小值的5 000組數(shù)據(jù)分別畫出正態(tài)概率分布圖，發(fā)現(xiàn)圖形的增長趨勢類似，以y=20.369ln(x)+402.08為例，畫出柱狀圖和擬合圖，見圖3。對每組數(shù)據(jù)最大值與最小值的差值進(jìn)行比較，當(dāng)AGV數(shù)量很少時，差值還是很大的，隨著AGV數(shù)量的增多，每組數(shù)據(jù)的最大值與最小值的差值就越來越小，說明在AGV數(shù)量很少時，外界不確定因素對最末任務(wù)結(jié)束時間最小值影響很大；隨著AGV數(shù)量增加時，外界不確定因素對最末任務(wù)結(jié)束時間最小值的影響就會越來越小，直到幾乎沒有影響，見圖4和圖5。

對8種情況下5 000組數(shù)據(jù)最大值，平均值和最小值散點(diǎn)進(jìn)行了擬合，因?yàn)閳D形類似，于是以一種情況為例畫擬合圖，見圖6。發(fā)現(xiàn)最大值、平均值和最小值的擬合程度很高，最大值的擬合線為y=-24.546x+541.9，存在明顯的負(fù)相關(guān)線性關(guān)系。本文可以這樣理解，在自動化集裝箱碼頭中實(shí)際運(yùn)輸過程，最末任務(wù)完成時間最小值總受不確定因素影響，所有最末任務(wù)結(jié)束時間最小值當(dāng)中，最大值變化是很明顯的，這就意味著最末任務(wù)結(jié)束時間最大值受外界不確定性因素影響是很大的，呈負(fù)相關(guān)關(guān)系；所有最末任務(wù)結(jié)束時間最小值當(dāng)中，最小值變化幅度不大，最小值的擬合直線為y=432.29x-0.155，趨向于一個平緩趨勢。說明，外界不確定因素對于最末任務(wù)結(jié)束時間最小值的影響是有限的，在一定程度上增加了工作時間，但不是時間增加的決定性因素。

本文考慮Tasks為10和20，AGV=2,3,4,5, 6,7,8時，對應(yīng)的f值，得到了5 000組解，為了使得結(jié)果清晰明了，本文對每一組Tasks隨機(jī)選取了7組數(shù)據(jù)(表1)繪制折線圖。

圖3最末任務(wù)結(jié)束時間最小值的正態(tài)概率分布圖

Fig.3Normal probability distribution of

the minimum last task end time

圖4最末任務(wù)結(jié)束時間最大值、平均值

最小值隨AGV數(shù)量的變化

Fig.4The maximum、average、minimum of the

last task end time values changes with AGVs

圖5　最末任務(wù)結(jié)束時間最大值

首先，用對數(shù)趨勢線對AGV最末任務(wù)結(jié)束時間最小值關(guān)系圖進(jìn)行擬合見圖7和圖8,發(fā)現(xiàn)擬合效果很好，見表2。當(dāng)任務(wù)一定時，一開始曲線下降的速度很快，但之后降速又會趨于平穩(wěn)。 隨著AGV數(shù)量的增加，最末任務(wù)結(jié)束時間最小值基本上是呈下降的趨勢，但是當(dāng)數(shù)量趨于一定的值時，最末任務(wù)結(jié)束時間最小值就趨向于一個值，不會再發(fā)生明顯的上升或者下降，也就是說在自動化集裝箱碼頭實(shí)際運(yùn)

圖7　AGV與最末任務(wù)結(jié)束時間最小值關(guān)系

行過程中，并不是AGV數(shù)量越多，整個運(yùn)作效率就會越高，對于AGV的數(shù)量選擇，碼頭工作人員應(yīng)該選取一個相對最優(yōu)值。

同時還可以看出，當(dāng)任務(wù)一定時，最末任務(wù)結(jié)束時間最小值一定時，存在8輛AGV完成任務(wù)的時間與3、4輛AGV完成任務(wù)的時間相同的情形，說明外界不確定因素對自動化集裝箱碼頭運(yùn)輸確實(shí)有影響，合理安排工作流程，對AGV進(jìn)行合理調(diào)度，減少岸吊、龍門吊等待的時間都是很有必要的。

根據(jù)兩次試驗(yàn)，自動化集裝箱碼頭實(shí)際運(yùn)行過程中，AGV的成本較高，需根據(jù)任務(wù)數(shù)目，選擇合適的車輛數(shù)，車輛數(shù)目并不是越多越好，可以通過一定的方式，得出AGV的最優(yōu)值，這樣可以降低很多成本；其次,外界不確定因素對最末任務(wù)結(jié)束時間最小值確實(shí)是有影響的，但不是決定性因素，集裝箱碼頭內(nèi)部應(yīng)該盡量安排好自己的作業(yè)流程，避免發(fā)生任務(wù)重疊，交通擁堵情況，提高工作效率，降低工作成本，增加碼頭的競爭力。

4結(jié)語

在自動化集裝箱碼頭對于AGV的調(diào)度模式要科學(xué)與合理，合理的調(diào)度模式可以提高 AGV的利用率，減少空駛時間，提升重載率，并且其制造成本較高，如果使用效率太低的話，不僅會增加成本，造成資源浪費(fèi)，而且會降低生產(chǎn)效率，影響企業(yè)的服務(wù)效率。本文在已有文獻(xiàn)的基礎(chǔ)上考慮了不確定因素，包括自動化集裝箱碼頭堆場內(nèi)的交通控制、交通擁堵情況等，建立了以最末任務(wù)結(jié)束時間最小化為目標(biāo)的混合整數(shù)規(guī)劃模型，研究了不確定環(huán)境下AGV的調(diào)度與配置問題，對今后研究該領(lǐng)域的問題提供理論價值，有實(shí)際應(yīng)用價值。

不足之處就在于，沒有考慮具體的某種不確定性因素對集裝箱碼頭調(diào)度的影響，以及對AGV數(shù)量的影響，以后可以在這方面進(jìn)行研究。

參考文獻(xiàn):

[1]LEE D , CAO J X, SHI Q X, et, al.Integrated quay crane and yard truck schedule problem in container terminals[J]. Tsinghua Science and Technology, 2010, 15(4): 467-474.

[2]CAO J X, LEE D H, CHEN J H, et, al.The integrated yard truck and yard crane scheduling problem: Benders’ decomposition-based methods[J]. Transportation Research Part E:Logistics and Transportation Review,2010, 46(3):344-353.

[3]ELMEKKAWY T Y, LIU S.A new memetic algorithm for optimizing the partitioning problem of tandem AGV systems[J]. International Journal of Production Economics, 2009, 118(2): 508-520.

[4]CONFESSORE G, FABIANO M, LIOTTA G.A network flow based heuristic approach for optimising AGV movements[J]. Journal of Intelligent Manufacturing , 2011, 24(2): 405-419.

[5]康志敏.集裝箱自動化碼頭 AGV 路徑優(yōu)化和調(diào)度研究[D]. 武漢理工大學(xué),2011.

[6]徐遠(yuǎn)琴，韓曉龍.集卡與岸橋及場橋聯(lián)合調(diào)度模型優(yōu)化[J],重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,32(2):318-320.

[7]張遠(yuǎn)春,范秀敏,駒田邦久.基于仿真優(yōu)化的多種類型AGV數(shù)量配置優(yōu)化方法[J]. 中國機(jī)械工程, 2011, 22(14):1680-1685.

[8]計(jì)明軍，靳志宏.集裝箱碼頭集卡與岸橋協(xié)調(diào)調(diào)度優(yōu)化[J]. 復(fù)旦學(xué)報(bào)(自然科學(xué)版),2007,46(4):476-480.

[9]曾慶成.集裝箱碼頭裝卸作業(yè)集成調(diào)度模型與方法[D]. 大連：大連海事大學(xué)，2008.

[10]秦天保，彭嘉瑤，沙梅.帶任務(wù)順序約束的岸橋集卡集成調(diào)度約束規(guī)劃模型[J]. 上海海事大學(xué)學(xué)報(bào)，2013,34(3):1-7.

[11]馬超，梁承姬.集裝箱碼頭岸橋分配與集卡調(diào)度整合問題研究[J]. 廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，40(3):643-650.

[12]梁承姬,王玲玲,佘文靜.考慮時間窗約束的集卡調(diào)度耦合模型及求解[J]. 廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014,39(3):656-662.

(責(zé)任編輯梁碧芬)

The dispatching and scheduling problems of AGVs at automated container terminals under uncertainty conditions

MA Yue-hui, HU Zhi-hua

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

Abstract：In order to study the dispatching and scheduling problems of AGVs at automated container terminals under uncertainty conditions, a model for minimizing the last task end time is established. 5000 data have been generated in a reasonable scope, with two decision variables, including the time for loading and unloading container task with boxes as well as the empty driving time from completing a task to performing the next task, and then the representative data are analyzed. The uncertainty factors, such as the traffic control and traffic jam, are taken into account. The results show that： The external uncertainties have limited impact on the minimum value of the last task end time, and they increase the working time to a certain extent but are not the decisive factors of increasing time. During the process of automated container terminal operation, a large quantity of AGV will not lead to higher operating efficiency. With the increase of the number of AGV, the impact of uncertainty factors on the minimum value of the last task end time will reduce, until there is almost no impact .Computational experiments have been conducted to verify the validity and practicality of the model.

Key words:automated container terminals; automated guided vehicle; linear program; dispatching and scheduling

中圖分類號:U691.31; TP301.6

文獻(xiàn)標(biāo)識碼:A

文章編號：1001-7445(2016)02-0589-09

doi:10.13624/j.cnki.issn.1001-7445.2016.0589

通訊作者：胡志華(1977—)，男，湖南長沙人，上海海事大學(xué)教授，博士后，博士;E-mail：zhhu@shmtu.edu.cn。

基金項(xiàng)目：國家自然科學(xué)基金青年項(xiàng)目(71101088)；國家自然科學(xué)基金面上項(xiàng)目(71471109)；上海市曙光計(jì)劃項(xiàng)目(13SG48)；上海市教委科研創(chuàng)新項(xiàng)目(14YZ100);交通部應(yīng)用基礎(chǔ)研究項(xiàng)目(2015329810260)

收稿日期：2015-11-11；

修訂日期：2016-01-07

引文格式：馬越匯,胡志華.不確定環(huán)境下自動化集裝箱碼頭AGV調(diào)度與配置問題[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，41(2)：589-597.