孙 哲，刘晨磊，孙知信 （南京邮电大学，江苏 南京 210003）

0 引言

在贸易全球化的现在，各物流公司更加有效地优化和管理物流环节是很有必要的。其中，最重要的一种实现方法就是对货物进行物流运输时车辆路线进行合理的规划，因为这不仅可以降低运输成本，还对提升服务质量起到重要作用。经典的车辆路径问题（Vehicle Route Problem，VRP）[1]是指在给定的运输网络上的对物流车辆的路线进行有效规划，以便物流公司在一些特定的约束条件下高效地服务于客户。其中，缩减所有车辆的总运输距离、总运输成本或者减少行程时间成本被视为VRP的典型目标。可持续的物流运输问题需要充分考虑目标和相当多的约束条件，文献[1] 提出了新的车辆路径模型和应用场景，但是同样引出了一种更复杂的组合优化问题。一般意义上，基本的车辆路径问题是指确认一组有效的多个旅行商（TSP）路线问题，即车辆从起点到目的地的，以服务给定的一组客户，并且每个客户应该只被一辆车访问一次。此外，由于单个路线可能超过允许的运输距离或者运输时间，因此物流车辆可能存在多种不同运输路线。因此，VRP实际上被认为是更复杂、更高级别和更广泛的一类路由问题。

VRP由于约束条件或者目标的不同存在着多种变体，例如容量VRP（CVRP）[2]，多仓库VRP（MDVRP）[3]和带时间窗的VRP（VRPTW）[4]。此外，随着不同运输方式的发展，传统的道路运输模式已不再是唯一的物流运输解决方案，基于多式联运的物流运输方案已成为全球物流行业的重要工作模式，并且多式联运的应用被政府视为推动运营高效化和环保化的重要动力。与经典的VRP类似，多式联运VRP[5]也是一个NP难的优化问题，同时被认为是一个复杂的组合优化问题，研究人员需要在运输成本和时间成本方面协调规划车辆路线和运输模式，因此在过去20年中已经成为一个具有挑战性的研究课题。

精确算法被认为是解决这类物流运输车辆路径问题的最有效方法之一，在文献[6] 中，作者提出了一种基于经典Dijkstra算法的路径搜索算法及其决策机制，解决了大型应用系统中搜索算法的时空复杂度较大的问题。在文献[7] 中，作者通过建立迭代矩阵和序列数矩阵提出了一种改进的Floyd算法，并成功地采用该算法来处理汽车导航系统中的路径选择问题。文献[8] 中，作者为了获得最佳路线，提出了基于概率变量邻域搜索的三步局部搜索算法，并将其用于车辆路径规划问题的求解中。在文献[9] 中，作者提出了一种分支切割算法来解决商人库存路径问题，并运用经济目标函数分析了经济环境变化对车辆路径问题的运输平均利润造成的影响。还有研究[10]为VRP开发了一种有效稳健的分支切割和价格算法，在这个算法中路线通常与列相关联，这些列是容量化基本路线的松弛，这使得定价问题在假多项式时间内能够被解决。通常，这些精确算法适用于那些简单的VRP和路由规划，但是对于处理复杂的路由规划问题，精确算法的性能可能就无法满足计算要求了。

