文档介绍：河南大学
硕士学位论文
改进粒子群算法在车辆路径问题中的应用研究
姓名:杨凌云
申请学位级别:硕士
专业:计算机应用技术
指导教师:徐彬
2011-04
摘要
摘要
被称为“第三利润源泉”的物流,越来越受到人们的重视,同时随着以网络为基础
的电子商务迅速发展,物流配送对电子商务的支撑作用越发明显。其中,物流配送车辆
路径优化问题(VRP),是物流配送优化中关键的一环,同时也是电子商务活动中不可
缺少的内容。对车辆配送路径进行优化,可以提高物流经济效益、实现物流科学化。因
此,研究物流配送车辆路径优化问题,不仅具有较大的理论意义,而且还有相当大的使
用价值。粒子群算法是一种基于群智能的优化方法,由一群粒子组成,粒子群在问题空
间中进行协同搜索,是一种并行算法,搜索速度比较快,具有很高的搜索效率。
本文所做的工作主要包括以下几个方面:
(1)对车辆路径问题及粒子群优化算法进行了系统的研究,在此基础上建立了车
辆路径问题模型,并用改进的粒子群算法求解其数学模型。
(2)针对粒子群算法的特点,提出了改进的粒子群算法。
因为粒子群算法具有简单、实现容易、参数较少、收敛速度较快的优点,但同时也
存在一些问题,这些问题中最主要的是它容易产生早熟收敛,局部寻优能力较差,易于
陷入局部最优,使问题偏离最优解,考虑到模拟退火算法具有较强的局部搜索能力,提
出了混合模拟退火思想的粒子群算法;首先对基本的粒子群算法做了一个改进,粒子的
速度更新公式采用带收缩因子的更新方法;由于模拟退火算法对初始温度的依赖性比较
强,本文将初始温度的确定是与初始种群的性能建立起一定的关系;而在模拟退火算法
中选择下一代粒子的时候使用了遗传算法中的轮盘赌策略。
(3)用本文所提出的算法,求解一般车辆路径问题及带时间窗的车辆路径问题,
并进行的仿真实验,验证了算法的高效性。

关键词:粒子群算法;车辆路径问题;混合策略;模拟退火算法;PSOSA

I
ABSTRACT
ABSTRACT
As “the third profit source”, logistics is playing a more and more important role in our life. As
the same time, with the development of merce, Logistics distribution on merce role
in supporting the more obvious. Among of them, the logistics distribution vehicle routing optimization
problem is a key part of logistics distribution optimization ,as the same time it’s the indispensable content
of merce activities. Vehicle distribution path is optimized can improve economic efficiency and
make logistics scientific. Therefore, studying the logistics distribution vehicle routing optimization
problem is not only has a great theoretical significance but also useful. Particle swarm optimization is
based on swarm group and made by a group of particles, it is a kind of intelligent optimization method. as
the same time, it is a parallel algorithm. In problem space particle swarm has the efficiency of search
efficiency through cooperative search.
This article’s main work includes:
(1)It has a studying on vehicle routing problem and particle swarm optimization algorithm, the
veh