基于萤火虫算法的动态车辆路径规划

董 海，雷凤达

(沈阳大学 1.应用技术学院；2.机械工程学院，辽宁 沈阳 110044)

信息技术的进步促进了智慧交通系统(intelligent transport system,ITS) 的发展。目前很多城市开始朝着智慧城市方向发展。作为智慧城市重要组成部分的智慧交通成了研究热点。而动态车辆路径问题(dynamic vehicle routing problem,DVRP) 作为车辆路径问题的变体之一，是智慧交通研究中不可或缺的组成部分。通过动态获取实时交通信息和客户需求变更信息，根据城市实时交通情况和客户需求的变更进行车辆路径规划，为客户提供更加快速的服务，以解决由于城市基建滞后、交通结构单一、客户需求变更等原因导致的城市拥堵问题和成本浪费，实现智慧交通让城市更美好的愿景。

目前，大多数关于VRP的研究都假设在路径规划之前，信息不随时间变化而变化。基于这样的假设，路径的安排相对固定，该种VRP被称为静态VRP。然而，客观世界存在很多不确定性，需要动态地改变车辆的运行路线并及时调整原来的行车路线。此时，静态VRP 的理论和方法对这些问题不再适用。因此，对于动态车辆路径问题的求解，需要研究一套全新的理论和方法。1988 年，Psaraftis[1]首次将车辆调度问题定义为“安排车辆路径以满足实时出行的顾客需求”。从线性规划(linear programning,LP) 到启发式算法，有许多方案可以解决DVRP及其变体。Yang 等[2]在以车队必须为动态请求提供服务的基础上提出一种基于线性规划的滚动时域方法用以解决卡车动态交付问题。Montemanni 等[3]利用时间片策略开发了一个求解DVRP问题的蚁群算法(ant colony optimization，ACO)，并在每个时间节点上都检查并处理请求。Chen等[4]提出一种用于DVRPTW的动态列生成器方案，在适应度函数方面取得了较好的结果。吴斌等[5]提出基于状态分类更新的粒子群算法(particle swarm optimization,PSO)用以求解开放式动态网络车辆路径。Pillac 等[6]提出带有多场景方法(mutliple scane analysis,MSA) 的事件驱动框架，通过将请求的子集分配给车辆来完成路径规划。宁涛等[7]将车辆链和货物链的双链量子编码，提出改进的多相量子粒子群算法用以求解多目标DVRP。Briseida 等[8]提出可变邻域搜索算法(variable neighborhood search,VNS)，通过对随机场景进行采样来扩展解的空间，更加精确求解DVRP。Alchami 等[9]提出一种带有人类调度员的遗传算法(genetic algorithm,GA) 来解决DVRP问题，使GA在整个范围内一直运行并不断更新路径。闫凯等[10]在此基础上将GA与ACO结合，更快地求解单配送中心路径优化问题模型。孙俊成等[11]基于贪婪思想的随机邻域搜索策略提出一种新改进的萤火虫算法(firefly algorithm,FA)，解决软时间窗的多配送中心开放式车辆路径问题。Maroua 等[12]针对CDVRP需求与决策支持系统的性能差异，提出一种新的基于图形处理单元(graphics processing unit,GPU) 的分布式蜂群算法。辜羽洁等[13]基于嵌套分割算法，设计了邻近救援策略、最佳离库策略、增派车辆策略对DVRP模型进行求解。范双南等[14]采用智能水滴算法对车辆路径优化模型进行求解，使用灰狼优化算法改善智能水滴算法的搜索能力，获取最优路径。Orivalde 等[15]在多蚁群系统的基础上，引入随机变量邻域下降策略求解带时间窗的DVRP。Resmi 等[16]利用带学习能力的尖峰神经P系统与FA进行结合，利用尖峰神经系统的并行性优化FA，以解决绿色动态车辆路径问题。

综上所述，现有解决策略大多基于优先分配原则，这样会延迟客户对车辆的请求分配。因此，一些客户可能会进入一个较长的等待期，进而影响系统的整体性能。本文提出一种改进的萤火虫优化方案，引入萤火虫的运动和吸引概念来表达模型动态性，用改进后的算法对解空间进行智能化探索和开发，解决CDVRPTW问题。

1 问题描述

