基于改进差分进化算法的多重交通网络运输调度问题研究

徐钊

摘要：文章认为多重交通网络运输调度问题就是在特定的约束条件下允许采用不同交通运输工具的组合，差分进化算法以其自身的智能算法优势在解决这个问题时具有独特优势。然而这种算法在解决多重交通网络运输调度问题时容易陷入局部搜索困局，采用构造梯度算子可解决这一不足，并通过实例证明了这种改进算法是可行的。

关键词：多重交通网络;差分进化算法;梯度算子;遗传算法

中图分类号：U491 文献标识码：A DOI：10.13282/j.cnki.wccst.2019.10.043

文章编号：1673-4874（2019）10-0156-03

0引言

隨着我国经济的快速发展，我国的公路、铁路、航运以及航空运输都得到了迅猛发展。随着市场经济的开放，我国的交通运输压力也随之增加，在多重交通网络运输条件下，如何提高交通运输的效率以及经济效益成为了一个难题，并从最初的基本车辆路径问题上衍生出了多重交通运输网络综合调度问题。

对于这个问题，国内外学者进行了大量研究。文献基于大量数据分析，研究了在多重交通运输情况下，最优化线路以及交通运输方式组合对于提高交通运输效率和经济性的必要性。文献采用数字模拟技术分析了多重交通运输网络的优化组合问题。文献通过借鉴最新数学算法问题对多重运输网络调度问题进行了深入的分析和研究。

多重交通网络问题的优化和组合，其本质就是采用数学计算理论，结合该问题设计的环境污染、经济效益以及社会影响等因素，为交通运输选择经济性最好且节能环保的绿色运输组合。对多重交通网络问题进行研究，并提出最优化运输组合方式，对我国经济发展及节能减排具有重大意义。本文基于差分进化算法，对多重交通网络问题进行了研究，并通过实例进行分析，证明该方法对解决多重交通网络问题是可行的。

1差分进化算法介绍

差分进化算法是由国外学者Rainer和Kenneth在1997年提出的，是在遗传算法基础上进行改进的，其本质就是多目标的优化算法，这种计算方法常用于多维空间最优化问题的求解。

和遗传算法相比，两种计算方法共同点都是随机生成初始的种群，以种群中每个个体的适应度作为选择标准。这个过程包括选择、变异以及交叉三个步骤。两种算法不同之处在于：差分进化算法变异是由父代差分向量产生，和父代的个体进行选择;而遗传算法是根据适应度来控制的。差分进化算法相对于遗传算法逼近目标效果更加有效。

差分进化算法的计算过程如图1所示。

通过对多重交通网络的分析，建立交通网络最优化数学模型，充分利用差分进化算法的优势，同时考虑对计算结果会产生影响的时间价值以及时间窗口等因素，对最优化组合的交通运输方式进行分析。通过一个实例的分析验证，表明差分进化算法能够有效解决多重交通网络的组合选择问题。

2 多重交通运输网络问题分析

多重交通运输网络问题的本质，就是选择最优化组合。下面以某钢铁企业运输问题为例进行分析，钢铁企业需要将一批货物从A地运输到B地。在运输过程中需要经过m个中转站，两个中转站之间有n种运输方式可以选择，每种运输方式的费用、耗费时间以及运输能力都是不同的。且从一个运输方式转换为另外一种运输方式需要支付中转费用以及耗费一定中转时间。货物需要在规定的期限内运输到目的地，如何选择合理的运输组合方式，使规定时间内运输到目的地经济性最好，这就需要研究多重运输网络问题。

在上述约束条件情况下，求出式（1）的最优解，就能解决多重交通运输网络问题。下面采用改进差分进化算法，对上述问题进行分析。

3 改进差分进化算法

目前差分进化算法在迭代计算取得某一代种群最优解后，不能充分利用梯度信息进一步进行局部探索最优解，因此传统差分进化算法局部搜索能力不足。改进差分进化算法基于梯度寻求最优解的思想，通过构造梯度加速算子，提高了差分进化算法的局部搜索能力。为了避免计算过程中出现无效计算，在计算分析时设置一个启用要求：如果在求解某一代最优解陷入停滞状态时，启用附加操作算子，算子设计如下：

参数λ有多种计算方法，如搜索法、试算法以及微分法等。为了提高算法的效率采取了试算，即初始假定一个λ值，然后检验判定条件是否成立，如果成立就采用计算步长;如果检验条件不满足，就减小步长迭代计算。

4 算例分析

假定某钢铁厂需要将一批钢材，从场地O运输到目的地D，运输过程中需要经过P1、P2、P3、P4中转城市，在各个点之间交通运输方式有航空、火车、水运以及轮船四种方式，各种运输方式的运输费用F、时间T、能力A如表1所示。

在每个中转点转换交通运输工具，就会涉及到中转时间和中转费用，在各个中转城市之间的中转时间以及中转费用如表2所示。

采用改进的差分进化算法对综合交通运输方案进行分析，假定需要运输钢材800t，根据相关市场调研资料，各参数取值如下：Fmin=0.65、Fmox=0.92、θ=110，每个步骤迭代次数为300次，进行10次迭代计算。计算过程如图2所示。

通过分析可以看出，最低运输费用为8192元，各种交通运输组合方式为起点O→P1→P2→P3采用火车运输，P3→P4采用汽车运输，P4→D采用轮船进行运输。

5 结语

多重交通运输调度问题其本质就是对于多种交通运输方式组合的最优化选择问题，从而使得经济性和效率达到最优。差分进化算法以其自身全局并行和直接搜索的特点，在解决这个多重交通组合的问题上，比其他智能算法更具有优越性。但是差分进化算法在求解后期，容易陷入局部最优解的求解问题。为了解决这个问题，在既有的差分进化算法基础上，构造了梯度算子，解决了算法最优化求解问题，提高了计算效率和精度。通过实例分析表明，改进的差分进化算法在解决多重交通运输调度问题上具有较高的计算速度和准确性。