基于混合粒子群算法的物流配送车辆路径问题的研究

摘要

配送是物流系统中很重要的一个环节。在物流的各项成本中，配送成本占了相当高的比例。车辆路径问题是配送系统中的核心问题，也是研究热点之一。路径安排合理能有效提高运输效率、降低服务成本。本文以物流配送为背景，对物流配送车辆路径问题和带时间窗的车辆路径问题采用基于爬山算法的混合粒子群算法进行了深入的研究。 粒子群算法是一种基于群智能方法的演化计算技术，具有深刻的智能背景，广泛应用于科学研究和工程问题。针对粒子群算法早熟收敛和局部搜索能力不足的缺陷，本文引入局部搜索能力强的爬山算法对其进行优化，提出了基于爬山算法的混合粒子群算法。设计了两种混合粒子群算法，对每代群体中的全局极值引入爬山操作构成混合PSO方案一，对每个粒子进行爬山操作构成混合：PSO方案二。混合粒子群算法在局部搜索能力和收敛速度上较标准PSO都有很大的改进。混合PSO方案一局部搜索能力大于标准PSO，混合PSO方案二局部搜索能力大于混合PSO方案一。混合PSO方案二的收敛速度最快，混合PSO方案一次之，标准PSO的收敛速度最慢。 本文在查阅大量中外文献的基础上，结合物流配送的特点，建立了物流配送车辆路径问题的数学模型。采用标准PSO算法、混合PSO方案一和混合PSO方案二3种方法求解了物流配送车辆路径问题和带时间窗的车辆路径问题。仿真试验表明，本文提出的混合PSO方案一和混合PSO方案二性能均优于标准PSO。混合PSO方案二的性能最优，具有很强的收敛能力，能够有效地求解物流配送车辆路径问题。该方法对物流配送企业优化配送路径、降低配送成本和提高物流经营管理水平，最终增加企业的竞争能力具有重要的参考价值。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题的研究背景及意义

1.2国内外研究现状

1.3论文研究的主要内容

第二章物流配送及车辆路径问题

2.1配送的概念与特点

2.2配送的分类

2.3我国物流配送的现状及展望

2.4物流配送车辆路径问题

2.4.1物流配送车辆路径问题的提出

2.4.2 VRP的分类与约束条件

2.4.3 VRP问题的模型

2.4.4配送车辆路径优化原则

2.5本章小结

第三章粒子群算法及其优化

3.1粒子群算法简介

3.1.1粒子群算法的数学描述

3.1.2粒子群算法同遗传算法的比较

3.2粒子群算法的变化和改进

3.2.1收敛速度的改进

3.2.2增加多样性的改进

3.2.3全局方法

3.2.4其他改进

3.3粒子群算法在物流中的应用

3.4混合粒子群算法

3.5本章小结

第四章混合粒子群算法求解物流配送车辆路径问题

4.1物流配送车辆路径问题的数学模型

4.2粒子群算法设计

4.2.1粒子编码

4.2.2适应值函数

4.3引入爬山算法的混合粒子群算法

4.3.1求解物流配送车辆路径问题的标准PSO

4.3.2混合PSO方案一

4.3.3混合PSO方案二

4.3.4三种算法的比较

4.4算例与结果分析

4.4.1算例一

4.4.2算例二

4.4.3结果分析

4.5本章小结

第五章混合粒子群算法求解带时间窗的车辆路径问题

5.1带时间窗的车辆路径问题概述

5.1.1带时间窗的车辆路径问题的概念及基本描述

5.1.2时间窗的分类

5.2带时间窗的车辆路径问题的数学模型

5.3混合粒子群算法求解带时间窗的车辆路径问题

5.3.1粒子群算法模型

5.3.2构造粒子实数编码

5.3.3到达任务点时间的计算

5.3.4算法实现伪代码

5.4算例与结果分析

5.4.1算例一

5.4.2算例二

5.4.3结果分析

5.5本章小结

第六章结论与展望

6.1结论

6.2进一步的研究方向

参考文献

致谢

攻读学位期间主要的研究成果