Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (20): 54-56.DOI: 10.3778/j.issn.1002-8331.2008.20.016

• 理论研究 • Previous Articles     Next Articles

Hybrid intelligence algorithm based on vehicle routing problem with time windows

ZHANG You-hua,ZHANG Cui-jun,CUI Zhong-qiang   

  1. College of Information and Technology,Shijiazhuang University of Economics,Shijiazhuang 050031,China
  • Received:2007-10-11 Revised:2008-01-04 Online:2008-07-11 Published:2008-07-11
  • Contact: ZHANG You-hua

有时间窗车辆路径问题的混合智能算法

张有华,张翠军,崔忠强   

  1. 石家庄经济学院 信息工程学院,石家庄 050031
  • 通讯作者: 张有华

Abstract: Vehicle routing problem with time windows is a NP-hard problem in combinatorial optimization field.Based on the analysis about it,a mathematical model is built and a hybrid intelligence algorithm for solving it is designed.The algorithm lets ant colony algorithm and genetic algorithm execute alternately and communicate timely in the optimization process.It learns the colony algorithm’s and genetic algorithm’s advantages and makes up their disadvantages.Thus its ability of optimization is enhanced and premature phenomenon is avoided.The experiment results show that the hybrid algorithm is efficient in solving vehicle routing problem with time windows.

Key words: vehicle routing problem with time windows, NP-hard problem, ant colony algorithm, genetic algorithm, hybrid intelligence algorithm

摘要: 有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化,并且及时交换信息,弥补了蚁群算法和遗传算法各自的不足,达到了优势互补的效果,增强了算法的寻优能力,避免了停滞现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。

关键词: 有时间窗车辆路径问题, NP-hard问题, 蚁群算法, 遗传算法, 混合智能算法