基于DE和NSGAⅡ的集装箱多式联运的路径优化算法

梅梦婷 米小珍 郑晓军

摘  要： 考虑集装箱多式联运过程中时间参数的不确定性，引入三角模糊数用于表示在途时间和中转时间，同时考虑班期产生的等待时间，将碳排放纳入考量范畴，建立基于时间、成本和碳排放量的多目标模型。提出基于DE和NSGA?Ⅱ的DE?NSGAⅡ多目标优化算法，该算法通过差分方法模拟NSGA?Ⅱ的交叉和变异算子及自适应控制策略调整交叉因子和缩放因子来提高算法搜索能力。实例表明，在求解组合优化问题时，DE?NSGAⅡ算法的Pareto最优解集分布更均匀，收敛速度更快，证明了DE?NSGAⅡ算法的可行性和优越性。

关键词： 集装箱多式联运; NSGA?Ⅱ; 差分算法; 碳排放; 多目标模型; 优化算法

中图分类号： 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  引  言

多式联运是指通过多种运输方式相互承接、转运而共同完成运输任务的过程。目前国内外关于多式联运的研究内容主要有：文献[1]基于最短路径问题提出时间依赖性的单源单目标多式联运网络模型，设计相关算例求解;文献[2?4]建立了基于成本和时间的路径优化模型并求解;文献[5]利用决策分析方法从经济、社会、环境方面构建了不确定环境下的多式联运路径评价指标体系，为决策者提供合理运输方案;文献[6]从运输时间、费用和碳排放三方面构建了多目标优化模型并利用权重系数法转换为单目标求解;文献[7]针对时间不确定性，构建了具有时效性的协同优化模型，采用智能算法得到了有效求解;文献[8]以班期限制为出发点构建决策模型，验证了模型中考虑班期限制更为合理。

现有研究主要针对运输成本和时间，运输碳排放对社会造成的影响考虑欠缺;选用权重系数法或决策方法求解多目标问题，结果具有主观随意性;此外考虑在途时间和换装时间，忽略了实际运输过程中的不确定性因素以及铁路和水路存在确定的发班时间。

本文采用三角模糊數表示运输和中转时间，加入铁路、水路的班期产生的等待时间，结合运输成本、时间和碳排放量构建多目标模型。以带精英策略的非支配排序遗传算法（Non?dominated Sorting Genetic Algorithm，NSGA?Ⅱ）为理论基础，提出DE?NSGAⅡ算法，采用差分算法（Differential Evolution，DE）的变异交叉策略，同时利用自适应控制策略调整变异交叉扰动能力。设计算例求解，对比DE?NSGAⅡ与NSGA?Ⅱ求解相关问题的性能优劣。

1  数学模型构建

1.1  问题描述

以集装箱装载的形式将一批货物从起始城市[o]送往目的城市[d]，中间有[N]个城市节点，城市之间提供多种运输方式，各城市节点可以转换运输方式。考虑到运输过程中不确定因素的干扰，运行时间和转换时间可能有误差，故用模糊数表示。运输过程综合考量成本、运输时间和碳排放量三个目标，求解提供最优运输方案。

1.2  模型假设

对多式联运组合优化模型提出以下假设条件：

1） 货物不可分，即相邻节点间的直接运输由单一运输方式承担;

2） 运输方式的承接转运只发生在城市节点处;

3） 节点处设施设备均满足运输方式转换的条件;

4） 货物运输成本与运输方式、节点间的距离以及货运量相关;

5） 换装成本只与换装单价和货运量相关;

6） 货物运输过程产生的碳排放量与运输方式使用的燃料消耗量相关。

1.3  符号说明

该模型的优化目标式（1）表示货物运输成本最小，包括直接运输成本和换装成本;式（2）表示货物运输时间最短，由直接运输时间、换装时间以及换装后等待最近班期出发的时间组成;式（3）表示直接运输以及中转运输产生的总碳排放量最少。

在约束条件中，式（4）保证流量守恒，从起始点[o]出发，终止于终点[d];式（5）和式（6）为决策变量的取值约束;式（7）表示相邻运输节点之间选择单一运输方式;式（8）表示货物中转选择单一运输方式;式（9）保证运输过程的连续性，如果在节点[j]运输方式由[k]转换为[l]，则表明从节点[i]到节点[j]，运输方式为[k];节点[j]到节点[p]，运输方式为[l];式（10）表示货物在[j]点换装结束时刻与在上一节点[i]出发时刻、运输耗时以及在[j]点换装耗时相关;式（11）保证货物在节点的出发时刻按照班期表执行（公路运输不存在班期约束问题）[8]。

其中，式（2）目标函数的运输时间[tkij]和中转时间[tklj]具有不确定性，用三角模糊数进行表示，即：

2  模型求解

2.1  模型转换

不确定参数运输时间和中转时间，不便于模型直接求解，可以对其进行确定性转换。不确定规划的变量处理方法主要有机会约束规划、期望值法以及相关机会规划[9]。本文借鉴文献[10]提出的理论清晰化模糊规划，将约束规划转化为确定的等价数学规划。转换后的模型为：

2.2  算法求解

融合DE算法和NSGA?Ⅱ算法的DE?NSGAⅡ进化多目标优化算法，继承了NSGA?Ⅱ算法的快速非支配排序和种群多样性保持策略，采用差分方式进行变异交叉操作，同时利用自适应控制策略调整变异交叉扰动能力，提高NSGA?Ⅱ搜索能力。算法的基本步骤如图1所示。

图1  DE?NSGAⅡ流程图

主要要素设计如下：

1） 染色体编码。同时考虑节点和运输方式因素，选用矩阵编码方法，以矩阵为染色体个体进行遗传运算，既能降低运算复杂度，又可以保持子代个体基因的完整性[12]。

