有限緩沖空間下岸橋和自動(dòng)升降車的集成調(diào)度

余孟齊，韓曉龍

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

?

有限緩沖空間下岸橋和自動(dòng)升降車的集成調(diào)度

余孟齊，韓曉龍

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

摘要：為了解決自動(dòng)化集裝箱碼頭中岸橋和自動(dòng)升降車(ALV)的集成調(diào)度問(wèn)題,考慮ALV自身能夠從地面提升集裝箱的特點(diǎn),提出碼頭前沿的緩沖區(qū)約束,建立以最小化ALV總移動(dòng)時(shí)間和岸橋作業(yè)總延遲為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型并進(jìn)行了求解；通過(guò)數(shù)值實(shí)驗(yàn)將調(diào)度模型與同一問(wèn)題中的自動(dòng)導(dǎo)引小車(AGV)相比較,并對(duì)ALV的數(shù)量和緩沖能力進(jìn)行靈敏度分析,結(jié)果表明在有限緩沖空間情況下,使用ALV集成調(diào)度方案的作業(yè)總成本比使用AGV的調(diào)度方案減少了近28.72%,驗(yàn)證了ALV在有限緩沖情況下比AGV有更好的性能，有助于提高集裝箱碼頭整體作業(yè)效率和港口競(jìng)爭(zhēng)力。

關(guān)鍵詞：自動(dòng)化集裝箱碼頭;ALV;岸橋;有限緩沖空間;集成調(diào)度

在過(guò)去十年中，全球貿(mào)易快速發(fā)展，世界集裝箱碼頭吞吐量在2011年增長(zhǎng)了5.9%，達(dá)到歷史最高水平(5.728億標(biāo)準(zhǔn)箱)[1]。如今超過(guò)60%的深海普通貨物通過(guò)集裝箱運(yùn)輸，尤其是在經(jīng)濟(jì)發(fā)達(dá)、關(guān)系穩(wěn)定的國(guó)家之間[2]。集裝箱裝運(yùn)數(shù)量的增加會(huì)導(dǎo)致集裝箱碼頭之間的競(jìng)爭(zhēng)變得越來(lái)越激烈。因此，對(duì)于港口運(yùn)營(yíng)商而言，開(kāi)發(fā)不同的優(yōu)化算法和決策工具提高其性能和競(jìng)爭(zhēng)力是非常重要的。自動(dòng)化集裝箱碼頭(ACT)將有助于到降低運(yùn)營(yíng)成本，提高集裝箱碼頭的吞吐量[3]。

目前，國(guó)內(nèi)外學(xué)者對(duì)集裝箱碼頭裝卸設(shè)備的調(diào)度已經(jīng)有了一定的研究。HASSAN等[4]將集裝箱碼頭的AGV調(diào)度問(wèn)題制定為最低費(fèi)用流問(wèn)題的一個(gè)特例，并為解決該問(wèn)題提出了NSA+(network simplex algorithm+)算法和貪婪車輛搜索算法。HOMAYOUNI等[5]將岸橋和AGV的集成調(diào)度制定為一個(gè)混合整數(shù)線性規(guī)劃模型，并將Lingo軟件的求解結(jié)果與模擬退火算法的結(jié)果進(jìn)行對(duì)比，結(jié)果表明模擬退火算法在實(shí)際調(diào)度問(wèn)題中具有更好的性能。HOMAYOUNI等[6]還研究了自動(dòng)化集裝箱碼頭岸橋、AGV和存儲(chǔ)平臺(tái)這3種設(shè)備的集成調(diào)度，并提出了一種遺傳算法，對(duì)存儲(chǔ)平臺(tái)3個(gè)不同停留點(diǎn)的策略進(jìn)行了檢驗(yàn)，并將所提出的遺傳算法與已有算法進(jìn)行比較，結(jié)果表明遺傳算法在調(diào)度范圍內(nèi)的作業(yè)次數(shù)增加條件下優(yōu)于已有算法。國(guó)內(nèi)學(xué)者康志敏[7]研究了自動(dòng)化碼頭AGV路徑優(yōu)化和調(diào)度，建立了以無(wú)效等待時(shí)間最少的小車調(diào)度優(yōu)化模型，并利用遺傳算法對(duì)建立的模型進(jìn)行分析求解。梁承姬等[8]對(duì)集裝箱港口岸橋、集卡、場(chǎng)橋3種裝卸作業(yè)設(shè)備的集成調(diào)度問(wèn)題進(jìn)行建模，并設(shè)計(jì)了一種矩陣編碼方式的遺傳算法對(duì)問(wèn)題進(jìn)行求解。BAE等[9]通過(guò)仿真研究比較了AGV和ALV的運(yùn)行效率，仿真實(shí)驗(yàn)表明，ALV到達(dá)與AGV相同的生產(chǎn)力水平，使用的車輛數(shù)量比AGV少。NGUYEN等[10]為ALV交付作業(yè)的最優(yōu)分配提出了一種混合整數(shù)規(guī)劃模型，將模型中的緩沖區(qū)約束轉(zhuǎn)化為時(shí)間窗約束，然后提出了一個(gè)啟發(fā)式算法來(lái)解決帶有優(yōu)先約束和時(shí)間窗約束的調(diào)度問(wèn)題。

