求解带时间窗车辆路径问题的改进FPA

丛扬潇，袁志高，李 素，姜缘平，王祖荣

(北京工商大学 计算机学院，北京 100048)

0 引 言

车辆路径问题[1](VRP)是典型的组合优化问题。旨在为客户安排合理的行车路线，在满足约束的前提下，得到配送方案的最优解。带时间窗车辆路径问题[2](VRPTW)是车辆路径问题的另一扩展问题。由于VRPTW模型采用精确算法对其求解的效率很低，国内外学者将重点转移到各种启发式算法上。Jacobsen-Grocott J等[3]采用遗传编程求解VRPTW。Asadi-Gangraj E等[4]提出了一种混合遗传算法求解VRPTW；马龙等[5]利用鸽群与水滴算法结合求解多目标多时间窗车辆路径问题。张瑾等[6]利用改进的蝙蝠算法求解带容量和时间窗约束的车辆路径问题。李珺等[7]利用改进的细菌觅食算法求解VRPTW。Belhaiza S等[8]提出了混合遗传变量邻域启发式搜索算法求解VRPTW。上述算法虽然在解决VRPTW方面取得了一定效果，但还有较大的提升空间。

FPA(flower pollination algorithm)是一种启发式群智能算法[9]，是受自然界中显花植物花朵授粉过程的启发而提出的，具有全局搜索能力强、选用参数少、搜索路径优及多目标问题求解能力强等特点，已成功应用于蛋白质分子对接[10]、视频跟踪[11]、车间调度[12]、机器人导航路径优化[13]和图像色彩量化[14]等方面。因此本文深入研究FPA，发现其不足之处，并用遗传算法(genetic algorithms，GA)对其改进，提出了一种改进FPA(GA-FPA)，并将其用于VRPTW求解。

1 问题描述与数学模型

VRPTW问题描述为：一组车辆从配送中心出发，根据客户的需求量和时间窗的限制制定配送路线，最终返回配送中心，使配送总成本达到最小。

带时间窗的车辆路径问题主要分为硬时间窗和软时间窗硬时间窗要求车辆必须在客户的规定时间内完成配送任务；软时间窗允许客户在规定时间外完成任务，但要支付额外的惩罚费用。由于硬时间窗在执行中很难找到合适可行的调度方案，同时与实际弹性时间情况不符，而软时间窗具有一定应用性，更符合实际情况。因此在本研究中采用软时间窗作为约束条件。

配送车辆应该满足的约束条件请参见文献[15]。

符号定义与数学模型如下：

配送中心为C0；客户集为C={1，2，…，n}；每个客户的需求量为qi(i∈C)；配送车辆数量为k，车辆集为V={1，2，…，k}；每辆配送车的载重量为Q；客户i与j之间的距离为dij；配送车辆在i与j配送点之间所需的行驶时间tij；配送车辆到达Ci客户的时间为Si；配送车辆在Ci客户点的服务时间为Ti；配送车辆在Ci客户点的等待时间为Wi；如果配送车辆k从第i个客户前往到第j个客户，则xijk=1，否则，xijk=0；如果客户i的配送任务由配送车辆k完成xijk，则yik=1，否则yik=0；[ETi，LTi]表示客户i的服务时间窗，ETi为开始服务时间，LTi为结束服务时间；

目标函数如式(1)所示

(1)

约束条件如式(2)～式(11)所示

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Si+Wi+Ti+tij=Sj，i，j(1，2，…，n)，i≠j

(9)

ETi≤Si≤LTi，i(1，2，…，n)

(10)

Wi=max{ETi-Si，0}，i(1，2，…，n)

(11)

式(1)为目标函数，表示完成配送服务的最短距离；式(2)为配送车辆的装载量限制；式(3)表示配送车辆均从配送中心出发；式(4)表示配送车辆完成服务后，返回配送中心；式(5)和式(6)表示每个客户被车辆访问一次；式(7)表示配送车辆在服务完节点i后服务节点j；式(8)表示车辆在服务节点j之前服务节点i；式(9)、式(10)和式(11)表示时间约束，确保配送车辆在时间窗限制内完成服务。

2 FPA的基本原理

花朵授粉算法定义请参见文献[13]。

在理想条件下的花朵授粉可以用数学公式表示，全局授粉的位置变化公式为

(12)

(13)

式中：Г(λ) 是标准的伽马函数。

全局授粉的位置变化公式为

(14)

3 求解带时间窗车辆路径问题的GA-FPA

3.1 算法思想

GA-FPA的基本思想是使用FPA和GA结合，设计一种求解VRPTW问题的混合算法。首先，针对原始FPA是用来求解连续优化问题的情况，重新定义了FPA中的全局授粉和局部授粉操作；其次，在FPA中加入GA的交叉算子和变异算子。通过交叉算子的加入，使花朵种群中的优良个体在种群中频繁出现，提高了FPA的寻优精度。通过变异算子的加入可以增加花朵种群的多样性，避免FPA过早陷入局部最优；然后，针对原始FPA中控制局部授粉和全局授粉的转换概率p为常数，不能够根据算法执行情况控制全局授粉和局部首份操作的次数，进而使算法不易于收敛和容易陷入局部最优解等问题，对FPA中的转换概率p进行改进，使其可以根据算法执行情况，进行自适应调整。

