集裝箱碼頭的集卡兩階段路徑優化研究

趙金樓，黃金虎，劉 馨

(1.哈爾濱工程大學經濟管理學院，黑龍江 哈爾濱 150001；2.工業和信息化部電子第五研究所，廣東 廣州 510610)

?

集裝箱碼頭的集卡兩階段路徑優化研究

趙金樓1，黃金虎1，劉 馨2

(1.哈爾濱工程大學經濟管理學院，黑龍江 哈爾濱 150001；2.工業和信息化部電子第五研究所，廣東 廣州 510610)

針對目前研究集卡路徑問題的文章多數未考慮到空載對集卡運輸效率的影響，且多在忽略集卡數量的情況下對路徑進行優化，本文考慮集卡數量和空載距離構建了集裝箱碼頭的集卡兩階段路徑優化模型。其中，以集卡行使距離最小為目標構建了第一階段集卡路徑優化模型，解決了不考慮集卡數量時的初步路徑規劃及每條路徑的運輸量問題。基于第一階段結果，引入集卡數量，以集卡任務間空載距離最小為目標構建了第二階段集卡路徑優化模型，通過粒子群算法解決了每輛集卡的路徑任務分配及作業順序的問題。算例結果表明，進行第二階段優化后的集卡空載距離和空載率得到降低。

集裝箱碼頭；集卡；兩階段路徑優化；粒子群算法

1 引言

2016年上半年，全國港口貨物吞吐量和集裝箱吞吐量同比分別增長2.2%和2.5%。隨著集裝箱運輸業務的不斷發展，集裝箱碼頭作為集裝箱貨物的中轉站和裝卸重要場所，其效率和管理水平越來越受到關注。集卡(集裝箱卡車)是實現碼頭作業效率的主要水平機械，其調度水平的高低，直接影響碼頭運營效率[1]，而集卡路徑問題是集卡調度的核心和重要環節。

對于集裝箱碼頭的集卡路徑問題，國外學者多關注于碼頭自動導向車(AGV)和模型求解算法。Grunow等[2]研究了在自動化程度較高的集裝箱港口中多個AGV的運行路徑問題。Bish[3]提出了AGV的動態調度模型以減少船舶在港時間，并采用啟發式算法進行求解。Nishimura[4]通過對比集卡靜態調度與動態調度，構建了集卡動態路徑優化模型，并采用遺傳算法進行模型求解。Amini和Moghaddam[5]在集裝箱交叉堆放的情況下，面對集卡運輸過程中存在擁堵等待的問題構建了多目標線性規劃模型，并結合三種啟發式算法進行求解。Cordeau等[6]以集卡運輸和等待時間之和最小為目標，構建了集卡路徑優化模型，采用局部搜索算法和仿真手段對不同時刻下的集卡運行情況進行了模擬。Kozan等[7]運用啟發式算法研究集裝箱碼頭集卡運輸問題，討論了影響集裝箱碼頭作業效率的因素。Berghman等[8]將碼頭集卡作業劃分為三個階段，以時間最短為目標，參考柔性流水車間問題構建了調度模型，并引入枚舉搜索樹設計了拉格朗日啟發式算法來求解。國內對于集卡路徑優化的研究起步較晚，著重于優化模型的構建和求解。楊靜蕾[9]以集卡行駛距離最小為目標提出了集裝箱碼頭物流路徑優化模型，在不考慮集卡數量以及滿足集裝箱堆存要求情況下獲得集卡最優路徑。呂品和樂美龍[10]在作業面模式下，面向兩船構建了以路徑最短為目標的集卡路徑優化模型，并采用遺傳算法來求解。魏宏磊和朱瑾[11]基于“作業面”優先策略，建立了集卡路徑優化模型，用Lingo軟件得到了最短路徑。計明軍和靳志宏[12]在單船同時裝卸情況下，考慮集卡和岸橋作業時間，以時間最小為優化目標，構建了集卡線路優化模型，并利用改進的進化規劃來求解。曹慶奎[13]建立了面向“作業面”的港口集卡路徑成本優化模型，并設計了遺傳蟻群算法并結合實例對問題求解。曾慶成[14,15]在已知裝卸橋作業序列的情況下，研究了卸船的集卡調度問題，應用Q學習算法來求解，并對碼頭外部的集卡預約進行了優化。邢曦文和毛鈞等[16]借鑒多階段混合流水線調度問題，將卸載過程劃分為三階段，對岸橋、集卡、場橋同時進行調度優化。楊忠振和程健南[17]在出口箱隨機到達碼頭的背景下，基于車船直取的內外集卡聯合裝船模式，構建了裝船序列優化模型，并采用遺傳算法來求解。

