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

发布时间：2017-07-17 23:37

  本文关键词：基于蚁群算法的物流配送车辆路径问题研究

  更多相关文章： 物流配送 车辆路径问题 改进蚁群算法

【摘要】：车辆路径问题属于运筹学范畴,是运输线路规划、选取合理配送车辆的核心工作,在提高货物运输经济中起着至关重要的作用。随着市场竞争的剧烈化和顾客需求的多样化,带能力约束的VRP已经不能科学地指导企业完成其配送任务;从提高企业的市场竞争力和满足客户的多样性需求的角度研究VRP问题越来越受到大量学者的广泛关注,相比于只包含车辆载重约束的基本VRP,带时间窗的车辆路径问题(VRPTW)能更好地反应实际应用情况。本文结合实际的生产运作情况,运用改进的蚁群算法,有效的求解带时间窗的多车型车辆路径问题。研究结论主要有:(1)蚁群算法中,蚂蚁在初始寻优过程中,在选择下一节点时,根据状态转移概率确定备选客户点的概率值。通常情况下,蚂蚁选择概率较大的节点,这样就会导致蚁群算法在搜索过程中容易出现停滞现象。本文在选择下一节点时引入一个随机数,让部分蚂蚁有一定的犯错概率,也就是蚂蚁在选择下一节点时会有一定的探索性搜索,并在蚂蚁完成一次迭代后对结果进行遗传算子操作,这样可以有效扩大问题的解空间,从而提高算法的求解性能。(2)在对带时间窗的车辆路径问题求解时,客户的服务时间窗要求对目标函数有直接影响,因此在蚂蚁选择下一节点的转移概率中,仅考虑路径长度以及路径上的信息素浓度可能得不到问题的合理解。本文通过在蚂蚁的转移概率中加入了时间窗因素,使得问题的解更接近最优解,通过对蚁群算法改进前后的结果对比分析,发现改进蚁群算法在求解该问题时更具优势。(3)目前对于带时间窗的多车型车辆路径问题的研究较少,大容量货车有装载量大、行驶距离远的优点,但却不可避免的具有行驶速度慢、配送效率低的缺陷,而小容量货车则相反。因此,本文在综合考虑不同车型的特点,结合不同客户对服务时间窗要求的基础上,设计了改进的蚁群算法对带时间窗的多车型车辆路径问题进行求解,研究结果表明,对于同一配送任务,选用混合车型的配送方案在某种程度上会取得更好的效果。
【关键词】：物流配送 车辆路径问题 改进蚁群算法
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U116.2;F252
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-15
• 1.1 研究背景及意义9-10
• 1.2 国内外研究现状10-13
• 1.2.1 VRP国内外研究现状10-12
• 1.2.2 蚁群算法国内外研究现状12-13
• 1.3 本文的主要研究内容13-15
• 2 物流配送及车辆路径优化概述15-27
• 2.1 基本理论15-16
• 2.1.1 定义15
• 2.1.2 物流配送中存在的问题15-16
• 2.2 车辆路径问题概述16-19
• 2.2.1 VRP的定义16
• 2.2.2 VRP的构成要素16-18
• 2.2.3 VRP的优化目标18-19
• 2.3 车辆路径问题的数学模型19-24
• 2.3.1 经典VRP模型19-21
• 2.3.2 时间窗问题概述21-22
• 2.3.3 带软时间窗车辆路径问题的模型22-24
• 2.4 带时间窗车辆路径问题的求解方法24-26
• 2.4.1 精确算法24
• 2.4.2 启发式算法24-26
• 2.5 本章小结26-27
• 3 改进蚁群算法研究27-42
• 3.1 基本蚁群算法27-32
• 3.1.1 蚁群算法基本原理27
• 3.1.2 基本蚁群算法中的参数及其含义27-29
• 3.1.3 算法执行过程描述29-31
• 3.1.4 蚁群算法的优缺点31-32
• 3.2 改进蚁群算法32-36
• 3.2.1 蚁群系统32-33
• 3.2.2 精英蚁群系统33-34
• 3.2.3 最大最小蚁群系统34-35
• 3.2.4 排序蚁群系统35-36
• 3.3 本文对蚁群算法的改进36-41
• 3.3.1 对选择下一节点概率的改进36-37
• 3.3.2 对信息素挥发因子的改进37-38
• 3.3.3 基于遗传算法的蚁群算法38-40
• 3.3.4 改进后的蚁群算法的计算步骤40-41
• 3.4 本章小结41-42
• 4 带时间窗的多车型车辆路径问题算例分析42-58
• 4.1 基于Matlab的改进蚁群算法设计42-44
• 4.2 问题描述44-45
• 4.3 算法实现与结果分析45-58
• 结论与展望58-60
• 结论58-59
• 展望59-60
• 致谢60-61
• 参考文献61-65
• 攻读硕士期间发表的论文及科研成果65

【相似文献】

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

1 王云平;;车辆路径问题的形式化及其知识表示方法研究[J];辽宁省交通高等专科学校学报;2006年04期

2 王江晴;康立山;;动态车辆路径问题仿真器的设计与实现[J];核电子学与探测技术;2007年05期

3 曹二保;赖明勇;张汉江;;模糊需求车辆路径问题研究[J];系统工程;2007年11期

4 唐连生;梁剑;;突发事件下的车辆路径问题研究综述[J];铁道运输与经济;2008年12期

5 唐伟勤;张隐;张敏;;大规模突发事件应急物资调度中的车辆路径问题[J];物流技术;2008年12期

6 刘红梅;陈杨;;车辆路径问题的形式化方法研究[J];科技资讯;2008年05期

7 唐加福;孔媛;潘震东;董颖;;基于划分的蚁群算法求解货物权重车辆路径问题[J];控制理论与应用;2008年04期

8 熊志华;邵春福;姚智胜;;车辆路径问题的可靠性研究[J];物流技术;2008年08期

9 徐俊杰;;利用微正则退火算法求解车辆路径问题[J];安庆师范学院学报(自然科学版);2009年02期

10 宁晓利;;车辆路径问题的组合优化算法[J];物流技术;2009年06期

中国重要会议论文全文数据库 前10条

1 符卓;陈斯卫;;车辆路径问题的研究现状与发展趋势[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

2 杨世坚;陈韬;;随机车辆路径问题研究综述[A];中国系统工程学会决策科学专业委员会第六届学术年会论文集[C];2005年

3 李桂平;陈楠;;多中心车辆路径问题的解决思路[A];中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集[C];2007年

4 李大卫;王梦光;;广义车辆路径问题——模型及算法[A];1997中国控制与决策学术年会论文集[C];1997年

5 符卓;聂靖;;开放式车辆路径问题及其若干研究进展[A];中国运筹学会第八届学术交流会论文集[C];2006年

6 陈宝文;宋申民;陈兴林;单志众;;应用于车辆路径问题的多蚁群算法[A];第25届中国控制会议论文集（下册）[C];2006年

7 戎丽霞;;模糊需求条件下的多车场车辆路径问题[A];第三届中国智能计算大会论文集[C];2009年

8 张凤姣;张兴芳;;基于不确定理论的车辆路径问题[A];第九届中国不确定系统年会、第五届中国智能计算大会、第十三届中国青年信息与管理学者大会论文集[C];2011年

9 肖雁;符卓;李育安;;带软时间窗的车辆路径问题及其应用前景探讨[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

10 许鑫;范文慧;冯雅U，

本文编号：555150