与精确算法相比，启发式算法，如禁忌搜索算法[11]、模拟退火算法[12]、蚁群算法[13]、遗传算法[14]、粒子群优化[15]和差分进化算法[16]由于强大的搜索能力，在大规模多重约束优化方面表现出优异的性能。例如，在文献[17] 、[18] 中，Brando提出了禁忌搜索算法，并利用3个过程来得出初始解，还为邻域定义了3个运算符：单个插入、双插入和交换。该算法还在搜索期间利用了强化和多样化的操作，故该方法能够获得更高质量的解决方案。在文献[19] 中，作者提出了一种结合了几种局部搜索技术的模拟退火算法（SA）来处理车辆路径问题（VRP）的变体，其中时间窗口是与每个客户服务相关联。在文献[20] 中，研究人员提出了一种粒子群优化方法，采用自学习方法处理配送中心的车辆路径规划问题，该配送中心具有多个交叉对接处理多种产品。针对算法早熟收敛问题与降低基本蚁群算法（ACA）的计算成本，文献[13] 提出了一种基于信息熵和局部搜索的自适应蚁群算法求解车辆路径问题和能力的VRP。在文献[14] 中，研究人员采用混合的遗传算法来解决具有时间窗的VRP（VRPTW），其中有一个特定的时间可服务任何客户，然后他对他的结果和其他算法的结果进行了比较，如模拟退火算法。

作为一种高效且功能强大的全局优化算法——差分进化算法（Differential Evolution Algorithm，DE）[16]已成功应用于各种邻域，因为其性能优于其他优化算法[13-15]。因此，搜索多式联运VRP问题的差分进化算子被认为是优化最佳路径的有效、可行的方案，这构成了本篇文章的基础。本文的结构如下：第1章中我们描述了差分进化算法；多式联运的VRP模型在第2章；模拟测试和结果讨论在第3章；总结部分在最后一个章节中。

1 差分进化算法

1.1 算法原理。DE算法被认为是用于实际参数优化问题的有效且易于理解的一种优化方法。根据文献[21] 的描述，DE算法启动时随机生成NP只个体，记为P ｝。第i个潜在解决方案由D维向量xi=表示。 通常，标准的DE算法由3个基本操作组成，即变异、交叉和选择。

变异操作：在其变异阶段，DE算法从当前群体中随机选择3个目标个体x1,x2和x3。需要注意的是，这些被挑选出的目标向量不能够重合。其中，变异个体通过式（1）产生。

其中：Fm∈ [0,2 ] 是一个控制差分变量的缩放因子。通常情况下，Fm过小会导致算法过早收敛，但是Fm过大也会导致减弱算法的局部最优解搜索能力。

交叉操作：为了提高概率密度，变异操作之后通常采用交叉操作。新的个体向量] 将通过以下规则获得。

其中：randj是第j次随机进化，其范围是是交叉概率约束，] 是选择指数，用来保证元素vi,j能够得到。

选择操作：选择操作的目的是决定将哪些个体保留到下一代以及将多少个体复制到下一代。贪婪选择方案被应用在DE算法中，以确定新的个体ui和目标个体xi。如果ui优于xi，那么新个体将替换到下一代中的相应目标向量，否则目标个体保留在种群中。因此，种群要么变得更好，要么在健康状态下保持不变，但永远不会产生恶化。贪婪选择方案被描述为以下的优化问题minf（x）：

1.2 差分进化算法流程。基于以上提及的操作，差分进化算法的执行步骤进行如下总结，并且具体的差分进化算法执行流程图如图1所示。

图1 差分进化算法流程图

步骤2：更新种群迭数g=g+1，并设置个体索引i=1;

步骤3：从当前的种群中选择3个不同的目标个体，通过对xi的变异操作计算出变异个体vi；

步骤4：在xi和vi间执行交叉操作，随后执行选择操作；

步骤5：更新个体索引i=i+1，返回步骤3直至i=NP；

步骤6：判断当前一代的最佳值是否符合终止条件，如果符合，则停止算法的执行；否则返回步骤2。

2 多式联运车辆路径问题建模与优化

2.1 模型构建。结合客户的需求本文对模型中涉及的参数进行如下定义：P是所有运输站点的集合；S是运输模式的集合；di,j表示站点i和站点j之间距离；表示站点i和站点j之间使用运输方式k；表示在站点j上将运输方式k调整为运输方式l；

