長(zhǎng)江集裝箱多式聯(lián)運(yùn)路徑優(yōu)化動(dòng)態(tài)規(guī)劃算法

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

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

0 引 言

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

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

1 問(wèn)題提出

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

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

2 模型構(gòu)建

2.1 假設(shè)條件

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

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

(2)僅考慮20 ft標(biāo)準(zhǔn)普通集裝箱，暫不考慮其它尺寸和類(lèi)型的集裝箱；

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

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

2.2 數(shù)學(xué)模型

(1)集合

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

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

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

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

M表示貨流集合。

(2)參數(shù)

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

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

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

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

Cmmax表示貨流m最大可接受運(yùn)輸費(fèi)用(元)， ?m∈M；

ξi表示在節(jié)點(diǎn)i單位時(shí)間單位集裝箱的存儲(chǔ)費(fèi)用(元/TEU·h)， ?i∈N；

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

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

α為載運(yùn)系數(shù)。

(3)決策變量

(4)模型

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

3 算法設(shè)計(jì)

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

圖1 算法總框架

3.1 第一階段

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

(1)模塊1：貨流離開(kāi)當(dāng)前節(jié)點(diǎn)時(shí)間計(jì)算。根據(jù)貨流到達(dá)當(dāng)前節(jié)點(diǎn)時(shí)間，確定貨流在該節(jié)點(diǎn)處的發(fā)車(chē)班次，得到貨流離開(kāi)時(shí)間；

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

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

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

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

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

3.2 第二階段

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

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

4 算例研究

4.1 算例設(shè)計(jì)

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

4.2 算例參數(shù)

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

表1 不同節(jié)點(diǎn)間不同運(yùn)輸方式距離

4.3 算例求解

4.3.1 不同貨流可行路徑方案

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

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

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

表2 不同運(yùn)輸方式班次信息/h

表3 節(jié)點(diǎn)加收費(fèi)用信息

表4 貨流時(shí)間窗約束及懲罰費(fèi)用

表5 道路能力約束/t

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

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

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

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

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

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

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

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

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

4.3.3 時(shí)間窗約束松弛分析

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

圖4 貨流2路徑到達(dá)時(shí)間與總費(fèi)用關(guān)系趨勢(shì)

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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