3.2 全局授粉操作

在本文中，每一朵花代表群体中的一个个体，用一种排列形式表示，排列的先后顺序是车辆运输货物的先后顺序，每朵花被认为是一种解决方案。例如，在车辆路径问题当中，每朵花代表一种配送方案，排列中的节点表示客户的编号，排列顺序即为配送顺序。在车辆路径问题中，配送中心和客户的位置是固定不变的，不能修改其坐标值，所以全局授粉操作应该是按照某种规定方式基于配送顺序的改变，然后从已有的方案中得到新的配送方案。本文采用的方法是针对每种配送方案的排列顺序，每次随机选取两个不相邻的客户节点，交换这两个客户节点的位置，判断是否满足约束条件，满足则视为新的配送方案，否则视为无效解。以10个客户节点为例，随机选择3号客户节点和7号客户节点，然后交换位置，从而产生一种配送方案，如图1所示。

图1 交换配送方案中两个客户节点

3.3 局部授粉操作

原始FPA中的局部授粉是随机选取出种群中两朵花，然后根据两朵花的差异程度决定更新下一代花朵的位置。然而在车辆路径问题中，要进行局部搜索就必须小量地改变相邻单位，从而得到新的结果，搜索步长应该较全局搜索小。所以，本文采用的方法是随机选取种群中的两种配送方案，随机选择相同下标指定的客户节点，然后对调位置，从而产生两种新的配送方案。然后判断是否满足约束条件，如果满足则视为新的配送方案，否则视为无效解。以10个客户节点为例，随机选择3号客户节点和c号客户节点，然后交换位置，从而产生两种新的配送方案，如图2所示。

图2 交换两种配送方案中两个客户节点

3.4 转换概率p的自适应调整

在FPA中，全局授粉和局部授粉操作通过转换概率p∈[0，1]进行调节。在算法的执行过程中，如果全局授粉的操作过多，那么算法易得到全局最优解，但是不容易收敛。如果局部授粉的操作过多，那么容易陷入局部最优解。因此需要转化概率p对授粉操作进行调整，如式(15)所示

p=0.8+0.2×rand

(15)

式中：rand是[0，1]之间的随机数。在标准FPA算法中表明，p=0.8更为有效，算法性能最好，因此自转化概率p设定在0.8附近浮动。

通过式(15)对转化概率p值进行改进后，每次迭代会更新一次p值，使每一次迭代都能够自适应地调节执行概率，有效地解决了算法在全局和局部之间的平衡问题，提高了算法收敛速度。

3.5 基于精英父代的多点交叉算子

本文采用保留精英解的策略。首先选取当前方案的最优解，记为精英单亲父代。随机产生两个交叉点，将交叉点之间的片段记为精英交叉段。随机在群体中选取一条单亲父代个体，将精英交叉段插入到该父代个体的尾部，从而得到一条新的配送方案。保持交叉片段不变，将新的配送方案中与交叉段重复的节点删除，最终得到新的子代。

以客户标号为1-10的配送方案举例，首先选取精英父代，然后随机选择精英父代中3号客户节点和7号客户节点为交叉位，将3号客户节点到7号客户节点之间作为交叉段，然后随机选取一条客户标号为1-10的单亲父代个体，最后将交叉段的基因插入到该个体尾部，保留交叉段不变，将新的配送方案中与交叉段重复的客户节点删除，从而产生一种新的配送方案。基于精英父代的多点交叉过程如图3所示。

图3 基于精英父代的多点交叉过程

3.6 单亲多点基因变异换位算子

本文选取多点基因算子进行变异换位操作。在一条染色体中，随机生成多个交换节点，两两交换彼此的节点，其余片段保持不变，最终得到新的子代。

以客户标号为1-10的配送方案举例，首先随机选取一条客户标号为1-10的父代个体，然后随机选取3号客户节点和7号客户节点为一对交换位对，5号客户节点和9号客户节点为一对交换位对，最后同时交换3号客户节点和7号客户节点，5号客户节点和9号客户节点，从而产生一种新的配送方案。单亲多点基因变异换位过程如图4所示。

图4 单亲多点基因变异换位过程

4 GA-FPA算法实现步骤

步骤1 输入测试实例数据

数据包括客户数目和位置、货物需求量、时间窗、车辆载重量限制等；

步骤2 花朵种群初始化

步骤3 计算花朵目标函数值

根据目标函数对每个花朵位置进行测试，得出每个花朵的目标函数值，同时记录当前最优配送路线及最少配送成本；

步骤4 按规则更新花朵位置

首先按照式(15)对转换概率p值进行计算，然后随机产生rand∈[0，1]，如果rand>p，则按照3.2节中重新定义的全局授粉规则进行异花授粉；否则按照3.3节中的局部授粉规则进行自花授粉。计算更新后花朵位置的目标函数值，与步骤3得到的最优值相比较，选出当前最优位置(最优配送路线)及最优值(最少配送成本)；

步骤5 执行遗传操作

