车辆路径问题(Vehicle Routing Problem, VRP)是1959年由Dantzig G B等^[1]首次提出的, 即已知客户和出发点位置、车辆最大负荷和客户需求, 设计车辆路径, 使运行距离最短。带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows, VRPTW)是在VRP的基础上加上客户要求访问的时间窗约束^[2]。40多年来, 许多学者对VRPTW问题进行了深入研究, 尤其是20世纪90年代以来, 遗传算法、神经网络、模拟退火、禁忌搜索等人工智能算法的出现, 为求解VRPTW问题提供了新的工具。其中, Thangiah S R^[3]曾用遗传算法求解过VRPTW问题。本文在其基础上提出一种混合遗传算法, 该算法采用一种包含有更多信息的染色体结构, 辅以局部搜索技术, 寻找车辆路经最优解。

1.   VRPTW问题的数学模型

VRPTW问题可以描述为出发点O有若干完全相同的车辆将访问n个客户C₁、c₂、…、c_n, 已知车辆载货量为q, 客户c_i任务量为d_i, 1<i<n, 距离矩阵为C=[c_ij], 0 < i, j < n, c_ij为c_i与c_j间的距离, s_ik为车辆k开始对客户i进行访问的时刻, [a_i, b_i]为客户c_i的访问时间窗约束, 即车辆到达c_i的时间最早不能早于a_i, 最迟不能晚于b_i。要求在上述条件下, 设计车辆路径, 使运行距离最短, 因此, VRPTW问题的数学模型为

约束条件式(2)表示某一车辆任务量之和不大于其容量; 式(3)表示客户i的任务只能由某一辆车完成; 式(4)和式(5)表示两个变量之间的约束关系^[4]; 式(6)~(8)保证每辆车始于出发点, 访问客户后, 最后又回到出发点^[5]; 式(9)表示时间窗约束。

2.   VRPTW问题的混合遗传算法

本文提出了一种混合遗传算法, 即在标准遗传算法中巧妙嵌入一个优化过程, 算法流程如下。

2.1   产生初始种群

本研究采用的是自然数编码方式, 用矢量(s₁, s₂, …, s_n)表示染色体G, 其中元素(基因)s_j为[1, n]之间的一个互异自然数。随机产生一组互异染色体G_h(h=1, 2, …, k), 其中k为一代种群中的个体数, 此为第一代种群^[6]。

2.2   优化过程

从左向右进行分组, 可将其编码为线路结构, 比如, 染色体: (2, 5, 8, 3, 6, 7, 1, 4)可编码成如下线路结构: ((2, 5, 8)(3, 6, 7)(1, 4))、((2, 5, 8)(3, 6)(7, 1, 4))、((2, 5, 8, 3)(6, 7)(1, 4))等。每一组表示一条路径, 不同分组的染色体表示不同的解。显然, 这些解可行, 但不一定是最优解。

为了找到每个染色体的最佳分组, 把分组信息和每个解联系起来^[7], 例如, 染色体可以表示为

新表示中, 括弧内部分是分组信息。[3 3 2]表示前3个客户在第一条线路, 接下来的3个客户在第二条线路。

然后使用λ-交换局部搜索方法在路径之间交换客户, 以改善可行解。该方法是1994年由Osman等^[8]提出的一种局部搜索方法。不妨令λ=1, 即路径间至多交换1个客户。λ的取值决定了可定义3种交换操作, 即(0, 1)、(1, 0)、(1, 1)。对一个线路对(R_P, R_Q)执行操作(1, 1), 含义是1个客户从R_p迁移到R_Q, 同时1个客户从R_Q迁移到R_P。其他操作类似定义, 应沿路径逐一考虑所有客户在每种交换情况下的成本, 目的是寻找导致总成本下降的交换。如果初始分组信息是[3 3 2], 就可检查[2 3 3]、[3 2 3]等, 容易定义搜索顺序和操作。每个新分组将首先进行可行性检查, 只有可行的分组才会被考虑。当然, 搜索策略有2种: 局部最优法和全局最优法。前者当找到第一个导致成本下降的分组时停止搜索, 如果搜索时间结束, 还没有找到新的分组时, 则分组信息不变; 后者则寻找导致成本下降最大解^[7]。显然, 后者比前者搜索完备, 但时间长。

2.3   计算适应值

对种群中每个染色体G_h(h-1, 2, …, k), 将上面得到的改善解代入式(1), 求出对应的目标函数值Z_h; 若某染色体对应不可行解, 则赋予其目标函数一个很大的整数Z_h=M; 令G_h的适应值函数f_h=1/Z_h, f_h是G_h个体生存能力的表现, 越大表明其性能越好, 即其对应的解越接近最优解。

2.4   判断停止进化条件

判断迭代代数是否为要求代数N, 若是, 停止进化, 选性能最好的染色体G_h所对应的路径集合, 作为优化解输出; 反之, 继续执行2.5。

2.5   复制

将每代种群中适应值f_h最大的染色体复制后直接进入下一代种群; 剩下的染色体从前代种群染色体中用轮盘旋转法产生。这样既可保证最优个体可以生存至下一代, 又可避免个体间因适应值不同而使被选择进入下一代的机会相差悬殊。

2.6   染色体交叉

对2.5产生的新种群, 按交叉概率p_c进行n/2次交叉重组, 交叉规则采用PMX法^[9]。设父代的两个染色体为G₁=(8, 4, 5, 6, 7, 1, 3, 2), G₂=(8, 7, 1, 2, 3, 5, 4, 6), 按PMX法, 交叉重组过程如下

其中交叉交换点k₁、k₂是随机选取的。对交叉成功得到的子代应用2.2、2.3求得其对应的适应值, 并与其父代进行比较, 择性能优者进入种群。

2.7   染色体变异

在每代种群中以变异概率p_m进行染色体变异, 采用随机交换选中染色体内2个基因值的变异策略, 对变异成功的染色体应用2.2、2.3求其适应值, 与父代染色体比较, 择性能优者进入种群。

3.   实验分析

某公司有1家配送中心和8家连锁店, 各连锁店任务量为d_i(单位: t), 服务时间T_i(单位: h)和配送中心与各连锁店间的距离c_ij(单位: km), 其中0表示配送中心, 见表 1。服务时间窗口[a_i, b_i]依次为[6, 9]、[6, 8]、[7, 9]、[8, 12]、[7, 11]、[7, 10]、[7, 10]、[9, 12]。所有配送均由载货量为10 t的车辆完成, 要求合理安排车辆行驶路线, 使总运输里程最短。

表  1  配送任务的特征描述

Table  1.  Assignment characteristics

下载: 导出CSV 

| 显示表格

使用标准遗传算法对该问题进行求解, 预定进化代数为100, 车辆的行驶路线结果为

总行驶里程为182 km。使用混合遗传算法进行求解, 车辆的行驶路线结果为

总行驶里程为162 km。经验证, 该结果完全满足车辆容量约束和时间窗约束。

4.   结语

本文针对VRPTW问题提出了一种混合遗传算法, 即在标准遗传算法中巧妙地嵌入一个优化过程。在优化过程中, 该混合遗传算法的求解结果随着进化代数的增加而逐渐优化, 当种群失去多样性时再继续迭代下去, 优化结果仍有改善, 并没有出现“早熟收敛”问题; 求出的总行驶里程远远小于使用标准遗传算法求出的总行驶里程, 这说明本文提出混合遗传算法的求解结果大大优于标准遗传算法。