余孟齊，韓曉龍

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

?

集裝箱碼頭岸橋與集卡集成調(diào)度問(wèn)題研究

余孟齊，韓曉龍

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

摘要：岸橋與集卡是集裝箱碼頭的重要資源。為了提高碼頭的裝卸效率，針對(duì)集裝箱碼頭岸橋和集卡的集成調(diào)度問(wèn)題，以完工時(shí)間最小為優(yōu)化目標(biāo)，考慮集裝箱之間優(yōu)先關(guān)系和岸橋安全邊際的實(shí)際約束，建立混合整數(shù)線(xiàn)性規(guī)劃模型，利用改進(jìn)粒子群算法(IPSO)對(duì)模型進(jìn)行求解, 制定了粒子編碼和解碼規(guī)則，設(shè)計(jì)了一種新的速度更新策略來(lái)改進(jìn)解的質(zhì)量。實(shí)驗(yàn)表明，將改進(jìn)算法的結(jié)果與優(yōu)化軟件CPLEX所求得的最優(yōu)解比較，IPSO算法求得12組數(shù)值算例的平均偏差為 0.582%，且CPLEX計(jì)算時(shí)間的跨度隨著計(jì)算規(guī)模的擴(kuò)大從2.92 s到1 h，而IPSO的求解時(shí)間控制在50 s之內(nèi)，并得到最優(yōu)解，證明了該模型和算法可以快速有效地解決岸橋與集卡的集成調(diào)度問(wèn)題。

關(guān)鍵詞：岸橋;集卡;集成調(diào)度;粒子群算法

0引言

由于集裝箱運(yùn)輸量的增加，集裝箱碼頭已經(jīng)成為海陸運(yùn)輸間的重要接口。在這個(gè)競(jìng)爭(zhēng)日益激烈的行業(yè)，碼頭必須提高各種資源的運(yùn)作效率。圖1顯示了集裝箱碼頭的典型布局。如圖1所示，碼頭中存在三個(gè)主要的集裝箱處理設(shè)備：岸橋，集卡和場(chǎng)橋。岸橋負(fù)責(zé)從船上卸載集裝箱和將集裝箱裝載到船上，場(chǎng)橋負(fù)責(zé)堆疊進(jìn)口箱和從堆場(chǎng)檢索出口箱，集卡負(fù)責(zé)在岸橋和堆場(chǎng)之間運(yùn)輸集裝箱。這三種設(shè)備作業(yè)緊密相連，需要良好的協(xié)調(diào)來(lái)避免由于互相等待造成的效率損失。

圖1集裝箱碼頭典型布局

Fig.1Typical layout of a container terminal

國(guó)內(nèi)外學(xué)者對(duì)集裝箱碼頭裝卸設(shè)備調(diào)度已有一定研究。對(duì)于岸橋調(diào)度問(wèn)題，Kim等[1]為船舶貝位中的多任務(wù)岸橋調(diào)度問(wèn)題建立了一個(gè)混合整數(shù)規(guī)劃模型，并設(shè)計(jì)啟發(fā)式搜算法來(lái)解決問(wèn)題。Lee等[2]考慮岸橋間的干擾，通過(guò)遺傳算法為船上任務(wù)找到了一組岸橋分配序列。董良才等[3]采用遺傳算法求解帶時(shí)間窗的岸橋調(diào)度混合整數(shù)規(guī)劃模型。靳志宏等[4]為碼頭岸橋調(diào)度問(wèn)題構(gòu)建非線(xiàn)性整數(shù)規(guī)劃模型，并設(shè)計(jì)基于任務(wù)排序的遺傳算法對(duì)模型進(jìn)行求解。

對(duì)于集卡調(diào)度問(wèn)題，尚晶等[5]提出具有集卡實(shí)時(shí)調(diào)度規(guī)則的動(dòng)態(tài)仿真模型，并利用WITNESS仿真軟件進(jìn)行仿真實(shí)驗(yàn)分析。Bish[6]通過(guò)啟發(fā)式算法求解集卡動(dòng)態(tài)調(diào)度模型，其目標(biāo)是為了最小化船舶周轉(zhuǎn)的時(shí)間。Nishimura等[7]提出集卡動(dòng)態(tài)路徑的調(diào)度方法，并采用遺傳算法進(jìn)行求解?？抵久舻萚8]通過(guò)集裝箱碼頭物流系統(tǒng)有色 Petri 網(wǎng)建模的基本構(gòu)架來(lái)求解集卡調(diào)度問(wèn)題。

