改进遗传算法在车辆路径问题中的研究应用

摘要

目前在物流的运转流程中,配送是一个关键环节,配送的成本占总成本三分之一以上。因此如何合理有效的安排配送成为降低物流成本的首要任务,而配送的核心是车辆运输路径安排,可以说解决了车辆路径安排问题,也就解决了配送的核心问题。
　　随着电子商务的普及,客户数目呈爆炸式增长,这使得配送的难度越来越大,车辆运输路径的安排也成为首要解决的问题。由于车辆运输路径问题的难度很大,并且有着十分巨大的经济价值,已经吸引越来越多的学者和企业竞相研究。
　　为此本论文首先分析了国内外对车辆运输路径安排问题的研究进展,同时结合实际情况,给出了本文的研究问题--带时间窗的取送货车辆路径问题(VRP/SDP/TW)。由给出的模型公式进一步阐释出问题的约束条件:如何在满足车辆的容量和客户服务时间的条件下,合理安排路径运输,以满足客户的服务需求和使运输路径最小化。
　　接下来,对遗传算法进行了详细的介绍与分析,阐释了遗传算法的优点与不足,并针对遗传算法易于早熟和运算速度慢的缺点,提出了三个改进的策略:1、依据种群进化程度自适应调整参数的设置,避免早熟;2、将粒子群算法(PSO)嵌入到遗传算法(GA)的遗传过程中,提升遗传质量;3、将种群进化并行化,提高进化速度。
　　最后,将本文提出的方法应用到带时间窗的取送车辆路径问题(VRP/SDP/TW)中去,并给出了详细操作流程,并使用JAVA编程语言实现算法。本文进行了三个验证实验:第一个实验与基本遗传算法比较、第二个实验与改进的蚁群算法比较,前两个实验的结果验证了本文提出三个策略既可以有效的避免早熟提升全局搜索能力,又使运算速度有较大的提升,显示了本算法在解决(VRP/SDP/TW)问题的优越性。第三个实验的数据规模很大,验证本文算法对于超大规模的问题依然可以有效求解,证明本文算法具有很好的鲁棒性。
　　本文提出的方法可以有效帮助企业提高配送的优化能力,更快捷的满足用户的需求,提高企业在行业的竞争能力。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景与意义

1.2 国内外的研究现状

1.3 本文的研究内容与组织结构

1.4 本章小结

第2章 车辆路径问题研究与模型优化

2.1 车辆路径问题描述

2.2 车辆路径问题分类

2.3 车辆路径问题基本解法

2.4 常见的VRP数学模型及其改进

2.5 本章小结

第3章 遗传算法及其改进

3.1 遗传算法

3.2 遗传算法的改进

3.3 实例仿真

3.4 本章小结

第4章 改进遗传算法求解VRP问题

4.1 改进的遗传算法在车辆路径问题中的应用

4.2 实验结果与分析

4.3 本章小结

结论

参考文献

致谢

个人简历