车辆路径问题的混合粒子群算法研究

论文摘要

物流被称为“第三利润源泉”,越来越受到人们的关注,日益成为国民经济的基础产业。配送是物流中的重要环节,占物流成本的60%以上。车辆路径问题是配送系统中的核心问题,主要研究物流配送中的车辆线路优化,用以提高物流配送的经济效益、降低配送成本,实现物流科学化。粒子群优化算法是一种新型的进化计算技术,由Eberhart和Kennedy博士共同于1995年提出,已经被证明是一种有效的全局优化方法,并且广泛应用于解决各类组合优化问题。本文以物流配送为背景,对带时间窗的车辆路径问题采用粒子群算法进行了深入的研究。在查阅中外文献的基础上,根据车辆路径问题的基本原理和约束条件,建立了物流配送带有时间窗约束的车辆路径问题的数学模型。依据粒子群算法的基本原理,确立了粒子群算法求解车辆路径问题的编码方法和具体求解方法,并采用Visual Basic6.0编写算法优化程序,应用于实例对算法进行分析验证。合理设置粒子群优化算法的参数将影响算法的求解性能,本文通过对主要参数进行对比实验,分析了粒子群算法主要参数对算法求解车辆路径问题性能的影响以及参数的选取方法。针对粒子群算法容易陷入局部最优解的缺点,提出了一种混合的粒子群算法（PSO-SA算法）来求解车辆路径优化问题,这也是本文研究的核心所在。利用粒子群算法易于实现,收敛速度快的优点,结合模拟退火算法具有较好的全局搜索能力的特点,将粒子群算法与模拟退火算法相复合来提高算法的求解效率,最终实现了算法的有效改进,克服了粒子群算法求解问题的缺陷,从而保障了混合粒子群算法求解实际问题的可行性和有效性。利用Visual Basic6.0编写程序对经典的车辆路径问题solomon测试数据进行优化仿真,可直观的显示配送路线等结果,并在与基本粒子群算法结果进行比较中,取得了较满意的结果,充分验证了混合粒子群算法求解带时间窗车辆路径问题的可行性、优越性及通用性。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 课题背景与研究意义
• 1.1.1 课题背景
• 1.1.2 研究意义
• 1.2 国内外研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 研究内容及研究方法
• 第2章 车辆路径问题的数学模型
• 2.1 车辆路径问题的概述
• 2.1.1 车辆路径问题的描述
• 2.1.2 车辆路径问题的组成因素
• 2.1.3 车辆路径问题的分类
• 2.1.4 车辆路径问题的求解算法
• 2.2 时间窗车辆路径问题的数学模型
• 2.2.1 时间窗车辆路径问题的描述
• 2.2.2 车辆路径问题的数学模型
• 2.2.3 软时间窗车辆路径问题的模型描述
• 第3章 粒子群算法求解车辆路径问题
• 3.1 粒子群算法的基本原理
• 3.2 粒子群算法的数学描述
• 3.3 粒子群算法求解车辆路径问题的基本思路
• 3.3.1 粒子群算法的编码方法
• 3.3.2 粒子群算法的求解步骤
• 3.4 粒子群算法的程序设计
• 3.4.1 粒子群算法的模块结构设计
• 3.4.2 粒子群算法的程序设计
• 3.4.3 粒子群算法的实例分析
• 第4章 粒子群算法的参数分析
• 4.1 惯性权重因子
• 4.1.1 固定权重
• 4.1.2 时变权重
• 4.1.3 综合对比结果
• 4.2 加速因子
• 1的分析研究'>4.2.1 c₁的分析研究
• 2的分析研究'>4.2.2 c₂的分析研究
• 4.3 粒子群算法其他参数的选取
• 第5章 混合粒子群算法求解车辆路径问题
• 5.1 混合粒子群算法的必要性
• 5.2 模拟退火算法
• 5.2.1 模拟退火算法的基本思想
• 5.2.2 模拟退火算法的相关概念
• 5.3 模拟退火算法的求解步骤
• 5.4 混合粒子群算法的设计
• 5.4.1 混合粒子群算法的内部衔接
• 5.4.2 混合粒子群算法的求解步骤
• 5.5 混合粒子群算法的程序实现
• 5.5.1 混合粒子群算法的模块结构设计
• 5.5.2 混合粒子群算法的实例分析
• 第6章 结论
• 参考文献
• 致谢