刘睿琼 张文丽 侯爱华

（1.西安理工大学高等技术学院 西安 710082）（2.陕西理工大学物电学院 汉中 723000）

1 引言

遗传算法属于随机搜索算法，其来源于生物界自然选择和自然遗传机制，在各类工程优化问题中得到了广泛应用。在车辆调度领域，遗传算法应用已经很多，但多采用标准遗传算法［1］。遗传算法是以点集到点集的方式进行搜索，相对于点到点的搜索方法能以更大的概率搜索到全局最优解，但在实践应用过程中遗传算法往往容易产生早熟［2］，而得不到全局最优解，因此需要对其进行改进。模拟退火算法不仅接收使目标函数变好的解，还在一定程度上接收使目标函数变差的解，克服了遗传算法局部搜索能力较差、易出现早熟现象的缺点。因此，如果能够使用模拟退火算法对种群进行优化，能够有效提高遗传算法的运行效率和准确性。

2 数学模型

本文主要讨论单配送中心有时间窗约束车辆调度（VRPTW）问题［3］。设 N 表示为客户总数，编号分别为1，2，…，N；编号0表示配送中心。D=(dij)为历程矩阵。配送中心的车辆数为K，q为车辆的容积。gi表示第i个客户的需求量。[ai，bi]为客户i的时间窗，即送货时间不能早于ai，且不能晚于bi，否则就要追加一定的时间窗惩罚值。ti为车辆到达客户i的时间。此外，对于客户i，j(i≠j)、车辆k定义如下两个变量：xijk和 yik

根据以上假设，有时间窗约束车辆调度问题的数学模型可表示为

约束条件如下：

在上述表达式中，式（1）为目标函数，时间窗惩罚函数将在后面讨论；式（2）表示每个客户的货物只由一辆车配送；式（3）～（4）表示变量之间的约束关系；式（5）～（7）保证了车辆始于配送中心，不重复的经过客户后，最终又回到配送中心；式（8）表示一辆车的任务量不大于其容量；式（9）表示交货时间窗约束。

3 融合了模拟退火的改进遗传算法的实现

融合模拟退火的遗传算法是在基本遗传算法运算流程的基础上，融入了模拟退火算法，针对选择运算、交叉运算和变异运算产生的新种群，使用模拟退货算法逐一进行优化，改善遗传算法的局部搜索能力。整个算法的执行过程如图1所示。

图1 融合模拟退火的遗传算法流程图

3.1 遗传算法的实现

3.1.1 染色体编码

本文采用自然数编码［4～5］，使用自然数对每个客户进行编码，以客户点作为基因，按访问的先后次序组成的染色体对应问题的解。例如，若问题的解路线为

路线1：0—2—5—6—0

路线2：0—1—7—3—8—0

路线3：0—4—9—0

去除配送点编号0，然后将车辆路线的客户点首尾顺序连接起来，那么，上例中的染色体编码应该为256173849。解码只是编码的逆向操作，按顺序依次将基因位表示的节点插入到路线中。当某一个结点加入后不满足时间或者体积约束时，就新增一条路线且把此点插入［6］。

3.1.2 适应度函数

在实际的车辆调度配送问题中，运行成本主要由两部分组成。一部分是车辆在配送过程的行驶成本，如果车速一定的情况下，这一部分与距离成正比；另一部分是违反客户配送时间要求（即时间约束窗口）的惩罚成本，这一部分与货物配送至客户的时间相关。本文中对于时间窗约束的惩罚函数［7］形式如下：

其中：si为客户 pi的时间窗惩罚函数，M 为一个足够大的正整数，α1、α2、β1、β2为常数。综合配送车辆的行驶成本和时间窗惩罚成本，配送过程中的总成本可用如下函数表示：

3.1.3 选择算子

本文采用比例选择算子。为了使适应度最好的个体尽可能地保留下来，我们在遗传算法中还使用了最优保留策略。

2）对于第i个个体，计算从第1个到第i个个体的累计相对适应度

3）产生［0，1］内均匀分布的随机数 r，当P(i-1)＜r≤Pi时选择此个体i；

3.1.4 交叉算子

