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

梅夢婷 米小珍 鄭曉軍

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

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

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

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

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

1 ?數(shù)學模型構建

1.1 ?問題描述

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

1.2 ?模型假設

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

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

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

3） 節(jié)點處設施設備均滿足運輸方式轉換的條件;

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

5） 換裝成本只與換裝單價和貨運量相關;

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

1.3 ?符號說明

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

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

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

2 ?模型求解

2.1 ?模型轉換

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

2.2 ?算法求解

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

圖1 ?DE?NSGAⅡ流程圖

主要要素設計如下：

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

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

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

3） 變異算子。通過父代個體間的差異實現(xiàn)對目標個體的擾動：

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

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

3 ?實驗與結果分析

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

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

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

貨物用20TEU標準箱裝載，標準箱平均裝載17.5 t貨物，故選用6個集裝箱裝載。班期時刻以整點計算。

分段制計算運輸成本，直接運輸成本與運輸基價、運輸距離及貨物重量相關。不同運輸方式的運輸基價、運輸速度和單位碳排放量見表1，運輸中轉的成本、時間和單位碳排放量見表2。

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

表1 ?運輸速度、運輸基價及碳排放量

表2 ?中轉成本、中轉時間和碳排放

3.2 ?結果與分析

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

貨物從廣州運輸?shù)缴蜿?，兩種算法分別進行30次獨立運算，圖3給出兩種算法下Pareto解集的空間分布圖，圖4為算例迭代過程中各目標均值比較，表3綜合30次測試結果總結兩種算法的對比分析結果。

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

圖3 ?Pareto解集空間分布

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

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

表3 ?算法結果對比分析

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

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

4 ?結 ?語

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

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

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

參考文獻

[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] 何艷梅，何俊生.多目標多式聯(liá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ō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)運路徑選擇評價方法[J].北京交通大學學報（社會科學版），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] 李玉民，郭曉燕，楊露.考慮多目標的中歐集裝箱多式聯(lián)運路徑選擇[J].鐵道科學與工程學報，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ōu)化模型及其求解算法[J].鐵道科學與工程學報，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ōu)化研究[J].中國科技論文，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ī)劃及應用[M].北京：清華大學出版社，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ōu)化研究[D].北京：北京交通大學，2016.

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

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

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

[13] 陶文華，劉洪濤.基于差分進化與NSGA?Ⅱ的多目標優(yōu)化算法[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].計算機工程與應用，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.