基于多目标免疫进化算法的动态车辆路径优化研究

作     者：胡宇博 

作者单位：郑州大学 

学位级别：硕士

导师姓名：陈铁军

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：车辆路径 动态优化 免疫进化 多目标 

摘      要：车辆路径优化问题(VRP:Vehicle Routing Problem)是具有多个约束条件的组合优化NP难题,是在控制科学、优化学说以及运筹论及其相关学科中的研究热点之一。其较难使用一般的算法达到满意解,通常采用智能优化方法进行研究探讨。车辆路径优化问题已经拓展到社会日常生活、工作中的公共交通中铁路、公路和航空等调度,邮件、货物等物流的配送以及城市水、电、煤气等运输调配等,在现代信息社会中起到了不可估量的作用。 通过对多种智能优化算法进行了分析比较,针对动态车辆路径优化的特点选取免疫进化算法作为有效的解决方法。在对多目标优化基础问题的研究上,把免疫系统的克隆选择学说与生物进化法则应用到多目标优化计算中,即并行了免疫进化系统的记忆单元体。应用聚类方法对抗体种群进行优化排序,单抗体采用非均匀变异的位操作促进种群抗体个性化;抗体间采用交叉到位操作模仿进化操作,通过种群中抗体间亲和力维持竞争进化,抗体与抗原亲和度来促使优化,抑制竞争过度,使种群更具广泛性。 本论文主要的工作内容和研究成果如下: 首先,由国内外在多目标车辆路径优化的研究情况展开,分析了多目标优化研究方面各种经典、智能算法的发展趋势,以及在信息化的社会中运用智能的手段解决多目标车辆路径优化是非常必要的。 其次,针对动态车辆路径优化的特点,提出采用动态车辆路径配送策略规划即模块分组优化的策略,对工作时间分段处理,划分为三个子模块:订单处理模块,多目标免疫进化优化算法模块,信息存储模块,使其能更好的记忆、调整、优化动态车辆路径问题。 文章最后对三类顾客点分布情况下的车辆路径优化进行了仿真实验对比,主要选取了近些年在智能优化上取得良好优化结果的蚁群算法、禁忌搜索算法、贪婪算法和遗传算法在相应领域的实验结果进行对比。通过优化性能指标“达优率来对比实验数据,结果表明:免疫进化算法在动态车辆路径配送策略规划中可以有效求解动态多目标车辆路径优化问题,而且所得结果与其他优化算法得到结果有较明显改善。 本文利用多目标免疫进化算法在三类顾客点分布情况下所得到了多个非支配解,不仅为决策者提供了多种个性化选择,也有利于决策者依据现实情况做出更好的决策。为与我们生活、工作结合日益紧密的车辆路径优化问题提供了一种崭新的解决方法与途径。