计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (21): 225-228.

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

求解车辆路径安排问题的混合遗传算法

戴树贵1,2,姜昌华1,潘荫荣1,胡幼华1   

  1. 1.华东师范大学 计算机科学技术系,上海 200062
    2.滁州学院 数学系,安徽 滁州 239000
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-21 发布日期:2007-07-21
  • 通讯作者: 戴树贵

Hybrid Genetic Algorithm for solving Vehicle Routing Problem

DAI Shu-gui1,2,JIANG Chang-hua1,PAN Yin-rong1,HU You-hua1   

  1. 1.Dept. of Computer Science and Technology,East China Normal University,Shanghai 200062,China
    2.Dept. of Mathematics,Chuzhou University,Chuzhou,Anhui 239000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-21 Published:2007-07-21
  • Contact: DAI Shu-gui

摘要: 讨论了具有容量限制的车辆路径安排问题,设计了一个高效混合遗传算法。针对简单遗传算法易收敛于局部最优解的缺点,算法设计了交叉规则和选择策略。只有当两个个体的评价函数值满足一定条件时,才能进行交叉操作。采用优良个体保留策略执行选择操作,设计了保留函数。算法依据顶点间的位置关系,设计了优化策略,在每代进化中按概率选择一定数量的个体执行优化操作。数据实验表明,该算法是一个有效的求解车辆路径安排问题的混合遗传算法。

关键词: 车辆路径安排问题, 遗传算法, 交叉规则, 优化策略

Abstract: Capacitated Vehicle Routing Problem(CVRP) is discussed,and an efficient hybrid genetic algorithm is designed.Crossover and selection rule are designed to overcome the shortcoming of simple genetic algorithm that is easy to trapping in local optimum.Crossover can be performed only between two individuals satisfying the given condition.Better individuals preserved policy is adopted and a function is designed to decide the number of better individuals.Optimal policy is schemed out according to locations relations between points and some individuals are selected to optimize in every generation according to the given probability.The data experiment show the algorithm is an efficient algorithm for solving CVRP.

Key words: Vehicle Routing Problem, genetic algorithm, crossover rule, optimal policy