CDVRPTW是VRP的一个变体，是由于最近通信方面的改进而出现的。DVRP在开始设置路径时，并不是所有的信息都是可用的；即使在路径被构建之后，信息也可能发生变化。图1列出了CDVRPTW的路径规划图。该图中有4个顶点(A、B、C和D)，其对应已知请求的4个不同客户。连接客户的边缘表示不同的参数，如旅行成本、旅行距离等。为满足已知请求而进行的初始路线为车场→A→B→C→D→车场，当车辆沿着AB路线行驶时，出现一个动态请求E。此时，如果车辆的总容量小于或等于路线中每个客户的所有容量之和，则车辆路径规划为车场→A→B→C→D→E→车场；反之则需要在满载前更改路径以满足客户需求。

图1 动态环境下的线路规划Figure 1 Route planning in dynamic environment

2 带时间窗和容量受限的动态车辆路径模型(CDVRPTW)

CDVRPTW可以看作是一个完全的图论问题。其中，顶点集A={A0···AB}；边缘集E={(Ai,Aj):Ai,Aj∈A,i≠j}。顶点A0车场，每个顶点AK∈A都有参数，定义请求Pk、到达时间Tak、等待时间Twk、服务时间Tsk和时间窗口[Tek,Tlk,]，C′kj是客户j到客户k在时间段t内的运输成本。每辆车k有一个非负的容量Wk。总时段数用T表示，fc和tc分别是车辆的固定成本和每单位时间的行驶成本。

总成本是车辆固定成本和路线成本的总和，车辆总成本最小问题表达式为

受以下约束。

1) 将客户分配到车辆：每个客户在给定时间仅分配给一辆车。

2) 车场容量：车场出发的车辆数量不超过车场的车辆总数(N) 。

3) 同一车辆服务于同一个集群上的客户。

其中，M是一个非常大的数，定义为第k个客户的最晚时间与第j个(连续) 客户的最早时间之间的最大差值，∀k,j,k≠j。

4) 每个客户节点都必须由一辆车提供服务。

5) 车辆容量(Wk) ：车辆交付给客户的负载不应超过客户需求Pk的车辆容量。

6) 排除备用路径：如果车辆从客户k在t处为客户j服务，则不应存在任何路径。此处|A|是路径中的客户总数。

7) 时间窗口约束：为客户提供服务的时间限制不应超过时间窗口。

3 求解方法

本文采用改进萤火虫算法求解模型，并利用DVRP求解器来处理新的动态请求。与其他生物启发算法相比，FA被选择作为所提出解决方案方法的基础有以下优势。

1) FA整个群被细分为多个子群，并且每个子群位于一个局部最优的周围，促进FA的灵活性。

2) 光吸收系数γ作为一个比例因子，调节FA的多温能力，并连续调节种群的多样性。

因为经典FA在实域中是连续的，而VRP的解空间是离散整数，FA不能直接用于求解VRP问题，因此本文提出基于坐标的萤火虫算法，利用CR编码/解码方法，使VRP的离散解映射到连续域，从而求解模型。

3.1 DVRP求解器

根据本文对DVRP的定义可知，可以将DVRP模型的求解划分为两个阶段：工作开始前基于已知顾客信息的车辆初始路径的求解阶段与每次接收到新需求后车辆路径的调整阶段。

在车辆开始工作之前，只能将当前已知所有的顾客信息进行整合并规划路线，也就是说此时面对的规划问题中需求是完全确定的。在第1个阶段的车辆路径规划相当于对CVRPTW模型进行求解。当每次接收到新顾客需求时，将结合新顾客与原规划路线中关键节点以后的未服务顾客的需求信息和位置信息，调整关键节点以后的车辆行驶路线，并执行新路线。此时，每辆车处于不同的位置，剩余的容量也不同，可将车辆当前位置虚拟为新的起点。从本质上来看，与第1阶段规划车辆路径相比，出现动态需求后对路径规划在车的容量和车辆位置上有差异。因此如果在一个工作日内出现了N次动态信息，则对整个过程的CDVRPTW模型就分解成了求解一个车辆在同一位置出发的CVRPTW模型和N个车辆在不同位置出发的CVRPTW模型，分别对应了对车辆初始行驶路径的求解和N次接收到新顾客需求后新路径的求解。