目前對集卡路徑問題的研究雖然較多，但國外研究多集中于AGV自動導向車，而我國目前多數碼頭自動化水平尚未達到該標準。國內學者在研究集裝箱碼頭的集卡路徑優化時體現出兩點不足：一是多數模型并未考慮集卡數量，僅做出了初步的路徑規劃，沒有將路徑優化執行方案落實到具體集卡。二是在優化目標方面，目前的研究多以最小化集卡行駛距離或時間為目標函數，少有文章考慮空載對于集卡運輸效率的影響。實際上，空載距離和空載率的降低有利于減少集卡油耗和提高集卡運輸效率。

針對上述兩點，本文在前人研究的基礎上，考慮了集卡數量和空載距離，構建了集卡兩階段路徑優化模型，通過第二階段模型的建立豐富了現有的集卡路徑優化研究。首先，本文不考慮集卡數量，以集卡行駛距離最小為優化目標，構建了第一階段集卡路徑優化模型，來解決初步的集卡運輸路徑問題。然后，基于第一階段的路徑優化結果，引入集卡數量，將每條路徑的一次運輸過程視為一項任務，以集卡任務間空載距離最小為目標，構建了第二階段集卡路徑優化模型，通過粒子群算法對模型進行求解，對集卡進行路徑任務分配以及執行順序的安排。最后，通過算例對模型進行數值計算。

2 問題描述

本文基于作業面模式來進行集卡路徑優化，較多文獻指出該模式能夠有效提高集卡運輸效率，是目前較為常見的作業方式[9-11]。該模式下集卡作業過程如圖1所示，作業路徑如圖2所示。在圖1中，待卸船舶和待裝船舶分別停靠于泊位1和泊位2。進口集裝箱從待卸船舶被卸到集卡上，由集卡運輸至進口箱區進行卸載，然后集卡運行至出口箱區，裝載相應出口集裝箱運輸至待裝船舶。碼頭堆場內存在若干進出口箱區，各個箱區之間以及箱區與泊位之間形成了若干條可行路徑，集卡路徑優化即在這些路徑中選擇最佳路徑，以達到既定目標的要求。圖2反映了一次裝卸作業時的集卡路徑，即：泊位1進口箱區出口箱區泊位2。假設每輛集卡每次只能運送1個40英尺集裝箱(FEU)。要解決集卡的路徑優化問題，即解決在每一次運輸過程中要經過哪些進出口箱區的問題。而集卡每次只能運送一個集裝箱，故沿某路徑的運行次數也就反映了運輸的集裝箱數量。

考慮到裝卸不平衡情況下，待卸集裝箱數量與待裝集裝箱數量不一定相等，除了圖2反映的裝卸作業路徑外，可能存在泊位與箱區之間的單獨裝載或卸載路徑。如果待卸進口箱數量大于待裝出口箱數量，則集卡還需要在待卸船舶與進口箱區之間往返運輸進口箱。反之需要在待裝船舶與出口箱區之間往返運輸出口箱。

圖1 作業面模式下的碼頭集卡作業過程

圖2 一次裝卸作業路徑

