基于DE和NSGAⅡ的集裝箱多式聯(lián)運(yùn)的路徑優(yōu)化算法

梅夢(mèng)婷 米小珍 鄭曉軍

摘 ?要： 考慮集裝箱多式聯(lián)運(yùn)過(guò)程中時(shí)間參數(shù)的不確定性，引入三角模糊數(shù)用于表示在途時(shí)間和中轉(zhuǎn)時(shí)間，同時(shí)考慮班期產(chǎn)生的等待時(shí)間，將碳排放納入考量范疇，建立基于時(shí)間、成本和碳排放量的多目標(biāo)模型。提出基于DE和NSGA?Ⅱ的DE?NSGAⅡ多目標(biāo)優(yōu)化算法，該算法通過(guò)差分方法模擬NSGA?Ⅱ的交叉和變異算子及自適應(yīng)控制策略調(diào)整交叉因子和縮放因子來(lái)提高算法搜索能力。實(shí)例表明，在求解組合優(yōu)化問(wèn)題時(shí)，DE?NSGAⅡ算法的Pareto最優(yōu)解集分布更均勻，收斂速度更快，證明了DE?NSGAⅡ算法的可行性和優(yōu)越性。

關(guān)鍵詞： 集裝箱多式聯(lián)運(yùn); NSGA?Ⅱ; 差分算法; 碳排放; 多目標(biāo)模型; 優(yōu)化算法

中圖分類號(hào)： TN911.1?34; U169 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）15?0144?06

Path optimization algorithm for container multimodal transportation

based on DE and NSGA?Ⅱ

MEI Mengting1， MI Xiaozhen1， ZHENG Xiaojun2

（1.School of Transportation and Transportation Engineering， Dalian Jiaotong University， Dalian 116028， China;

2.School of Mechanical Engineering， Dalian Jiaotong University， Dalian 116028， China）

Abstract：In consideration of the uncertainty of time parameters during container multimodal transportation， triangular fuzzy numbers are introduced to express the haulage time and transit time， while the waiting time produced in the time period is considered. Taking carbon emissions into consideration， a multi?objective model based on time， cost and carbon emissions is established. A DE?NSGAⅡ hybrid multi?objective optimization algorithm based on DE and NSGA?Ⅱ is proposed， which simulates the crossover and mutation operators of NSGA?Ⅱ by means of the difference method， and adjusts the cross factor and scaling factor of the adaptive control strategy to improve the search ability of the algorithm. The example shows that the Pareto optimal solution set distribution of DE?NSGAⅡ is more uniform and has faster convergence speed when solving the combinatorial optimization problem， which proves the feasibility and superiority of the hybrid algorithm.

Keywords： container multimodal transportation; NSGA?Ⅱ; differential evolution; carbon emission; timetable; multi?objective model; optimization algorithm

0 ?引 ?言

多式聯(lián)運(yùn)是指通過(guò)多種運(yùn)輸方式相互承接、轉(zhuǎn)運(yùn)而共同完成運(yùn)輸任務(wù)的過(guò)程。目前國(guó)內(nèi)外關(guān)于多式聯(lián)運(yùn)的研究?jī)?nèi)容主要有：文獻(xiàn)[1]基于最短路徑問(wèn)題提出時(shí)間依賴性的單源單目標(biāo)多式聯(lián)運(yùn)網(wǎng)絡(luò)模型，設(shè)計(jì)相關(guān)算例求解;文獻(xiàn)[2?4]建立了基于成本和時(shí)間的路徑優(yōu)化模型并求解;文獻(xiàn)[5]利用決策分析方法從經(jīng)濟(jì)、社會(huì)、環(huán)境方面構(gòu)建了不確定環(huán)境下的多式聯(lián)運(yùn)路徑評(píng)價(jià)指標(biāo)體系，為決策者提供合理運(yùn)輸方案;文獻(xiàn)[6]從運(yùn)輸時(shí)間、費(fèi)用和碳排放三方面構(gòu)建了多目標(biāo)優(yōu)化模型并利用權(quán)重系數(shù)法轉(zhuǎn)換為單目標(biāo)求解;文獻(xiàn)[7]針對(duì)時(shí)間不確定性，構(gòu)建了具有時(shí)效性的協(xié)同優(yōu)化模型，采用智能算法得到了有效求解;文獻(xiàn)[8]以班期限制為出發(fā)點(diǎn)構(gòu)建決策模型，驗(yàn)證了模型中考慮班期限制更為合理。

