原文传递
基于IA与TS的带时间窗车辆路径优化算法研究
| 论文题名： | 基于IA与TS的带时间窗车辆路径优化算法研究 |
| 关键词： | 时间窗;车辆路径;优化算法;禁忌搜索算法;免疫算法 |
| 摘要： | 研究车辆路径问题(Vehicle Routing Problem，VRP)的相关理论和算法是为了降低物流的成本。该问题通过规划出合理的行驶路线来实现运输成本的最小化。这个问题是运筹学和组合优化领域的研究热点。对这个问题的不断深入研究使得它已经延伸出了许多新的研究分支。本文首先分析了目前车辆路径问题的研究现状，再结合实际提出了本文的研究问题--带时间窗的车辆路径问题(VRPTW)。通过对带时间窗车辆路径问题的数学建模，明确定义了问题的目标函数和约束条件。在考虑了配送的距离、配送的时间性和配送的车辆数等因素的影响，最后构建了以配送总路径最短为目标。在分析了目前多种求解方法后，本文采用的是免疫禁忌搜索算法的混合策略。 首先，对禁忌搜索算法和免疫算法分别进行了分析。了解了禁忌搜索算法的求解思想，重点是渴望水平的设计，针对车辆路径问题目标函数的特点求解最短路径，将禁忌搜索算法渴望水平设计为与目标函数相同的函数。对TSP问题分别用禁忌搜索算法、遗传算法和蚁群算法进行了求解。用平均值，方差和平均计算时间进行了比较，实验验证了禁忌搜索算法的有效性，同时验证了对初始解的依赖性。其次了解了免疫算法的算法思想，免疫算法的特点是疫苗的提取。用TSP问题验证了免疫算法能够在全局范围内求得最优解，从实验的结果验证了免疫算法改进了遗传算法的不足。最后介绍了免疫禁忌搜索算法的混合策略的算法，本文是通过免疫算法产生的最优解作为禁忌搜索算法的初始解，设计了适合建立的数学模型的编码方式和渴望水平和亲和度等。 本文应用solomon benchmark测试数据集进行了仿真实验，利用MATLAB软件计算出了最优目标函数值和最优配送路径方案，通过对实验结果的分析，验证了所建模型和求解算法对solomon benchmark测试集中的R类和RC类数据是合理并有效的。 |
| 作者： | 王容 |
| 专业： | 计算机应用技术 |
| 导师： | 邓辉文 |
| 授予学位： | 硕士 |
| 授予学位单位： | 西南大学 |
| 学位年度： | 2011 |
| 正文语种： | 中文 |
检索历史
应用推荐