近年來(lái)，學(xué)者們已經(jīng)對(duì)岸橋和集卡的集成調(diào)度問(wèn)題進(jìn)行研究。Chen等[9]將岸橋、集卡和場(chǎng)橋的集成調(diào)度問(wèn)題制定為約束規(guī)劃模型并提出三階段算法來(lái)求解模型。Lau等[10]對(duì)相同問(wèn)題進(jìn)行深入研究，其目標(biāo)函數(shù)是最小化場(chǎng)橋行走的時(shí)間、集卡運(yùn)輸?shù)臅r(shí)間與岸橋空閑的時(shí)間。Kaveshgar等[11]為卸載入境集裝箱的岸橋與集卡集成調(diào)度問(wèn)題制定了混合整數(shù)規(guī)劃模型，并使用遺傳算法求解。張笑等[12]提出基于岸橋作業(yè)和集卡運(yùn)輸總時(shí)間最小的岸橋與集卡協(xié)作優(yōu)化模型，并通過(guò)Gurobi實(shí)現(xiàn)集卡路徑優(yōu)化。馬超等[13]等在同時(shí)考慮進(jìn)出口集裝箱的情況下，采用多層遺傳算法求解岸橋和集卡的協(xié)同調(diào)度問(wèn)題。秦天保等[14]提出帶任務(wù)順序約束的岸橋集卡集成調(diào)度約束規(guī)劃模型，并設(shè)計(jì)新的下界求法評(píng)價(jià)解的質(zhì)量。邢曦文等[15]建立了基于三階段混合流水作業(yè)的碼頭裝卸作業(yè)集成調(diào)度優(yōu)化模型，采用兩階段啟發(fā)式算法求解。

但目前已有研究大都是針對(duì)岸橋與集卡單向作業(yè)集成調(diào)度，對(duì)于雙向作業(yè)集成調(diào)度研究較少。本文在考慮集裝箱之間的優(yōu)先關(guān)系以及岸橋安全邊際的實(shí)際約束的基礎(chǔ)上，研究岸橋與集卡雙向作業(yè)集成調(diào)度問(wèn)題，提出基于改進(jìn)粒子群算法(IPSO)求解調(diào)度優(yōu)化模型，并通過(guò)數(shù)值實(shí)驗(yàn)對(duì)算法可行性和實(shí)用進(jìn)行了分析。

1問(wèn)題描述

在傳統(tǒng)碼頭作業(yè)中，岸橋通常被安排來(lái)處理到達(dá)的船舶，然后集卡被分配來(lái)服務(wù)特定的岸橋。在這種方法中，每臺(tái)岸橋與一組固定的集卡合作。岸橋和集卡可能經(jīng)常互相等待。以卸載過(guò)程為例，如果一個(gè)集裝箱被岸橋卸載，但是沒(méi)有集卡到達(dá)，岸橋必須保留集裝箱并等待集卡到達(dá)。反之，如果當(dāng)集卡到達(dá)時(shí)岸橋沒(méi)有完成集裝箱的卸載，集卡必須等待。這樣就會(huì)降低集卡的利用率。如圖2所示，兩條船停泊在碼頭。岸橋1和岸橋2分別分配給船舶1和船舶2。集卡1和集卡2都分配給岸橋1用于運(yùn)輸集裝箱到堆場(chǎng)；集卡3被分配給岸橋2。當(dāng)沒(méi)有可用的集卡運(yùn)送由岸橋2卸載的集裝箱時(shí)，岸橋2必須持有集裝箱并等待集卡。與此同時(shí)，被分配到岸橋1的集卡1和集卡2都必須排隊(duì)等待來(lái)運(yùn)輸由岸橋1卸載的集裝箱。為了避免這樣的情況，在本文中，我們通過(guò)岸橋和集卡的集成調(diào)度，以減少船舶的周轉(zhuǎn)時(shí)間，如圖3所示，集卡1轉(zhuǎn)為服務(wù)于岸橋2。因此，岸橋2不需要等待，從而提集裝箱碼頭的總生產(chǎn)率。

圖2岸橋與集卡單獨(dú)調(diào)度

Fig.2Schedule quay cranes and yard trucks separately

圖3岸橋與集卡集成調(diào)度

Fig.3Schedule quay cranes and yard trucks jointly

我們問(wèn)題的決策包括岸橋和集卡的分配以及分配給岸橋和集卡的裝卸作業(yè)的順序。

2模型的建立

環(huán)境假設(shè)：①集裝箱之間存在優(yōu)先關(guān)系。②不考慮岸橋間的相互干擾。③場(chǎng)橋有足夠的裝卸能力，集卡不需要在堆場(chǎng)等待。④每個(gè)集裝箱在船上和堆場(chǎng)中的位置都是已知的。⑤岸橋和集卡每次只能處理一個(gè)集裝箱。

