求解带时间窗车辆路径问题的改进型烟花算法

牛群，刘 军

(兰州理工大学 机电工程学院，甘肃 兰州 730050)

0 引言

车辆路径问题(vehicle routing problem，VRP)由DANTZIG和RAMSER于1959年在研究卡车配送汽油行驶路径问题时提出。当前VRP考虑实际生活中的约束，在基本VRP上增加客户配送的时间窗要求，并提出带时间窗车辆路径问题(vehicle routing problem with time windows，VRPTW)，更贴近实际情况。

VRP自提出以来就受到广泛关注。EKSIOGLU总结出常用求解方法可分为解析算法和启发式算法[1]。解析算法包括分支界定法、动态规划法等。由于VRP是NP-hard问题[2]，计算时间会随着客户数增多呈指数级增长，在实际应用中受限。启发式算法在可接受的计算成本内能找到近优解，使用迭代方式实现寻优过程，通过反馈信息，根据搜索规则及时更新并缩小搜索范围，当解或迭代次数达到预设值时终止。目前启发式算法分为构造启发式、改进启发式和元启发式。

G. CLARK和J.R.WRIGHT[3]的经典节约算法，GILLET[4]的高效扫描算法，SOLOMON[5]的插入启发式、节约启发式、邻近启发式等，都是根据相应插入准则，将客户迭代地插入到当前可行路径中，直到所有客户都被安排。构造启发式算法在解的质量上存在差距。LIN[6]的2-OPT和3-OPT算法，在插入过程暂时接受不可行解，然后改进使其可行。改进启发式在构造启发式的初始解的基础上改进，扩大了初始解的搜索空间。改进型启发式算法易陷入局部最优。为跳出局部最优，对搜索空间多样化探索，发展了遗传算法[7]、蚁群优化[8]和烟花算法[9]等算法。GILLETT[10]用自适应文化基因算法来求解VRPTW，并与遗传算法作了比较。

当前烟花算法与其改进算法已被广泛应用，例如油料作物施肥问题与电力系统重构问题[11]等，但在VRPTW中应用不多，本文将烟花算法用于求解VRPTW，为解决此类问题提供新思路。

1 带时间窗的车辆路径问题

基于VRP相关理论的基本假设：1) 对客户仅进行送货；2) 客户需求量及时间窗一定；3) 每个客户仅被一辆车服务一次；4) 给定配送中心及客户位置；5) 车辆具有相同载重；6)车辆不得超过最大载重；7) 每个客户在指定时间窗内进行，超过则不可行或加以惩罚；若早到需等待；8) 只有一个配送中心，车辆从配送中心出发并最终返回；9) 所有道路均畅通，不考虑突发情况。

VRPTW模型如下：用有向图G=(C,E)定义，由客户集C={0,1,2,…,n,n+1}和弧集E组成。节点0和n+1代表配送中心，其他n个顶点集合记为N。每个客户i(i∈N)需求为di，服务时间为si和时间窗[ei，li]，ei和li分别代表最早和最晚开始时间。假设车速=1，则行驶距离等于行驶时间。tij表示客户i到客户j(i,j∈N)的行驶距离；Cij代表车辆每条弧的成本。引入决策变量x和s，车辆k从客户i行驶到客户j(i≠j,i≠0,j≠n+1)，则决策变量xijk等于1，否则为0。决策变量sik表示车辆k开始为客户提供服务的时间。

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

sik+tij-(1-xijk)k=sjk,∀jN,∀iN,∀kK

(8)

ei≤si≤li,∀iN

(9)

目标函数式(1)表示最小化配送总成本；式(2)为确保每辆车需求总和不超过其最大载重； 式(3)-式(6)表示保证每辆车从配送中心离开，在服务完客户后返回配送中心；式(7)表示保证每个客户被一辆车服务一次；式(8)表示车辆从客户i行驶到客户j，不能在sik+tij之前到达客户j；式(9)表示确保满足所有时间窗。

2 求解VRPTW的改进型烟花算法

谭营在2010年提出烟花算法，通过模拟烟花爆炸行为建立相应模型。其思路是将初始生成烟花看作解空间中部分可行解，烟花爆炸生成火花过程类比为在原有烟花的邻域搜索过程，爆炸半径为相邻烟花位置的选择。通过烟花适应度值的信息交互，烟花对应的适应度值大，则在较大范围内生成较少火花，拥有全局搜索能力；反之，适应度值小，在较小范围内生成更多火花，具备更强局部搜索能力。

2.1 解决方案表示

在求解时，用一维向量表示解决方案，每一个数字代表一个客户，解决方案的长度代表客户总数，路径数量等于“0”的个数减1。在图1中，第一条路径有3个客户，第2、第3条路径都有2个客户。

图1 解决方案表示

2.2 适应度评估函数

通过适应度评估个体质量优劣，因VRPTW是多目标优化问题，所以用加权求和将其转化为单目标优化问题。适应度F(x)计算如下：

(10)

(11)

加权系数α和β分别是车辆数及行驶距离的权重参数。根据经验确定为α=100，β=0.001。

2.3 爆炸产生火花数

对于每个烟火xi(对应问题解决方案)，生成火花数量需在爆炸之前计算。为使烟花差异化，根据适应度值来控制爆炸产生火花数目。公式如下：

(12)

其中：Ni为第i个烟花的火花数量；M是限制火花数量常数；Ymax是当前种群适应度最大值；f(xi)是个体xi适应度值；ε是避免分母为0的极小常数值；其中M为50，N为5。由于生成火花数是一个整数，因此通过式(13)将其转换为整数，其中a为0.04，b为0.8。

(13)

2.4 爆炸操作

