基于群智能算法的机器人及带时间窗的车辆路径规划研究

摘要

目前，群智能算法的核心是蚁群算法与粒子群算法，由于群智能算法在优化性能，鲁棒性、通用性等方面的突出优点，为其在求解路径规划问题的最优解上占尽优势，使得越来越多的学者投入到如何运用群智能算法解决路径规划问题的研究中。
　　本文针对机器人路径规划问题及带时间窗的车辆路径规划问题，首先构建数学模型，然后利用群智能算法对模型进行求解。主要研究内容如下:
　　1、提出一种基于改进的链接图法建模的机器人路径规划问题的求解方法。首先在链接图法的改进上采用局部路径重规划方法，该方法结合双向局部搜索思想，保证环境模型自适应重构的准确性;其次在重构的环境模型中利用Dijkstra算法求解初始最优路径，求解过程引入枚举法以保证初始最优路径的多样性，然后采用动态双变异粒子群算法对初始最优路径进行再优化，同时引入搜索算子以增大粒子在每个维度边缘的搜索空间，提高算法的局部寻优能力;最后通过仿真对比实验，验证了该算法的可行性与优越性。
　　2、提出了一种求解带时间窗的车辆路径规划问题的二阶段优化算法。算法的第一阶段是根据蚁群算法的优点设计一条初始预路径，算法的第二阶段是根据客户点的分布规律，将预路径分为若干条子路径，同时保证每条子路径有且只能由一辆车在时间及载重量的双重约束下完成对客户点的服务。对于得到的每条子路径，应用基于时间窗分类的插入启发式算法进行优化，优化目标是实现总运输成本最小。将该优化结果与其它算法优化得到的结果进行仿真对比，对比结果说明该算法的有效性与优越性。

目录

摘要

1 绪论

1．1 课题研究背景与意义

1．2 国内外研究现状

1．3 本文研究内容及结构安排

2 相关理论基础

2．1 图论的基本知识介绍

2．2 蚁群算法的基本原理

2．3 粒子群算法的基本原理

2．4 本章小结

3 复杂环境下机器人路径规划

3．1 问题描述与环境建模

3．2 算法分析与实现

3．2．1 Dijkstra算法

3．2．3 枚举法的引入

3．2．4 算法实现的具体步骤

3．3 仿真分析

3．4 本章小结

4 带时间窗的车辆路径规划

4．1 问题描述及建模

4．2 算法分析与设计

4．2．1 预优化路径

4．2．2 子路径的确定

4．2．3 基于时间窗分类的插入启发式算法

4．2．4 二阶段算法实现的具体步骤

4．3 仿真分析

4．4 本章小结

5 总结与展望

参考文献

致谢

攻读学位期间取得的研究成果

声明