丁 一， 何樂媚， 沙 梅

(上海海事大學 a.物流研究中心;b.交通運輸學院， 上海 201306)

集裝箱運輸在全球貿(mào)易中扮演著重要角色，各大集裝箱港口都在致力于通過擴大碼頭規(guī)模和增加碼頭數(shù)量滿足日益增長的集裝箱運輸需求。由于中轉(zhuǎn)箱碼頭之間拖運等原因，集裝箱在大、中型港口的碼頭之間運輸是不可避免的。OTTJES等[1]用ITT(Inter-Terminal Transportation)表示多碼頭間運輸，這不僅是港口營運人和碼頭運營公司需處理的一個運營問題，而且是新建碼頭和集裝箱港口規(guī)劃中需考慮的一個戰(zhàn)略問題。[3]水水中轉(zhuǎn)和駁船作業(yè)是上海洋山港重要的作業(yè)類型，洋山港水水中轉(zhuǎn)比例超過70%，其中絕大部分通過駁船進行。為保證該項業(yè)務(wù)的業(yè)務(wù)量持續(xù)增長，洋山港5期計劃建設(shè)為全駁船集裝箱碼頭，同時設(shè)立為 “駁船碼頭中心”，即所有港口進口和出口駁船不再停靠該碼頭以外的其他碼頭。洋山港碼頭分布圖見圖1。

圖1 洋山港碼頭分布圖

國內(nèi)外學者已針對多碼頭間運輸優(yōu)化開展許多研究。HEILIG等[2]提出關(guān)于ITT問題的文獻可分為優(yōu)化算法[3-6]、仿真研究[9-11]和信息系統(tǒng)方法等3類。[12-13]現(xiàn)有研究主要集中在鹿特丹港馬斯萊可迪地區(qū)，為進一步評估所提出方法的有效性，需考慮不同港區(qū)的實證研究?；诖?，本文建立新的整數(shù)規(guī)劃模型以驗證洋山港新建碼頭的ITT成本優(yōu)化結(jié)果。當前已有幾種優(yōu)化模型可用于研究ITT問題。TIERNEY等[3]利用時空圖提出ITT完整定義的數(shù)學模型，考慮集裝箱長期裝卸節(jié)點，求解車流與多商品流的最優(yōu)組合問題，該研究只考慮最小化因交付集裝箱超過截止日期而產(chǎn)生的罰款，缺乏對運輸中其他成本的考慮。NIEUWKOOP等[4]提出一種具有時空拓展圖的確定性最小費用流模型，通過尋找最優(yōu)的車輛配置，最大程度地減少延遲成本。該研究未考慮通過采取最優(yōu)的ITT交付、車輛裝載和發(fā)車計劃降低總運營成本和延誤成本。HU等[5]提出一種禁忌搜索算法，用于解決港口碼頭到鐵路終端的ITT問題，建立ITT與鐵路運輸相結(jié)合的數(shù)學優(yōu)化模型。該研究未考慮運輸車輛的額外成本與延遲成本之間的均衡問題。在集裝箱卡車運輸研究方面，李順勇等[7]建立多通路網(wǎng)絡(luò)下的多車型低碳城市配送混合整數(shù)規(guī)劃模型，根據(jù)問題特征提出一組加速模型求解的有效不等式。

分析現(xiàn)有研究可知:高效的ITT網(wǎng)絡(luò)的主要目標是最小化運輸延遲成本,同時，縮短運輸時間和處理時間、減少空車和費用、提高占用率、避免交通堵塞[2]和減少碳排放[8]等。ITT問題研究的關(guān)鍵是在港口的不同碼頭之間實現(xiàn)高效、安全和可靠的運輸。[4]現(xiàn)有文獻缺乏對ITT問題中多種新型運輸設(shè)備效率和成本的比較，以及通過對ITT問題進行研究，輔助港口對新建碼頭道路布局做出決策。本文研究的目標是為ITT系統(tǒng)構(gòu)建可靠的數(shù)學模型，并通過定量分析估計使用特定ITT運輸設(shè)備、新基礎(chǔ)設(shè)施和交通規(guī)劃的成本,幫助港口營運人正確選擇碼頭的道路布局和碼頭之間的運輸連接，以及車輛的類型和數(shù)量，保證港口具有高效的物流運輸，提高港口ITT作業(yè)效率，降低相關(guān)成本。

1 問題描述