當(dāng)前研究中涉及岸橋和ALV的集成調(diào)度問(wèn)題較少，筆者將重點(diǎn)探討考慮自動(dòng)化集裝箱碼頭在有限緩沖情況下岸橋和ALV的集成調(diào)度，提出了一個(gè)以ALV的總移動(dòng)時(shí)間和岸橋作業(yè)的總延遲時(shí)間最小化為目標(biāo)函數(shù)的岸橋和ALV集成調(diào)度問(wèn)題，并應(yīng)用CPLEX求解該混合整數(shù)規(guī)劃模型。通過(guò)算例驗(yàn)證該模型和方案對(duì)自動(dòng)化集裝箱碼頭實(shí)際資源調(diào)度均衡性的效果。

1問(wèn)題描述

岸橋和ALV的集成調(diào)度問(wèn)題是指在已知條件下合理調(diào)配岸橋和ALV的裝卸作業(yè)，完成集裝箱船舶任務(wù)的優(yōu)化問(wèn)題。裝卸活動(dòng)分為兩個(gè)部分，①由岸橋執(zhí)行的裝卸活動(dòng)，稱為海邊作業(yè)；②由ALV和自動(dòng)化場(chǎng)橋(AYC)執(zhí)行的裝卸活動(dòng)，稱為岸邊作業(yè)。卸載作業(yè)中，岸橋撿取集裝箱放在碼頭前沿岸橋下的緩沖空間中；然后ALV撿取集裝箱并將其傳送到編組堆場(chǎng)；在編組堆場(chǎng)，ALV釋放集裝箱到堆場(chǎng)中轉(zhuǎn)運(yùn)點(diǎn)的緩沖空間；AYC撿取集裝箱并將其堆放在海灣中空的位置。裝載作業(yè)以與卸載作業(yè)相反的順序執(zhí)行。

ALV卸載作業(yè)的功能和職責(zé)是把集裝箱從碼頭前沿傳送到堆場(chǎng)，裝載作業(yè)則是把集裝箱從堆場(chǎng)傳送到碼頭前沿。在卸載作業(yè)期間，岸橋從船頭撿取集裝箱并將其傳送到緩沖區(qū)?？紤]碼頭前沿和堆場(chǎng)有一定的緩沖空間，其中岸橋、AYC、ALV均可釋放集裝箱。岸橋或AYC可以直接從ALV上撿取集裝箱或者把集裝箱放在ALV上。然而，由于ALV自身有能力從地面上提升集裝箱，如果緩沖空間是可用的岸橋可以將集裝箱放在緩沖空間，但緩沖空間已滿時(shí)岸橋和ALV必須等待。為了提高作業(yè)效率，降低船舶操作延遲，筆者以最小化的岸橋延遲時(shí)間和ALV移動(dòng)時(shí)間為目標(biāo)。

2模型假設(shè)

結(jié)合實(shí)際情況，對(duì)問(wèn)題進(jìn)行了合理簡(jiǎn)化，提出如下假設(shè)：①所有ALV的能力和形狀都是相同的，且一次傳送一個(gè)集裝箱。②對(duì)于一個(gè)ALV共享策略被應(yīng)用到調(diào)度過(guò)程，既不分配給特定類型的集裝箱，也不分配給特定的起重機(jī)。這意味著沒(méi)有ALV是專用于一個(gè)岸橋的。③不考慮ALV在導(dǎo)引路徑中的擁塞。④ALV或岸橋拾取和釋放集裝箱的作業(yè)時(shí)間足夠小，可以忽略不計(jì)。⑤ALV的移動(dòng)時(shí)間、岸橋在碼頭和船只區(qū)域(TQ)的移動(dòng)時(shí)間及其作業(yè)時(shí)間是預(yù)先確定的。⑥在雙循環(huán)中，緩沖區(qū)中岸橋(或ALV)釋放一個(gè)集裝箱之后到緩沖區(qū)中ALV(或岸橋)撿取另一個(gè)集裝箱之前的時(shí)間可以忽略不計(jì)。

