考慮多節(jié)點(diǎn)時間窗差異的集裝箱多式聯(lián)運(yùn)路徑選擇研究

湯銀英，戴煒東，陳 思

考慮多節(jié)點(diǎn)時間窗差異的集裝箱多式聯(lián)運(yùn)路徑選擇研究

湯銀英1,2，戴煒東1，陳 思1,2

（1. 西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 611756；2. 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實(shí)驗(yàn)室，成都 611756）

基于多式聯(lián)運(yùn)網(wǎng)絡(luò), 考慮不同運(yùn)輸方式的能力以及工作時間窗和發(fā)車班期, 并且根據(jù)貨主的具體貨運(yùn)需求, 構(gòu)建了運(yùn)輸成本最小、運(yùn)輸時間最少的多目標(biāo)0-1整數(shù)規(guī)劃模型。通過決策運(yùn)輸路線、運(yùn)輸方式來優(yōu)化運(yùn)輸路徑, 采用非支配排序遺傳算法 (NSGA-II) 以及二階段編碼的方式求解模型, 經(jīng)過多次種群進(jìn)化和非支配解篩選, 獲得多式聯(lián)運(yùn)運(yùn)輸路線的Pareto非劣解集。最后以20個節(jié)點(diǎn)、39條運(yùn)輸弧、3種運(yùn)輸方式的多式聯(lián)運(yùn)網(wǎng)絡(luò)為例進(jìn)行算例分析, 驗(yàn)證了算法和模型的可行性和有效性。

多目標(biāo)規(guī)劃；路徑選擇；時間窗

0 引 言

集裝箱多式聯(lián)運(yùn)具有高效便捷、安全可靠的優(yōu)勢，是降低物流成本、減少運(yùn)輸時間的有效方式，是貨物運(yùn)輸發(fā)展的重要方向[1]。因此，集裝箱多式聯(lián)運(yùn)路徑規(guī)劃一直國內(nèi)外學(xué)者研究的主要方向，旨在提高多式聯(lián)運(yùn)的運(yùn)輸效率和服務(wù)質(zhì)量[2]。

近年來，國內(nèi)外學(xué)者對于集裝箱多式聯(lián)運(yùn)路徑優(yōu)化問題進(jìn)行了深入的研究。于雪嶠等[3]在需求不確定性的基礎(chǔ)上，考慮節(jié)點(diǎn)時間窗以及貨主滿意度，構(gòu)建運(yùn)輸費(fèi)用最小的路徑優(yōu)化模型。劉杰等[4]考慮出發(fā)時間對運(yùn)輸路徑選擇影響，將運(yùn)輸費(fèi)用分為固定費(fèi)用、路段運(yùn)費(fèi)、換裝費(fèi)以及等待花費(fèi)，建立多式聯(lián)運(yùn)路徑優(yōu)化模型，采用改進(jìn)的Dijkstra算法求解。張小龍等[5]在考慮運(yùn)輸時間窗的基礎(chǔ)上，構(gòu)建運(yùn)輸時間最短、運(yùn)輸費(fèi)用最少、運(yùn)輸碳排放最小的多目標(biāo)路徑優(yōu)化模型。魏宇[6]考慮節(jié)點(diǎn)能力以及節(jié)點(diǎn)時間窗，構(gòu)建多商品流多式聯(lián)運(yùn)路徑優(yōu)化模型，最后采用Anylogic進(jìn)行仿真求解。熊桂武[7]引入代理商的概念，構(gòu)建多代理商、多運(yùn)輸方式的多式聯(lián)運(yùn)路徑優(yōu)化模型，采用遺傳算法得出最優(yōu)路徑。劉杰等[8]考慮低碳環(huán)境下的多式聯(lián)運(yùn)問題，構(gòu)建了碳排放最小，運(yùn)輸費(fèi)用最低的多目標(biāo)模型。雷定猷等[9]考慮長大貨物的特性，以線路限界、線路承載能力、起重設(shè)備的起重能力為約束條件，構(gòu)建了長大貨物路徑優(yōu)化模型。申勇等[10]考慮危險(xiǎn)廢物的特性進(jìn)行了路徑規(guī)劃。任剛等[11]將混合時間窗和班期引入路徑選擇模型。劉暢等[12]根據(jù)貨物時間價(jià)值對貨物進(jìn)行路徑規(guī)劃。Sun等[13]考慮CO2的排放，以運(yùn)輸成本最低構(gòu)建路徑選擇模型，最后利用LINGO進(jìn)行求解。James等[14]以墨西哥為實(shí)例，在考慮運(yùn)輸時間與運(yùn)輸成本的基礎(chǔ)上，采用Dijkstra算法得出了最優(yōu)的路徑。Mnif等[15]采用煙花算法求解多目標(biāo)多式聯(lián)運(yùn)問題，并將其與CPLEX的求解結(jié)果進(jìn)行對比分析，得出啟發(fā)式算法效率更高的結(jié)論。

