基于改进混合蚁群算法的带时间窗车辆路径问题优化研究

发布时间：2017-05-25 15:12

  本文关键词：基于改进混合蚁群算法的带时间窗车辆路径问题优化研究，由笔耕文化传播整理发布。

【摘要】：当今物流业发展迅速,而物流配送过程较为复杂,其中运输成本与总成本的比率已经超过50%。提高配送过程中车辆调度的效率,降低运输成本,同时满足顾客各种各样的需求,不但在理论上有一定的研究价值,而且在现实应用中也有一定的意义。本文首先对物流配送业务流程以及VRP问题进行了详细的介绍,通过对前人研究成果的总结,在深入了解蚁群算法和细菌觅食算法的优缺点的前提下,提出了一种改进混合蚁群算法的新型启发式算法。主要研究工作如下：(1)通过对VRPTW的问题描述,建立本文的VRPTW数学模型,模型中相对于VRP问题增加两个约束条件。第一,从配送中心出发,服务完客户节点后,必需返回配送中心；第二,每个客户节点的配送任务,必需由一辆车来完成,且仅服务一次,车辆须在指定的时间窗内服务客户,如果早到须等待。(2)本文针对蚁群算法易陷入局部最优解这一不足,对信息素更新方法进行改进。当一次迭代结束,所有的蚂蚁均构建出解后,对信息素矩阵进行更新,为了增强较优解所包含的边上的信息素浓度,使得其在后续迭代中以较大概率被蚂蚁选中,利用三种不同的最好解来更新信息素。(3)本文针对蚁群算法易于出现早熟和停滞的现象,对局部搜索策略进行改进。通过变邻域下降搜索能动态改变考查的邻域空间的大小,在进行局部搜索时只接受最好的邻域解,直到陷入局部最优,提高算法摆脱局部最优的能力。节省了大量冗余节点的计算时间,有利于算法搜索速度的提高,为快速、有效地求解大规模优化问题提供了可能。(4)在系统仿真实验中,通过系统需求和系统分析,利用C++开发语言对VRPTW系统进行仿真实现。并采用国际上通用的Benchmark Problems中的C1-01测试数据进行测试,将得到的数据结果与目前求解的最好结果进行比较,本算法的求解结果对蚁群算法的求解结果有所改进,并且优于部分文献中已有的最好结果,其它则与最好结果比较接近。这表明本文提出的改进混合蚁群算法在求解VRPTW问题上的有效性。对流配送的发展具有一定的理论意义与应用价值。
【关键词】：蚁群算法 细菌觅食算法 MMAS 带时间窗车辆路径问题
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要5-6
• Abstract6-14
• 1 绪论14-17
• 1.1 论文的选题背景14-15
• 1.2 带时间窗的车辆路径问题(VRPTW)的研究现状15-16
• 1.3 本文主要研究内容16-17
• 2 带时间窗的车辆路径问题17-26
• 2.1 车辆路径问题概述17-18
• 2.2 车辆路径问题中的约束条件18
• 2.3 车辆路径问题中的影响因素18-19
• 2.4 VRPTW问题描述及其数学模型19-21
• 2.4.1 问题描述19-20
• 2.4.2 VRPTW模型的构建20-21
• 2.5 VRPTW的常见求解方法21-26
• 2.5.1 精确算法21-22
• 2.5.2 经典启发式算法22-24
• 2.5.3 现代启发式算法24-26
• 3 蚁群算法和细菌觅食算法的改进26-41
• 3.1 蚁群算法26-31
• 3.1.1 蚁群算法发展历史26-27
• 3.1.2 蚁群算法的特征和机制27-28
• 3.1.3 蚁群算法的数学模型28-29
• 3.1.4 蚁群算法的基本流程29-30
• 3.1.5 蚁群算法的参数设置30-31
• 3.2 细菌觅食算法(BFO)的改进31-41
• 3.2.1 细菌觅食算法的仿生机理31-32
• 3.2.2 细菌觅食算法的基本原理32-36
• 3.2.3 BFO算法的流程36-37
• 3.2.4 BFO算法存在的优缺点37-38
• 3.2.5 细菌觅食算法的改进38-41
• 4 改进混合蚁群算法在VRPTW中的研究41-58
• 4.1 算法结合可行性41
• 4.2 算法结合的基本思想41-42
• 4.3 IHACO算法的基本原理42-47
• 4.3.1 信息素限制的改进42-43
• 4.3.2 局部搜索的改进43-44
• 4.3.3 目标客户节点选择策略44
• 4.3.4 设置相关控制参数44-45
• 4.3.5 细菌觅食算子45
• 4.3.6 IHACO参数自适应策略45-47
• 4.4 IHACO算法求解VRPTW的基本步骤47-49
• 4.5 算法仿真实验49-58
• 4.5.1 系统需求49
• 4.5.2 系统分析49
• 4.5.3 数据文件格式49-51
• 4.5.4 算法实现51-54
• 4.5.5 仿真结果分析54-58
• 5 结论与展望58-60
• 5.1 结论58-59
• 5.2 展望59-60
• 参考文献60-64
• 致谢64-65
• 作者简介及读研期间主要科研成果65

【参考文献】

中国期刊全文数据库 前4条

1 赵国材;刘洋;;基于MMAS的多目标优化算法研究[J];计算机仿真;2011年07期

2 邹彤,李宁,孙德宝;不确定车辆数的有时间窗车辆路径问题的遗传算法[J];系统工程理论与实践;2004年06期

3 朱庆保,杨志军;基于变异和动态信息素更新的蚁群优化算法[J];软件学报;2004年02期

4 张涛,王梦光;遗传算法和3-opt结合求解带有能力约束的VRP[J];东北大学学报;1999年03期

中国硕士学位论文全文数据库 前1条

1 袁杰;基于蚁群算法的多车场车辆路径问题研究[D];山东经济学院;2010年

  本文关键词：基于改进混合蚁群算法的带时间窗车辆路径问题优化研究，，由笔耕文化传播整理发布。

本文编号：394120