爆炸算子是将进行爆炸的烟花与目前存在的烟花及最优个体进行交叉重组产生新的火花。用示例给出解释：p1为等待爆炸烟花，p2代表所有烟花及火花中最优个体。p1的3条路径R1为4—8—2—9，R2为1—7和R3为3—5—6。步骤a)：从p1中选择R2，p2中选择R3。将给定个体在所选路径中移除，在p1中移除5和9，产生C1。同样，在p2中移除5和6，生成C2。步骤b)：将5和9重新插入到C1，同时将1和7重新插入到C2。首先插入哪个是随机的，若插入之后路径不满足约束，则插入点不可行。步骤c)：5和9都被插入到C1中恰当位置。若没找到可行插入点，则建立一条新路径。客户7没有被插入到p2当前路径中，因此创建新路径。爆炸操作示意如图2所示。

图2 爆炸操作示意图

自适应爆炸半径核心是使用已产生火花来计算最优烟花的爆炸半径，通过这一代信息来计算下一代最优烟花的半径。自适应半径是一种全新的控制步长方式，爆炸半径是否具有自适应能力对算法性能至关重要。公式如下：

(14)

自适应半径的计算，首先选择一个个体，用它与最优个体之间的距离作为下一次爆炸半径。必须满足条件：1) 适应度值比这一代的烟花差；2) 到最优个体的距离是满足1) 的个体中最短的；3) 确保目标函数至少比这一代进步要大，在下一次爆炸中找到更好位置；4) 确保半径收敛。虽然无法保证半径每次都减小，但当迭代次数足够大、火花数量足够多时，还是收敛的。

将计算的自适应半径乘以特定系数λ=1.3(经验值)以控制全局和局部搜索的平衡，A(g+1)←λ·A(g+1)，λ过小会过快收敛，λ过大将不会收敛。为减少火花数量有限的影响，采用简单平滑机制A(g+1)←0.5·[A(g)+A(g+1)] ，将计算的自适应半径和该代爆炸半径的平均值作为下一代爆炸半径。

2.5 变异操作

引入变异火花加强种群多样性，变异算子主要作用是增强局部搜索能力，免于陷入局部最优。在此采用高斯变异火花位置，计算如下：

(15)

其中g是服从均值为1、方差为1的高斯分布的随机数。

2.6 选择策略

用基于距离的选择策略选出剩余N-1个个体组成下一代群体。算法的分布式信息共享机制，是基于免疫浓度思想的选择，使烟花分布在不同区域不聚集来避免早熟。采用欧氏距离度量两个个体之间距离：

(16)

其中：d(xi，xj)表示任意两个个体xi和xj之间的欧氏距离，R(xi)表示个体xi与其他个体的距离之和；K是由爆炸算子产生的火花位置和高斯变异产生的火花位置的集合。个体选择采用轮盘赌的方式，个体被选中的概率p(xi)表示为：

(17)

得出个体距离更远的个体具有更多的机会成为下一代个体，此选择方式保证了算法的种群多样性。

3 实验结果与分析

通过对Solomon数据集的测试来验证改进型烟花算法对VRPTW求解的适用性和有效性。此数据集包含100个客户点，分为R1、R2、C1、C2、RC1和RC2 6个子类。C类在地理位置上是聚类的，R类是随机的，RC是两种情况的混合。对于R1、C1和RC1类问题，车辆载重小且时间窗紧，每辆车服务较少客户；相反，R2、C2和RC2具有大载重和宽松时间窗，每辆车服务较多客户。算法采用Matlab2014a编程，在Intel Core i5-3240MCPU@3.40GHz双核处理器，操作系统为32位的Windows7环境下运行。

用车辆数和行驶总里程评价最优解，通常固定成本高于运输成本，因此最小化车辆数优先级高于最小化行驶总里程，本文选取部分计算结果与已公布最优解比较。表1和表2得到的距离改进显著，但以增加额外车辆为代价，如R103和RC102。在R2及RC2中，车辆数大多等于当前最优解，但行驶总里程得到很好优化，如R204和RC207。算法的群体多样性使得算法跳出局部极值收敛到全局最优，另外自适应半径作为时变趋化步长使得局部搜索与全局搜索达到适应性平衡，在搜索时首先从有前途的邻域开展全局搜索，然后减慢开展局部搜索，从而得到最优解。

表3是IFWA的平均表现。通过比较表3、表1及表2，发现10次的平均结果与最优解相差不大，且平均结果都在可接受范围内，说明算法求解整体性能稳定。对解质量而言，使用该算法求解VRPTW具有可行性和有效性。在爆炸和变异算子作用下，根据烟花适应度值产生不同个数的火花和不同的爆炸半径，保证火花个数和爆炸半径的多样性；高斯变异保证爆炸的多样性；通过选择策略保留的烟花保证烟花的多样性，以上群体多样性的3个方面确保算法全局收敛。算法采用动态信息策略，保证在每次搜索中每个烟花都对搜索作出贡献，以达到快速寻优。

表1 IFWA与硬时间窗最佳公布结果比较

表2 IFWA与软时间窗最佳公布结果比较

表3 所罗门基准下的IFWA平均表现

4 结语

通过模拟烟花爆炸行为，设计了一种改进型烟花算法。求解带时间窗车辆路径问题。在迭代过程中通过优化控制策略对爆炸半径提出改进，使得爆炸半径实现自适应量化，有效提升算法的局部搜索能力。算法的分布式信息共享机制还避免了早熟。通过对测试算例与已知最优解比较，表明改进型烟花算法具有较好的求解精度，能够有效处理带时间窗车辆路径问题。

研究表明，改进型烟花算法在VRPTW上的成功应用拓宽了实际应用领域，为求解实时动态、复杂VRP问题提供了新思路。在此基础上，进一步考虑实际生活中客户需求的动态变化、道路实际交通情况等影响因素，将会是下一步研究重点。