ITT是指集裝箱在港口內(nèi)各碼頭(海運、鐵路或其他)之間的移動。本文研究的ITT問題與車輛路徑問題(Vehicle Routing Problem,VRP)非常相似，都與給定網(wǎng)絡(luò)上具有給定釋放和交付時間的裝運集裝箱有關(guān)。與典型的碼頭內(nèi)運輸(即在有限的距離內(nèi)將集裝箱從起重機移動到堆垛機)相比，ITT擁有專用的封閉路線運輸網(wǎng)絡(luò)，且不與其他模式或系統(tǒng)交互。為在港口不同的碼頭之間實現(xiàn)高效、安全和可靠的集裝箱運輸，并確定與ITT系統(tǒng)不同需求水平相匹配的最佳車輛配置，本文提出一種基于時空拓展圖的確定性最小成本流整數(shù)規(guī)劃模型，并將目標函數(shù)擴展到考慮整車需求和整個系統(tǒng)的性能水平。

實現(xiàn)集裝箱ITT作業(yè)的運輸設(shè)備有自動引導車(Automated Guided Vehicles，AGV)、自動舉升車輛(Automated Lift Vehicles，ALV)和多掛車系統(tǒng)(Multi Trailer System，MTS)。DUINKERKEN等[9]對這幾種運輸設(shè)備的性能進行對比，并通過仿真模型對其實際運行效率進行分析。ITT研究需確定合理的運輸設(shè)備和設(shè)備的數(shù)量，以提高港口車輛資源配置效率；生態(tài)目標是進一步減少通過ITT產(chǎn)生的CO2排放。近年來,國內(nèi)外很多港口都在推進無人駕駛電動集卡在港口運輸作業(yè)中的應(yīng)用，本文考慮多種ITT運輸設(shè)備，如AGV、ALV、MTS和無人駕駛電動集卡，并對多種運輸設(shè)備的運輸效率和成本進行比較分析。

時空拓展圖[4]是能通過ITT系統(tǒng)在時間和空間上對集裝箱流進行建模的圖，可詳細描述集裝箱隨時間的移動過程。因此，引入一個基于時空拓展圖的優(yōu)化模型確定ITT網(wǎng)絡(luò)中車輛和集裝箱的最優(yōu)流動。首先建立一個基本圖V(N,A)，其中:N為基本圖節(jié)點集合，N={1,2,…,n+m}，n為碼頭節(jié)點數(shù)，m為交叉路口節(jié)點數(shù)；A為連接基本圖弧線(i,j)的集合。通過對時間進行擴展，即通過復制基礎(chǔ)圖，每次復制1個時間步長λ，提出時空擴展圖TLD(NT,AT)，其中:NT為時空擴展圖的節(jié)點集合，NT={1,2,…,τλ(n+m)}，τ為時間段的數(shù)量，λ為時間步長；AT為時空擴展圖弧線的集合;Nint為交叉路口節(jié)點的集合，Nint={1,2,…,m}。車輛在時間周期范圍內(nèi)開展集裝箱運輸活動，時間t=1,2,…,τλ，其中:τλ為時間周期的長度。通過該時空拓展圖ITT系統(tǒng)，可在時間和空間上對集裝箱流進行建模，并通過時間拓展和空間描述，更好地解釋基于ITT網(wǎng)絡(luò)的各碼頭之間集裝箱轉(zhuǎn)運的過程。

時空拓展圖見圖2。圖2中：左邊部分為基本圖，包含3個港口碼頭節(jié)點和1個交叉口路口節(jié)點;右邊部分為時空拓展圖。設(shè)時間步長為10 min，假設(shè)2個轉(zhuǎn)運任務(wù)，其中：任務(wù)1為將集裝箱從碼頭1運輸?shù)酱a頭5;任務(wù)2為將集裝箱從碼頭3運輸?shù)酱a頭1。假設(shè)執(zhí)行這2個任務(wù)的運輸設(shè)備為同一輛AGV，任務(wù)釋放時間均為t=0，交貨時間為t=40 min。執(zhí)行任務(wù)的運輸車輛在t=0時接到任務(wù)后，分別在碼頭1和碼頭3的堆場裝載集裝箱運往目標碼頭, 到達目標碼頭之后在碼頭堆場卸下集裝箱。圖2中，帶箭頭的實線表示運輸任務(wù)1的車輛行駛路線；帶箭頭的虛線表示運輸任務(wù)2的車輛行駛路線。運輸任務(wù)1在規(guī)定交貨時間內(nèi)完成運輸任務(wù)，而運輸任務(wù)2由于交叉路口擁堵，導致延遲5 min完成運輸任務(wù)，因此運輸任務(wù)2將產(chǎn)生延遲成本。