綜上所述，本文作者在既有文獻(xiàn)研究的基礎(chǔ)上，考慮了如下方面的內(nèi)容：

（1）時間窗。既有文獻(xiàn)大多只是簡單地給節(jié)點(diǎn)一個模式單一的時間窗，沒有對不同運(yùn)輸方式的時間窗區(qū)別對待。例如公路運(yùn)輸較為自由，其時間窗為是一個時間段，而鐵路和水運(yùn)則有固定的班期，應(yīng)為固定的時間點(diǎn)，因此給不同運(yùn)輸方式不同類型的時間窗。

（2）多貨物品類。現(xiàn)有文獻(xiàn)大多沒有考慮節(jié)點(diǎn)運(yùn)輸方式能力，只是對單一貨物進(jìn)行路徑優(yōu)化研究，而現(xiàn)實(shí)生活中，節(jié)點(diǎn)能力不足會影響運(yùn)輸方案的實(shí)施。

（3）多目標(biāo)。現(xiàn)有文獻(xiàn)雖然構(gòu)建了考慮運(yùn)輸時間和運(yùn)輸費(fèi)用的多目標(biāo)模型，但大多都是將其轉(zhuǎn)化為單目標(biāo)進(jìn)行求解，沒有求解Pareto解集。

因此，本文考慮不同節(jié)點(diǎn)不同運(yùn)輸方式的時間窗、能力、貨物的運(yùn)到時限、貨主能接受的最大運(yùn)輸費(fèi)用等因素，構(gòu)建運(yùn)輸費(fèi)用最小、運(yùn)輸時間最短的多目標(biāo)模型，采用NSGA-II算法得到Pareto解集。

1 問題描述與建模

1.1 問題描述

集裝箱多式聯(lián)運(yùn)選擇過程中，多式聯(lián)運(yùn)人會考慮運(yùn)輸成本、運(yùn)輸時間等因素選擇合適的路線將貨物運(yùn)輸?shù)侥康牡兀\(yùn)輸路線會途經(jīng)多個節(jié)點(diǎn)，進(jìn)行多次換裝。相鄰節(jié)點(diǎn)間能通過公路、水運(yùn)、鐵路這三種方式來運(yùn)輸集裝箱，不同運(yùn)輸方式的運(yùn)輸費(fèi)用、運(yùn)輸速度、運(yùn)輸能力存在差異，并且在運(yùn)輸?shù)倪^程中，節(jié)點(diǎn)有通過能力限制以及工作時間窗的限制。

1.2 符號說明

1.3 模型構(gòu)建

考慮運(yùn)輸費(fèi)用最小，運(yùn)輸時間最小的的多式聯(lián)運(yùn)路徑選擇模型可表示如下：

目標(biāo)函數(shù)：

約束條件：