目標(biāo)函數(shù)：

(1)

約束條件：

(2)

(3)

(4)

(5)

Fh≥Ci1i∈Ah,h∈B,

(6)

Fh-Sh′+Yhh′M≥0h,h′∈B,

(7)

Fh-Sh′-(1-Yhh′)M≤0h,h′∈B,

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

3基于粒子群算法的岸橋-集卡集成調(diào)度問(wèn)題求解

粒子群算法(PSO)是一種基于種群的優(yōu)化算法，在每次迭代中，每個(gè)粒子代表具有位置和速度的解。位置反映解的質(zhì)量，速度決定在下一次迭代中粒子的移動(dòng)位置。速度和位置的普通更新公式如下：

(32)

(33)

3.1解的表示

本文的調(diào)度問(wèn)題必須決定岸橋和集卡的分配以及集裝箱被岸橋和集卡裝卸的順序。因?yàn)檫@個(gè)問(wèn)題有由岸橋卸載作業(yè)和集卡運(yùn)輸作業(yè)兩個(gè)階段，對(duì)每臺(tái)岸橋的分配和集裝箱順序編碼，然后根據(jù)岸橋的調(diào)度順序?qū)⒓ǚ峙浣o集裝箱。

表1　粒子編碼

表2　粒子解碼

3.2速度更新策略

粒子群算法一個(gè)主要優(yōu)點(diǎn)是它收斂速度很快，但這容易導(dǎo)致其陷入局部最優(yōu)解。這是因?yàn)槊總€(gè)粒子總是傾向于朝著它曾經(jīng)達(dá)到的最優(yōu)位置和迄今為止整個(gè)粒子群全局最優(yōu)位置飛行。在本文的算法中，適應(yīng)值等于目標(biāo)值。為了克服陷入局部最優(yōu)的缺點(diǎn)，當(dāng)一個(gè)粒子適應(yīng)值不大于粒子群中所有粒子的平均適應(yīng)值時(shí)，我們提出修改的速度更新公式如下：

(34)

3.3粒子群優(yōu)化算法步驟

解決多個(gè)岸橋和集卡調(diào)度問(wèn)題的粒子群算法執(zhí)行步驟如圖4所示。

圖4　粒子群算法步驟

4數(shù)值實(shí)驗(yàn)與結(jié)果分析

為了評(píng)估IPSO算法的性能，我們隨機(jī)生成3種類(lèi)型的問(wèn)題——6個(gè)小規(guī)模問(wèn)題、3個(gè)中等規(guī)模問(wèn)題以及3個(gè)大規(guī)模問(wèn)題。將提出的IPSO算法的結(jié)果與使用優(yōu)化軟件(CPLEX)求解混合整數(shù)線(xiàn)性規(guī)劃模型得到的最優(yōu)解相比較。

4.1試驗(yàn)設(shè)計(jì)

問(wèn)題的實(shí)驗(yàn)數(shù)據(jù)產(chǎn)生如下：

①作業(yè)時(shí)間(以s為單位)從下面的均勻分布中生成：岸橋作業(yè)U(105，161)；集卡移動(dòng)U(60,130)。

②進(jìn)口(出口)箱的原始(目標(biāo)位置)考慮船舶布局隨機(jī)生成，進(jìn)口(出口)箱的目標(biāo)(原始)位置基于集裝箱碼頭的實(shí)際布局產(chǎn)生。

考慮算法參數(shù)設(shè)置的不同同樣會(huì)影響算法性能，所以選擇試算后各算法的最優(yōu)參數(shù)進(jìn)行運(yùn)算。IPSO算法中，對(duì)于所有數(shù)值實(shí)驗(yàn)，最大迭代次數(shù)gen=500，種群規(guī)模pop_size=30，c1=c2=2，c3=1。

所有實(shí)驗(yàn)都是在4 GB內(nèi)存和2.80 GHz處理器的計(jì)算機(jī)上進(jìn)行的。該算法是用Matlab編寫(xiě)，并且所述模型使用CPLEX解決。

4.2試驗(yàn)結(jié)果分析與評(píng)價(jià)

為測(cè)試IPSO算法的性能，本文設(shè)計(jì)12組算例(如表3所示)，其中目標(biāo)值顯示是 CPLEX 和IPSO算法的計(jì)算結(jié)果。設(shè)置CPLEX 最大運(yùn)行時(shí)間為60 min，即如果運(yùn)算60 min 也無(wú)法取得最優(yōu)解，就停止運(yùn)算。

