刘睿琼 张文丽 侯爱华

（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）表示每个客户的货物只由一辆车配送；……