目標(biāo)函數(shù)（1）表示總費(fèi)用（運(yùn)輸費(fèi)用、轉(zhuǎn)運(yùn)費(fèi)用）最少；目標(biāo)函數(shù)（2）表示總時間最少；約束（3）表示節(jié)點(diǎn)的流量平衡約束；約束（4）表示貨物在兩節(jié)點(diǎn)間運(yùn)輸最多只能選擇一種運(yùn)輸方式；約束（5）為貨物在節(jié)點(diǎn)至多轉(zhuǎn)運(yùn)一次；約束（6）為貨物在節(jié)點(diǎn)轉(zhuǎn)運(yùn)時對運(yùn)輸路徑的要求；約束（7）為貨物到達(dá)節(jié)點(diǎn)的時間；約束（8）為貨物在節(jié)點(diǎn)換裝完的時間；約束（9）表示貨物在節(jié)點(diǎn)用公路運(yùn)輸方式被運(yùn)走需要等待的時間；約束（10）表示貨物在節(jié)點(diǎn)用水運(yùn)、鐵路運(yùn)輸方式被運(yùn)走需要等待的時間；約束（11）為貨物離開起點(diǎn)的等待時間；約束（12）為貨物到達(dá)節(jié)點(diǎn)的天數(shù)；約束（13）表示每一天到達(dá)節(jié)點(diǎn)的貨運(yùn)量要小于節(jié)點(diǎn)接收的能力；約束（14）為貨物可接受的最長運(yùn)輸時間限制；約束（15）為貨運(yùn)需求可接收的最大運(yùn)輸費(fèi)用限制；約束（16）為0-1變量，其中ceil（）函數(shù)為向上取整函數(shù)。

2 模型求解

上述問題是一個多目標(biāo)問題，而針對多目標(biāo)問題，適合采用多目標(biāo)遺傳算法NSGA-II進(jìn)行求解。其基本原理對每個“染色體”的目標(biāo)函數(shù)進(jìn)行快速非支配排序，對每個“染色體”進(jìn)行擁擠度計(jì)算，根據(jù)非支配關(guān)系以及擁擠度選取合適的“染色體”組成父代種群，在遺傳算法的基礎(chǔ)上產(chǎn)生新的子代種群，將父代染色體與子代染色體合并形成新的父代染色體，依此類推，得到Pareto解。具體計(jì)算過程如下：

（1）編碼

在編碼的時候，“染色體”分為兩段，第一段為路徑編碼，采用優(yōu)先級編碼；第二段為運(yùn)輸方式編碼，用1~3分別表示公路、鐵路、水運(yùn)三種運(yùn)輸方式，對圖1進(jìn)行編碼，染色體如圖2所示。

圖1 運(yùn)輸網(wǎng)絡(luò)圖

圖2 貨運(yùn)需求染色體

單貨運(yùn)路徑部分6，2，1，4，3，5為節(jié)點(diǎn)的優(yōu)先級，即節(jié)點(diǎn)1的優(yōu)先級為6，節(jié)點(diǎn)2的優(yōu)先級為2，以此類推。運(yùn)輸方式部分為線路運(yùn)輸方式編碼。多貨運(yùn)需求與單貨運(yùn)需求的編碼含義相同，不再贅述。

（2）解碼

在對染色體進(jìn)行解碼，得到染色體表示的運(yùn)輸路線和運(yùn)輸方式，步驟如下所示：

step 1 先尋找每個節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)集。

step 2 將所有節(jié)點(diǎn)劃分成兩個集合、（包含起始節(jié)點(diǎn)，為其他節(jié)點(diǎn)）。

step 3 從集合末節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)集中選擇優(yōu)先級最大的節(jié)點(diǎn)，將歸入集合，并且集合減去該節(jié)點(diǎn)。

step 4 當(dāng)不等于終點(diǎn)時，重復(fù)第三步，直到為終點(diǎn)。

對圖2（a）單貨運(yùn)需求染色進(jìn)行解碼（多貨運(yùn)需求類似），按照上述步驟進(jìn)行解碼后，路徑為1—2—5—6，運(yùn)輸方式為2，2，1。

（3）適應(yīng)值計(jì)算

