基于改进的GA-PSO的车辆路径问题系统设计.doc

摘要: 随着经济社会的发展，物流运输在社会占据着举足轻重的位置。如何制定最优配送方案成为人们的关注点，通常这类问题称为车辆路径问题。

为了解决这一类车辆路径问题，本文设计了改进的混合遗传粒子群算法（GA-PSO）。首先，针对遗传算法与粒子群算法的优缺点，结合领导者和自适应思想，提出了改进的混合遗传粒子群算法。将遗传算法、粒子群算法和改进混合遗传粒子群算法分别对单峰和多峰函数进行寻优测试，结果显示，改进的混合遗传粒子群算法较之于单个算法，具有更高的搜索精度，不容易陷入局部最优解和更高的全局寻优能力等特点。其次，将改进的混合遗传粒子群算法用来解决大规模的带时间窗车辆路径问题，结果显示，该混合算法搜索到的最优配送路线较为理想，可以用于指导实践。最后，通过Matlab的GUI将上述的改进混合算法封装成交互式应用程序界面，方便用户的使用。

关键词  车辆路径问题；领导者；自适应 ；GUI

目录

摘要

Abstract

1 绪论-1

1.1 选题背景与意义-1

1.2 国内外VRP问题的研究现状-1

1.2.1 国外VRP问题的研究现状-1

1.2.2 国内VRP问题的研究现状-2

1.2.3 国内外 GA、PSO和混合GA-PSO算法的研究现状-2

1.3 本文的主要研究内容及结构-2

1.3.1 论文的主要研究内容-3

1.3.2 论文结构-3

2 车辆路径问题的数学模型-4

2.1 车辆路径问题概述-4

2.1.1 车辆路径问题的一般描述-4

2.1.2 车辆路径问题的组成因素-4

2.1.3 车辆路径问题的基本解法-5

2.2带时间窗车辆路径问题的数学模型-6

2.2.1 带时间窗车辆路径问题的描述-6

2.2.2 带时间窗的车辆路径问题的数学模型-7

3 改进的混合遗传粒子群算法-8

3.1 遗传算法-8

3.1.1 遗传算法的优点-8

3.1.2 遗传算法的缺点-8

3.1.3 遗传算法函数寻优测试-8

3.2 粒子群算法-9

3.2.1 粒子群算法的优点-9

3.2.2 粒子群算法的缺点-9

3.2.3 粒子群算法函数寻优测试-10

3.3 遗传和粒子群算法能够结合的原因-10

3.4 改进的混合遗传粒子群算法-11

3.4.1 改进混合算法的思想-11

3.4.2 改进混合算法的操作步骤-12

3.5三种算法性能测试对比-13

3.6本章小结-15

4 基于改进GA-PSO算法的车辆路径问题求解-16

4.1问题描述-16

4.2基于改进GA-PSO的车辆路径问题求解算法步骤-16

4.3求解结果与分析-17

5 改进混合算法的车辆路径问题系统设计-20

5.1系统可视化界面设计-20

5.2系统具体操作-20

结论-22

致谢-23

参考文献-24

附录-26