本文對集卡的路徑優化分兩個階段展開，第一階段在不考慮集卡數量的情況下對集卡運輸路徑進行初步規劃，即集卡在每一次運輸過程中要經過哪些進出口箱區。在第一階段基礎上，第二階段在已知集卡數量的情況下，將初步得到的路徑規劃結果落實到每輛集卡，對各輛集卡進行路徑任務的分配，并對相應路徑任務的執行順序進行安排。與此對應，本文建立了集卡兩階段路徑優化模型來實現上述過程。

3 集卡兩階段路徑優化模型

3.1 第一階段集卡路徑優化模型

3.1.1 參數與變量

(1)已知參數

H：待卸船舶集裝箱數量；

h：待裝船舶集裝箱數量；

L：進口箱區的集合，共有l個箱區；用i表示進口箱區的序號，i=1,2,…,l；

B：出口箱區的集合，共有m個箱區；用j表示出口箱區的序號，j=1,2,…,m；

do,i：集卡在泊位1與進口箱區i之間的往返行駛距離；

do,j：集卡在泊位2與出口箱區j之間的往返行駛距離；

di,j：集卡沿路徑“泊位1進口箱區i出口箱區j泊位2”的行駛距離；

Qi：第i個進口箱區的容量；

Ej：第j個出口箱區的已堆存集裝箱數量；

(2)決策變量

Xi,j：集卡沿路徑 “泊位1進口箱區i出口箱區j泊位2”的行駛次數；

Yo,i：集卡在泊位1與進口箱區i之間的往返行駛次數；

Zo,j：集卡在泊位2與出口箱區j之間的往返行駛次數；

3.1.2 第一階段集卡路徑優化的數學模型

假設集卡一次只能運輸一個集裝箱(FEU)。基于上述參數與決策變量，以集卡總行駛距離最小為目標，建立集卡路徑優化的數學模型如下：

(1)

(2)

(3)

(4)

(5)

Xi,j≥0,i∈L,j∈B

(6)

Yo,i≥0,i∈L

(7)

Zo,j≥0,j∈B

(8)

其中，目標函數(1)表示集卡完成所有裝卸任務的總行駛距離最短，式中第1項表示裝卸協同作業下集卡沿路徑“泊位1→進口箱區i出口箱區j泊位2”在兩泊位之間的總行駛距離。第2項表示在泊位1與進口箱區之間往返的行駛距離，第3項表示在泊位2與出口箱區之間往返的行駛距離。式(2)保證所有待卸集裝箱都能卸載完畢。式(3)保證所有待裝集裝箱都能裝載完畢。式(4)保證運送到進口箱區的集裝箱總數不超過該進口箱區的容量。式(5)保證出口箱區的已堆存集裝箱都能裝船。式(6)至式(8)表明了決策變量取值范圍。

3.2 第二階段集卡路徑優化模型

3.2.1 參數與變量

(1)已知參數

根據上述集卡路徑優化模型，可得到集卡的行駛路徑以及每條路徑的行駛次數，把它作為已知參數，以集卡沿一條路徑的一次運輸過程作為一項任務，具體參數如下：

I：任務集合，共有p項任務；用s/r表示任務的序號，s,r=1,2,…,p；

N：集裝箱卡車的集合，共有n輛集卡；用k表示集卡的序號，k=1,2,…,n；

cs,r：任務s與r之間的空載距離，與路徑“泊位1進口箱區i出口箱區j泊位2”對應的任務，空載距離為兩泊位間的距離。對于單獨裝載或者卸載任務，空載距離即為泊位與箱區的距離；

(2)決策變量

3.2.2 第二階段集卡路徑優化的數學模型

基于上述參數與決策變量，以集卡任務間空載距離最小為目標，建立集卡路徑任務分配的數學模型如下：

(9)

(10)

(11)

(12)

Ws,r,k∈{0,1},s∈I,r∈I,k∈N