圖2 時空拓展圖

2 模型構(gòu)建

2.1 數(shù)學模型構(gòu)造

文獻[3]提出的數(shù)學模型用于盡量避免集裝箱交貨延誤，該模型考慮4個碼頭節(jié)點和2個交叉口，規(guī)劃時間為8 h，時間步長為5 min。本文基于時空拓展圖提出一個新的整數(shù)規(guī)劃模型，用以優(yōu)化ITT問題。與文獻[3]提出的模型相比，該模型能包含ITT網(wǎng)絡(luò)所需的車輛數(shù)量和運輸需求,對堆場中集裝箱裝卸[14]、實載行程、空車行程、處理時間和道路擁堵進行建模。同時,該模型考慮集裝箱延誤懲罰成本、運輸車輛啟用成本、運輸車輛司機工資成本、車輛運輸和裝卸成本。

最小化運輸車輛由于集裝箱運輸延遲而造成的懲罰成本，表達式為

(1)

使車輛啟用總成本之和最小的目標函數(shù)為

(2)

式(2)中:Tsθ為滿足運輸需求θ的集裝箱釋放時間，為λ的整數(shù)倍；bh為h型車輛每次運輸啟用費用；Ch為h型車輛的承載集裝箱能力，Ch∈{1,5}。

使車輛支付的司機工資成本之和最小的目標函數(shù)為

(3)

使運送集裝箱所花費的車輛運輸成本之和最小的目標函數(shù)為

(4)

為保證在運輸需求的起始點、中間流轉(zhuǎn)位置和終點流動的集裝箱流平衡設(shè)置約束條件為

(5)

Tsθ≤t≤τλ;k∈NθD;θ∈Θ;h∈H

(6)

(7)

式(5)～式(7)中:Oθ為運輸需求θ的起始點；?θ為運輸需求θ需要運輸?shù)募b箱數(shù)量;NθD為不與需求θ起點和終點匹配的其他節(jié)點集合，NθD={i∈NT|i/τ≠Oθ∧i/τ≠dθ}；H為所有車輛類型的集合，H={1,2,…,h}。

限制運輸線路啟用的運輸車輛數(shù)要小于等于該線路持有車輛總數(shù)上限，有

Tsθ≤t≤τλ;h∈H

(8)

為防止集裝箱被存儲在交叉路口節(jié)點，有

Tsθ≤t≤τλ;(i,j)∈Asta;h∈H

(9)

式(9)中:Asta為靜止弧的弧線集合，靜止弧上的車輛和集裝箱不會在空間中移動，在給定的時間周期內(nèi)停留在同一節(jié)點。

為限制規(guī)定時間步長內(nèi)在交叉路口節(jié)點的持有車輛總數(shù)上限，防止交叉口車輛擁堵有

r∈Nint;Tsθ≤t≤τλ;h∈H

(10)

式(10)中:Γint為交叉路口節(jié)點的最大車輛吞吐量。

為保證在堆場裝卸節(jié)點內(nèi)的集裝箱流平衡,有

(11)

為將裝卸節(jié)點與運輸需求起始碼頭節(jié)點相連接，即在堆場上將集裝箱通過堆場裝卸設(shè)備裝載在運輸車輛上，有

(12)

為將裝卸節(jié)點與運輸需求終點碼頭節(jié)點相連接，即在堆場上將集裝箱通過堆場裝卸設(shè)備從運輸車輛上卸載下來，有

θ∈Θ;h∈H

(13)

j∈NLT;θ∈Θ;h∈H

(14)

j∈NLT;θ∈Θ;h∈H

(15)

考慮裝載和卸載集裝箱所花費的時間，約束每種車輛在規(guī)定時間步長內(nèi)可在節(jié)點上執(zhí)行的裝卸操作的最大數(shù)量，有

j∈NLT;θ∈Θ;h∈H

(16)

式(16)中:ldi為在給定時間段中節(jié)點i同時運動的集裝箱最大數(shù)量。

在運輸需求起始點與終點裝載的集裝箱數(shù)量的表達式為

θ∈Θ;h∈H

(17)

(18)

限制車輛運輸過程總花費時間要大于等于運輸時間與運輸車輛充電時間之和為

(i,j)∈AT;θ∈Θ;h∈H

(19)

