计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (15): 205-207.

• 工程与应用 • 上一篇    下一篇

混合遗传算法求解配送车辆调度问题

曲倩倩,曲仕茹,温凯歌

  

  1. 西北工业大学 自动化学院,西安 710072
  • 收稿日期:2007-11-13 修回日期:2008-01-29 出版日期:2008-05-21 发布日期:2008-05-21
  • 通讯作者: 曲倩倩

Hybrid genetic algorithm for distribution vehicle routing problem

QU Qian-qian,QU Shi-ru,WEN Kai-ge   

  1. College of Automation,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2007-11-13 Revised:2008-01-29 Online:2008-05-21 Published:2008-05-21
  • Contact: QU Qian-qian

摘要: 车辆调度优化是物流配送的关键环节。针对有时间窗的车辆调度问题,综合考虑了路网中的交通状况,提出改进的车辆调度模型。并针对这个模型,设计了混合遗传算法,采用自适应策略调整交叉和变异概率,引进有效的交叉和变异算子,并结合模拟退火算法缓解遗传算法的选择压力,避免早熟收敛。仿真结果表明该算法与标准遗传算法相比有更好的性能。

关键词: 车辆调度问题, 混合遗传算法, 自适应策略, 路阻函数

Abstract: The optimization of vehicle routing is the focus of the logistic distribution.Aiming at solving the vehicle routing problem with time windows,an improved vehicle routing model is built under the consideration of the traffic status.A hybrid genetic algorithm is proposed based on the model above and the self-adaptive strategies are introduced to adjust the parameters of crossover and mutation.Effective crossover and mutation operators are also adopted in the algorithm.Moreover,in order to relieve the selecting pressure,the simulated annealing algorithm is combined with the genetic algorithm and consequently the global convergence has been greatly improved.Results of the simulation show that the proposed algorithm is more efficient compared with the classic genetic algorithm.

Key words: vehicle routing problem, hybrid genetic algorithm, self-adaptive strategy, impedance function