(13)

Gk,s∈{0,1},s∈I,k∈N

(14)

Gk,r∈{0,1},r∈I,k∈N

(15)

其中，目標函數(9)表示所有集卡執行完任務的空載距離最短。式(10)表示每個任務有且僅有1輛集卡執行；式(11)、(12)給出了決策變量間的關系。式(13)至式(15)表明了決策變量的取值，是0-1變量。

4 模型求解

根據模型的特點，對于第一階段集卡路徑優化模型，將采用Lingo軟件直接求解。對于第二階段集卡路徑優化模型，本文將使用帶慣性權重的粒子群算法來進行求解。集卡路徑問題屬于車輛路徑問題(Vehicle Routing Problem，簡稱VRP)的一種，Salman為VRP問題提出了一種較好的編碼方法，第二階段采用Salman的編碼思想來進行算法設計[18]。算法實現過程如下[19]：

步驟1：初始化粒子群。

(1)基于編碼將粒子群分成若干兩兩相互重疊的子群。具體設置兩個位置向量Xv和Xr，分別表示執行每項任務的集卡以及該任務在集卡中的執行順序。對應設置兩個速度向量Vv和Vr。

(2)每個粒子位置向量Xv的每一維隨機取1至n(車輛數)之間的整數，Xr的每一維隨機取1至p(任務數)之間的實數。

(3)每個速度向量Vv的每一維取-(n-1)至(n-1)之間的整數，Vr的每一維取-(p-1)至(p-1)之間的實數。

(4)對于相同的Xv，將得到的Xr按從小到大的順序分別賦予整數值，以代表作業順序。

根據步驟(1)至(4)，編碼操作過程見表1。表中第一行表示全部任務，第二行表示各任務對應的執行集卡，在該示意表格中任務1由集卡1執行，任務2、3、4、5由集卡2執行，任務6由集卡3執行。第三行的數字反映同一集卡的作業先后順序，以集卡2為例，根據所執行任務對應的Xr大小順序，分別給第二輛集卡的序列賦值3、4、1、2，表示任務2排在集卡2作業序列的第3位執行，任務3排在第4位，任務4排在第1位，任務5排在第2位。

表1 編碼過程示意

(5)評價每個粒子適應度，即所有集卡的空載距離之和。

(6)將初始位置作為個體歷史最優解，尋找各子群內的最優解Pl和總群體的最優解Pg。

步驟2：設置迭代終止條件。

步驟3：重復以下步驟，直到滿足終止條件。

(1)對每一個粒子，按位置和速度公式進行更新，超過邊界范圍時按邊界取值。

(2)用適應度函數(目標函數)評價所有粒子。

(3)若某個粒子的當前適應度優于歷史最優適應度，則記當前適應度為歷史最優適應度。同時記下此時的粒子位置為該粒子的歷史最優位置。

(4)尋找當前各粒子群內的最優解和總群體最優解，若優于歷史最優解則更新Pl和Pg。

5 算例

5.1 第一階段集卡路徑優化模型求解

碼頭堆場有5個進口箱區和5個出口箱區用于堆放集裝箱。堆場箱區間的距離、箱區至泊位的距離、泊位之間的距離見表2，各進口箱容量見表3，出口箱堆放的待裝集裝箱數量見表4。待卸集裝箱數量為500，待裝集裝箱數量為450。涉及到集裝箱容量或數量均按40英尺集裝箱(FEU)算，涉及到距離的均以米為單位。使用Lingo軟件對第一階段集卡路徑優化模型進行求解，結果見表5，集卡行駛距離為2300000米。

表2 堆場箱區間的距離

表3 進口箱區容量

表4 出口箱區堆存量

表5 集卡運輸路徑及裝卸箱量

5.2 第二階段集卡路徑優化模型求解