表3中的數(shù)據(jù)是基于Kaveshgar等[11]論文第五部分?jǐn)?shù)值實(shí)驗(yàn)和討論中的數(shù)據(jù)，包括岸橋數(shù)量、集卡數(shù)量以及集裝箱數(shù)量來(lái)設(shè)計(jì)的算例規(guī)模。

從表3中可以看出，IPSO算法對(duì)于三種規(guī)模問(wèn)題可以得到令人滿(mǎn)意的解，算法求解12個(gè)算例的平均偏差為0.582%。對(duì)于中小規(guī)模問(wèn)題，CPLEX求得的解優(yōu)于IPSO算法，如算例1到算例9，CPLEX都獲得了最優(yōu)解。但對(duì)于大規(guī)模問(wèn)題，由IPSO算法得到的3個(gè)解中有2個(gè)比CPLEX好。IPSO算法在計(jì)算時(shí)間方面明顯優(yōu)于CPLEX。對(duì)于小規(guī)模問(wèn)題，CPLEX的平均計(jì)算時(shí)間大約是1.65 min，而IPSO平均僅用0.27 s。然而CPLEX求解模型優(yōu)化的計(jì)算時(shí)間隨著問(wèn)題規(guī)模增大迅速增加，例如算例7到算例10，CPLEX計(jì)算時(shí)間跨度從213.2 s 到接近1 h，而IPSO算法求解時(shí)間的跨度是從3.43 s到8.50 s；算例11與算例12，CPLEX已無(wú)法在1 h內(nèi)求出解，而IPSO算法分別只需要24.76 s和41.57 s。這表明IPSO算法對(duì)岸橋和集卡集成調(diào)度問(wèn)題是有效的。

表3　CPLEX與改進(jìn)的粒子群算法(IPSO)對(duì)比結(jié)果

1.相對(duì)偏差=(IPSO的目標(biāo)值-CPLEX的目標(biāo)值)/CPLEX的目標(biāo)值×100%。

下面以算例6為例，解釋運(yùn)用IPSO算法得到的最優(yōu)裝卸計(jì)劃，如表4所示。表4中的數(shù)據(jù)是通過(guò)MATLAB軟件計(jì)算算例6得到的。表4借鑒馬超等[13]論文第四部分圖表而設(shè)計(jì)的。

算例6的問(wèn)題有2臺(tái)岸橋，4輛集卡，16個(gè)集裝箱?？偼旯r(shí)間為1 240 s。其中，U代表卸載計(jì)劃，L代表裝載，數(shù)字為集裝箱編號(hào)。以岸橋1為例，U1代表卸載集裝箱1，L15代表裝載集裝箱15，以此類(lèi)推。

表4　算例6中的岸橋和集卡的裝卸計(jì)劃

4.3討論

通過(guò)對(duì)12個(gè)算例實(shí)驗(yàn)的分析，可以看出提出的IPSO算法在得到問(wèn)題解的質(zhì)量和計(jì)算時(shí)間上都優(yōu)于軟件CPLEX，這表明IPSO算法對(duì)岸橋和集卡集成調(diào)度問(wèn)題是有效的。

本文在考慮我國(guó)集裝箱碼頭現(xiàn)實(shí)情況下的作業(yè)約束，如集裝箱之間的優(yōu)先關(guān)系以及岸橋安全邊際的實(shí)際約束的基礎(chǔ)上，研究岸橋與集卡雙向作業(yè)集成調(diào)度問(wèn)題，集卡可以運(yùn)輸兩個(gè)方向的集裝箱，減少空駛，使岸橋一集卡調(diào)度更加系統(tǒng)化、合理化，對(duì)提高我國(guó)集裝箱碼頭作業(yè)效率具有實(shí)際意義。

5結(jié)論

本文考慮集裝箱之間存在優(yōu)先關(guān)系時(shí)岸橋和集卡集成調(diào)度問(wèn)題的完工時(shí)間最小化，并提出了基于IPSO算法求解的混合整數(shù)線(xiàn)性規(guī)劃模型，旨在提高集裝箱碼頭運(yùn)作效率。實(shí)驗(yàn)表明，將改進(jìn)算法的結(jié)果與CPLEX軟件所求得的最優(yōu)解比較，IPSO算法求得12組數(shù)值算例的平均偏差為 0.582%，且隨著問(wèn)題規(guī)模的不斷擴(kuò)大，CPLEX計(jì)算時(shí)間的跨度從2.92 s到1 h，已經(jīng)無(wú)法在有效時(shí)間內(nèi)求出解；而IPSO的求解時(shí)間控制在50 s之內(nèi)，能夠很好的在有限時(shí)間內(nèi)找到最優(yōu)解，證明了其有效性。將本文提出的模型和其求解算法應(yīng)用到港口實(shí)際調(diào)度中，能夠有效提高碼頭資源的利用率，具有一定使用價(jià)值。接下來(lái)的研究可以考慮將場(chǎng)橋加入集成調(diào)度，開(kāi)發(fā)集成范圍更大的調(diào)度模型。

