Abstract: Focused on the vehicle scheduling problem with time window and based on standard genetic algorithm, a new improved genetic algorithm was set up. In the new algorithm, local search ability is enhanced by adding hill-climbing algorithm; the constringency ability is improved through global-best-gene-protection strategy; and a self-organized mutation arithmetic operator is involved. The experimentation demonstrated that the improved algorithm can constringe fast, have the strong ablity of local-search and can avoid prematurity in a certain sense.

Key words: time window, vehicle schedual, complex generic algorithm, hill-climbing search, self-organized mutation arithmetic operator

摘要： 针对有时间窗的车辆调度问题，在标准遗传算法的基础上，加入爬山算法增强算法的局部搜索能力，通过保护全局最优基因的方法提高了算法的收敛能力，并辅以自适应变异算子，构造了一种改进的混合遗传算法。实验结果表明，改进后的算法具有抗“早熟”能力强、收敛速度快和局部搜索能力强的特点。

关键词: 时间窗, 车辆调度, 混合遗传算法, 爬山算法, 自适应变异算子