对执行步骤4后的花朵种群中的每个花朵位置进行遗传操作。首先按照花朵位置的目标函数值进行从低到高排序，选择出目标函数值较低的M个个体作为重新繁殖的下一代群体。产生一个随机数rand∈[0，1]。若rand≤0.5，则对花朵种群中的花朵位置按照3.5节中提出的基于父代的多点交叉算子进行运算，然后计算更新后花朵位置的目标函数值；若rand>0.5，则对花朵种群中的花朵按照3.6节中提出的单亲多点基因变异换位算子进行运算，计算更新后花朵位置的目标函数值。将步骤4得到的最优值与遗传操作后的花朵位置的目标函数值进行比较，选出当前的最优位置及最优值；

步骤6 终止条件

令t=t+1，若t≤T，则转步骤3；否则输出当前最优值(总的最少配送成本)和相对应的最优位置(最优配送路线)；

5 实验分析

为了测试算法的有效性及求解性能，使用著名的Solomon算例为实验测试数据(数据来源：http：//www.ber-nabe.dorronsoro.es/vrp/)，并使用GA-FPA算法对其求解。算法使用Python编程实现，在操作系统：OS X EI Capitan，CPU：2.7 GHz Intel Core i5，内存：8.00 GB的MacBook Pro主机上运行所得。

取该测试算例里C104、R208、RC107中规模为25个客户和C104、R101中规模为50个客户的情形进行测试，求解次数均为20次，求解结果见表1。对于客户数为25的算例，种群规模indSize=50，进化代数max_gen=50；对于客户数为50的算例，种群规模indSize=100，进化代数max_gen=50。配送路径的单位配送成本unitCost=8，车辆的租赁费为initCost=100，车辆早到的等待成本waitCost=1，车辆迟到的惩罚成本delayCost=1.5。

表1 标准测试算例运算结果

表1为准测试算例运算结果，给出了在标准遗传算法、粒子群算法、FPA算法、粒子群改进算法、狼群算法以及本文提出的GA-FPA算法在算例中的表现，并给出GA-FPA算法最优解与已知最优解的gap值 (gap=((GA-FPA算法求解结果-已知最优路径长/已知最优路径长)*100%))。

表1采用文献[15]的算例，设置相同的参数进行对比。结果发现，在25个客户数的情况下，GA-FPA在C104、R208数据集的结果优于粒子群改进算法，以及改进的狼群算法。但是在RC107数据集中，GA-FPA算法的效果则低于上述两种算法。在50个客户数的情况下，GA-FPA在C104数据集的效果优于狼群算法。尽管GA-FPA在小部分数据集上不如其它改进算法，但在大部分数据集上结果优于其它改进算法，总体来看GA-FPA算法能优于其它算法，本实验具有可比性。

由表1可知，GA-FPA算法求得的最优解与已知最优解中使用的车辆数基本相同，结果如表2～表6所示。但是在R101算例中，GA-FPA算法求解结果使用的车辆数较最优解少，结果见表5，有50个客户(编号1-50)和1个配送中心(编号0)。尽管其总路程较最优解大一些，但其gap值大部分不超过5%。GA-FPA算法在解决多客户的VRPTW问题上，与GA、粒子群算法、原始FPA、粒子群改进算法以及狼群算法相比具有一定优势。总体来看，GA-FPA算法能够在较小的迭代次数和较小种群规模的实验中取得较好的结果，并且算例结果十分接近最优解。

表2 GA-FPA求解C104(25个客户)算例

表3 GA-FPA求解R208(25个客户)算例

表4 GA-FPA求解RC107(25个客户)算例

表5 GA-FPA求解C104(50个客户)算例

表6 GA-FPA求解R101(50个客户)算例

对GA-FPA中控制全局授粉和局部授粉的转换概率p的取值进行实验测试。取测试算例里C104、R208、RC107、R101中规模为25个客户和50个客户的情形进行测试，首先令p=0.8，分别求解次数均为20次，记录下车辆运输费用。然后按照式(15)对p值进行赋值，使其可以根据程序执行情况，进行自适应调整，然后记录下车辆运输费用，进行对比，结果见表7。由表7可知，对转换概率p值进行改进后，每迭代一次，更新一次p值，自适应地调节搜索执行概率，对求解到的目标值(车辆的运输费用)有所下降。有效解决了算法的全局搜索和局部搜索之间的平衡问题，避免了FPA陷入局部最优。

表7 转换概率p取值的运算结果

6 结束语

本文设计了一种求解VRPTW的GA-FPA算法，算法通过加入基于精英父代的多点交叉算子，提高了FPA的寻优精度。通过加入单亲多点基因变异换位算子和对转换概率p值进行改进，自适应地调节全局搜索和局部搜索的执行概率两种策略避免了FPA过早陷入局部最优。算法求解结果与已知最优解和GA、粒子群算法、原始FPA、粒子群改进算法以及狼群算法进行对比，结果表明GA-FPA具有更优的求解精度与收敛性，是一种行之有效的求解VRPTW的算法。今后在此基础上，进一步研究改进FPA及其它新的群智能算法在低碳约束下的物流配送车辆路径问题上的应用。