车辆路径问题的粒子群算法研究与应用

论文摘要

物流被称为“第三利润源泉”,越来越受到人们的关注,日益成为国民经济的基础产业。运输是物流中的重要环节,占物流成本的60%以上。车辆路径问题主要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题,在航班调度、列车编组等众多领域都有应用。由于NP问题求解的复杂性,目前车辆路径问题的求解方法主要使用各种智能优化算法。本文主要研究了以下四种模型的车辆路径问题:有能力约束的车辆路径问题,开放式车辆路径问题,基于客户满意度的开放式车辆路径问题,开放式动态网络车辆路径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下:（1）首先介绍了论文的研究背景及意义,给出了车辆路径问题的定义,分析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上,从车辆路径问题的模型和求解算法两方面,深入分析了车辆路径问题的国内外研究现状。（2）系统研究了基于粒子群算法的有能力约束车辆路径问题（CapacityVehicle Routing Problem,CVRP）。提出了整数编码、实数编码两种求解CVRP的方法。在整数编码中,以交换数为基础,对粒子的速度重新定义,并对速度的加、减等操作进行了定义,提出了“换位减”算子作为整数编码的速度计算方法;针对整数编码算法存在的问题,提出了一种实数编码方法求解CVRP,用实数的整数部分表示客户所在的车辆,小数部分表示在该车辆中配送的次序,融合遗传算法的思想,引入交叉算子以增加种群的多样性,详细讨论了粒子群算法的各个参数对算法结果的影响。为了与其他智能优化算法比较,研究了遗传算法、人工鱼群算法在CVRP中的应用。将双种群遗传算法用于CVRP的求解;提出了人工鱼群算法在CVRP中的应用,针对车辆路径问题的特点,定义了鱼群的距离、领域等概念,提出了人工鱼根据自身在鱼群中的排序,自适应选择移动算子的策略。（3）通过引入虚拟配送中心的概念,建立了开放式车辆路径问题的三下标数学模型。提出了开放式车辆路径问题的粒子群求解方法,将最邻近插入、最远插入、2-Opt、3-Opt等启发式算法作为再优化过程引入粒子群算法,通过这些启发式算法调整线路内和线路间的客户来改进解,从理论上分析了这些算法的计算复杂度。通过实验分析,找出合适的启发式算子,并和其他的算法进行了比较。（4）以客户满意度为首要优化目标,建立了基于客户满意度的开放式车辆路径问题的数学模型,使用梯形模糊数表示客户满意度。综合考虑距离、等待时间、客户的满意度等因素,定义了广义的距离和节约费用的概念,提出了改进的最邻近法和最廉价插入法,将这两个算法作为初始化和改进算子结合粒子群算法进行优化求解。分析了算法的复杂度,对算法的各个参数进行了讨论,通过实验仿真对这几种方法进行了分析比较。（5）动态网络车辆路径问题目前研究的热点和难点问题,将动态网络与开放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态网络车辆路径问题的数学模型,提出了一种连续时间依赖函数模型。提出了自适应惯性权重调整的粒子群算法,定义了粒子的“位置比”概念,充分利用粒子的已有知识,动态的调整惯性权重。在算法中,引入公告板策略,根据粒子适应度的高低分类更新粒子状态,对于优秀粒子使用一种新的状态更新公式,以使其跳出局部极值点。对于适应度低的粒子,通过统计其在公告板中出现的频率,用新的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置,对几种惯性权重方案进行了分析比较,实验结果证明了算法的有效性。（6）在上述理论工作的基础上,针对第三方物流在国内的迅速发展,而相应的车辆调度软件功能不够完善,开发了智能车辆调度系统。该系统包括智能车辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有能力约束等多种情况的车辆调度问题,提供遗传算法、粒子群算法等多种优化算法供用户使用。系统在杭州某物流公司应用,取得了良好的效果。最后,对全文研究工作进行了总结,展望了车辆路径问题的模型和算法研究的前景。

论文目录