针对模型的求解算法，本文将采用坐标萤火虫算法求得模型的初始解。为解决该初始算法求解质量不高的问题，利用局部搜索对其进行改进。本文DVRP模型的求解策略如图2所示。

图2 DVRP求解策略Figure 2 DVRP solution strategy

3.2 萤火虫算法

萤火虫算法的灵感来自生物发光的过程，在自然界中，萤火虫利用生物发光来吸引潜在的伙伴和猎物，或者作为一种警告机制。用每只萤火虫的光强来模拟解的质量，即萤火虫在三维空间中的目标函数和运动机制。一般来说，一只明亮的萤火虫会吸引一只不太亮的萤火虫向其靠近，但光强不是该机制的唯一因素。随着两个萤火虫之间的距离增加，光强根据平方反比定律减小，萤火虫间的吸引力减小。本文建立3个规则来模拟所描述的行为。

1) 所有的萤火虫都是不分性别的，都能够相互吸引。

2) 萤火虫的吸引力与其亮度成正比。因此，对于任何两个闪烁的萤火虫来说，不太亮的一个会移向较亮的一个。随着任意两只萤火虫之间距离的增加，吸引力和亮度都会降低，如果两只萤火虫亮度相同将会随机移动。

3) 萤火虫的亮度受目标函数影响。

每只萤火虫都有两个重要的特征，光强度I和吸引力β。关于优化问题，萤火虫在H位置的光强与目标函数f(x)的值(在最大化的情况下) 或其倒数(在最小化的情况下) 直接相关。吸引力与相邻萤火虫看到的光线强度成正比，并遵从笛卡尔距离方程，随着rij(萤火虫i和萤火虫j距离) 的变化而变化。其中，γ表示固定光吸收系数，β0表示在r=0时的吸引力。距离公式为

萤火虫i在时间t朝吸引力更大的萤火虫j运动表示为

式(13) 中最后一项包括随机化参数和在时间t从高斯或均匀分布中提取的随机数向量。参数设置是为了控制解的多样性，文献[17]建议

其中，L为平均问题比例。

算法1为最初的萤火虫算法，伪代码如下。

3.3 基于相关坐标的萤火虫算法(CR-FA)

3.3.1 相关坐标方法的描述

本文提出的相关坐标编码/解码过程是为利用标准的FA方案及其方程来求解VRP变体而设计的。CR的主要功能是将离散编码的解转换为连续值，以便可以直接应用FA方程。

目前广泛使用的VRP解的表示是向量或数组列表。每条路径的起点和终点是节点“0”，其余可用节点的访问序列由其所在解向量中的索引表示。但由于问题的复杂性和可选择性，不应访问可用集合中的每个节点，无法在CDVRPTW的解决方案中直接实现这些机制。因此本文提出了CR编码/解码方法，利用每个节点的笛卡尔坐标(二维空间中的位置) 和节点之间的欧几里德距离。按照CR编码方案，每个解决方案向量由两个新的向量表示，其分别对应于解决方案中每个节点的X和Y坐标，如表1所示。

表1 CR变换向量示例Table 1 Example of CR transform vector

表2表示车场的节点“0”位于(0，0)，遵循FA的算法框架，每个萤火虫都由一个解向量表示，并被吸引到一个更亮的，即一个解将向一个更好的方向移动，运动和距离由方程控制。

表2 相关解向量Table 2 Correlation solution vector

在目前的研究中，认为两个给定解的距离可以计算为在两个不同向量中相同位置的每对节点的最小欧几里德距离，不包括公共节点和节点“0”。此时，可以计算吸引力。假设解向量1的光强大于解向量2的光强，则应更新向量2。在实践中，每个维度(X和Y) 通过计算，产生一个新的坐标集作为解向量2的更新版本，如表3所示。

表3 更新解向量2示例Table 3 Example of updated solution vector 2

解码过程遵循索引过程，并且相关性遵循以下原则。

1) 可用节点集中的所有节点都应是“对应节点”的候选节点，并应通过可行性控制决定，具体取决于CDVRPTW公式施加的路径约束。

2) 搜索的方向，即X轴或Y轴，是从均匀分布的随机数中随机选择的，其增强了该过程的探索强度。

3) 如果上述候选数中有最初被列入被审查的数，则应选择其他，以增加过程的多样化。

