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

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

0 引 言

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

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

1 問題提出

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

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

2 模型構(gòu)建

2.1 假設(shè)條件

從長江集裝箱多式聯(lián)運特點和現(xiàn)實約束出發(fā)，做出以下建模假設(shè)：

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

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

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

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

2.2 數(shù)學模型

(1)集合

N表示多式聯(lián)運路徑中節(jié)點集合；

K表示多式聯(lián)運路徑中節(jié)點間運輸方式集合；

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

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

M表示貨流集合。

(2)參數(shù)

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

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

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

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

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

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

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

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

α為載運系數(shù)。

(3)決策變量

(4)模型

以運輸總費用最小為目標，構(gòu)建長江集裝箱多貨流多式聯(lián)運路徑優(yōu)化的0-1整數(shù)規(guī)劃模型

3 算法設(shè)計

深度優(yōu)先遍歷算法屬于搜索樹或圖算法的一種，其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次。基于深度優(yōu)先遍歷的兩階段多式聯(lián)運路徑優(yōu)化動態(tài)規(guī)劃算法設(shè)計如圖1所示。其中，第一階段根據(jù)輸入的貨流、節(jié)點以及時間窗等數(shù)據(jù)，完成當前不同貨流所有可行路徑的遍歷與計算；第二階段以不同貨流所有可行路徑方案為初始輸入條件，利用動態(tài)規(guī)劃算法完成最優(yōu)多式聯(lián)運路徑優(yōu)化。

圖1 算法總框架

3.1 第一階段

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

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

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

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

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

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

圖2 算法第一階段設(shè)計

3.2 第二階段

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

圖3 算法第二階段設(shè)計

4 算例研究

4.1 算例設(shè)計

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

4.2 算例參數(shù)

各種運輸方式的相關(guān)參數(shù)設(shè)置為：鐵路運輸速度為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萬元。其它數(shù)據(jù)設(shè)計參見表1至表6。

表1 不同節(jié)點間不同運輸方式距離

4.3 算例求解

4.3.1 不同貨流可行路徑方案

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

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

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

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

表3 節(jié)點加收費用信息

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

表5 道路能力約束/t

表6 節(jié)點中轉(zhuǎn)能力約束/TEU

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

表8 貨流2多式聯(lián)運可行路徑方案

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

表9 貨流3多式聯(lián)運可行路徑方案

4.3.2 集裝箱多式聯(lián)運最優(yōu)路徑方案

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

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

表10 集裝箱多式聯(lián)運最優(yōu)路徑選擇

4.3.3 時間窗約束松弛分析

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

圖4 貨流2路徑到達時間與總費用關(guān)系趨勢

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

表11 時間窗調(diào)整后貨流2可行路徑方案

4.3.4 班次信息調(diào)整分析

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

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

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

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

表13 調(diào)整班次信息后貨流2可行路徑方案

5 結(jié)束語

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