• 摘要
• ABSTRACT
• 文中常用符号
• 第一章 绪论
• 1.1 论文的研究背景及意义
• 1.2 车辆路径问题的定义及组成要素
• 1.2.1 车辆路径问题的定义
• 1.2.2 车辆路径问题的组成要素分析
• 1.3 车辆路径问题的研究现状
• 1.3.1 车辆路径问题的模型综述
• 1.3.2 车辆路径问题的算法综述
• 1.3.3 研究中存在的问题
• 1.4 论文的主要研究内容
• 第二章 有能力约束车辆路径问题的智能优化算法研究
• 2.1 引言
• 2.2 CVRP的数学模型
• 2.3 CVRP的粒子群算法研究
• 2.3.1 粒子群算法的原理与研究进展
• 2.3.2 粒子群算法求解CVRP的过程
• 2.3.3 算法复杂度分析
• 2.3.4 实验及分析
• 2.4 CVRP的实数编码粒子群算法研究
• 2.4.1 实数编码粒子群算法
• 2.4.2 算法求解过程
• 2.4.3 算法复杂度分析
• 2.4.4 实验及分析
• 2.5 CVRP的双种群遗传算法研究
• 2.5.1 双种群遗传算法的原理
• 2.5.2 算法求解过程
• 2.5.3 算法复杂度分析
• 2.5.4 实验及分析
• 2.6 CVRP的人工鱼群算法研究
• 2.6.1 人工鱼群算法的原理
• 2.6.2 人工鱼群算法求解CVRP的过程
• 2.6.3 算法复杂度分析
• 2.6.4 实验及分析
• 2.7 几种算法的分析对比
• 2.8 本章小结
• 第三章 开放式车辆路径问题的粒子群算法研究
• 3.1 引言
• 3.2 OVRP的数学模型
• 3.3 粒子群算法在OVRP中的应用
• 3.3.1 算法求解过程
• 3.3.2 算法复杂度分析
• 3.4 实验及分析
• 3.5 本章小结
• 第四章 基于客户满意度的OVRP及其粒子群算法研究
• 4.1 引言
• 4.2 基于客户满意度的OVRP的数学模型
• 4.2.1 模糊时间窗口
• 4.2.2 数学模型
• 4.3 算法求解过程
• 4.3.1 客户插入可行性分析
• 4.3.2 改进的最邻近启发式算法
• 4.3.3 改进的最廉价插入算法
• 4.3.4 粒子群算法的流程
• 4.3.5 算法复杂度分析
• 4.4 实验分析
• 4.4.1 实验数据
• 4.4.2 算法参数讨论
• 4.4.3 结果分析
• 4.5 本章小结
• 第五章 动态网络OVRP的粒子群算法研究
• 5.1 引言
• 5.2 动态网络OVRP的数学模型
• 5.2.1 数学模型
• 5.2.2 时间依赖函数
• 5.3 自适应惯性权重调整粒子群算法
• 5.3.1 粒子群算法惯性权重调整方法
• 5.3.2 自适应惯性权重调整粒子群算法
• 5.3.3 算法求解过程
• 5.3.4 算法复杂度分析
• 5.4 实验及分析
• 5.4.1 实验数据
• 5.4.2 结果分析
• 5.5 本章小结
• 第六章 智能车辆调度系统的实现
• 6.1 系统的工程背景及开发意义
• 6.2 系统的平台和框架
• 6.2.1 系统的开发平台
• 6.2.2 系统的总体框架
• 6.3 系统各功能的实现
• 6.3.1 承运单管理
• 6.3.2 回单管理
• 6.3.3 调度基础信息管理
• 6.3.4 报表管理
• 6.3.5 智能算法模块
• 6.4 系统应用实例
• 6.5 本章小结
• 第七章 总结与展望
• 7.1 论文总结
• 7.2 工作展望
• 参考文献
• 致谢
• 攻读博士学位期间参与的项目和获得的成果
• 攻读博士学位期间发表的学术论文