4) 初始节点和最终节点“0”可以是相应的节点，也可以由进程强制实施，以符合问题的可行性限制。

3.3.2 CR-FA算法

所提出的基于坐标的萤火虫算法包括运用启发式方法来创建初始解种群，以确保更新解的可行性，并改进更新解。因此，CR-FA的框架包含初始群、坐标化(解码/编码)、增强路径、移除节点和交换节点。算法2伪代码如下。

对于初始种群的构造，采用了初始种群启发式方法。第1步是制定M条初始路线，其中只包括车辆段和一个其他节点。这些路径被组合成一个初始解向量，未包含的节点根据它们的亮度值进行排序。

最有效的插入位置(节点I、j之间)Sij为

整个解决方案达到的总需求Qlow为

解决方案的每条路径都由节点扩充，达到预定义的容量限制应不超过Qlow。算法3伪代码如下。

随后，FA方案被初始化，定义了光吸收系数γ，并计算对于所创建的群体中的每个成员的适应值fi与相应的光强度Li。由于CDVRPTW是一个最小化问题，所以光强被分别定义为每个解的适应值的倒数。然后，对群体中的每一对解进行比较，光强值较低的解应该向另一个解移动。为此，首先应测量它们相应的距离，然后再应用坐标化编码/解码过程。为了提高算法解的质量，使用局部搜索技术，包含增强路径、移除节点和交换节点技术。在增强路径过程中，考虑到所有上述约束，使用节省方法用于填充每个路径节点。将解决方案中的节点添加到它们各自的最佳位置。随后，另外两种局部搜索技术被用于改善迭代次数。首先，在移除节点过程中，算法在移除节点后重构，并且连续地，在不违反最小需求约束的情况下构建更高质量的解决方案。所采用的原则是，当具有低强度的节点从解中移除时，剩余的解与新的弧连接，并且如果新的方案在成本(距离) 方面是可行的，则可以出现更好的解(具有更低的目标函数值) 。算法4伪代码如下。

交换节点是一个重复的交换过程，在一个解决方案中的随机路径之间进行指定次数的迭代。随机选择两条路线，并且还随机选择所选路线之一的位置。交换所需的第2位置，即来自第2路径的节点，是使用距离向量计算的。所描述的节点交换旨在通过省略无效的节点序列并创建更有效的连接来创建具有更少行驶距离(更低成本) 的解决方案。算法5伪代码如下。

4 算例测试与分析

本节评估解决CDVRPTW的CR-FA算法的性能。由于目前还没有形成CDVRPTW的基准数据集，因此，本文将动态模型看作很多静态车辆路径模型的集合，在开放数据集上的 CVRPTW实例对CR-FA进行了测试，并对结果进行了分析。本文采用Intel Xenon2.93ghz处理器、12gbram、Windows10操作系统，用Matlab对实验进行了仿真。

4.1 参数设置

本文提出的CR-FA的优势在于其需要与标准FA相同的参数化。Yang 等[18]考虑到问题规模与解空间中可用节点的数量N有关，对于每个测试实例，初始随机性比例因子分别计算为a0=0.01N，光吸收系数计算为。人口规模w和冷却系数δ的设为w=40，δ=0.96。

4.2 CVRPTW数据集测试

CR-FA在所罗门数据集上进行了平均40次测试，本文算法有两个停止标准。当它到达最优解或最大迭代次数，设为500次迭代。将CR-FA的最佳值和平均值与蚁群算法(ACO)、粒子群算法(PSO)、遗传算法(GA) 和差分进化算法(DE) 进行比较，并对结果进行分析。

表4给出了5种方法的解质量的最佳值和平均值，其中最好的结果用黑体表示。与其他4种算法相比，本文所提出的CR-FA实现了20个最佳值中的15个和20个平均值中的14个高于其他算法，并在20个实例中取得平均最佳。为了清楚地区分这些方案的优劣性，以解的最小值、最大值、中位数、上四分位数以及下四分位数为原始数据，见表4。

表4 各种算法解的平均值与最佳值Table 4 The average value and best value of various algorithm solutions

选择ACO作为基准绘制算法对比箱线图，用于分析各种方案的改进百分比，如图3。通过对箱线图的分析可以看出，就总体而言，CR-FA的改善百分比明显优于其他方案。