式(19)中:當h型車輛不是電動車輛時，σh等于無窮大;當h型車輛為AGV時，σh=600(時間步長以min為單位);當h型車輛為無人駕駛電動集卡時，σh=240;Ba為無人駕駛車輛每次充電時間，為λ的整數(shù)倍；σh為h型車輛充電系數(shù)。

在運輸開始之前，集裝箱不需要被交付的表達式為

(20)

式(20)中:Ts′為滿足運輸需求θ的集裝箱最早釋放時間，Ts′=min(Tsθ)。

運輸車輛在交叉路口節(jié)點的起始數(shù)量為0,表達式為

(21)

運輸車輛在運輸開始之前數(shù)量為0，表達式為

(22)

2.2 有效不等式

首先運行式(5)～式(22)，并求解相應(yīng)的整數(shù)規(guī)劃模型。式(5)～式(22)對應(yīng)于集裝箱多商品流[3]，通過GUROBI或其他開源的混合整數(shù)規(guī)劃求解器即可求解出最優(yōu)解，但像GUROBI這樣的求解器對多商品流結(jié)構(gòu)有很大的削減作用。通過分析問題的結(jié)構(gòu)，構(gòu)建以下有效不等式形成割平面，控制車輛的流動并確保集裝箱由車輛運輸，可收緊模型的可行域，加快收斂過程和求解速度。然后加入式(23)～式(25)有效不等式與式(5)～式(22)一起運行這些求解整數(shù)規(guī)劃問題。

1)車輛在運輸需求的最早釋放時間出發(fā)，有

(23)

式(23)中:V為所有車輛的集合，V={1,2,…,v}。

2)限制進入節(jié)點車輛數(shù)量與離開節(jié)點車輛數(shù)量相等，有

k∈NθD;Tsθ≤t≤τλ;h∈H

(24)

3)車輛交付的集裝箱數(shù)量不能超過其承載能力，有

Tsθ≤t≤τλ;h∈H

(25)

將車輛與集裝箱連接在一起，限制在ITT網(wǎng)絡(luò)上行駛的車輛所能裝載的集裝箱最大數(shù)量要大于等于在ITT網(wǎng)絡(luò)上流動的集裝箱的總數(shù)量。不同類型車輛的最大承載能力不同，其中MTS每次最多能運輸5個集裝箱。

3 算例分析

根據(jù)洋山港碼頭區(qū)域的ITT網(wǎng)絡(luò)布局、運輸需求和運輸設(shè)備的屬性生成多組數(shù)據(jù)集，對數(shù)學模型進行求解，并對運算結(jié)果進行系統(tǒng)分析。

3.1 ITT網(wǎng)絡(luò)布局

洋山港堅持將水水中轉(zhuǎn)作為集裝箱業(yè)務(wù)增長的重要支撐，持續(xù)優(yōu)化航線航班配置和集、疏運網(wǎng)絡(luò)。洋山港共有5個集裝箱碼頭，其中洋山5期駁船碼頭為新建碼頭，最遠的2個碼頭之間的直線距離為10 km。若新建碼頭與原有碼頭都有駁船?？?，則ITT 網(wǎng)絡(luò)圖見圖3，設(shè)此“無駁船碼頭中心”的ITT運輸網(wǎng)絡(luò)為運輸網(wǎng)絡(luò)1;若只有洋5能?？狂g船，則ITT 運輸網(wǎng)絡(luò)圖見圖4，設(shè)此“有駁船碼頭中心”的ITT運輸網(wǎng)絡(luò)為運輸網(wǎng)絡(luò)2。

圖3 “無駁船碼頭中心”運輸網(wǎng)絡(luò)1

圖4 “有駁船碼頭中心”運輸網(wǎng)絡(luò)2

3.2 運輸需求

當每天不同運輸需求的情形發(fā)生時，為測試不同運輸方式和2種ITT運輸網(wǎng)絡(luò)的性能表現(xiàn)，各碼頭之間的集裝箱運輸需求由需求生成器產(chǎn)生[4]，該需求生成器根據(jù)3種場景創(chuàng)建需求(見表1)，且各階段的需求量區(qū)間都服從均勻分布。

表1 3種運輸需求場景的屬性

需求生成器的其他屬性還包括起始碼頭與目標碼頭、集裝箱釋放時間與交付時間。在“無駁船碼頭中心”的運輸網(wǎng)絡(luò)1中，將洋山港的任一碼頭a匹配其他任一的碼頭b，需求釋放時間為[0,tmax-2time(a,b)]范圍內(nèi)隨機均勻選擇的釋放時間;在“有駁船碼頭中心”的運輸網(wǎng)絡(luò)2中，將洋山5期碼頭與其他任一碼頭c匹配，需求釋放時間為[0,tmax-2time(5,c)]范圍內(nèi)隨機均勻選擇的釋放時間。tmax為運輸車輛在碼頭之間運輸?shù)淖畲髸r間值;time(a,b)和time(5,c)為運輸車輛在碼頭之間運輸?shù)淖钚r間值。