种群的矩阵编码方式定义如下：种群规模为[s]，第[k]代种群[Pk={A1，A2，…，As}]，其中，[Ai]表示[k]代种群中第[i]个个体，即矩阵染色体，[aiuv]表示矩阵染色体的基因元素，其中，[i∈{1，2，…，s}]，[u，v∈{1，2，…，n}]。

2） 染色体解码。矩阵[Ai]大小取决于运输网络节点数，染色体基因元素[aiuv]与节点运输方式相关，分别取1，2，3表示公路、铁路和水路三种运输方式。如矩阵[A]表示为4节点运输网络，[a12]=2，表示节点1到节点2采用第2种运输方式，即铁路，其余取Inf，表示节点之间不连通。染色体解码表示该运输路径为：1→2→3→4，运输方式分别为2（铁路）→3（水路）→1（公路）。

3） 变异算子。通过父代个体间的差异实现对目标个体的扰动：

4） 交叉算子。将变异个体与其相应的父代个体相互交叉产生个体：

5） 自适应变异操作。[F]，[cr]参数具有难调性，对其采取动态调整策略，从而提高算法初期全局搜索能力及后期局部搜索能力[14]。交叉因子和缩放因子为：

3  实验与结果分析

多目标非支配解集质量评价从空间分布性和收敛性两方面展开，分别用于权衡Pareto解集的质量及算法的寻优能力[13]。本文采用DE?NSGAⅡ算法求解路径优化问题，通过实例比较DE?NSGAⅡ算法和NSGA?Ⅱ的解集空间分布情况和迭代收敛趋势。实验程序均用Matlab编写，在Matlab R2014a环境下运行。

3.1  算例数据

构造广州—沈陽运输网络如图2所示，货物重量为100 t，8：00装载完毕等待运输。

货物用20TEU标准箱装载，标准箱平均装载17.5 t货物，故选用6个集装箱装载。班期时刻以整点计算。

分段制计算运输成本，直接运输成本与运输基价、运输距离及货物重量相关。不同运输方式的运输基价、运输速度和单位碳排放量见表1，运输中转的成本、时间和单位碳排放量见表2。

图2  广州—沈阳集装箱多式联运网络图

表1  运输速度、运输基价及碳排放量

表2  中转成本、中转时间和碳排放

3.2  结果与分析

设置种群规模[NP=80]，最大进化代数[Gmax=200]，交叉概率[Pc=0.8，Pm=0.05];DE?NSGAⅡ算法中，初始交叉因子[CR0]=0.4，初始缩放因子[F0]=0.4。

货物从广州运输到沈阳，两种算法分别进行30次独立运算，图3给出两种算法下Pareto解集的空间分布图，图4为算例迭代过程中各目标均值比较，表3综合30次测试结果总结两种算法的对比分析结果。

比较图3的Pareto最优解集空间分布可知，DE?NSGAⅡ算法的Pareto最优解集空间分布比NSGA?Ⅱ均匀，即DE?NSGAⅡ算法能够获得较高质量的Pareto最优解。

图3  Pareto解集空间分布

从图4目标函数均值迭代过程来看，运行前期算法都稍有波动，但DE?NSGAⅡ算法在120代后趋于稳定达到收敛，NSGA?Ⅱ迭代过程波动较大，截止算法终止仍未达到收敛，DE?NSGAⅡ算法收敛速度优于NSGA?Ⅱ。

由表3可知，DE?NSGAⅡ算法运行时间比NSGA?Ⅱ算法长，DE?NSGAⅡ由DE和NSGA?Ⅱ串联而成，其执行循环相当于对DE和NSGA?Ⅱ依次执行循环，故在时间复杂度方面弱于NSGA?Ⅱ。

表3  算法结果对比分析

综合30次运算比较，DE?NSGAⅡ求得的Pareto解集数量平均数、最大/最小Pareto解集数均大于NSGA?Ⅱ，算法运行结果更稳定，提供运输方案更为全面。

图4  算法不同目标函数均值比较

4  结  语

为向承运人提供合理的运输方案，提高运输效率，将碳排放量纳入考量范围，结合实际运输中不确定环境和班期时刻的影响，从时间、成本和碳排放三个角度建立多目标优化模型。采用DE?NSGAⅡ算法求解Pareto解集，算例证明，在大规模运输网络下DE?NSGAⅡ算法求解的Pareto解集质量数量及空间分布、算法的收敛性均优于NSGA?Ⅱ，进一步验证了DE?NSGAⅡ算法求解路径优化问题的可行性。

多式联运实际运输过程复杂繁琐，仍有诸多实际情况需要考虑，如节点运输能力对运输货物的限制，货物装箱策略等，且提出的算法仍有不足，如大规模数据计算下时间复杂度较高等，都将作為下一步研究工作的主要内容。

注：本文通讯作者为米小珍。

参考文献

[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] 何艳梅，何俊生.多目标多式联运配送路径研究[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] 周骞，白云卯，徐春龙.基于遗传算法的多式联运物流运输配送路径优化研究[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] 胡辉，顾丽琴，查伟雄.不确定环境下基于ELECTRE的多式联运路径选择评价方法[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] 李玉民，郭晓燕，杨露.考虑多目标的中欧集装箱多式联运路径选择[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] 张得志，李双艳.不确定环境下协同运输优化模型及其求解算法[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] 彭勇，刘星，罗佳，等.考虑班期限制的货物多式联运路径优化研究[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] 刘宝碇，赵瑞清，王纲.不确定规划及应用[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] 刘艳芳.考虑模糊需求的多式联运路径优化研究[D].北京：北京交通大学，2016.

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

[12] 王碧鹤.港口集装箱多式联运路径与运输方式组合优化研究[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?Ⅱ的多目标优化算法[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.