本文采用部分映射交叉算子［8］，整个交叉操作过程分为两步。首先对父代基因串进行双点交叉操作；然后根据交叉区域内各基因值的映射关系来修改交叉区域以外的基因位的基因值。

⇓根据如上的映射关系得

其中交叉交换点k1，k2是随机选取的。

3.1.5 变异算子

本文采用倒位变异的方法作为变异算子［9］。倒位变异是指在父体中随机的选择两个断点，将断点之间的基因逆序排列，从而产生一个新的个体。

3.2 模拟退火算法的实现

3.2.1 冷却进度表

冷却进度表是一组算法进程的控制参数，用以逼近模拟退火算法的渐进收敛性，可以使算法执行一定时间后返回一个近似最优解［10］。

1）控制参数初值t0。本文通过计算若干次随机变换目标函数平均增量的方法来确定t0［11］的值：，其中为计算若干次随机变换目

标函数平均增量。只要设定初始接受率 p0，就能求出相应的t0值。

2）停止准则。当连续若干次降温后目标函数无改进或者接受率小于给定足够小的正数λ时停止算法。

3）控制参数衰减函数［12］。本文采用指数衰减策略，取tk=αtk-1其中α为一接近1的常数，一般取0.5～0.99之间，本文选取α=0.9。

4）马尔科夫链长度。本文采用固定长度马尔科夫链 Lk=20［13］。

3.2.2 状态产生函数

文献［14］给出一种新的方法——排序反转并移位，即随机在编码串中产生三个断点k1、k2、k3（k1＜k2＜k3），将k1和k2之间的编码倒序排列并插入到k3之后。并证明了此方法求解旅行商问题相当有效，本文采用此方法。

3.2.3 状态接受函数

采用Metropolis准则作为状态接受函数［15］。即接受新解的概率为

Metropolis接受准则的优点是可以对优化解以一定的概率来接受，尽可能避免陷入局部最优更有可能最终获得系统的全局或近似全局最优解。

4 仿真结果分析

根据实际问题有这样一个配送系统，系统中含有1个配送中心，编号为0；8个客户，编号依次从1至8，配送中心车辆的容量最大为8t。已知每个客户的货运量：gi（单位：立方），卸货时间为：si（单位：小时），每项任务时间窗[ai，bi]（单位：小时）见表1，客户之间的距离见表2。合理安排行车路线，使总运输距离最小。

表1 客户的特征及要求

表2 客户之间的距离

本文采用的算法的仿真参数取值如下：初始种群随机产生，种群个体数为50；种群遗传进化的代数设为100；针对选择的个体以 pc=0.8概率进行交叉；交叉操作后的个体以 pm=0.1概率进行变异；车辆按60公里/小时的固定速度行驶；马尔科夫链长L=20；接受概率小于0.01或连续40次降温无变化则停止；退火系统为α=0.9，p0=0.95。表3给出了融合了模拟退火的改进遗传算法和基本遗传算法的多次仿真结果比较（总成本的单位：公里，行驶时间的单位：小时）。该问题的最优解为：0-8-5-7-0，0-6-4-0，0-3-1-2-0，最 优 距 离 为1092，行驶时间为33.5。

表3 融合了模拟退火的改进遗传算法和基本的遗传算法结果比较

通过比较可以看出，融合了模拟退火的改进遗传算法和基本遗传算法都能得到最优解，但本文所使用算法的局部搜索能力得到了显著提高，避免了出现早熟现象，将进化代数由100降到了10，仍然能每次都得到1092km的最优解。而且，融合了模拟退火的改进遗传算法的收敛速度明显优于遗传算法。

5 结语

本文讨论了有时间约束窗口的车辆调度系统的数学模型和遗传算法的详细实现过程，指出了遗传算法具有局部搜索能力较差、易产生早熟现象的缺点，并在遗传算法搜索过程中融入了模拟退火算法，针对选择运算、交叉运算和变异运算产生的新种群，使用模拟退货算法逐一进行优化，新算法兼顾了局部和全局两方面，克服了遗传算法的缺点，仿真结果证明是一套完善可行的优化方法。