基于第一階段路徑優化模型的求解結果，將一條路徑的一次運輸過程作為一項任務，則共有500項任務，從路徑1的任務開始依次編號。實際上，后450個任務具有相同的起點和終點，任務間空載距離相同，執行順序并不影響目標函數值。故只要確定前50項任務的集卡配置，余下的任務由任何集卡在剩下的序列位置執行即可。假設集卡數量為10。粒子群算法中，迭代次數設為100，種群規模設為80，學習因子均設為1.4，初始慣性權重值設為0.95，最終慣性權重值設為0.1。采用粒子群算法計算10次，取最優結果見表6和表7。表6列出了前50項任務的執行集卡序號以及在該集卡作業序列中的執行順序。以任務1為例，它由第5輛集卡執行，排在第5輛集卡作業序列的第10位。表7列出了各集卡的執行任務的數量。前50項任務按表6的規劃執行，其余450項任務根據表6和表7在剩下的序列位置中執行即可。優化后總空載距離為420200米。

表6 前50項任務的集卡配置

表7 各集卡執行任務數量

5.3 結果分析

基于第一階段集卡路徑優化模型的求解結果可知，集卡總行駛路徑為2300000米。在未經第二階段路徑優化之前，按各個路徑依次執行的方式，計算空載距離為430000米。空載率為18.70%。進行第二階段集卡路徑優化之后，根據上述結果空載距離為420200米，空載率為18.35%，空載率得到降低。

對于不同集卡數量，基于第二階段優化模型，空載率情況見圖3。可見集卡數量的增加有利于降低空載率，但在實際決策過程中需要考慮集卡數量增加帶來的成本。

圖3 集卡數量對空載率的影響

6 結語

針對傳統文獻僅對集卡路徑做了初步優化而未考慮集卡數量和作業順序的問題，本文從兩個階段對集裝箱碼頭的集卡路徑優化問題展開了研究。第一階段研究了集卡路徑初步規劃問題，考慮到集卡行使距離影響運輸時間從而影響整個碼頭的作業效率，第一階段以集卡總行駛距離最小為目標函數，建立了集卡路徑優化模型，得到了各條路徑以及每條路徑運輸的集裝箱數量。在上述基礎上，將第一階段模型求解結果作為已知輸入，把每條路徑的一次運輸過程當成一項任務。同時考慮到集卡的空載距離影響集卡單位運輸成本與運輸效率，以集卡任務間空載距離最小為目標，建立了第二階段集卡路徑優化模型。并采用粒子群算法進行求解，得到了每輛集卡的行走路徑以及作業順序。結果顯示，經過第二階段集卡路徑優化之后集卡空載率得到降低，并且集卡數量的增加有利于降低空載率。

[1] 計明軍,劉豐碩,李郭記,等. 基于裝卸協同作業的集裝箱碼頭集卡調度及配置優化[J]. 大連海事大學學報,2010,36(1):47-50.

[2] Grunow M, Günther H O, Lehmann M. Dispatching multi-load AGVs in highly automated seaport container terminals[M]. Berlin Heidelberg： Springer, 2005.

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

[4] Nishimura E.Yard trailer routing at a maritime container terminal[J].Transportation Research Part E,2005,41(1):53-76.

[5] Amini A, Tavakkoli-Moghaddam R. A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks[J]. Computers & Industrial Engineering, 2016, 96:180-191.

[6] Cordeau J F, Legato P, Mazza R M, et al. Simulation-based optimization for housekeeping in a container transshipment terminal[J]. Computers & Operations Research, 2015, 53: 81-95.

[7] Kozan E. Optimising container transfers at multimodal terminals[J]. Mathematical and Computer Modelling, 2000, 31(10): 235-243.

[8] Berghman L, Leus R. A Lagrangian heuristic for a dock assignment problem with trailer transportation[C]//Proceedings of 2010 IEEE International Conference on, Industrial Engineering and Engineering Management, (IEEM), 2010.

