長江集裝箱多式聯運路徑優化動態規劃算法

李 俊，梁曉磊+，趙 勝，張 煜

(1.武漢科技大學 汽車與交通工程學院，湖北 武漢 430065；2.福建工程學院 交通運輸學院，福建 福州 350108；3.武漢理工大學 港口物流技術與裝備教育部研究中心，湖北 武漢 430063)

0 引 言

已有的集裝箱多式聯運路徑優化研究大多將問題轉化為最短路問題，以總成本最小為目標，基于模型構建、算法設計及仿真分析等方法實現問題求解[1,2]。Hao等[3]基于動態規劃方法構建優化模型，利用動態規劃算法求解。Tsao等[4]考慮碳排放影響，引入非線性優化方法實現問題優化。李敏[5]構建了長江經濟帶中段多式聯運網絡優化模型。陳偉[6]引入時間窗約束構建模型，采用遺傳算法尋優。劉清等[7]構建多目標優化模型，并轉化為單目標后基于遺傳算法求解。湯銀英等[8]構建雙目標優化的0-1整數規劃模型，采用非支配排序遺傳算法(NSGA-II)求解。范方玲子等[9]構建多目標路徑優化模型，設計遺傳算法求解。任剛等[10]構建中歐集裝箱多式聯運路徑選擇優化模型，采用遺傳算法尋優。Bok等[11]針對集裝箱化貨物運輸需求，提出多式聯運路徑選擇模型，并通過構建PC數據實現模型驗證。Wang等[12]考慮降低碳排放，基于Witness仿真軟件實現多式聯運路徑參數動態計算。陳釘均等[13]面向綠色多式聯運，基于MATLAB仿真實現問題求解。

綜上所述，已有研究大多基于已有算法改進實現問題求解，且對不同貨流帶來的路徑通過能力、節點接收及中轉能力之間的相互干涉影響也少有關注。因此，本文從長江集裝箱多式聯運實際需求出發，考慮不同貨流運輸需求及其時間窗約束，研究其模型構建與算法設計。

1 問題提出

集裝箱多式聯運是兩種及以上交通運輸方式相互銜接、轉運來共同完成集裝箱運輸需求的一種復合運輸方式。在集裝箱多式聯運網絡中，往往包含多個不同的節點，且在每個節點存在多種運輸方式可以選擇，如何確定各節點的運輸方式選取，為不同貨流確定最佳路徑方案，保證運輸成本最低，是多式聯運路徑優化關鍵所在。

對于長江集裝箱多式聯運路徑優化問題而言，需要綜合考慮不同貨流運輸需求以及網絡中路徑與節點服務能力限制，制定出多式聯運總費用最小的路徑方案。具體來說，在滿足不同貨流運輸需求前提下，需要考慮的約束包括貨流時間窗限制、貨流最大運輸成本、路徑最大通過能力、節點接收及中轉能力等。多式聯運總費用則包括不同節點間的運輸成本、中途節點的轉運成本和存儲費用、錯開時間窗帶來的終點存儲費用和逾期懲罰費用等。

2 模型構建

2.1 假設條件

從長江集裝箱多式聯運特點和現實約束出發，做出以下建模假設：

(1)考慮水路、公路和鐵路3種運輸方式；

(2)僅考慮20 ft標準普通集裝箱，暫不考慮其它尺寸和類型的集裝箱；

(3)運輸途中任一節點至多可換裝一次；

(4)各種運輸方式及各貨流基本信息已知。

2.2 數學模型

(1)集合

N表示多式聯運路徑中節點集合；

K表示多式聯運路徑中節點間運輸方式集合；

O表示多式聯運路徑中所有起點集合，O?N；

D表示多式聯運路徑中所有終點集合，D?N；

M表示貨流集合。

(2)參數

vk表示第k種運輸方式的運輸速度(km/h)， ?k∈K；

Tkk′表示由第k種運輸方式轉換為第k′種運輸方式的單位轉運時間(h)， ?k,k′∈K；

Um表示貨流m包含的20 ft集裝箱量(TEU)， ?m∈M；

