基于改进蚁群算法的物流配送路线研究

论文摘要

随着信息技术的发展,现代物流作为“第三个利润源泉”正受到日益广泛的重视。在现代物流中,配送是一个重要的与消费者直接相连的环节,物流配送路线研究,又是配送系统中的重要一环。有时间窗约束的车辆路径问题(VRPTW)是一个NP(多项式复杂程度的非确定性问题)难题,用启发式算法求解该问题已成为人们研究的一个重要方向。本文以蚁群算法思想为基础,分析了基本蚁群算法搜索时间长和易于出现早熟停滞现象的主要原因,并针对此在信息素更新方式上进行了改进,同时引入目标节点选择策略和最优个体灾变策略及局部最优搜索策略,有效地抑制了收敛过程中的时间过长和早熟停滞现象。并将改进后算法应用于求解VRPTW问题,实验结果分析表明,改进算法是有效的。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 本文研究背景和意义
• 1.1.1 本文研究的背景
• 1.1.2 本文研究的意义
• 1.2 国内外相关研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 本文主要研究内容
• 1.4 本文的技术路线
• 2 物流和物流配送理论
• 2.1 物流配送理论
• 2.1.1 物流配送概述
• 2.1.2 物流配送模式
• 2.1.3 物流配送路线约束条件
• 2.2 物流配送中的车辆路线问题
• 2.2.1 车辆路线问题的定义
• 2.2.2 车辆路线问题的分类
• 3 带时间窗约束的车辆路线模型的构建
• 3.1 VRPTW 问题中的时间窗
• 3.1.1 硬时间窗
• 3.1.2 软时间窗
• 3.1.3 混合时间窗
• 3.2 VRPTW 问题的分析
• 3.2.1 VRPTW 问题的界定
• 3.2.2 求解 VRPTW 问题存在的困难
• 3.2.3 求解 VRPTW 问题的关键因素
• 3.2.4 解决 VRPTW 问题的有效途径
• 3.2.5 组合优化问题及其计算复杂性的分析
• 3.3 VRPTW 模型的构建
• 3.3.1 基本假设与符号说明
• 3.3.2 VRPTW 模型的构建
• 3.3.3 对求解 VRPTW 问题算法的综合分析
• 4 基本蚁群优化算法
• 4.1 蚁群算法
• 4.1.1 自然蚁群的特点
• 4.1.2 人工蚁群的模型
• 4.1.3 蚁群系统
• 4.2 蚁群优化算法
• 4.2.1 蚁群优化算法的实现
• 4.2.2 蚁群优化算法的特点
• 4.2.3 蚁群优化算法的收敛性分析
• 4.3 蚁群优化算法中参数的设置
• 4.4 蚁群优化算法的优点与不足
• 4.4.1 蚁群算法的优点
• 4.4.2 蚁群算法的不足
• 5 改进蚁群算法求解 VRPTW 问题
• 5.1 改进蚁群算法的基本原理
• 5.1.1 信息素更新方式
• 5.1.2 目标节点选择策略
• 5.1.3 局部最优搜索策略
• 5.1.4 最优个体灾变策略
• 5.1.5 相关控制参数设置
• 5.1.6 改讲算法收敛性分析
• 5.2 改进蚁群算法求解 VRPTW 问题的基本步骤
• 5.3 算法仿真实验
• 5.3.1 算法仿真研究
• 5.3.2 实验结果分析
• 6 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 致谢
• 攻读学位期间已发表的学术论文及科研成果