计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (25): 237-239.

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

单车场多送货点车辆路径问题的改进遗传算法

屈 援1,2,汪 波2,钟石泉2   

  1. 1.暨南大学 管理学院,广州 510632
    2.天津大学 管理学院,天津 300072
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-01 发布日期:2007-09-01
  • 通讯作者: 屈 援

Improved genetic algorithm for vehicle routing problem with single depot and weight limit

QU Yuan1,2,WANG Bo2,ZHONG Shi-quan2   

  1. 1.School of Management,Jinan University,Guangzhou 510632,China
    2.School of Management,Tianjin University,Tianjin 300072,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-09-01 Published:2007-09-01
  • Contact: QU Yuan

摘要: 针对单车场多送货点容量约束的车辆路径问题提出了一种改进的遗传算法。该算法基于自然数编码的染色体,采用了改进的交叉和变异法、内部扰动和外部扰动等技术,提高了遗传算法的优化效率和优化效果。介绍了此算法的原理,给出了具有两个代表性算例试验结果和结果分析。试验结果表明了该改进遗传算法对求解单车场多送货点容量约束的车辆路径问题的有效性。

关键词: 车辆路径问题, 遗传算法, 容量约束

Abstract: In this paper,an improved Genetic Algorithm(GA) has been presented to the vehicle routing Problem(VSP) with a single depot,many delivery points and weight limit.The algorithm is also based on the chromosome on nature number,but some techniques such as improved crossover and mutation,inside perturbation,outside perturbation are used in the algorithm.In this paper,the principium of the GA has been introduced,two representative results and the analysis have been given.The experiments indicate the validity of the improved GA to the VSP with the above-mentioned conditions.

Key words: vehicle routing problem, genetic algorithm, weight limit