带时间窗的车辆路径问题的研究与应用

发布时间：2020-11-12 01:30

【摘要】：车辆路径问题是研究如何优化物流运输的核心问题。研究车辆路径问题对于降低物流公司的运输成本,提高物流公司的服务质量都有重要意义。本文重点研究了带时间窗的车辆路径问题。针对在物流运输中的实际情况,本文提出了一种新的带时间窗车辆路径问题的双目标规划模型。第一个优化目标是使配送过程中总的车辆使用数目最小。在实际的货物运输中,由于汽车的油箱容量限制、司机的工作时间等,配送车辆的行驶距离往往会受到限制。因此,在每辆车都有行驶距离限制的约束下,用最少的车辆来完成配送任务能最大程度的节约运输成本。此外,本文考虑了每个用户都有自己的期望服务时间。尽可能的使得顾客在自己期望时间内被服务,从而提高物流公司的服务满意度,这是本文提出的规划模型的另一个优化目标。基于上述的规划模型,本文提出了一种双标准近似算法。该算法可以在多项式时间内给出上述问题的近似最优解。本文通过严格的理论分析证明了该算法的近似比为?O(log1/?),1???,并通过模拟实验分析了算法的运行效率。本文还设计了基于遗传算法的车辆路径系统。遗传算法是一种现代启发式算法,在求解整数规划问题时有着广泛的应用。本文介绍了用遗传算法求解车辆路径问题的方法,并通过实验分析了遗传算法的运行效率。实验结果表明遗传算法可以应用在实际的系统设计中。随后,本文介绍了车辆路径系统用到的相关技术,并通过模拟实例展示了此系统的功能。模拟实例选择了深圳20家三甲医院作为配送点。运行系统后,路径方案将以可视化的形式显示在百度地图上。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18
【图文】：

图 1-1 物流配送流程1.2 国内外相关研究和综述车辆路径问题（VRP）概括的说就是如何选取路径，使得配送货物总价最小。图 1-2 是车辆路径问题的示意图。VRP 经过多年的研究，形成了较完整的理论体系。车辆路径问题是典型的 NP-Hard 问题[2]，也是组合优领域的经典问题。至今，车辆路径问题的研究成果已经得到了十分广泛的用，比如快递员配送货物，救护车选取快捷路径等。文献[3]详细介绍了车路径问题的各种应用场景。Dantzig 和 Ramser 于 1959 年在他们的论文中首次提出了车辆路径问题及相应的数学模型。随后，车辆路径问题得到了泛的研究，并且从基本的车辆路径问题衍生出许多的变种问题，例如有运能力限制的模型，带时间窗约束的模型，有总路长限制的模型等。

车辆路径问题的示意图。VRP 经过多年的研。车辆路径问题是典型的 NP-Hard 问题[2]，至今，车辆路径问题的研究成果已经得到了送货物，救护车选取快捷路径等。文献[3]详用场景。Dantzig 和 Ramser 于 1959 年在他们径问题及相应的数学模型。随后，车辆路径基本的车辆路径问题衍生出许多的变种问题带时间窗约束的模型，有总路长限制的模型

点的距离分成若干部分。对于每一部分求解无源 VRP，然库节点组合，最后成为 DVRPTW 的一组合法路径。分割区据仓库节点的距离来进行区域划分。图 3-1 为 DVRPTW 分 描述 DVRPTW 的求解算法。
【相似文献】

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

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

2 钟雪灵;王雄志;;开放式车辆路径问题的混合算法[J];计算机仿真;2011年08期

3 熊浩;符卓;鄢慧丽;;动态车辆路径问题的隐分区灵活分批策略[J];同济大学学报(自然科学版);2013年05期

4 娄山佐;吴耀华;肖际伟;廖莉;;基于增强学习解决随机需求车辆路径问题[J];系统仿真学报;2008年14期

5 徐俊杰;;车辆路径问题的改进微正则退火算法[J];信息化纵横;2009年06期

6 吴斌;邵建峰;方叶祥;;基于客户满意度的开放式车辆路径问题研究[J];计算机工程;2009年17期

7 王江晴;张潇;;复杂环境下动态车辆路径问题的建模与求解[J];武汉大学学报(理学版);2010年04期

8 陆琳;蔡绍洪;;一类随机顾客车辆路径问题及其算法[J];南京航空航天大学学报;2010年04期

9 温惠英;孙博;;协同车辆路径问题的模糊规划模型和算法[J];计算机应用研究;2011年02期

10 杨皎平;高雷阜;王俊;;装卸联盟车辆路径问题及两阶段优化方法[J];计算机工程与应用;2011年14期

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

1 刘霞;车辆路径问题的研究[D];华中科技大学;2007年

2 陆琳;不确定信息车辆路径问题及其算法研究[D];南京航空航天大学;2007年

3 陈宝文;蚁群优化算法在车辆路径问题中的应用研究[D];哈尔滨工业大学;2009年

4 唐连生;突发事件下的车辆路径问题研究[D];西南交通大学;2008年

5 谢秉磊;随机车辆路径问题研究[D];西南交通大学;2003年

6 符卓;开放式车辆路径问题及其应用研究[D];中南大学;2003年

7 吕雄伟;邮政物流车辆路径问题研究[D];西南交通大学;2009年

8 潘立军;带时间窗车辆路径问题及其算法研究[D];中南大学;2012年

9 彭碧涛;三维装载约束下车辆路径问题研究[D];华南理工大学;2013年

10 马华伟;带时间窗车辆路径问题及其启发式算法研究[D];合肥工业大学;2008年

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

1 李文忠;有捎带的车辆路径问题的研究[D];西南交通大学;2010年

2 曹高立;基于求解车辆路径问题的混合智能优化算法研究[D];昆明理工大学;2015年

3 杜涛涛;仿生智能算法在逆向物流选址与车辆路径问题中的应用研究[D];上海工程技术大学;2015年

4 罗敖翔;基于实时交通信息的快递企业车辆路径问题研究[D];西南交通大学;2015年

5 邓璇;考虑货物类别的多车型车辆路径问题优化研究[D];长安大学;2015年

6 焦云龙;基于行程时间预测的物流运输车辆路径优化研究[D];大连海事大学;2015年

7 陈瑞杰;取送一体化多配送中心车辆路径问题的研究[D];大连海事大学;2015年

8 董蕊;具有时间窗约束的累积性车辆路径问题研究[D];上海交通大学;2015年

9 史春燕;带车辆时间窗的多车场车辆路径问题研究[D];重庆工商大学;2015年

10 徐腾飞;危险化学品选址及车辆路径问题研究[D];北京化工大学;2015年

本文编号：2880044