集裝箱碼頭的集卡兩階段路徑優(yōu)化研究

趙金樓，黃金虎，劉 馨

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

?

集裝箱碼頭的集卡兩階段路徑優(yōu)化研究

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

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

針對(duì)目前研究集卡路徑問題的文章多數(shù)未考慮到空載對(duì)集卡運(yùn)輸效率的影響，且多在忽略集卡數(shù)量的情況下對(duì)路徑進(jìn)行優(yōu)化，本文考慮集卡數(shù)量和空載距離構(gòu)建了集裝箱碼頭的集卡兩階段路徑優(yōu)化模型。其中，以集卡行使距離最小為目標(biāo)構(gòu)建了第一階段集卡路徑優(yōu)化模型，解決了不考慮集卡數(shù)量時(shí)的初步路徑規(guī)劃及每條路徑的運(yùn)輸量問題?；诘谝浑A段結(jié)果，引入集卡數(shù)量，以集卡任務(wù)間空載距離最小為目標(biāo)構(gòu)建了第二階段集卡路徑優(yōu)化模型，通過粒子群算法解決了每輛集卡的路徑任務(wù)分配及作業(yè)順序的問題。算例結(jié)果表明，進(jìn)行第二階段優(yōu)化后的集卡空載距離和空載率得到降低。

集裝箱碼頭；集卡；兩階段路徑優(yōu)化；粒子群算法

1 引言

2016年上半年，全國(guó)港口貨物吞吐量和集裝箱吞吐量同比分別增長(zhǎng)2.2%和2.5%。隨著集裝箱運(yùn)輸業(yè)務(wù)的不斷發(fā)展，集裝箱碼頭作為集裝箱貨物的中轉(zhuǎn)站和裝卸重要場(chǎng)所，其效率和管理水平越來越受到關(guān)注。集卡(集裝箱卡車)是實(shí)現(xiàn)碼頭作業(yè)效率的主要水平機(jī)械，其調(diào)度水平的高低，直接影響碼頭運(yùn)營(yíng)效率[1]，而集卡路徑問題是集卡調(diào)度的核心和重要環(huán)節(jié)。

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

目前對(duì)集卡路徑問題的研究雖然較多，但國(guó)外研究多集中于AGV自動(dòng)導(dǎo)向車，而我國(guó)目前多數(shù)碼頭自動(dòng)化水平尚未達(dá)到該標(biāo)準(zhǔn)。國(guó)內(nèi)學(xué)者在研究集裝箱碼頭的集卡路徑優(yōu)化時(shí)體現(xiàn)出兩點(diǎn)不足：一是多數(shù)模型并未考慮集卡數(shù)量，僅做出了初步的路徑規(guī)劃，沒有將路徑優(yōu)化執(zhí)行方案落實(shí)到具體集卡。二是在優(yōu)化目標(biāo)方面，目前的研究多以最小化集卡行駛距離或時(shí)間為目標(biāo)函數(shù)，少有文章考慮空載對(duì)于集卡運(yùn)輸效率的影響。實(shí)際上，空載距離和空載率的降低有利于減少集卡油耗和提高集卡運(yùn)輸效率。

針對(duì)上述兩點(diǎn)，本文在前人研究的基礎(chǔ)上，考慮了集卡數(shù)量和空載距離，構(gòu)建了集卡兩階段路徑優(yōu)化模型，通過第二階段模型的建立豐富了現(xiàn)有的集卡路徑優(yōu)化研究。首先，本文不考慮集卡數(shù)量，以集卡行駛距離最小為優(yōu)化目標(biāo)，構(gòu)建了第一階段集卡路徑優(yōu)化模型，來解決初步的集卡運(yùn)輸路徑問題。然后，基于第一階段的路徑優(yōu)化結(jié)果，引入集卡數(shù)量，將每條路徑的一次運(yùn)輸過程視為一項(xiàng)任務(wù)，以集卡任務(wù)間空載距離最小為目標(biāo)，構(gòu)建了第二階段集卡路徑優(yōu)化模型，通過粒子群算法對(duì)模型進(jìn)行求解，對(duì)集卡進(jìn)行路徑任務(wù)分配以及執(zhí)行順序的安排。最后，通過算例對(duì)模型進(jìn)行數(shù)值計(jì)算。

2 問題描述

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

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

圖1 作業(yè)面模式下的碼頭集卡作業(yè)過程

圖2 一次裝卸作業(yè)路徑

本文對(duì)集卡的路徑優(yōu)化分兩個(gè)階段展開，第一階段在不考慮集卡數(shù)量的情況下對(duì)集卡運(yùn)輸路徑進(jìn)行初步規(guī)劃，即集卡在每一次運(yùn)輸過程中要經(jīng)過哪些進(jìn)出口箱區(qū)。在第一階段基礎(chǔ)上，第二階段在已知集卡數(shù)量的情況下，將初步得到的路徑規(guī)劃結(jié)果落實(shí)到每輛集卡，對(duì)各輛集卡進(jìn)行路徑任務(wù)的分配，并對(duì)相應(yīng)路徑任務(wù)的執(zhí)行順序進(jìn)行安排。與此對(duì)應(yīng)，本文建立了集卡兩階段路徑優(yōu)化模型來實(shí)現(xiàn)上述過程。

3 集卡兩階段路徑優(yōu)化模型

3.1 第一階段集卡路徑優(yōu)化模型

3.1.1 參數(shù)與變量

(1)已知參數(shù)

H：待卸船舶集裝箱數(shù)量；

h：待裝船舶集裝箱數(shù)量；