由于ACO算法对解决此类车辆路径问题效果较差，所以在下面分析R101实例结果中不作分析。具体运行结果如表5所示。其中，Pk代表客户的需求；Ve表示车辆数；R表示车辆所行驶的距离；F表示车辆的成本；T表示算法的运行时间。结果表明CR-FA除了迭代速度较其他算法比稍显不足，在成本以及行驶距离上明显优于其他算法，图3在算法迭代速度上进行进一步分析。

表5 算法比较-R101实例Table 5 Algorithm comparison-R101 instance

图3 改进质量百分比比较Figure 3 Comparison of improved quality percentage

图4显示了最优路径的收敛性，将本文提出的CR-FA算法的收敛性与其他算法作出对比分析。结果表明CR-FA在初期就具有优于其他算法的收敛能力，并在最终收敛结束的目标值优于其他算法。在迭代次数为250次时得到最优路径，算法持续探索解的空间追求更高质量的解。

图4 最优路径收敛曲线Figure 4 Optimal path convergence curve

图5通过大型实例C150，展示了CR-FA到达最优解或最优解附近的收敛行为和CR-FA解决C150实例的结果。该图描述了运行期间获得的最佳解和平均解，并显示了CR-FA的收敛行为。算法在280次迭代后求出最优解。在初始阶段，CR-FA具有很高的收敛速度。在搜索过程中，CR-FA实现了最优解和搜索速度之间的良好平衡。这种平衡有助于CRFA有效地探索搜索空间并避免陷入局部最优。此外，在搜索过程中没有出现停滞。

图5 C150实例下的迭代行为Figure 5 Iterative behavior in C150 instance

4.3 实例验证

为了验证所提CR-FA的实用性，将其应用于沈阳市新鲜果蔬物流一个实际实例中。将果蔬从仓库(水果蔬菜配送中心) 送到13个配送点(沈阳市13家果蔬超市)，每两点之间的距离详见表6。

当货物从配送中心运送至各配送点时，运输车辆为同一类型的普通卡车。该卡车的最大承载能力为40 t，平均速度为60 km/h。每辆车的固定运输费为600 元/km，运输费为5 元/km。表6根据标记顺序给出了配送中心和超市的具体情况。本文的研究并没有考虑到交通拥堵，车辆可以在超市规定的时间窗口内送货。

表6 任意两个超市间距Table 6 Distance between any two supermarketsm

实际问题的具体目标是尽量减少车辆数量、减少车辆总行驶距离和配送中心的总成本。因此，应用FA和CR-FA来解决VRPTW实例。通过比较这两种算法的结果，分析并验证该CR-FA的实用性和有效性，其结果见表7。

从表7可以看出，使用FA解决CVRPTW实例需要6辆车，但这6辆车并未得到充分利用。根据最后一行，总距离为57 158.92 m，车队需花费3 890.02元才能完成全部交付。然而，当使用CR-FA来解决CVRPTW实例时，需要5辆车，并且与FA方案中的6辆车相比，这5辆车几乎被充分使用。总距离为54 395.47 m，比CR-FA解决方案中的总距离小2 763.45 m。车队完成所有交付的成本为3 276.88元，节约613.14元。因此，通过对实例的应用和分析表明，所提出的CR-FA是有效的，具有实际意义。

表7 CR-FA与FA解决方案对比Table 7 Comparison of CR-FA and FA solutions

5 结论

本文提出一种改进萤火虫算法解决带时间窗和容量约束的动态车辆路径问题，主要结论如下。

1) 在动态车辆路径模型的基础上加入时间窗和容量约束，以总成本最小化为目标构建CDVRPTW模型。

2) 提出基于CR编码/解码方法使萤火虫算法的解坐标化，将离散解映射到连续域，其在解决车辆路径问题时，不需要在标准算法框架中应用杂交或离散化技术；同时根据CR过程的解码部分，使每对新坐标对应一个节点，可以根据特定VRP公式施加的约束进行可行性控制；采用局部搜索技术优化运算过程，避免其陷入局部最优。

3) 在实例验证中，将CR-FA在解的质量、车辆利用率以及收敛性等方面与蚁群算法、粒子群算法、遗传算法和差分进化算法进行比较，统计分析验证了本文所提的算法解决CDVRPTW的有效性。