动态多目标车辆路径问题的算法研究

论文摘要

近年来,随着社会市场竞争的日趋激烈,尤其是经济的飞速发展、多样化的社会运输交通工具、复杂性、多变性的交通运输网络,使得物流配送管理及其优化越来越受到整个社会各方面的关注。这些都促使了车辆路径问题的发展,也为车辆路径问题(Vehicle Routing Problem,VRP)的研究提供了广泛的现实基础,其中,实时处理车辆路径问题的应用研究,由于现代通信及其信息技术的发展成果而成为可能。被称为“运筹学领域最为成功的研究之一”的车辆路径问题(VRP)是理论和实践结合最为紧密的研究课题方向之一。现在,许多研究车辆路径问题的工作大部分都是集中在静态问题上,而对有动态需求变化方面的车辆路径问题的的研究很少。然而,随着社会和科学信息技术的发展,人们更希望在物流运输配送管理上能够实时的满足他们的需求。这样,就使得动态需求方面的车辆路径问题成为热点。因此,在对实际配送(尤其是动态需求)车辆路径问题的研究意义重大。论文主要研究工作及成果有以下几个方面:1.提出了动态需求VRP的多目标求解问题以及动态需求VRP的优化策略,采用基于灰色与马尔可夫链组合模型的需求预测方法将未知的信息转换成已知的信息,从而将动态问题转换为静态问题,重点研究基于优先预测的动态需求信息车辆路径问题的建模和相应的混合算法的策略问题,对于提高物流配送管理的工作效率和经济利益具有重大的现实意义和实用价值。2.引入时间段和关键点的概念,建立了基于时间段和关键点的动态问题的优化策略,通过动态问题的静态化处理将动态车辆路径问题转化成若干静态子问题来进行求解,从而为动态车辆路径问题的求解提供新的优化策略。3在将动态问题分解成若干静态子问题进行求解(即通过设立时间段和关键点),实现动态问题的静态化处理的基础上。最后,设计两种混合算法分别是基于预测优化策略和动态问题静态化处理的优化机制的基础上进行模型的求解,最后通过仿真实验论证,该混合算法可以提高效率。a.基于遗传算法的混合算法,通过遗传算法的改进,在变异操作中加入禁忌搜索算法,利用遗传算法得到一个较好的初始解,提高解的质量,避免陷入“早熟”的现象,并提出新颖的编码方式和交叉操作;并且在算法后期加入爬山算法,补充遗传算法局部搜索能力不足的缺陷。b.基于禁忌搜索算法的混合算法,通过节约法得到的初始解,为禁忌搜索算法提供较好的初始解,从而提高整个混合算法的收敛速度。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 选题背景和研究意义
• 1.1.1 选题背景
• 1.1.2 研究意义
• 1.2 车辆路径问题的研究现状
• 1.2.1 车辆路径问题的概述
• 1.2.2 车辆路径问题的局限性
• 1.3 动态车辆路径问题的研究现状
• 1.3.1 动态车辆路径问题的概述
• 1.3.2 动态车辆路径问题的局限性
• 1.4 研究内容
• 第二章 物流配送中的车辆路径问题分析
• 2.1 车辆路径问题
• 2.1.1 车辆路径问题的定义
• 2.1.2 车辆路径问题的分类
• 2.1.3 论文研究的方向
• 2.2 静态车辆路径问题
• 2.2.1 静态车辆路径问题的定义
• 2.2.2 静态车辆路径问题的分类
• 2.2.3 静态车辆路径问题的优化方法
• 2.3 动态车辆路径问题
• 2.3.1 动态车辆路径问题的定义
• 2.3.2 动态车辆路径问题的特征
• 2.3.3 动态车辆路径问题的分类
• 2.3.4 动态车辆路径问题的求解策略
• 2.4 静态和动态VRP 的区别
• 2.5 小结
• 第三章 车辆路径问题中的算法
• 3.1 精确算法
• 3.2 启发式算法
• 3.3 车辆路径问题中若干种启发式算法的具体描述
• 3.3.1 节约算法（C-W 算法）
• 3.3.2 爬山算法
• 3.3.3 遗传算法
• 3.3.4 禁忌搜索算法
• 3.4 小结
• 第四章 一类特殊的动态需求车辆路径问题的求解策略的研究
• 4.1 基于一般预测方法的动态优化策略
• 4.1.1 基于一般预测方法的几个概念
• 4.2 灰色系统预测方法
• 4.2.1 灰色系统预测方法
• 4.2.2 灰色系统预测模型
• 4.3 马尔科夫链预测方法
• 4.4 灰色-马尔科夫链模型预测未知需求量
• 4.5 小结
• 第五章 基于预测的VRP 数学模型的描述
• 5.1 引言
• 5.2 数学模型
• 5.3 算法设计
• 5.3.1 基于遗传算法的混合算法的思想描述
• 5.3.2 基于禁忌搜索算法的混合算法的思想描述
• 5.4 仿真实验
• 5.4.1 实验一
• 5.4.2 实验二
• 5.5 小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 发表论文和科研情况说明
• 致谢