有容量约束车辆路径问题的多目标遗传算法  

Multi-Objective Genetic Algorithm for Solving Capacitated Vehicle Routing Problems

作　　者：邹书蓉[1,2] 黄晓滨[2] 张洪伟[2] 

机构地区：[1]西南交通大学CAD中心,四川成都610031 [2]成都信息工程学院计算机系,四川成都610225

出　　处：《西南交通大学学报》2009年第5期782-786,共5页Journal of Southwest Jiaotong University

基　　金：国家863计划资助项目(2007AA04Z188);四川省科技公关项目(07GG012-001);成都信息工程学院资助项目(KYTZ200901)

摘　　要：针对有容量约束车辆路径问题,提出了基于Pareto方法的多目标优化遗传算法.该算法引入基于擂台法的Pareto锦标赛选择算子,避免了求解非凸解的困难.采用最邻近算法和扫描算法构造初始种群及引入启发式交叉算子来加快算法的收敛速度.通过E-n30-k3算例实验表明:应用该算法得到的Pareto解集,为决策者提供了多种途径有效解决有容量约束车辆路径问题.A multi-objective genetic algorithm based on Pareto approach was proposed for capacitated vehicle routing problems （CVRPs）. In this algorithm, a new Pareto tournament selection operator based on arena＇s principle is used to avoid the difficulty of solving non-convex problems; meanwhile, the nearest-neighbor algorithm and sweep algorithm are adopted to initialize population, and heuristic crossover operator is introduced to accelerate the convergence speed. The simulation result on the E-n30-k3 test specimen shows that the Pareto set obtained by this algorithm can provide manifold paths for decision makers to solve CVRPs.

关 键 词：车辆路径问题 多目标遗传算法 Pareto锦标赛选择算子 擂台法则 启发式算法 

分 类 号：U492.22[交通运输工程—交通运输规划与管理]