現(xiàn)有研究主要針對(duì)運(yùn)輸成本和時(shí)間，運(yùn)輸碳排放對(duì)社會(huì)造成的影響考慮欠缺;選用權(quán)重系數(shù)法或決策方法求解多目標(biāo)問(wèn)題，結(jié)果具有主觀隨意性;此外考慮在途時(shí)間和換裝時(shí)間，忽略了實(shí)際運(yùn)輸過(guò)程中的不確定性因素以及鐵路和水路存在確定的發(fā)班時(shí)間。

本文采用三角模糊數(shù)表示運(yùn)輸和中轉(zhuǎn)時(shí)間，加入鐵路、水路的班期產(chǎn)生的等待時(shí)間，結(jié)合運(yùn)輸成本、時(shí)間和碳排放量構(gòu)建多目標(biāo)模型。以帶精英策略的非支配排序遺傳算法（Non?dominated Sorting Genetic Algorithm，NSGA?Ⅱ）為理論基礎(chǔ)，提出DE?NSGAⅡ算法，采用差分算法（Differential Evolution，DE）的變異交叉策略，同時(shí)利用自適應(yīng)控制策略調(diào)整變異交叉擾動(dòng)能力。設(shè)計(jì)算例求解，對(duì)比DE?NSGAⅡ與NSGA?Ⅱ求解相關(guān)問(wèn)題的性能優(yōu)劣。

1 ?數(shù)學(xué)模型構(gòu)建

1.1 ?問(wèn)題描述

以集裝箱裝載的形式將一批貨物從起始城市[o]送往目的城市[d]，中間有[N]個(gè)城市節(jié)點(diǎn)，城市之間提供多種運(yùn)輸方式，各城市節(jié)點(diǎn)可以轉(zhuǎn)換運(yùn)輸方式。考慮到運(yùn)輸過(guò)程中不確定因素的干擾，運(yùn)行時(shí)間和轉(zhuǎn)換時(shí)間可能有誤差，故用模糊數(shù)表示。運(yùn)輸過(guò)程綜合考量成本、運(yùn)輸時(shí)間和碳排放量三個(gè)目標(biāo)，求解提供最優(yōu)運(yùn)輸方案。

1.2 ?模型假設(shè)

對(duì)多式聯(lián)運(yùn)組合優(yōu)化模型提出以下假設(shè)條件：

1） 貨物不可分，即相鄰節(jié)點(diǎn)間的直接運(yùn)輸由單一運(yùn)輸方式承擔(dān);

2） 運(yùn)輸方式的承接轉(zhuǎn)運(yùn)只發(fā)生在城市節(jié)點(diǎn)處;

3） 節(jié)點(diǎn)處設(shè)施設(shè)備均滿足運(yùn)輸方式轉(zhuǎn)換的條件;

4） 貨物運(yùn)輸成本與運(yùn)輸方式、節(jié)點(diǎn)間的距離以及貨運(yùn)量相關(guān);

5） 換裝成本只與換裝單價(jià)和貨運(yùn)量相關(guān);

6） 貨物運(yùn)輸過(guò)程產(chǎn)生的碳排放量與運(yùn)輸方式使用的燃料消耗量相關(guān)。

1.3 ?符號(hào)說(shuō)明