表示站点i和站点j之间在运输方式k下的运输时间；表 示在站点j上将运输方式k调整为运输方式l需要的时间；T是最长服务时间；表示站点i和站点j之间在运输方式k下的运输成本；表示在站点j上将运输方式k调整为运输方式l需要的成本；Q是运输量；表示站点i和站点j之间在运输方式k下的运输量。

根据以上定义，多式联运车辆路径问题的数学模型描述如下：

其中：该数学模型的约束条件可以被总结为如下公式：

2.2 优化过程。为了利用差分进化算法来优化多式联运VRP，VRP需要采用十进制代码编码。在该优化过程中本文采用两个分段编码的形式，DE个体的第一部分代表运输路径，其余部分是多模式运输类型。例如，如果共有8个运输点，在路径编码中，我们将 [0,1 ,…,7] 定义为传输点编号，并且0,7定义初始点和终点；在运输型编码中，[1,2,3,4] 分别代表公路运输、铁路运输、船舶运输和航空运输。

多式联运车辆路径问题优化过程如下：

步骤1：初始化差分进化算法的种群的道路和运输方式模型，并初始化算法相关参数（例如，1→2→4→3→5；公路→铁路→空运→公路等）。

步骤2：当迭代标志g＜200时，开始执行循环；否则，跳过优化算法，执行步骤13。

步骤3：当个体索引i＜NP时，将个体i设置目标个体。

步骤4：根据公式（4）计算原始种群所有个体的适应度值。

步骤5：随机选取3个个体利用公式（1）进行变异操作，得到变异个体。

步骤6：根据得到的变异个体，将其与目标个体通过公式（2）进行交叉操作，得到实验个体。

步骤7：比较实验个体和目标个体的适应度值，选取最优个体置于种群中，即进行选择操作。

步骤8：比较新的目标个体与原本的目标个体的适应值，选取最优个体置于种群中，即再进行一个选择操作。

步骤9：个体索引更新i=i+1。

步骤10：返回步骤3。

步骤11：返回步骤2。

步骤12：输出结果，结束程序。

3 仿真测试和结果

为了评估本文使用的差分进化算法的有效性，本文研究了一种路由优化案例，用于搜索不同运输方式的最优路径规划。此外，遗传算法将用于比较，并且表1给出了差分进化算法和遗传算法的相应参数设置情况。在本案例研究中，从A市到K市有一个10吨的运输任务，其中网络拓扑共包括11个城市。除了启动城市A和目的地城市K之外，该网络中有9个中转城市和数百个可选路线，该网络拓扑如图2所示。为了方便优化算法计算种群个体和染色体的适应度值，每个城市的运输成本和转移成本列于表2中，其中符号“-”表示列出的运输方式不可使用。

表1 差分进化算法和遗传算法的参数设置

图2 运输网络拓扑

通过分别使用差分进化算法和遗传算法，可以容易地获得具有运输模式的最佳路线，即从A市到K市的最佳路线是A→B→F→J→K，相应的交通方式是从A市到B市到F市的铁路运输，从F市到J市到K市的船舶运输。此外，为了确认差分进化算法的有效性与性能，本文在本案例实验中选择了标准遗传算法和标准差分进化算法进行对比，其迭代趋势的比较结果如图3所示。从图3可以看出，差分进化算法相比于遗传算法收敛速度更快，并且能够计算出更加优秀的物流运输车辆路径规划方案。综上，本文设计的差分进化算法在多式联运车辆路径问题上的应用方案是可行的、有效的。

4 总 结

物流运输车辆路径规划问题被认为是一个复杂的组合优化问题，其在过去的20年中已成为一个具有挑战性的研究课题。为了解决这类NP难问题，本文邻域搜索操作，提出了一种将差分进化算法应用于物流多式联运车辆路径问题的方案。同时，为了证明所提出方法的有效性，本文设计并测试了基于多式联运方式的物流运输实例，并通过仿真实验证明了差分进化算法应用在多式联运车辆路径问题上的可行性和有效性。

表2 多式联运模式运输开销

图3 实验迭代结果