基于蚁群算法的物流系统配送车辆路径优化问题研究

发布时间：2017-05-25 06:12

  本文关键词：基于蚁群算法的物流系统配送车辆路径优化问题研究，由笔耕文化传播整理发布。

【摘要】：随着科技的发展与社会的进步,物流是企业在生产领域之外的又一利润源泉。为了降低企业物流配送成本,物流系统中的车辆路径问题(VRP)已经成为了热点问题。如何将配送车辆路径进行合理的优化从而降低物流配送成本是该问题的研究宗旨。物流配送车辆调度路径优化问题是组合优化中典型的NP-hard问题,且计算VRP问题的时间会随着问题规模的增大而增加,当问题规模较大时,精确算法很难求解。因此,目前物流系统中的配送环节的车辆调度路径优化问题的求解方法主要使用启发式算法。本文主要针对不同约束条件的物流车辆调度路径优化问题,对蚁群算法进行了三种改进,并分别采用改进算法进行仿真来验证算法的有效性。首先,针对蚁群算法在求解VRPTW时易陷入局部最优的问题,基于节约思想定义了蚂蚁转移概率,采用了Pareto最优解集的全局信息素更新规则,提出了改进的Pareto蚁群算法(Improved Pareto ant colony algorithm,简称IPACA)。通过仿真实验表明该算法提高了蚁群算法的全局搜索能力,有效避免了算法陷入局部最优,降低了总的配送费用(路程),从而验证了该算法的有效性。其次,对带时间窗的单配送中心的物流车辆路径问题出现的顾客时间窗变动或需求量变动的干扰事件,进行描述分析并建立相应的数学模型,并用蚁群算法求解该问题。然后,将自适应记忆算法(Adaptive Memory Programing Algorithm, AMPA)与蚁群算法(Ant Colony Algorithm, ACA)相混合提出了基于自适应记忆的蚁群算法(Adaptive Memory Programing for Ant Colony Algorithm, AMP-ACA),并应用该算法求解单配送中心的具有同时送货和取货需求的车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pick-up, VRPSDP).最后,对全文做一个总结,并且对下一步的研究工作进行了展望。
【关键词】：VRP 蚁群算法 VRPTW 干扰管理 VRPSDP
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F252;TP18
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-14
• 1.1 物流配送车辆调度优化问题的研究背景及意义10-11
• 1.2 国内外的研究现状11-12
• 1.3 本文工作12-13
• 1.4 本文的组织结构13-14
• 第二章 物流系统中的配送车辆路径优化问题相关理论14-22
• 2.1 物流系统中的配送车辆路径优化问题及分类14-15
• 2.2 求解VRP问题的精确算法15-16
• 2.2.1 分枝定界法15
• 2.2.2 枚举法15-16
• 2.2.3 动态规划法16
• 2.3 求解VRP的启发式算法16-18
• 2.3.1 求解VRP的经典启发式算法16-17
• 2.3.2 求解VRP的现代启发式算法17-18
• 2.4 蚁群算法18-20
• 2.4.1 蚁群算法的基本思想18-19
• 2.4.2 蚁群算法的实现过程19-20
• 2.4.3 蚁群优化的特点20
• 2.5 本章小结20-22
• 第三章 基于改进Pareto蚁群算法的车辆路径问题研究22-30
• 3.1 带时间窗的车辆路径优化问题的描述22-23
• 3.2 改进的Pareto蚁群算法23-26
• 3.2.1 IPACA算法概述23
• 3.2.2 IPACA改进的蚂蚁状态转移规则23-24
• 3.2.3 IPACA的基于Pareto最优解集的全局更新规则24-25
• 3.2.4 算法步骤25-26
• 3.3 仿真实验与结果分析26-29
• 3.3.1 仿真实验126-28
• 3.3.2 仿真实验228-29
• 3.4 本章小结29-30
• 第四章 对有干扰事件发生的车辆路径问题研究30-36
• 4.1 有干扰事件发生的车辆路径问题描述30-32
• 4.2 带干扰处理的蚁群算法32-33
• 4.2.1 对于VRPTW的干扰事件的扰动恢复策略32-33
• 4.2.2 算法步骤33
• 4.3 仿真实验与结果分析33-35
• 4.4 本章小结35-36
• 第五章 具有同时送取货需求的车辆路径问题的研究36-46
• 5.1 具有同时送取货需求的车辆路径问题描述36-37
• 5.2 基于自适应记忆的蚁群算法37-40
• 5.2.1 评价值函数的选择37-38
• 5.2.2 邻域结构和候选解38
• 5.2.3 记忆表和特赦准则38-39
• 5.2.4 AMP-ACA的算法流程39-40
• 5.3 仿真实验与结果分析40-45
• 5.3.1 仿真实验140-42
• 5.3.2 仿真实验242-43
• 5.3.3 仿真实验343-45
• 5.4 本章小结45-46
• 第六章 总结与展望46-48
• 6.1 总结46
• 6.2 展望46-48
• 致谢48-50
• 参考文献50-54
• 附录A (攻读硕士期间发表的论文及参加的科研项目)54-56
• 附录B (攻读硕士期间发表的软件著作权)56

【参考文献】

中国期刊全文数据库 前3条

1 王旭坪;许传磊;胡祥培;;有顾客时间窗和发货量变化的车辆调度干扰管理研究[J];管理科学;2008年05期

2 陈迎欣;;基于改进蚁群算法的车辆路径优化问题研究[J];计算机应用研究;2012年06期

3 马冬青;王蔚;;基于改进粒子群算法的物流配送车辆调度[J];计算机工程与应用;2014年11期

中国博士学位论文全文数据库 前2条

1 李琳;电子商务环境下物流配送中若干优化问题的研究[D];东北大学;2010年

2 杨剑峰;蚁群算法及其应用研究[D];浙江大学;2007年

中国硕士学位论文全文数据库 前3条

1 殷志锋;蚁群算法及其在多用户检测中的应用[D];兰州大学;2006年

2 丁晓林;物流企业车辆调度管理系统的设计与实现[D];山东大学;2008年

3 潘雪娇;协同物流资源选择与网络动态配置建模研究[D];上海交通大学;2010年

  本文关键词：基于蚁群算法的物流系统配送车辆路径优化问题研究，，由笔耕文化传播整理发布。

本文编号：392845