該模型的優(yōu)化目標(biāo)式（1）表示貨物運(yùn)輸成本最小，包括直接運(yùn)輸成本和換裝成本;式（2）表示貨物運(yùn)輸時(shí)間最短，由直接運(yùn)輸時(shí)間、換裝時(shí)間以及換裝后等待最近班期出發(fā)的時(shí)間組成;式（3）表示直接運(yùn)輸以及中轉(zhuǎn)運(yùn)輸產(chǎn)生的總碳排放量最少。

在約束條件中，式（4）保證流量守恒，從起始點(diǎn)[o]出發(fā)，終止于終點(diǎn)[d];式（5）和式（6）為決策變量的取值約束;式（7）表示相鄰運(yùn)輸節(jié)點(diǎn)之間選擇單一運(yùn)輸方式;式（8）表示貨物中轉(zhuǎn)選擇單一運(yùn)輸方式;式（9）保證運(yùn)輸過(guò)程的連續(xù)性，如果在節(jié)點(diǎn)[j]運(yùn)輸方式由[k]轉(zhuǎn)換為[l]，則表明從節(jié)點(diǎn)[i]到節(jié)點(diǎn)[j]，運(yùn)輸方式為[k];節(jié)點(diǎn)[j]到節(jié)點(diǎn)[p]，運(yùn)輸方式為[l];式（10）表示貨物在[j]點(diǎn)換裝結(jié)束時(shí)刻與在上一節(jié)點(diǎn)[i]出發(fā)時(shí)刻、運(yùn)輸耗時(shí)以及在[j]點(diǎn)換裝耗時(shí)相關(guān);式（11）保證貨物在節(jié)點(diǎn)的出發(fā)時(shí)刻按照班期表執(zhí)行（公路運(yùn)輸不存在班期約束問(wèn)題）[8]。

其中，式（2）目標(biāo)函數(shù)的運(yùn)輸時(shí)間[tkij]和中轉(zhuǎn)時(shí)間[tklj]具有不確定性，用三角模糊數(shù)進(jìn)行表示，即：

2 ?模型求解

2.1 ?模型轉(zhuǎn)換

不確定參數(shù)運(yùn)輸時(shí)間和中轉(zhuǎn)時(shí)間，不便于模型直接求解，可以對(duì)其進(jìn)行確定性轉(zhuǎn)換。不確定規(guī)劃的變量處理方法主要有機(jī)會(huì)約束規(guī)劃、期望值法以及相關(guān)機(jī)會(huì)規(guī)劃[9]。本文借鑒文獻(xiàn)[10]提出的理論清晰化模糊規(guī)劃，將約束規(guī)劃轉(zhuǎn)化為確定的等價(jià)數(shù)學(xué)規(guī)劃。轉(zhuǎn)換后的模型為：

2.2 ?算法求解

融合DE算法和NSGA?Ⅱ算法的DE?NSGAⅡ進(jìn)化多目標(biāo)優(yōu)化算法，繼承了NSGA?Ⅱ算法的快速非支配排序和種群多樣性保持策略，采用差分方式進(jìn)行變異交叉操作，同時(shí)利用自適應(yīng)控制策略調(diào)整變異交叉擾動(dòng)能力，提高NSGA?Ⅱ搜索能力。算法的基本步驟如圖1所示。

圖1 ?DE?NSGAⅡ流程圖

主要要素設(shè)計(jì)如下：

1） 染色體編碼。同時(shí)考慮節(jié)點(diǎn)和運(yùn)輸方式因素，選用矩陣編碼方法，以矩陣為染色體個(gè)體進(jìn)行遺傳運(yùn)算，既能降低運(yùn)算復(fù)雜度，又可以保持子代個(gè)體基因的完整性[12]。

種群的矩陣編碼方式定義如下：種群規(guī)模為[s]，第[k]代種群[Pk={A1，A2，…，As}]，其中，[Ai]表示[k]代種群中第[i]個(gè)個(gè)體，即矩陣染色體，[aiuv]表示矩陣染色體的基因元素，其中，[i∈{1，2，…，s}]，[u，v∈{1，2，…，n}]。

