余孟齊，韓曉龍

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

?

集裝箱碼頭岸橋與集卡集成調度問題研究

余孟齊，韓曉龍

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

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

關鍵詞：岸橋;集卡;集成調度;粒子群算法

0引言

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

圖1集裝箱碼頭典型布局

Fig.1Typical layout of a container terminal

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

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

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

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

1問題描述

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

圖2岸橋與集卡單獨調度

Fig.2Schedule quay cranes and yard trucks separately

圖3岸橋與集卡集成調度

Fig.3Schedule quay cranes and yard trucks jointly

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

2模型的建立

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

目標函數(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基于粒子群算法的岸橋-集卡集成調度問題求解

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

(32)

(33)

3.1解的表示

本文的調度問題必須決定岸橋和集卡的分配以及集裝箱被岸橋和集卡裝卸的順序。因為這個問題有由岸橋卸載作業(yè)和集卡運輸作業(yè)兩個階段，對每臺岸橋的分配和集裝箱順序編碼，然后根據(jù)岸橋的調度順序將集卡分配給集裝箱。

表1　粒子編碼

表2　粒子解碼

3.2速度更新策略

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

(34)

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

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

圖4　粒子群算法步驟

4數(shù)值實驗與結果分析

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

4.1試驗設計

問題的實驗數(shù)據(jù)產生如下：

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

②進口(出口)箱的原始(目標位置)考慮船舶布局隨機生成，進口(出口)箱的目標(原始)位置基于集裝箱碼頭的實際布局產生。

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

所有實驗都是在4 GB內存和2.80 GHz處理器的計算機上進行的。該算法是用Matlab編寫，并且所述模型使用CPLEX解決。

4.2試驗結果分析與評價

為測試IPSO算法的性能，本文設計12組算例(如表3所示)，其中目標值顯示是 CPLEX 和IPSO算法的計算結果。設置CPLEX 最大運行時間為60 min，即如果運算60 min 也無法取得最優(yōu)解，就停止運算。

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

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

表3　CPLEX與改進的粒子群算法(IPSO)對比結果

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

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

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

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

4.3討論

通過對12個算例實驗的分析，可以看出提出的IPSO算法在得到問題解的質量和計算時間上都優(yōu)于軟件CPLEX，這表明IPSO算法對岸橋和集卡集成調度問題是有效的。

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

5結論

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

參考文獻:

[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]董良才, 丁以中, 宓為建.基于時間窗的集裝箱裝卸橋調度[J]. 上海海事大學學報, 2011, 32(1): 1-7.

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

[5]尚晶,陶德馨.集裝箱碼頭集卡調度策略的仿真研究[J]. 武漢理工大學學報: 交通科學與工程版, 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)化調度研究[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]. 水運工程, 2013(3): 124-128.

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

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

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

(責任編輯梁健)

收稿日期：2016-03-01；

修訂日期：2016-05-25

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

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

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

中圖分類號：U169.6; U691.3

文獻標識碼：A

文章編號：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

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