3.3 運輸設(shè)備的屬性

基于對洋山港各碼頭實際情況的調(diào)查研究，根據(jù)港口區(qū)域相關(guān)數(shù)據(jù)和ITT運輸設(shè)備相關(guān)數(shù)據(jù)(見表2),可得到用于算例分析的人工試驗數(shù)據(jù)集。

表2 ITT運輸設(shè)備相關(guān)參數(shù)

3.4 測評結(jié)果分析

通過將碼頭節(jié)點、交叉路口節(jié)點和運輸?shù)缆方橐幌盗泄?jié)點和弧線，輸入需求生成器創(chuàng)建的集合和4種運輸設(shè)備相關(guān)參數(shù)，共生成240個實例。采用PYTHON編程，并用GUROBI求解器進行求解，使用Intel Core i5、1.80 GHz CPU和8G內(nèi)存的計算機運算。測評部分結(jié)果匯總表見表3，展示了求解模型本身加上有效不等式之后(模型+VI)的運算時間，以及兩者的對比倍數(shù)。由表3可知:隨著運輸任務(wù)數(shù)量與運輸集裝箱總數(shù)的增加，有效不等式的加速作用更加明顯。

表3 測評結(jié)果匯總表(部分)

對4種不同ITT運輸設(shè)備的測試進行匯總，結(jié)果見圖5。由圖5可知：在“有駁船碼頭中心”運輸網(wǎng)絡(luò)2與“無駁船碼頭中心”運輸網(wǎng)絡(luò)1對比下，4種ITT車輛的總成本和最低調(diào)用車輛數(shù)都有所下降；在低谷需求下，總成本下降比率分別為15.22%、6.46%、25.73%和19.81%，調(diào)用車輛數(shù)下降比率分別為15.21%、17.99%、21.25%和30.07%;在常規(guī)需求下，總成本下降比率分別為23.04%、13.85%、22.29%和13.26%，調(diào)用車輛數(shù)下降比率分別為42.86%、18.55%、25.27%和13.07%;滿足在高峰需求的總成本下降比率分別為25.27%、12.78%、16.74%和9.50%，調(diào)用車輛數(shù)下降比率分別為22.28%、12.50%、12.64%和4.81%。

通過對測評結(jié)果進行整體分析可知：就2種運輸網(wǎng)絡(luò)而言，在滿足3種不同運輸需求的情況下，“有駁船碼頭中心”相比“無駁船碼頭中心”運輸網(wǎng)絡(luò),在碼頭節(jié)點最低調(diào)用車輛數(shù)量和總成本上都更低。隨著運輸需求數(shù)量的增加，人工駕駛車輛(ALV和MTS)總體上相比無人駕駛車輛,啟用比率下降，速度和總成本下降速度更快， MTS在最低調(diào)用車輛數(shù)上的表現(xiàn)最好，成本偏高。港口可根據(jù)實際需求情況使用哪種ITT運輸方式完成運輸。

a)AGV b)無人駕駛電動集卡

c)MTS d)ALV

4 結(jié)束語

本文對新建港口的多碼頭間集裝箱運輸問題進行研究，基于時空拓展圖提出一種整數(shù)規(guī)劃模型。結(jié)合港口實際運輸數(shù)據(jù)，包括需求任務(wù)集和作業(yè)時間要求等，確定最佳的車輛配置和最小化成本，研究ITT問題的特性和影響。同時，對洋山港ITT問題進行算例分析。結(jié)果表明:將新建碼頭設(shè)立為“駁船碼頭中心”能有效降低ITT成本和減少調(diào)用車輛數(shù)量，驗證有效不等式對大規(guī)模問題的加速作用。本文的研究結(jié)果可為港口營運人員對ITT運輸設(shè)備、車輛數(shù)量和配置等進行相關(guān)戰(zhàn)略決策及對港口擴建碼頭的道路進行布局提供支持。該研究也存在不足之處，例如：ITT模型中并未考慮駁船等長期運輸工具，也未結(jié)合智能優(yōu)化算法對ITT數(shù)學模型進行更深入的研究，這是港口ITT問題研究的一個方向。