2） 染色體解碼。矩陣[Ai]大小取決于運(yùn)輸網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，染色體基因元素[aiuv]與節(jié)點(diǎn)運(yùn)輸方式相關(guān)，分別取1，2，3表示公路、鐵路和水路三種運(yùn)輸方式。如矩陣[A]表示為4節(jié)點(diǎn)運(yùn)輸網(wǎng)絡(luò)，[a12]=2，表示節(jié)點(diǎn)1到節(jié)點(diǎn)2采用第2種運(yùn)輸方式，即鐵路，其余取Inf，表示節(jié)點(diǎn)之間不連通。染色體解碼表示該運(yùn)輸路徑為：1→2→3→4，運(yùn)輸方式分別為2（鐵路）→3（水路）→1（公路）。

3） 變異算子。通過(guò)父代個(gè)體間的差異實(shí)現(xiàn)對(duì)目標(biāo)個(gè)體的擾動(dòng)：

4） 交叉算子。將變異個(gè)體與其相應(yīng)的父代個(gè)體相互交叉產(chǎn)生個(gè)體：

5） 自適應(yīng)變異操作。[F]，[cr]參數(shù)具有難調(diào)性，對(duì)其采取動(dòng)態(tài)調(diào)整策略，從而提高算法初期全局搜索能力及后期局部搜索能力[14]。交叉因子和縮放因子為：

3 ?實(shí)驗(yàn)與結(jié)果分析

多目標(biāo)非支配解集質(zhì)量評(píng)價(jià)從空間分布性和收斂性兩方面展開(kāi)，分別用于權(quán)衡Pareto解集的質(zhì)量及算法的尋優(yōu)能力[13]。本文采用DE?NSGAⅡ算法求解路徑優(yōu)化問(wèn)題，通過(guò)實(shí)例比較DE?NSGAⅡ算法和NSGA?Ⅱ的解集空間分布情況和迭代收斂趨勢(shì)。實(shí)驗(yàn)程序均用Matlab編寫(xiě)，在Matlab R2014a環(huán)境下運(yùn)行。

3.1 ?算例數(shù)據(jù)

構(gòu)造廣州—沈陽(yáng)運(yùn)輸網(wǎng)絡(luò)如圖2所示，貨物重量為100 t，8：00裝載完畢等待運(yùn)輸。

貨物用20TEU標(biāo)準(zhǔn)箱裝載，標(biāo)準(zhǔn)箱平均裝載17.5 t貨物，故選用6個(gè)集裝箱裝載。班期時(shí)刻以整點(diǎn)計(jì)算。

分段制計(jì)算運(yùn)輸成本，直接運(yùn)輸成本與運(yùn)輸基價(jià)、運(yùn)輸距離及貨物重量相關(guān)。不同運(yùn)輸方式的運(yùn)輸基價(jià)、運(yùn)輸速度和單位碳排放量見(jiàn)表1，運(yùn)輸中轉(zhuǎn)的成本、時(shí)間和單位碳排放量見(jiàn)表2。

圖2 ?廣州—沈陽(yáng)集裝箱多式聯(lián)運(yùn)網(wǎng)絡(luò)圖

表1 ?運(yùn)輸速度、運(yùn)輸基價(jià)及碳排放量

表2 ?中轉(zhuǎn)成本、中轉(zhuǎn)時(shí)間和碳排放

3.2 ?結(jié)果與分析

設(shè)置種群規(guī)模[NP=80]，最大進(jìn)化代數(shù)[Gmax=200]，交叉概率[Pc=0.8，Pm=0.05];DE?NSGAⅡ算法中，初始交叉因子[CR0]=0.4，初始縮放因子[F0]=0.4。

貨物從廣州運(yùn)輸?shù)缴蜿?yáng)，兩種算法分別進(jìn)行30次獨(dú)立運(yùn)算，圖3給出兩種算法下Pareto解集的空間分布圖，圖4為算例迭代過(guò)程中各目標(biāo)均值比較，表3綜合30次測(cè)試結(jié)果總結(jié)兩種算法的對(duì)比分析結(jié)果。

