多约束条件车辆路径问题的二阶段遗传退火算法

吕　军　冯博琴　李　波

摘要：针对多约束条件的多配送中心有时间窗车辆路径问题，提出了一种二阶段遗传退火算法．在第1阶段，使用遗传算法对客户按供应量和路径长度进行模糊分区；在第2阶段，采用二维变长染色体编码及相应的遗传算子进行混合遗传算法的全局优化．在初始种群生成和交叉、变异算子中采用了随机贪心算法以避免无效解，并利用退火选择来提高种群的多样性。实验结果表明，二阶段遗传退火算法可加速收敛，提高搜索效率，在模糊分区上的搜索速度较之标准遗传算法提高了3～10倍。

关键词：车辆路径；遗传退火算法；贪心算法

中图分类号：TPl8；U116文献标识码：A文章编号：0253—987X(2005)12—1299—04