通過解碼得到的運(yùn)輸路徑滿足路徑約束，但沒考慮時間窗、運(yùn)輸能力、運(yùn)輸時限約束以及最大運(yùn)輸費(fèi)用的約束。因此，對于時間窗約束，按照解碼路徑計(jì)算到達(dá)各節(jié)點(diǎn)的時間，如果到達(dá)時間在工作時間窗內(nèi)，則按照路徑去往下個節(jié)點(diǎn)，否則進(jìn)行等待。對于節(jié)點(diǎn)能力約束，則根據(jù)貨物到達(dá)節(jié)點(diǎn)的天數(shù)計(jì)算，用這一天的節(jié)點(diǎn)能力減去貨物的數(shù)量，若得到的數(shù)小于零，則將運(yùn)輸時間和運(yùn)輸費(fèi)用設(shè)為極大的數(shù)，反之，則不變。對于運(yùn)輸時限約束以及最大運(yùn)輸費(fèi)用的約束，按照解碼路徑得到的運(yùn)輸時間和運(yùn)輸費(fèi)用不滿足約束時，則將運(yùn)輸時間和運(yùn)輸費(fèi)用分別乘以懲罰系數(shù)1.5，反之，則不變。

（4）快速非支配排序

根據(jù)目標(biāo)函數(shù)值，計(jì)算染色體的排序等級（rank）進(jìn)行分層和選擇，建立子代染色體種群。步驟為：

step 1 定義個體的適應(yīng)度值若優(yōu)于個體，則稱支配，若沒有被任何其他解支配，則稱為非支配解。將所有非支配解的集合賦予rank = 1。

step 2 在除去非支配解外的剩余種群中再次找出非支配解集，賦rank = 2。

step 3 按照此原則進(jìn)行，直到整個種群被分層，在分層的基礎(chǔ)上計(jì)算染色體的擁擠度值，對相同排序等級的染色體按擁擠度進(jìn)一步排序。

（5）選擇

采用競標(biāo)選擇算子，每次取兩個染色體，比較排序等級，若排序等級值小，則該染色體進(jìn)入子代種群，反之則被淘汰；若排序等級值相同則比較擁擠度，若擁擠度較大，該染色被淘汰，反之進(jìn)入子代種群。

（6）交叉、變異

染色體交叉是隨機(jī)選取兩個染色體，分別將染色體的一段編碼進(jìn)行交換。染色體變異是隨機(jī)變化染色體的編碼，算法流程如圖3所示。

圖3 算法流程圖

3 算例分析

3.1 案例設(shè)計(jì)

為了考察模型和算法的可行性，模擬了具有20個節(jié)點(diǎn)的多式聯(lián)運(yùn)網(wǎng)絡(luò)，運(yùn)輸弧段為39條，如圖4所示。運(yùn)輸方式有3種，分別為鐵路、公路、水運(yùn)，設(shè)定公路的運(yùn)輸速度為60km/h，水運(yùn)的速度為30km/h，鐵路的速度為50km/h。

在網(wǎng)絡(luò)中，運(yùn)輸網(wǎng)絡(luò)均采用集裝箱運(yùn)輸，各運(yùn)輸弧段不同運(yùn)輸方式的運(yùn)輸距離以及運(yùn)輸費(fèi)用如表1所示。

表1 運(yùn)輸弧段的運(yùn)輸距離以及運(yùn)輸費(fèi)用

多式聯(lián)運(yùn)網(wǎng)絡(luò)中，節(jié)點(diǎn)運(yùn)輸方式能力限制以及時間窗如表2所示。

圖4 多式聯(lián)運(yùn)網(wǎng)絡(luò)

表2 節(jié)點(diǎn)的通過能力以及時間窗

Tab.2 Node passability and time window

在多式聯(lián)運(yùn)網(wǎng)絡(luò)中，運(yùn)輸方式轉(zhuǎn)運(yùn)時間、轉(zhuǎn)運(yùn)費(fèi)用如表3所示，客戶具體貨物運(yùn)輸需求如表4所示。

表3 換裝費(fèi)用以及換裝時間

Tab.3 Transshipping cost and time

表4 貨物運(yùn)輸需求

Tab.4 Cargo transportation demand

3.2 求解結(jié)果

運(yùn)用matlab2016進(jìn)行計(jì)算，設(shè)置變異概率為0.4，交叉概率為0.9，初始種群大小為100，最大進(jìn)化次數(shù)為800次，計(jì)算時間為350s，得到Pareto最優(yōu)解集，目標(biāo)函數(shù)Pareto非劣解集的平均值如圖5所示。