qm表示貨流m的運輸重量(t)， ?m∈M；

Cmmax表示貨流m最大可接受運輸費用(元)， ?m∈M；

ξi表示在節點i單位時間單位集裝箱的存儲費用(元/TEU·h)， ?i∈N；

Bjk表示節點j對第k種運輸方式的最大接收能力(t)， ?i,j∈N，k∈K；

Qijk表示從節點i到節點j第k種運輸方式的最大路徑通過能力(t)， ?i,j∈N，k∈K；

α為載運系數。

(3)決策變量

(4)模型

以運輸總費用最小為目標，構建長江集裝箱多貨流多式聯運路徑優化的0-1整數規劃模型

3 算法設計

深度優先遍歷算法屬于搜索樹或圖算法的一種，其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次?；谏疃葍炏缺闅v的兩階段多式聯運路徑優化動態規劃算法設計如圖1所示。其中，第一階段根據輸入的貨流、節點以及時間窗等數據，完成當前不同貨流所有可行路徑的遍歷與計算；第二階段以不同貨流所有可行路徑方案為初始輸入條件，利用動態規劃算法完成最優多式聯運路徑優化。

圖1 算法總框架

3.1 第一階段

第一階段是在深度優先算法的基礎上為每個節點賦予屬性，以模擬貨物中轉、等待等情況。該階段主要包含4個模塊，其功能描述如下：

(1)模塊1：貨流離開當前節點時間計算。根據貨流到達當前節點時間，確定貨流在該節點處的發車班次，得到貨流離開時間；

(2)模塊2：中轉費用計算。判斷貨流在當前節點處中轉情況，若發生中轉，則在總費用中加入中轉費用；

(3)模塊3：集截貨時間計算。根據貨流到達下一節點采用運輸方式得到當前節點處的集截貨時間等數據；

(4)模塊4：存儲費用計算。判斷貨流是否在當前節點時間窗內到達，若早于某一班次集貨時間或晚于截貨時間，則在總費用中加入存儲費用。

綜上，算法第一階段設計如圖2所示，圖中“變異”表示把集合中遍歷過的元素數據替換為一個極大數，避免重復遍歷。

圖2 算法第一階段設計

3.2 第二階段

集裝箱多式聯運中不同貨流之間會相互疊加影響。節點中轉能力和路徑通過能力約束下，不同貨流的運輸路徑選擇產生干涉影響，需要進行整體優化和動態規劃尋找全局最優。以第一階段得到的不同貨流所有可行路徑方案為輸入，進行算法第二階段優化設計，求解多式聯運最優路徑方案。算法第二階段設計如圖3所示。

圖3 算法第二階段設計

4 算例研究

4.1 算例設計

從長江集裝箱多式聯運現狀出發，選取長江沿線5個關鍵節點(重慶、宜昌、武漢、南京、上海)，各節點間均有公路、鐵路和水路3種運輸方式供選擇。設計3條貨流展開算例研究，具體信息如下：①貨流1從重慶至南京，途徑宜昌和武漢，包含20TEU集裝箱；②貨流2從武漢至上海，途徑南京，包含15TEU集裝箱；③貨流3從宜昌至南京，途徑武漢，包含10TEU集裝箱。

4.2 算例參數

各種運輸方式的相關參數設置為：鐵路運輸速度為80 km/h，成本為0.135元/(t·km)；水路運輸速度為24 km/h，成本為0.03元/(t·km)；公路運輸速度為100 km/h，成本為0.35元/(t·km)[5]。3條貨流的最大運輸成本限制依次為16萬元、7萬元和7萬元。其它數據設計參見表1至表6。

表1 不同節點間不同運輸方式距離

4.3 算例求解

4.3.1 不同貨流可行路徑方案

所有集裝箱按20 t/TEU計算箱重。算法采用Python 3.7編程實現，所有算例均采用筆記本電腦(Intel Core I5-6200U, 2.30 GHz,8 GB RAM)運行求解。

對于貨流1，全部理論路徑共27條，見表7。其中，滿足時間窗、最大成本、路徑通行能力在內約束的多式聯運可行路徑為方案11，采用斜體標注(以下表格相同處理)。