比較圖3的Pareto最優(yōu)解集空間分布可知，DE?NSGAⅡ算法的Pareto最優(yōu)解集空間分布比NSGA?Ⅱ均勻，即DE?NSGAⅡ算法能夠獲得較高質(zhì)量的Pareto最優(yōu)解。

圖3 ?Pareto解集空間分布

從圖4目標(biāo)函數(shù)均值迭代過(guò)程來(lái)看，運(yùn)行前期算法都稍有波動(dòng)，但DE?NSGAⅡ算法在120代后趨于穩(wěn)定達(dá)到收斂，NSGA?Ⅱ迭代過(guò)程波動(dòng)較大，截止算法終止仍未達(dá)到收斂，DE?NSGAⅡ算法收斂速度優(yōu)于NSGA?Ⅱ。

由表3可知，DE?NSGAⅡ算法運(yùn)行時(shí)間比NSGA?Ⅱ算法長(zhǎng)，DE?NSGAⅡ由DE和NSGA?Ⅱ串聯(lián)而成，其執(zhí)行循環(huán)相當(dāng)于對(duì)DE和NSGA?Ⅱ依次執(zhí)行循環(huán)，故在時(shí)間復(fù)雜度方面弱于NSGA?Ⅱ。

表3 ?算法結(jié)果對(duì)比分析

綜合30次運(yùn)算比較，DE?NSGAⅡ求得的Pareto解集數(shù)量平均數(shù)、最大/最小Pareto解集數(shù)均大于NSGA?Ⅱ，算法運(yùn)行結(jié)果更穩(wěn)定，提供運(yùn)輸方案更為全面。

圖4 ?算法不同目標(biāo)函數(shù)均值比較

4 ?結(jié) ?語(yǔ)

為向承運(yùn)人提供合理的運(yùn)輸方案，提高運(yùn)輸效率，將碳排放量納入考量范圍，結(jié)合實(shí)際運(yùn)輸中不確定環(huán)境和班期時(shí)刻的影響，從時(shí)間、成本和碳排放三個(gè)角度建立多目標(biāo)優(yōu)化模型。采用DE?NSGAⅡ算法求解Pareto解集，算例證明，在大規(guī)模運(yùn)輸網(wǎng)絡(luò)下DE?NSGAⅡ算法求解的Pareto解集質(zhì)量數(shù)量及空間分布、算法的收斂性均優(yōu)于NSGA?Ⅱ，進(jìn)一步驗(yàn)證了DE?NSGAⅡ算法求解路徑優(yōu)化問(wèn)題的可行性。

多式聯(lián)運(yùn)實(shí)際運(yùn)輸過(guò)程復(fù)雜繁瑣，仍有諸多實(shí)際情況需要考慮，如節(jié)點(diǎn)運(yùn)輸能力對(duì)運(yùn)輸貨物的限制，貨物裝箱策略等，且提出的算法仍有不足，如大規(guī)模數(shù)據(jù)計(jì)算下時(shí)間復(fù)雜度較高等，都將作為下一步研究工作的主要內(nèi)容。

注：本文通訊作者為米小珍。

參考文獻(xiàn)

[1] IDRI Abdelfattah， OUKARFI Mariyem， BOULMAKOUL Azedine， et al. A new time?dependent shortest path algorithm for multimodal transportation network [J]. Procedia computer science， 2017， 109： 692?697.

[2] 何艷梅，何俊生.多目標(biāo)多式聯(lián)運(yùn)配送路徑研究[J].物流科技，2013（5）：112?114.

HE Yanmei， HE Junsheng. Researchon multimode transport distribution routes with objects [J]. Logistics sci?tech， 2013（5）： 112?114.

[3] 周騫，白云卯，徐春龍.基于遺傳算法的多式聯(lián)運(yùn)物流運(yùn)輸配送路徑優(yōu)化研究[J].物流工程與管理，2015（1）：89?91.