采用NSGA-II算法進(jìn)行計(jì)算后，得到3個解，具體如表5所示。解集滿足了客戶對于運(yùn)輸費(fèi)用和運(yùn)輸時間的要求。

在其他條件不變的基礎(chǔ)上，改變客戶的運(yùn)輸需求，需求1的運(yùn)輸時限為180h，最大可接受費(fèi)用為360 000元，需求2的運(yùn)輸時限和最大可接受費(fèi)用分別為105h和600 000元，如表6所示。

迭代次數(shù)

表5 Pareto解集

Tab.5 Pareto solution set

表6 貨物運(yùn)輸需求

Tab.6 Cargo transportation demand

運(yùn)用NSGA-II算法求解結(jié)果如表7所示。

表7 Pareto解集

Tab.7 Pareto solution set

比較表5和表7，可以看出當(dāng)運(yùn)輸需求的最大可接受時間和最大可接受費(fèi)用發(fā)生變化時，運(yùn)輸方案會發(fā)生變化。在現(xiàn)實(shí)運(yùn)輸過程中，在制定運(yùn)輸方案時，要具體考慮客戶的運(yùn)輸需求。當(dāng)運(yùn)輸需求的最大可接受費(fèi)用較大，運(yùn)輸時限較小時，路徑選擇的過程中，會選擇運(yùn)輸速度較快和運(yùn)費(fèi)較高的公路進(jìn)行運(yùn)輸，反之，會選擇鐵路或者水運(yùn)。

4 結(jié) 論

（1）考慮節(jié)點(diǎn)不同運(yùn)輸方式的能力、不同運(yùn)輸方式的運(yùn)輸時間窗以及客戶的具體需求，構(gòu)建了運(yùn)輸成本最小、運(yùn)輸時間最少的多目標(biāo)0-1整數(shù)規(guī)劃模型，采用NSGA-II算法進(jìn)行求解，通過算例證明模型和算法的可行性和有效性。

（2）通過設(shè)定不同的運(yùn)輸需求，對不同的運(yùn)輸方案進(jìn)行分析，當(dāng)運(yùn)輸時限較小且客戶可接受的費(fèi)用較大時，運(yùn)輸方式主要選擇公路。當(dāng)運(yùn)輸時限較大且客戶可接受的費(fèi)用較小時，運(yùn)輸方式主要選擇水運(yùn)和鐵路。當(dāng)處于其他情況時，會采用公鐵水這三種方式聯(lián)運(yùn)。

本文仍存在很多進(jìn)一步研究的空間，例如考慮多式聯(lián)運(yùn)不同箱型的情況以及運(yùn)輸需求的不確定等因素，希望以后的研究在這些方面進(jìn)一步完善。

[1] 胡元, 帥宇紅. 整車物流運(yùn)輸多式聯(lián)運(yùn)與路徑優(yōu)化研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2019, 17(1): 13-18.

[2] 劉清, 朱新建, 周張穎, 等. 長江干線集裝箱多式聯(lián)運(yùn)路徑優(yōu)化模型研究[J]. 武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 2019, 43(4): 622-626.

[3] 于雪嶠, 郎茂祥, 王偉哲, 等. 考慮模糊需求的多式聯(lián)運(yùn)路徑優(yōu)化[J]. 北京交通大學(xué)報(bào), 2018, 42(3): 23-29, 36.

[4] 劉杰, 何世偉, 宋瑞, 等. 基于運(yùn)輸方式備選集的多式聯(lián)運(yùn)動態(tài)路徑優(yōu)化研究[J]. 鐵道學(xué)報(bào), 2011, 33(10): 1-6.

[5] 張小龍, 陳小鴻. 混合時間窗約束下多目標(biāo)多式聯(lián)運(yùn)路徑優(yōu)化研究[J]. 綜合運(yùn)輸, 2018, 40(8): 98-104.

