物流配送中烟花算法结合遗传算法的异质车队路径优化方法

庞 凌12

(1.辽宁装备制造职业技术学院，沈阳 110161；2.辽宁广播电视大学，沈阳 110161)

0 引言

物流作为现代社会运转的重要环节，越来越受到人们的关注[1]。货物配送是物流的核心环节，车辆路径问题一直是物流中的基本问题之一，因此研究配送中的车辆路径问题(vehicle routing problem，VRP)对于企业经济性至关重要。VRP问题在传统意义上来说是指已知仓库位置、客户位置和需求，在特定的约束下寻找到一条最优路径，对各个客户进行访问，要求运输成本最低。VRP问题是经典的组合优化领域典型难题之一，在数学和计算机科学等领域已经研究多年的问题，它易于描述但很难解决[2]。

传统VRP的衍生变化主要来源于一些时间、空间和非空间限制，例如有考虑运输能力的VRP，其车辆的均匀可用且唯一的约束是车辆容量；或具有时间窗的VRP，其客户服务必须在规定的时间间隔内进行，需要确定车辆行程的时间表[3]；当以不同容量和成本为特征的车辆用于配送业务时，VRP的一个重要变体出现，这被称为混合车队VRP或异质车队VRP[4]。许多学者致力于解决这一难题及其衍生问题。文献[5]提出了一种基于遗传算法的应急疏散中车辆路径规划研究。文献[6]提出了一种基于禁忌搜索算法车辆路径优化方法，禁忌算法在初始解的基础上引入灵活的储存结构和相应的禁忌准则来避免重复的搜索，但对于初始解的依赖过多。文献[7]提出了一种混合回程和时间窗的VRP的粒子群优化算法。文献[8]提出了一种基于改进蝙蝠算法的带模糊需求的车辆路径优化方法。文献[9]提出了一种基于人工鱼群算法的模糊VRP问题优化方法。文献[10]研究了异构固定的开放式车辆路径问题，其中客户的需求由固定数量的具有各种容量和相关成本的车辆组成，是典型VRP的重要变体，可以涵盖运输中的更多实际情况。

已有的文献采用单个智能算法用于求解VRP问题，在全局搜索能力方面仍有一定的改进空间。混合智能算法能够有效结合各个算法中的优点，提高算法的全局搜索能力。因此，针对物流配送中异质车队路径优化问题，提出了一种烟花算法结合遗传算法的车辆路径优化方法。利用两阶段构造理论有效的将两种智能算法进行融合。车辆分配阶段采用改进的遗传算法为客户分配车辆。路径阶段的仓库局部路径采用烟花算法生成并优化从仓库到适当容量区域内所有城市的路线。提出的混合算法有效的提高了搜索的全局能力。

1 车辆路径问题及其拓展

车辆路径的目的是确定交通网络中车辆的最佳收集或交付路线[11]。VRP是一个非确定性的多项式时间内求解困难问题，通过要求将车顶点分配到每个车辆路线内的这些顶点的顺序来概括经典旅行商问题以获得解决方案。

1.1 车辆路径问题

VRP问题如图1中描述。假定有M个车辆，每辆车的运力为Q，并且具有N个客户，他们所要求的货物必须从仓库发出。每个客户要求的货物和它们之间的距离是事先已知的。车辆从仓库出发，为客户提供服务并返回仓库。要求车辆的路线应适当布置，以便使用最少数量的车辆并能够保证运送的距离最短，同时必须满足以下条件：(1)任何车辆路线的总需求不得超过车辆的容量；(2)任何特定客户由一辆且仅一辆车辆提供服务；(3)客户交付不能在两辆运输车辆之间分配。

图1 车辆路径问题

该成本通常被解释为距离或旅行时间，具体取决于上下文。除非另有说明，否则可以认为这是一个最具成本效益的车辆路线。这一点确定了一组最具成本效益的车辆路线，以便(1)除了仓库之外，每个顶点只需一辆车就可以访问一次以满足其需求;(2)所有车辆路线在仓库开始和结束;(3)每条路线的总需求量不超过车辆容量。

