摘要：利用遗传算法解决单车场单车型有时间窗约束的非满载车辆调度问题。针对非满载的VRP问题具有组间无序、组内有序的特性，采用一种有效的改进交叉算子，最大程度的保留了父代的优良特性并增强了算法的寻优能力，避免了早熟现象的发生，应用此方法分别对8个和13个客户有时间窗约束非满载车辆调度问题进行计算机仿真，得出了最优解，证明了本算法的优越性。

关键词：车辆调度；遗传算法；交叉算子；时间窗；非满载

0 引言

随着经济的全球化和网络信息技术的飞速发展，物流配送作为一个新的经济增长点已经引起了人们的注意。配送是物流系统的核心环节，是伴随着市场而诞生的一种必然的市场行为，随着市场竞争的日益激烈以及客户要求的不断提高，配送在未来的市场竞争中将起到举足轻重的作用。车辆优化调度问题是配送的核心问题，只有解决了调度问题才能使配送有效合理。因此许多专家学者将着眼点放在如何更好的解决车辆优化调度的问题上。

车辆调度问题(Vehicle Routing Problem 简称为VRP)问题最早是由Dantzig和Ramser于1959年提出的。VRP问题的解法丰富，基本上可以分为精确算法和启发式算法两大类。由于VRP属于强NP问题，运用精确算法求解计算量会随着问题的规模的增大而呈指数增加，因此，实际中其应用范围比较有限。实际应用中多采用启发式算法，其种类也很多，常用的有：Clarke和Wright提出的C-W节约启发式，Gillett 和Miller 提出的Sweep算法^[1]等。但这些算法也存在一定问题，节约法虽然运算速度快，但是组合点零乱、边缘点难以组合，往往在客户数目较多、问题规模增大时，可行解的空间也相应的增大，节约算法的优化效果也相应的下降；而扫描法为非渐进优化。随着科学的发展，不断有新的算法引入到VRP的求解中来，例如，模拟退火算法(Simulated  Annealing)，遗传算法(Genetic Algorithm)，神经网络算法(Neural Network)等。

国内对VRP的研究还处于刚刚起步的阶段。西南交通大学的郭耀煌、李军^[2]分别以分派和C-W为基础的启发式算法对VRP进行了求解。从解的过程来看，前者较适用于任务数较多的情况；而以C-W算法为基础的启发式算法可以处理有众多约束条件的实际问题。卜雷^[3]等用基于模拟退火的启发式算法求解了最短配送路径问题。郭耀煌^[4]等根据贪心算法原理设计的交互式优化方法解决了单车场满载问题。李军，谢秉磊^[5]设计了基于自然编码方式的可同时处理软、硬时间窗约束的遗传算法，给出了有9个客户的算例。张丽萍^[6]，姜大立^[7]等也运用遗传算法就VRP问题提出了自己的看法，用其求解没有时间窗的车辆调度问题。另外陈火根^[8]等提出了遗传算法与启发式算法相结合的求解方法，郎茂祥^[9]等将爬山算法与遗传算法相结合，提出了混合遗传算法。但是，车辆调度问题所涉及的种类繁多，遗传算法却没有普适的求解过程。

本文研究的是带有时间窗的VRP优化问题。优化目标是总运输路程最短，将客户的时间要求借助惩罚因子计入总运输路程最短的目标函数中，以消除不等式约束。在基本遗传算法的基础上进行改进，采用先进的编码方式和有效的交叉算子，实现了对优秀子串的最大保留，摆脱了对种群多样性的要求，提高了对种群的搜索能力，成功的实现了对带有时间窗约束的VRP问题的求解。

1 问题的描述及数学模型的建立

所谓带有时间窗的VRP问题就是指在对客户进行配送时，要考虑到各个客户对送货到达时间的要求，为了要取信于客户，必须在客户许可的时间范围内将货物送到。这类问题要比简单的VRP问题复杂的多，要想求得最优解也就更加困难了。