[6] 魏宇. 多路徑多式聯(lián)運(yùn)網(wǎng)絡(luò)組合優(yōu)化問題研究[D]. 西安: 長安大學(xué), 2016.

[7] 熊桂武. 帶時間窗的多式聯(lián)運(yùn)運(yùn)輸優(yōu)化研究[D]. 重慶: 重慶大學(xué), 2014.

[8] 劉杰, 彭其淵, 殷勇. 低碳背景下的多式聯(lián)運(yùn)路徑規(guī)劃[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2018, 18(6): 243-249.

[9] 雷定猷, 游偉, 張英貴, 等. 長大貨物多式聯(lián)運(yùn)路徑優(yōu)化模型與算法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2014, 14(1): 75-83.

[10] 申勇, 王子蘭, 吳友發(fā). 危險(xiǎn)廢物處理設(shè)施選址-路徑模型研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2019, 17(3): 85-90, 108.

[11] 任剛, 劉暢, 高智源, 等. 考慮多周期和混合時間窗的中歐電子產(chǎn)品多式聯(lián)運(yùn)路徑選擇優(yōu)化[J]. 系統(tǒng)工程, 2019, 37(6): 67-73.

[12] 劉暢, 關(guān)秀婷, 張金偉, 等. 考慮時間價(jià)值成本的中歐筆記本電腦多式聯(lián)運(yùn)路徑優(yōu)化研究[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2019, 16(9): 2352-2359.

[13] SUN Y, LANG M. Modeling the multicommodity multimodal routing problem with schedulebased services and carbon dioxide emission costs[J]. Mathematical Problems in Engineering, 2015, 2015(4): 1-21.

[14] JAMES H B, NEIL S F. Intermodal routing of Canada–Mexico shipments under NAFTA[J]. Transportation Research Part E: Logistics and Transportation Review, 1998, 34(4): 289-303

[15] MNIF M, SADOK B. Firework algorithm for multi- objective optimization of a multimodal transportation network problem[J]. Procedia Computer Science. 2017, 112: 1670-1682.

Container Multimodal Transport Route Planning Considering the Difference in a Multi-node Time Window

TANG Yin-ying1, 2，DAI Wei-dong1，CHEN Si1, 2

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 611756, China)

Based on a multimodal transport network, a multi-objective 0-1 integer programming model with the lowest transportation cost and the smallest transportation time is constructed considering the capacity of different modes of transport, the working time window, the departure schedule, and the client’s specific cargo demand. Transportation routes are optimized by determining transportation routes and modes. The non-dominated sorting genetic algorithm II (NSGA-II) and the two-stage coding method are used to solve the model. After multiple population evolution and non-dominated solution screening, the Pareto non-inferior solution set of multimodal transport route is obtained. Finally, a multimodal transport network with 20 nodes, 39 transport arcs, and 3 modes of transport is taken as an example to analyze the feasibility and effectiveness of the algorithm and model.

multi-objective planning; path selection; time window

U169.62；F511.4

A

10.3969/j.issn.1672-4747.2020.01.005

1672-4747（2020）01-0034-09

2019-04-08

中國鐵路總公司科技研究開發(fā)計(jì)劃重點(diǎn)課題（2018BX15）；教育部人文社會科學(xué)研究西部青年基金項(xiàng)目（16XJCZH001）；四川省農(nóng)村發(fā)展研究中心項(xiàng)目（CR1716）；西南交通大學(xué)雙一流學(xué)科建設(shè)項(xiàng)目（YX1300112601801-2532）；四川民族山地經(jīng)濟(jì)發(fā)展研究中心項(xiàng)目（SDJJ1812）

湯銀英（1979—），女，漢族，河南人，博士，西南交通大學(xué)交通運(yùn)輸與物流學(xué)院副教授，主要從事運(yùn)輸組織優(yōu)化研究，E-mail：yinyingtang@swjtu.edu.cn

湯銀英，戴煒東，陳思. 考慮多節(jié)點(diǎn)時間窗差異的集裝箱多式聯(lián)運(yùn)路徑選擇研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào)，2020，18（1）：34-42.

（責(zé)任編輯：李愈）