對于貨流2，全部理論路徑共9條，見表8。其中，滿足時間窗、最大成本、路徑通行能力在內約束的多式聯運可行路徑位方案5和6。

表2 不同運輸方式班次信息/h

表3 節點加收費用信息

表4 貨流時間窗約束及懲罰費用

表5 道路能力約束/t

表6 節點中轉能力約束/TEU

表7 貨流1多式聯運可行路徑方案(部分)

表8 貨流2多式聯運可行路徑方案

對于貨流3，全部理論路徑共9條，見表9。其中，滿足時間窗、最大成本、路徑通行能力在內約束的多式聯運可行路徑為方案4至方案8。

表9 貨流3多式聯運可行路徑方案

4.3.2 集裝箱多式聯運最優路徑方案

同時集裝箱多式聯運不同貨流運輸任務時，與不同貨流單一考慮相比，需考慮所有貨流帶來的節點接收能力、中

轉能力、班次運行能力以及路徑通過能力之間的相互影響，較單一貨流的路徑優化問題更為復雜。綜合考慮不同貨流間相互干涉影響，得到集裝箱多式聯運總成本最低的路徑方案見表10。由于受武漢至南京間鐵路運輸方式道路通過能力約束，在貨流1和貨流2均選擇費用最低路徑時，貨流3僅能選擇費用第二低的方案6。

表10 集裝箱多式聯運最優路徑選擇

4.3.3 時間窗約束松弛分析

以貨流2為例，多式聯運路徑到達時間與總成本之間的關系趨勢如圖4所示。從圖4可以看出，路徑的到達時間與總費用之間大體呈現負相關，因此如果調整到達時間，即將貨流的時間窗約束后移，可得到總費用更低的路徑方案。

圖4 貨流2路徑到達時間與總費用關系趨勢

例如將貨流2的時間窗約束由[222,246]調整為[222,251]，則此時貨流2的全部可行路徑方案見表11。從表11中可看出，通過適當松弛時間窗約束可有效降低集裝箱多式聯運總成本。原最優路徑6的總費用為33 980.75元，調整后最優路徑9的總費用為12 938.75元，下降比例明顯。

表11 時間窗調整后貨流2可行路徑方案

4.3.4 班次信息調整分析

如表2所示，在集裝箱多式聯運中各種不同運輸方式均按固定的時間控制班次到發，因此不同貨流抵達最終目的節點的到達時間與運輸方式的班次信息密切相關，同時班次信息的調整也可能會對不同貨流在中途節點的存儲費用、最終節點的存儲費用或逾期費用等產生影響。

現以貨流2為例，嘗試將表2不同運輸方式班次信息中的首次截貨時間提前5小時展開分析。調整后，貨流2所有路徑方案的變化情況見表12。從表12中可以看出，由于提前首次截貨時間帶來了班次提前發出，使得貨流2的所有路徑方案到達時間均提前5 h。

表12 調整班次信息后貨流2路徑方案變化情況

此時，貨流2的可行路徑方案見表13。從表13中可看出，通過適當調整運輸方式的班次信息可有效降低集裝箱多式聯運總成本。原最優路徑6的總費用為33 980.75元，調整后最優路徑9的總費用為13 688.75元，下降比例明顯。

表13 調整班次信息后貨流2可行路徑方案

5 結束語

本文從長江集裝箱多式聯運運輸需求及其時間窗限制出發，以運輸總費用最小為目標構建了集裝箱多式聯運路徑優化模型，并設計基于深度優先遍歷的多式聯運路徑優化動態規劃算法實現求解。算法包含兩階段：第一階段通過網絡遍歷求解得到不通貨流可行路徑方案集；第二階段以其作為輸入，實現多式聯運最優路徑方案選取。算例研究表明：適當調整貨流時間窗約束或運輸方式班次信息可得到總費用更低的路徑方案；算法可實現長江集裝箱多式聯運路徑優化，可為實際制定路徑方案提供參考。后續將針對算例數據的準確性以及節點更多的大規模問題展開研究。