有时，每个车辆都有一个固定的开销。需要优化的目标是最小化固定费用和旅行费用的加权总和。除了容量约束之外，还可以考虑每个车辆路线的最大距离或时间约束。

基于要优化的目标函数和要满足的约束类型，产生了该问题的大量的变体。当具有不同容量和成本的车辆可用于分配活动时，VRP的一个重要变体出现。

1.2 路由VRP 的数学表示

混合车队VRP 可以以下面的方式描述。给定一个有向图G=(V,A) ，其中V={0,1,2,...,n} 表示具有(n+1) 个节点的节点集合，A表示弧的集合。节点0表示仓库，剩余的节点V{0} 表示n个客户。

路径可以以二元组(R,k)的形式定义，其中R=(i1,i2,...,i|R|)，i1=i|R|=0且有一个包含仓库的回路G=(i2,...,i|R|-1)⊇V′，k是与路线相关的车辆类型，R用于参考访问序列和顾客的集合(包括仓库)的路线。一个路线(R,k) 是可行的如果路径上所有需要访问的客户的总需求不超过车辆的运力Qk。

异构VRP的最通用版本由分配一组可行的最短路径和使总开销最小化两部分组成，即：

1)每个客户都仅在一条路径上被访问；

2)每种车辆所执行的路径总数不超过mk。

可以通过以下方式呈现异构车辆路径问题的最一般变型的形式。由(F1)z(F1) 表示的目标函数表示路线的最小旅行成本函数，并由下面的式(1)定义：

(1)

(2)

∀p∈V′,∀k∈M

(3)

(4)

(5)

∀i,j∈V,i≠j,∀k∈M

(6)

yij≥0,∀i,j∈V,i≠j

(7)

(8)

在上述书面表述中，约束条件(2)和(3)确保客户被访问，并且访问客户需要从访问者的角度来看待客户。通过约束(4)，可以获得可用于汽车类型的车辆的最大数量。约束(5)是商品流量约束。他们指出，在访问客户之前和之后车辆携带的货物数量之间的差异等于该客户的需求。最后，约束(6)确保永远不会超过车辆容量。

在本研究中，式(5)未讨论车辆携带的货物数量与客户要求的货物数量之间的差异。通过这种方式，异构VRP部分地简化了这个NP 困难问题的复杂性。除容量限制外，还可以考虑每个车辆路线的最大距离约束。

2 烟花算法结合遗传算法的异质车队路径优化方法

2.1 烟花算法

烟花算法(Fireworks Algorithm, FWA)[11]是一种新型的群体智能算法。烟花算法通过模拟烟花在空中爆炸的现象来进行多点同时爆炸式搜索，能够解决各种全局最优解搜索的问题，并且适应性很强，易于融入到实际生产和生活中。

烟花算法将寻优问题中的搜索空间对应到实际烟花爆炸产生的范围，采用烟花爆炸的位置、爆炸产生火花的位置来表示可行解，并选择其中适应值最好的位置来当作下一个烟花的炸点，而且能够通过设置烟花爆炸范围、层数、烟花数量等来调整邻域集。在计算过程中，使用适应值函数对每个烟花及其产生的火花进行比较，求得适应值。若适应值越小，则对应的烟花及火花则属于优质的个体。在下一代中，其烟花或则火花爆炸时产生的火花数量越多，爆炸的范围越小。反之，适应值越大，烟花质量越差，下一代时产生火花越小，爆炸范围越大。

烟花算法主要由4个部分组成：爆炸算子、变异操作、映射操作和选择操作。

1)爆炸算子：由爆炸强度、爆炸幅度和位移操作三部分组成；

2)变异操作：采用高斯变异；

3)映射操作：由模运算、镜面反射、随机映射组成；

4)选择操作：由基于距离的选择操作、随机选择操作等组成。

烟花算法的算法执行流程如图2所示。

图2 烟花算法的算法执行流程

烟花算法具体包括以下几个步骤[12]:

1)所有的烟花都是无性的，因此，在一定的空间中随机产生一定数量的烟花，每个烟花代表该空间中的一个可行解。

