改进遗传算法在包装件物流配送中的研究与应用

论文摘要

随着物流产业的迅猛发展,车辆路径规划问题日益受到研究人员和管理者的关注。在包装件配送领域,随着包装件的小批量、多批次的及时配送方式的发展,作为物流组成环节的物流配送,由于其配送成本在物流成本中的比重逐渐加大,选择有效的配送路线,减少配送成本,己经成为控制物流成本的主要措施。本课题旨在通过对遗传算法的研究,构造一种较为适合包装件Vehicle RoutingProblem(VRP)问题的改进遗传算法,能够运用该算法更好的解决VRP问题,为包装件在物流配送的路径规划问题中提供决策支持,基于该目的,本课题主要完成了以下几项工作:(1)对国内外关于车辆路径规划的资料进行研究,确立了以遗传算法为基本优化工具,对包装件车辆路径规划进行优化设计的研究思路。(2)对包装件物流配送的特点进行了研究,对遗传算法进行了系统的研究,分析了遗传算法的基本实现过程,着重研究了单亲遗传算法与基本遗传算法的区别,发现单亲遗传算法更适合于求解包装件VRP问题。(3)针对包装件VRP问题的特点,结合实际算例,从算子设计的角度入手,对各算子对优化效果的影响进行分析,指出标准遗传算法在求解VRP问题时的固有缺陷,进而为下一步的算法改进设计提供理论依据。(4)针对上述缺陷,对标准遗传算法进行了改进设计。主要方法是采用射线扫描法生成初始种群,以提高算法的收敛速度;结合单亲遗传算法的优点,设计了基于单亲遗传算法的进化逆操作交叉算子,以加强算法的局部搜索能力。基于MALAB平台仿真结果表明,通过改进设计,提高了遗传算法在求解包装件VRP问题时的准确性和速度。(5)将三维地形特征引入包装件车辆路径规划问题,以总路径尽可能短和总坡度尽可能小为多目标优化的目标函数,构建了多目标VRP问题的优化模型。采用双向扫描方法生成初始种群,将改进遗传算法应用于考虑三维地形的路径规划,通过MATLAB实现了包装件VRP问题多目标优化。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 车辆路径问题简介
• 1.2.1 车辆路径问题的定义
• 1.2.2 车辆路径问题的分类
• 1.2.3 车辆路径问题的研究现状
• 1.2.4 求解车辆路径问题的常用算法
• 1.3 本课题的研究目的及内容
• 2 遗传算法研究概述
• 2.1 遗传算法的起源、研究历史与现状
• 2.1.1 遗传算法的思想起源
• 2.1.2 遗传算法的研究历史与现状
• 2.2 遗传算法的特点和应用
• 2.3 基本遗传算法及其实现
• 2.3.1 编码
• 2.3.2 群体设定
• 2.3.3 适应度函数
• 2.3.4 遗传算法的基本操作
• 2.3.5 约束条件的处理方法
• 2.4 遗传算法的改进
• 3 改进遗传算法在包装件单目标路径优化中的研究与应用
• 3.1 包装件物流配送车辆路径规划的问题描述和数学模型
• 3.2 标准遗传算法各算子对单目标路径优化的影响分析
• 3.2.1 单目标VRPTW问题染色体的编码形式
• 3.2.2 种群初始化对优化效果的影响
• 3.2.3 选择算子对优化效果的影响
• 3.2.4 交叉算子对优化效果的影响
• 3.2.5 变异算子对优化效果的影响
• 3.3 改进遗传算法的设计与实现
• 3.3.1 射线扫描法生成初始种群
• 3.3.2 适应度函数的设计
• 3.3.3 选择算子的改进设计
• 3.3.4 交叉算子的改进设计
• 3.3.5 变异算子的改进设计
• 3.4 基于MATLAB的仿真研究
• 3.4.1 基于MATLAB仿真平台的特点
• 3.4.2 单目标路径优化的实例分析
• 3.5 本章小结
• 4 基于三维地形的包装件多目标遗传算法求解VRP问题
• 4.1 基于三维地形的车辆路径的数学模型
• 4.2 求解VRP问题中多目标遗传算法设计
• 4.2.1 VRP问题中的非支配集定义
• 4.2.2 染色体编码和适应度函数
• 4.2.3 初始种群的产生
• 4.2.4 多目标遗传算法的设计
• 4.3 多目标路径优化的实现与分析
• 4.4 本章小结
• 5 结论和展望
• 5.1 研究结论
• 5.2 工作展望
• 致谢
• 参考文献
• 发表文章