ZHOU Qian， BAI Yunmao， XU Chunlong. The Research of logistics distribution routing optimization on multimodal transportation based on genetic algorithm [J]. Logistics engineering and management， 2015（1）： 89?91.

[4] MNIF Mouna， BOUAMAMA Sadok. Firework algorithm for multi?objective optimization of a multimodal transportation network problem [J]. Procedia computer science， 2017， 112： 1670?1682.

[5] 胡輝，顧麗琴，查偉雄.不確定環(huán)境下基于ELECTRE的多式聯(lián)運(yùn)路徑選擇評(píng)價(jià)方法[J].北京交通大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2017（4）：88?97.

HU Hui， GU Liqin， ZHA Weixiong. An ELECTRE?based eva?luation method under uncertainty for multi?modal route selection [J]. Journal of Beijing Jiaotong University （Social sciences edition）， 2017（4）： 88?97.

[6] 李玉民，郭曉燕，楊露.考慮多目標(biāo)的中歐集裝箱多式聯(lián)運(yùn)路徑選擇[J].鐵道科學(xué)與工程學(xué)報(bào)，2017，14（10）：2239?2248.

LI Yumin， GUO Xiaoyan， YANG Lu. Route optimization of China?EU container multimodal transport considering various factors [J]. Journal of railway science and engineering， 2017， 14（10）：2239?2248.

[7] 張得志，李雙艷.不確定環(huán)境下協(xié)同運(yùn)輸優(yōu)化模型及其求解算法[J].鐵道科學(xué)與工程學(xué)報(bào)，2010，7（4）：116?120.

ZHANG Dezhi， LI Shuangyan. An optimization model for coordination transportation and its solution algorithm under certain environment [J]. Journal of railway science and engineering， 2010， 7（4）： 116?120.

[8] 彭勇，劉星，羅佳，等.考慮班期限制的貨物多式聯(lián)運(yùn)路徑優(yōu)化研究[J].中國(guó)科技論文，2017（7）：787?792.

PENG Yong， LIU Xing， LUO Jia， et al. Study on the route optimization under schedule limits of multimodal transport of goods [J]. China sciencepaper， 2017（7）： 787?792.

[9] 劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用[M].北京：清華大學(xué)出版社，2003.

LIU Baoding， ZHAO Ruiqing， WANG Gang. Uncertain programming with applications [M]. Beijing： Tsinghua University Press， 2003.

[10] LIU Baoding， IWAMURA K. Chance constrained programming with fuzzy parements [J]. Fuzzy Sets and Systems， 1998， 94（2）： 227?237.

[11] 劉艷芳.考慮模糊需求的多式聯(lián)運(yùn)路徑優(yōu)化研究[D].北京：北京交通大學(xué)，2016.

LIU Yanfang. Study on the multimodal routing optimization with fuzzy customer demands [D]. Beijing： Beijing Jiaotong University， 2016.

[12] 王碧鶴.港口集裝箱多式聯(lián)運(yùn)路徑與運(yùn)輸方式組合優(yōu)化研究[D].北京：北京交通大學(xué)，2015.

WANG Bihe. Research on combinatorial optimization for route and model of seaport container multimodal transport [D]. Beijing： Beijing Jiaotong University， 2015.

[13] 陶文華，劉洪濤.基于差分進(jìn)化與NSGA?Ⅱ的多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)工程，2016，42（11）：219?224.

TAO Wenhua， LIU Hongtao. Multi?objective optimization algorithm based on differential evolution and NSGA?Ⅱ [J]. Computer engineering， 2016， 42（11）： 219?224.

[14] 譚躍，譚冠政，涂立.具有局部搜索策略的差分進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2009（7）：56?58.

TAN Yue， TAN Guanzheng， TU Li. Differential evolution algorithm with local search strategy [J]. Computer engineering and applications， 2009（7）： 56?58.