2)烟花爆炸释放出来的火花可以分为两种形式：爆炸火花和高斯变异火花。烟花质量的好坏可以通过计算每个烟花的适应度值来评估。

3)判定是否满足终止条件。如果满足则停止搜索，否则在爆炸火花、高斯变异火花和烟花中选择一定数量的个体作为烟花进入下一代的迭代。

2.3 两阶段构造理论

在许多VRP问题的解决方案中，两阶段理论常被采用的主要有两种：

1)优先聚类，其次路径。基于一些接近度测量，首先将顶点分组在两个不同的子集中。然后，在每一个组内，将顶点排序从而形成一条路径。

2)优先路径，其次聚类。这是聚类优先的一种替代方法，它首先构建了访问所有顶点的巨型路径。然后，路径被划分为较小的可行路径。

异质性VRP的特点是不同的容量和成本可用于分配活动。基于两阶段构造的理论，能够非常好地解决了异构的VRP的问题。采用优先聚类其次路径的构造理论。由两个不同的模块组成：通过聚类在第一个阶段内容为客户分配车辆；第二阶段通过对路径排序实现本地路径优化。

2.3 混合算法异质车队路径优化方法

混合算法利用两阶段构造理论对两种算法进行融合。对聚类阶段在的进行了改进，为了实现更真实的现实模型定义了运力空间，运力空间是一个地理区域，所有适当的客户及其订单只能通过一个参与的车队来提供服务。然后，按运力空间划分聚类区域，并且基于圆形层组。由两个不同的模块组成：1)聚类模块，它定义容量区，然后将客户分配给车辆—这是第一个过程；2)一个仓库区域路线模块，它优化从仓库到适当容量区域内所有城市的路线，这是第二个过程。

遗传算法[13]用于优化过程的第一部分，以定义容量区域。对于优化过程的第二部分，使用烟花优化算法。在路径异构车队VRP中提出的混合遗传算法结合了遗传算法和烟花算法来生成容量区、弧和路径，从而在数据集中获得异构车队VRP的最佳结果。

3 算例分析

实验结果显示了原始数据集的经验模型，其中显示了距离(km)、肉类重量(kg)、数量，接合能力(kg)和运力利用率。实验结果通过混合遗传算法获得。表1是车队中各种车辆的运输能力。

表1 车队中每种车辆的数量和运力 kg

实验结果如表2所示，它们包括距离，运输肉的重量，路线数量，参与的容量和经验模型的运力利用率。然后，对经验模型和混合算法得到的实验结果进行比较，比较包括距离，路径，参与的流量和流量利用率。特别强调这两种方法之间的比较结果，即1)减少和最小化距离方面的改进，以及2)车辆容量利用方面的改进。

表2 经验模型与混合算法对比

实验结果表明，通过对平均值、标准差和中位数的值进行比较，所提出的混合算法比经验模型得到的结果更好。与经验模型相比，所提出的混合算法中10个分布日覆盖的总距离值减少了5 103 km，即10.4%。可以认为车辆的平均油耗为每100公里32升，1升燃油成本为7.62[14]，这意味着在这10个工作日中可以节约12 000元的成本。混合算法与经验模型的总运力的值差异为84 420千克，或8 420千克/天。这意味着参与的车辆的总运力减少了4.4%，也就是每天可以少使用两辆车，每天减少两条路线。因此可以得出结论，更多的客户聚集在相似的位置，即同一容量区域，可以降低成本运输功能，从而能够更好地优化物流配送流程。

4 结论

针对物流配送中车辆路径的问题，提出了一种烟花算法结合遗传算法的物流配送中异质车队路径优化方法。将实验结果与经验结果对比，所提出的方法得到的实验结果优于原始数据的经验结果。

异质车队路径研究未来的发展主要集中在其他大型数据集上，并且在混合智能算法改进与应用中需进一步开展研究工作。另外所提的混合算法只考虑了不带时间窗的异质车队问题，对于更加复杂的VRP问题的应用仍需要后续进一步研究。