基于多目标遗传算法求解时间窗车辆路径问题  

Multi-Objective Genetic Algorithm for Vehicle Routing Problem with Time Windows

作　　者：刘敏[1] 郑金华[1] 蒋浩[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与应用》2006年第9期186-189,207,共5页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:90104021);湖南省自然科学基金资助项目(编号:01JJY2060)

摘　　要：有别于传统的单目标方法,将带时间窗约束的车辆路径问题描述成为一个多目标最优化问题,并为之提出了一种多目标遗传算法。在算法中设计了擂台法则作为构造非支配集的方法,提出了可变爬山率的局部爬山法,并通过将组合种群分成多层非支配集来实现精英保留策略。实验结果表明,该算法能有效地求解车辆路径问题并且为决策者提供了强有力的决策支持。Unlike traditional single objective method,Vehicle Routing Problem with Time Windows（VRPTW） is represented as a multi-objective optimization problem.This paper presents a multi-objective genetic algorithm to solve VRPTW, Arena＇s principle is designed to construct non-dominated set and a hill-climbing method with alterable probability is proposed too.In order to keep elitism,the combined population is divided into multiple layers.The experimental results indicate that this algorithm is quite effective for VRPTW and provides powerful decision support to the decision-maker.

关 键 词：车辆路径 遗传算法 多目标最优化 擂台法则 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]