參考文獻(xiàn):

[1]KIM K H, PARK Y M.A crane scheduling method for port container terminals [J]. European Journal of Operational Research, 2004, 156: 752-768.

[2]LEE D H, WANG H Q, MIAO L X.Quay crane scheduling with non-interference constraints in port container terminals [J]. Transportation Research Part E, 2008, 44(1): 124-135.

[3]董良才, 丁以中, 宓為建.基于時(shí)間窗的集裝箱裝卸橋調(diào)度[J]. 上海海事大學(xué)學(xué)報(bào), 2011, 32(1): 1-7.

[4]靳志宏,李娜.基于泊位計(jì)劃的集裝箱碼頭岸橋動(dòng)態(tài)調(diào)度優(yōu)化[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2011, 11(3):58-64.

[5]尚晶,陶德馨.集裝箱碼頭集卡調(diào)度策略的仿真研究[J]. 武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 2006, 30(5): 827-830.

[6]BISH E K.A multiple-crane-constrained scheduling problem in a container terminal [J]. European Journal of Operational Research, 2003, 144: 83-107.

[7]NISHIMURA E, IMAI A, PAPADIMITRIOU S.Yard trailer routing at a maritime container terminal [J]. Transportation Research: Part E, 2005, 41(1): 53-76.

[8]康志敏, 吳洪明.港口集裝箱碼頭集卡優(yōu)化調(diào)度研究[J]. 物流工程與管理, 2011, 33(2): 59-61.

[9]CHEN L, LANGEVIN A, LU Z Q.Integrated scheduling of crane handling and truck transportation in a maritime container terminal [J]. European Journal of Operational Research, 2013, 225: 142-152.

[10]LAU H Y K，ZHAO Y.Integrated scheduling of handling equipment at automated container terminals[J]. International Journal of Production Economics, 2008, 12(2): 665-682.

[11]KAVESHGAR N, HUYNH N.Integrated quay crane and yard truck scheduling for unloading inbound containers [J]. International Journal of Production Economics, 2015, 159: 168-177.

[12]張笑, 韓曉龍.集裝箱碼頭岸橋與集卡裝卸協(xié)作優(yōu)化[J]. 水運(yùn)工程, 2013(3): 124-128.

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

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

[15]邢曦文, 毛鈞, 靳志宏, 等.基于混合流水作業(yè)組織的集裝箱碼頭裝卸作業(yè)集成調(diào)度優(yōu)化[J]. 中國(guó)管理科學(xué), 2014, 22(10): 97-105.

(責(zé)任編輯梁健)

收稿日期：2016-03-01；

修訂日期：2016-05-25

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(7130110)；上海市科委工程中心能力提升項(xiàng)目(14DZ2280200)

通訊作者：韓曉龍(1980—)，男，上海市人，上海海事大學(xué)副教授，博士;E-mail:superhxl@163.com。

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

中圖分類(lèi)號(hào)：U169.6; U691.3

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

文章編號(hào)：1001-7445(2016)03-0745-09

Integrated scheduling of quay crane and yard truck in container terminals

YU Meng-qi, HAN Xiao-long

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

Abstract:Quay crane and yard truck are the important resources in container terminals. To improve the handing efficiency of the container terminal, the integrated quay-crane and yard truck scheduling problem is solved by formulating a mixed integer linear programming model to minimize the makespan with real-word operational constraints such as precedence relationships between containers and quay crane safety margin. The improved particle swarm optimization (IPSO) algorithm is used to solve the new model, and a new velocity updating strategy is devised to improve the solution quality via formulating the rules of particles encoding and decoding. The results of the IPSO are compared with the optimal solutions obtained by CPLEX software. The experiment demonstrates that the average gap of 12 cases of IPSO is less 0.582%. Along with the increase of the scale，the time span of the CPLEX solutions differs from 2.92 seconds to 1 hour，but the solving time of IPSO algorithm is controlled in 50 seconds to solve the problem and to obtain optimal solution. Numerical experiments result shows that the proposed model and the improved algorithm can effectively solve such problem.

Key words:quay crane; yard truck; integrated scheduling; particle swarm optimization algorithm

引文格式：余孟齊，韓曉龍.集裝箱碼頭岸橋與集卡集成調(diào)度問(wèn)題研究[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，41(3)：745-753.