3模型建立

(3)數(shù)學(xué)模型。其中目標(biāo)函數(shù)為：

(2)

(3)

l∈K,i=1,2，…,mk,j=1,2,…,m

(4)

(5)

(6)

i=1,2…,mk-1

(7)

(8)

(9)

(10)

(11)

(13)

(14)

(15)

(16)

i=1,2,…,mk,j=1,2,…,ml

(17)

4算例實(shí)驗(yàn)

通過(guò)一組測(cè)試算例將具有有限緩沖空間的ALV調(diào)度所提出的模型與帶有AGV的同樣問(wèn)題進(jìn)行比較。表1顯示了QC1應(yīng)用于船舶作業(yè)的一個(gè)序列表例子，其以雙周期的方式執(zhí)行船舶作業(yè)。表2顯示了QC1船舶作業(yè)中的事件及其符號(hào)。在表1最后一列中的最早事件時(shí)間是指岸橋作業(yè)在沒(méi)有任何中斷和延遲的假設(shè)下，岸橋傳送集裝箱到ALV或從ALV傳送集裝箱的時(shí)間。

表1　QC1船舶作業(yè)的序列表

注：QC1緩沖容量為2；船舶位置編號(hào)分別表示船舶的貝編號(hào)/行編號(hào)/列編號(hào)；堆場(chǎng)位置編號(hào)分別表示堆場(chǎng)箱區(qū)的編號(hào)/堆場(chǎng)貝的編號(hào)/行編號(hào)/列編號(hào)

4.1ALV與AGV 的目標(biāo)值分析

10個(gè)測(cè)試算例來(lái)自于一個(gè)堆場(chǎng)具有6個(gè)轉(zhuǎn)運(yùn)點(diǎn)和碼頭前沿有6臺(tái)岸橋的典型自動(dòng)化集裝箱碼頭。表3所示為算例中ALV和AGV的目標(biāo)值對(duì)比情況。所有ALV和AGV的測(cè)試由CPLEX軟件編程解決。表3中，CPLEX求出ALV與AGV目標(biāo)值的比值范圍為0.642 43～0.806 95。從數(shù)值結(jié)果可以觀察到，在所有的測(cè)試算例中，具有有限緩沖空間的ALV比AGV的結(jié)果更好，通過(guò)增加ALV的數(shù)量，可以得到更好的結(jié)果和更早的完工時(shí)間。在有限緩沖空間情況下，使用ALV的集成調(diào)度方案的作業(yè)總成本比使用AGV的調(diào)度方案減少了近28.72%。

表2　QC1船舶作業(yè)的事件

表3　算例結(jié)果比較

4.2ALV的數(shù)量和緩沖能力的靈敏度分析

圖1所示為ALV的數(shù)量對(duì)岸橋總延遲時(shí)間的影響折線圖，可見(jiàn)岸橋的延遲時(shí)間隨著ALV數(shù)量的增加而迅速減小。當(dāng)ALV的數(shù)量超過(guò)一定的水平條件下，減少量可以忽略不計(jì)。對(duì)于緩沖空間容量的變化，岸橋的延遲時(shí)間隨著緩沖空間容量的增加而減少。然而，當(dāng)ALV的數(shù)量達(dá)到4時(shí)(如圖2中所示)，緩沖區(qū)容量的變化不影響岸橋的延遲時(shí)間。

圖1　ALV的數(shù)量對(duì)岸橋總延遲時(shí)間的影響折線圖

圖2顯示了總延遲時(shí)間在有緩沖和沒(méi)有緩沖情況的不同。當(dāng)ALV的數(shù)量為2時(shí)，改進(jìn)比率的范圍為5.5%～18%。當(dāng)ALV的數(shù)量為4時(shí)，差異由1.5%到2%?？梢钥闯觯S著ALV數(shù)量的增加，改進(jìn)比率的差異減小。