L：進(jìn)口箱區(qū)的集合，共有l(wèi)個(gè)箱區(qū)；用i表示進(jìn)口箱區(qū)的序號(hào)，i=1,2,…,l；

B：出口箱區(qū)的集合，共有m個(gè)箱區(qū)；用j表示出口箱區(qū)的序號(hào)，j=1,2,…,m；

do,i：集卡在泊位1與進(jìn)口箱區(qū)i之間的往返行駛距離；

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

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

Qi：第i個(gè)進(jìn)口箱區(qū)的容量；

Ej：第j個(gè)出口箱區(qū)的已堆存集裝箱數(shù)量；

(2)決策變量

Xi,j：集卡沿路徑 “泊位1進(jìn)口箱區(qū)i出口箱區(qū)j泊位2”的行駛次數(shù)；

Yo,i：集卡在泊位1與進(jìn)口箱區(qū)i之間的往返行駛次數(shù)；

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

3.1.2 第一階段集卡路徑優(yōu)化的數(shù)學(xué)模型

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

(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)

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

3.2 第二階段集卡路徑優(yōu)化模型

3.2.1 參數(shù)與變量

(1)已知參數(shù)

根據(jù)上述集卡路徑優(yōu)化模型，可得到集卡的行駛路徑以及每條路徑的行駛次數(shù)，把它作為已知參數(shù)，以集卡沿一條路徑的一次運(yùn)輸過程作為一項(xiàng)任務(wù)，具體參數(shù)如下：

I：任務(wù)集合，共有p項(xiàng)任務(wù)；用s/r表示任務(wù)的序號(hào)，s,r=1,2,…,p；

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

cs,r：任務(wù)s與r之間的空載距離，與路徑“泊位1進(jìn)口箱區(qū)i出口箱區(qū)j泊位2”對(duì)應(yīng)的任務(wù)，空載距離為兩泊位間的距離。對(duì)于單獨(dú)裝載或者卸載任務(wù)，空載距離即為泊位與箱區(qū)的距離；

(2)決策變量

3.2.2 第二階段集卡路徑優(yōu)化的數(shù)學(xué)模型

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

(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)

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

4 模型求解

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

步驟1：初始化粒子群。

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

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

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

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

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

表1 編碼過程示意

(5)評(píng)價(jià)每個(gè)粒子適應(yīng)度，即所有集卡的空載距離之和。

(6)將初始位置作為個(gè)體歷史最優(yōu)解，尋找各子群內(nèi)的最優(yōu)解Pl和總?cè)后w的最優(yōu)解Pg。

步驟2：設(shè)置迭代終止條件。

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

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

(2)用適應(yīng)度函數(shù)(目標(biāo)函數(shù))評(píng)價(jià)所有粒子。

(3)若某個(gè)粒子的當(dāng)前適應(yīng)度優(yōu)于歷史最優(yōu)適應(yīng)度，則記當(dāng)前適應(yīng)度為歷史最優(yōu)適應(yīng)度。同時(shí)記下此時(shí)的粒子位置為該粒子的歷史最優(yōu)位置。

(4)尋找當(dāng)前各粒子群內(nèi)的最優(yōu)解和總?cè)后w最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新Pl和Pg。

5 算例

5.1 第一階段集卡路徑優(yōu)化模型求解

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

表2 堆場(chǎng)箱區(qū)間的距離

表3 進(jìn)口箱區(qū)容量

表4 出口箱區(qū)堆存量

表5 集卡運(yùn)輸路徑及裝卸箱量

5.2 第二階段集卡路徑優(yōu)化模型求解

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

表6 前50項(xiàng)任務(wù)的集卡配置

表7 各集卡執(zhí)行任務(wù)數(shù)量

5.3 結(jié)果分析

基于第一階段集卡路徑優(yōu)化模型的求解結(jié)果可知，集卡總行駛路徑為2300000米。在未經(jīng)第二階段路徑優(yōu)化之前，按各個(gè)路徑依次執(zhí)行的方式，計(jì)算空載距離為430000米?？蛰d率為18.70%。進(jìn)行第二階段集卡路徑優(yōu)化之后，根據(jù)上述結(jié)果空載距離為420200米，空載率為18.35%，空載率得到降低。

對(duì)于不同集卡數(shù)量，基于第二階段優(yōu)化模型，空載率情況見圖3?？梢娂〝?shù)量的增加有利于降低空載率，但在實(shí)際決策過程中需要考慮集卡數(shù)量增加帶來的成本。

圖3 集卡數(shù)量對(duì)空載率的影響

6 結(jié)語

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

[1] 計(jì)明軍,劉豐碩,李郭記,等. 基于裝卸協(xié)同作業(yè)的集裝箱碼頭集卡調(diào)度及配置優(yōu)化[J]. 大連海事大學(xué)學(xué)報(bào),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] 楊靜蕾. 集裝箱碼頭物流路徑優(yōu)化研究[J]. 水運(yùn)工程,2006,(1):32-35.

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

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

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

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

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

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

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

[17] 楊忠振, 程健南. 基于出口箱隨機(jī)到達(dá)碼頭的車船直取裝船作業(yè)優(yōu)化[J]. 大連海事大學(xué)學(xué)報(bào), 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] 紀(jì)震, 廖惠連, 吳青華. 粒子群算法及其應(yīng)用[M]. 北京：科學(xué)出版社, 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

工信部高技術(shù)船舶科研項(xiàng)目；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金重點(diǎn)項(xiàng)目(HEUCFD1505)；國(guó)家自然科學(xué)基金面上項(xiàng)目(71271062)

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

1003-207(2017)04-0152-06

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

U691；C931

A