基于時空拓展圖模型的多碼頭間集裝箱運輸優化

丁 一， 何樂媚， 沙 梅

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

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

圖1 洋山港碼頭分布圖

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

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

1 問題描述

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

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

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

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

圖2 時空拓展圖

2 模型構建

2.1 數學模型構造

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

(7)

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

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

Tsθ≤t≤τλ;h∈H

(8)

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

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

(9)

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

為限制規定時間步長內在交叉路口節點的持有車輛總數上限，防止交叉口車輛擁堵有

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

(10)

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

為保證在堆場裝卸節點內的集裝箱流平衡,有

(11)

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

(12)

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

θ∈Θ;h∈H

(13)

j∈NLT;θ∈Θ;h∈H

(14)

j∈NLT;θ∈Θ;h∈H

(15)

考慮裝載和卸載集裝箱所花費的時間，約束每種車輛在規定時間步長內可在節點上執行的裝卸操作的最大數量，有

j∈NLT;θ∈Θ;h∈H

(16)

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

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

θ∈Θ;h∈H

(17)

(18)

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

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

(19)

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

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

(20)

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

運輸車輛在交叉路口節點的起始數量為0,表達式為

(21)

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

(22)

2.2 有效不等式

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

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

(23)

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

2)限制進入節點車輛數量與離開節點車輛數量相等，有

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

(24)

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

Tsθ≤t≤τλ;h∈H

(25)

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

3 算例分析

根據洋山港碼頭區域的ITT網絡布局、運輸需求和運輸設備的屬性生成多組數據集，對數學模型進行求解，并對運算結果進行系統分析。

3.1 ITT網絡布局

洋山港堅持將水水中轉作為集裝箱業務增長的重要支撐，持續優化航線航班配置和集、疏運網絡。洋山港共有5個集裝箱碼頭，其中洋山5期駁船碼頭為新建碼頭，最遠的2個碼頭之間的直線距離為10 km。若新建碼頭與原有碼頭都有駁船停靠，則ITT 網絡圖見圖3，設此“無駁船碼頭中心”的ITT運輸網絡為運輸網絡1;若只有洋5能停靠駁船，則ITT 運輸網絡圖見圖4，設此“有駁船碼頭中心”的ITT運輸網絡為運輸網絡2。

圖3 “無駁船碼頭中心”運輸網絡1

圖4 “有駁船碼頭中心”運輸網絡2

3.2 運輸需求

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

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

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

3.3 運輸設備的屬性

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

表2 ITT運輸設備相關參數

3.4 測評結果分析

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

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

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

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

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

c)MTS d)ALV

4 結束語

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