圖2　有緩沖區(qū)和無(wú)緩沖區(qū)改進(jìn)比率對(duì)比圖

5結(jié)論

筆者針對(duì)岸橋和ALV在有限緩沖空間下集成調(diào)度問(wèn)題的一些特性和約束，建立了集成調(diào)度問(wèn)題的模型；通過(guò)算例分析得知，ALV集成調(diào)度方案的作業(yè)總成本比AGV調(diào)度方案可減少28.72%，驗(yàn)證了ALV在有限緩沖情況下比AGV有更好的性能；在其他條件相同的情況下，ALV比AGV能更有效地提高港口作業(yè)效率，增加港口的經(jīng)濟(jì)效益。此外，ALV數(shù)量和緩沖能力的敏感性分析實(shí)驗(yàn)結(jié)果證明，增加ALV的數(shù)量可以減少岸橋作業(yè)的延遲；當(dāng)ALV的數(shù)量較少時(shí)，緩沖空間的大小對(duì)岸橋作業(yè)的延遲時(shí)間影響很大，然而隨著ALV數(shù)量的增加，影響也隨之減小。

參考文獻(xiàn)：

[1]NARGES K,NATHAN H.Integrated quay crane and yard truck scheduling for unloading inbound containers[J].International Journal of Production Economics,2015,159(1):168-177.

[2]HOAI M L,ADNAN Y,RIADH M.DCA for solving the scheduling of lifting vehicle in an automated port container terminal[J].Computational Management Science,2012(9):273-286.

[3]XIN J B,RUDY R N,GABRIEL L.Energy-aware control for automated container terminals using integrated flow shop scheduling and optimal control[J].Transportation Research Part C:2014,44(2):214-230.

[4]HASSAN R,EDWARD PKT.A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals[J].Computers and Mathematics with Applications,2011,61(3):630-641.

[5]HOMAYOUNI S M,TANG S H，NAPSIAH I.Using simulated annealing algorithm for optimization of quay cranes and automated guided vehicles scheduling[J].International Journal of the Physical Sciences,2011,6(27):6286-6294.

[6]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(1):545-556.

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

[8]梁承姬，張松波.集裝箱港口裝卸作業(yè)設(shè)備集成調(diào)度[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,34(2):262-266.

[9]BAE H Y,CHOE R,PARK T,et al.Comparison of operations of AGVs and ALVs in an automated container terminal[J].Journal of Intelligent Manufacturing,2011,22(1):413-426.

[10]NGUYEN V D,KIM K H.A dispatching method for automated lifting vehicles in automated port container terminals[J].Computers & Industrial Engineering,2009,56(3):1002-1020.

YU Mengqi:Postgraduate; Logistics Research Center,Shanghai Martine University,Shanghai 201306,China.

[編輯：王志全]

文章編號(hào)：2095-3852(2016)01-0101-05

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

收稿日期：2015-07-14.

作者簡(jiǎn)介：余孟齊(1992-)，女，安徽安慶人，上海海事大學(xué)物流研究中心碩士研究生．

基金項(xiàng)目：上海市科學(xué)技術(shù)委員會(huì)工程中心能力建設(shè)項(xiàng)目基金資助項(xiàng)目(14DZ2280200)．

中圖分類號(hào)：U691;U169.63;N945.12

DOI：10.3963/j.issn.2095-3852.2016.01.022

Integrated Scheduling of Quay Cranes and Automated Lifting Vehicles with Limited Buffer Space

YU Mengqi,HAN Xiaolong

Abstract：In order to solve the integrated scheduling of quay cranes and ALVs in automated container terminal,considering that an ALV are capable of lifting a container from the ground by itself,buffer constraints in an apron were suggested,a mixed integer programming model was set up,aiming to minimize the total travel time of ALVs and the total delays in QC operations.Then,CPLEX was used to solve this model.Finally,comparing the scheduling results between the proposed model for dispatching of ALVs and the same problem with AGV,and analyzing the sensitivity of the number of ALVs and buffer capacity.The results showed that the total cost in scheduling of ALV almost reduced by 28.72% compared with AGV,which confirmed that ALV with limited buffer space has better performance than AGV.The sensitivity analysis can help to improve the operation efficiency of container terminals and increase the competitive strength of the port.

Key words：automated container terminal; ALV; quay crane; limited buffer space; integrated scheduling