基于蚁群算法的物流配送车辆路径问题的研究

论文摘要

本文首先介绍了物流的相关概念和物流系统的构成。在物流系统中,配送作业环节占据着物流过程很大一部分的成本,而在配送过程中成本与时间消耗具有较大的不确定性（变化幅度比较大,不太容易控制）,成为配送中心压缩运营成本、提高客户服务水平、增强自身市场生存能力的一大挑战。因此,合理的车辆路径规划这一问题应运而生。车辆路径优化问题（VRP）本质上属于NP-hard难题,即随着问题难度增大,求解过程（所需时间与空间）呈现非线性的“组合爆炸”式增长。而具有系统性特征的元启发式算法如遗传算法、模拟退火算法等可以较好的解决这一难题。作为一种新型的生物学算法——蚁群算法,在求解此类问题表现出优越的性能。文章接下来简要介绍冷链物流的相关内容。作为车辆路径优化问题的特例,旅行商问题（TSP）最先得到大量的研究,并用其检验一些启发式算法和各种蚁群优化算法（ACO）的性能。然后详细分析VRP的各项内容与分类标准,并指出带时间窗的各类车辆路线调度的数学模型。接下重点介绍蚁群算法的各项具体内容,包括其生物学原理特征、系统学特征;蚁群算法的数学模型及影响其执行能力的各项参数（信息素浓度、挥发系数、蚂蚁数量等）;算法的实现步骤;结合国内外对各种改进的蚁群算法比较结果,本文创新点是对最大最小蚁群算法（MMAS）进行分析比较后后,并将2-opt局部搜索策略和信息素平滑机制PTS引入到该算法中,对MMAS的路径选择能力进行改进,以期提高该算法的整体性能。在文章的最后简要介绍了一个算例,即某市一个冷链配送中心向市郊的各乡镇中小型超市供应鲜肉,并将改进的最大最小蚁群算法应用在这一带有软时间窗的车辆路径优化问题,达到在规定的时间范围内使得运输成本最小化,并实现较好的经济与社会效益。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 论文研究的背景与意义
• 1.2 国内外文献综述
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 本文主要研究内容
• 第2章 物流相关理论
• 2.1 物流基本理论
• 2.2 物流系统
• 2.3 运输配送
• 2.4 本章小结
• 第3章 车辆路径优化问题
• 3.1 车辆路径问题的概述
• 3.2 图论和最优化相关理论
• 3.2.1 图论基础知识
• 3.2.2 图论中的路径优化问题
• 3.2.3 最优化理论与方法
• 3.3 车辆路径优化的性质与构成
• 3.3.1 路径优化问题的性质
• 3.3.2 车辆调度问题的构成要素
• 3.4 VRP 数学模型
• 3.4.1 VRP 的基本数学模型
• 3.4.2 有限制因素的VRP 模型
• 3.5 VRP 问题的求解算法
• 3.5.1 精确算法
• 3.5.2 启发式算法
• 3.6 本章小结
• 第4章 蚁群优化算法
• 4.1 算法及算法分析
• 4.2 ACO 的生物学特性
• 4.3 ACO 的系统学特征
• 4.4 ACO 数学模型
• 4.5 ACO 算法实现过程
• 4.6 本章小结
• 第5章 蚁群优化算法的改进
• 5.1 各种改进的 ACO 算法
• 5.2 迭代局部搜索
• 5.3 平滑信息素轨迹
• 5.4 本章小结
• 第6章 算例分析
• 6.1 冷链物流简介
• 6.2 模拟实验
• 6.3 本章小结
• 结论与展望
• 参考文献
• 攻读硕士学位期间所发表的学术论文
• 致谢