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

摘要

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

目录

声明

摘要

1 绪论

1．1 论文的选题背景

1．2 带时间窗的车辆路径问题(VRPTW)的研究现状

1．3 本文主要研究内容

2 带时间窗的车辆路径问题

2．1 车辆路径问题概述

2．2 车辆路径问题中的约束条件

2．3 车辆路径问题中的影响因素

2．4 VRPTW问题描述及其数学模型

2．4．1 问题描述

2．4．2 VRPTW模型的构建

2．5 VRPTW的常见求解方法

2．5．1 精确算法

2．5．2 经典启发式算法

3 蚁群算法和细菌觅食算法的改进

3．1 蚁群算法

3．1．1 蚁群算法发展历史

3．1．2 蚁群算法的特征和机制

3．1．3 蚁群算法的数学模型

3．1．4 蚁群算法的基本流程

3．1．5 蚁群算法的参数设置

3．2 细菌觅食算法(BFO)的改进

3．2．1 细菌觅食算法的仿生机理

3．2．2 细菌觅食算法的基本原理

3．2．3 BFO算法的流程

3．2．4 BFO算法存在的优缺点

3．2．5 细菌觅食算法的改进

4 改进混合蚁群算法在VRPTW中的研究

4．1 算法结合可行性

4．2 算法结合的基本思想

4．3 IHACO算法的基本原理

4．3．1 信息素限制的改进

4．3．2 局部搜索的改进

4．3．3 目标客户节点选择策略

4．3．4 设置相关控制参数

4．3．5 细菌觅食算子

4．3．6 IHACO参数自适应策略

4．4 IHACO算法求解VRPTW的基本步骤

4．5 算法仿真实验

4．5．1 系统需求

4．5．2 系统分析

4．5．3 数据文件格式

4．5．4 算法实现

4．5．5 仿真结果分析

5 结论与展望

5．1 结论

5．2 展望

参考文献

致谢

作者简介及读研期间主要科研成果