[9] 楊靜蕾. 集裝箱碼頭物流路徑優化研究[J]. 水運工程,2006,(1):32-35.

[10] 呂品,樂美龍. 基于作業面的集裝箱港口集卡路徑及成本優化[J]. 青島科技大學學報(自然科學版),2015,36(3):327- 332.

[11] 魏宏磊,朱瑾. 基于“作業面”優先策略的集裝箱港口集卡路徑優化研究[J]. 中國水運(下半月), 2012,12(1):70-72.

[12] 計明軍, 靳志宏. 集裝箱碼頭集卡與岸橋協調調度優化[J]. 復旦學報: 自然科學版, 2008,46(4):60-64+72.

[13] 曹慶奎, 趙斐. 基于遺傳蟻群算法的港口集卡路徑優化[J]. 系統工程理論與實踐, 2013, 33(7): 1820-1828.

[14] 曾慶成, 楊忠振. 集裝箱碼頭集卡調度模型與 Q 學習算法[J]. 哈爾濱工程大學學報, 2008, 29(1): 1-4.

[15] 曾慶成, 陳文浩, 胡祥培. 集裝箱碼頭外部集卡預約優化模型與算法[J]. 中國管理科學, 2015, 23(10): 125-130.

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

[17] 楊忠振, 程健南. 基于出口箱隨機到達碼頭的車船直取裝船作業優化[J]. 大連海事大學學報, 2016, 42(4):97-104.

[18] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem[J]. Microprocessors and Microsystems, 2002, 26(8): 363-371.

[19] 紀震, 廖惠連, 吳青華. 粒子群算法及其應用[M]. 北京：科學出版社, 2009.

Two-stage Optimization for Yard Trailers Routing In Container Terminals

ZHAO Jin-lou1, HUANG Jin-hu1, LIU Xin2

(1. School of Management and Economics, Harbin Engineering University, Harbin 150001, China；2.CEPREI, Guangzhou 510610, China)

With the continuous development of container transportation business, the efficiency and management level of container terminal is more and more important. At the same time, the problem of yard trailers routing receives more attention because yard trailers work as the main machine to carry containers in the horizontal direction at terminals. However, most current research on yard trailers routing problem did not consider the influence of no-load distance on trailers’ transport efficiency, and a large part of current research just made routing optimization for singer yard trailers ignoring the condition of different trailers. Under the above background, a two-stage routing optimization model which consisting of two relevant models for yard trailers is proposed to solve the routing problem based on pool strategy. This strategy means loading and unloading operations are performed during one work route instead of doing loading and unloading operations separately. On the first stage, a routing optimization model is given to minimize the route distance without considering the number of yard trailers. This model is used to determine which import and export blocks to go through. On the second stage, for the purpose of minimizing no-load distance, the other routing optimization model which considers the number of trailers is constructed based on the result of the first model. According to the characteristics of two models, the software of Lingo is used to solve the first model, and particle swarm optimization method is utilized to solve the second model which involves route assignment and job order for every trailer. The results show that the no-load distance and no-load rate are decreased after the optimization on the second stage. In addition, with the second stage model, it is found that increasing the number of trailers is helpful to reduce the no-load rate. By proposing the two-stage routing optimization model, both the no-load distance and the number of yard trailers are taken into account and improves the existing research.

container terminals; yard trailers; two-stage routing optimization; particle swarm optimization

2015-06-03；

2016-05-26

工信部高技術船舶科研項目；中央高校基本科研業務費專項資金重點項目(HEUCFD1505)；國家自然科學基金面上項目(71271062)

劉馨(1992-)，女(漢族)，湖南衡陽人，工業和信息化部電子第五研究所標準與信息研究中心，助理工程師，研究方向：產業分析、優化理論與方法，E-mail: liuxin421001@163. com.

1003-207(2017)04-0152-06

10.16381/j.cnki.issn1003-207x.2017.04.018

U691；C931

A