基于时间依赖的车辆路径问题研究

摘要

社会经济的飞速发展,带给交通运输行业巨大的冲击力。道路拥堵问题正日渐严重,道路拥堵消耗了大量的机会成本。避免道路拥挤的有效措施是设计合理的出行路线,道路的拥挤依赖于人们的出行时间。道路交通流变化清楚地显示,拥挤出现的时间和地点。根据交通流的可预测性和规律性,预估出现拥挤的区域和时间。论文对时间依赖性车辆路径问题(TDVRP)的研究充分利用交通流的这一特点构建时间依赖性交通网络,同时采用启发式算法作为这一问题的主要解决方法。这一研究有助于企业进行高效精准的运输,提升了企业的竞争力,也对人们的简单快速出行提供了一些帮助。
　　当前对于时间依赖性车辆路径问题的解决主要是将道路上的速度进行变化,构造一些拥挤区域,缺乏对时间依赖性网络的研究,因此对于时间依赖性网络的研究还存在以下问题:
　　(1)如何构造时间依赖性网络,寻找在时间依赖性网络的基础上解决车辆路径问题的有效方法。
　　(2)构造时间依赖性网络时,寻找确定造成网络时间性变化的关键因素。
　　(3)时间依赖性车辆路径问题的解决方法与传统的车辆路径问题的解决方法存在哪些区别。
　　本文从分析交通流的变化趋势开始,分析总结交通流变化的时间特点以及交通流变化与速度的关系。通过交通流的变化估算道路拥挤的时间变化,以此理论为基础对所要研究的道路网上的每条路线进行分析标注。逐步构建具有时间特性的道路网络。在构建时间依赖性网络时,文中认真分析了国内外有关TDVRP中时间依赖性网络的研究,在此基础上充分利用交通流的变化趋势对于拥挤的影响,构建了具有时间依赖性、动态的交通网络。该网络可以根据目标区域交通流的变化趋势做出调整,使之贴近真实的路网环境。
　　时间依赖性网络是解决时间依赖性问题的关键,在进行路线构造时路线会随着网络的调整发生变化。为提高解决时间依赖性车辆路径问题的有效性,在解决的方法上选择启发式算法,该种发法能够有效控制可行解的质量,快速有效的解决问题。文中对TDVRP的路线构造主要有路线构造算法,路线优化算法。对于含有时间窗的TDVRP路线构造增加服务时间窗的改善算法。通过编程实现对时间依赖性网络的构建,并对带有时间窗的TDVRP和不带有时间窗的TDVRP进行求解,结果表明本文提出的方法能够获得有效的可行解。
　　本文通过深入分析交通变化的时间特性,以贴近现实的数学模型,精准简便的求解方法,详细描述了时间依赖性车辆路径问题的求解过程,为实现交通运输行业中的精准运输,改善城市环境污染,缓解城市交通压力提供了参考和借鉴。

目录

封面

声明

目录

中文摘要

英文摘要

第1章 绪论

1.1问题的提出

1.2时间依赖性车辆路径问题研究进展

1.3本文主要工作和主要框架

第2章 车辆路径问题描述

2.1车辆路径问题一般描述和特点

2.2车辆路径问题分类

第3章 时间依赖性网络

3.1时间依赖性网络研究进展

3.2时间依赖性网络特点

3.3构造时间依赖性网络模型

第4章 求解时间依赖性车辆路径问题

4.1 TDVRP求解思路

4.2 求解TDVRP的基本算法

4.3仿真实验及分析

第5章 求解带有时间窗的TDVRP

5.1带有时间窗的TDVRP的研究进展

5.2带有时间窗的TDVRP问题描述

5.3 带有时间窗的TDVRP求解方案

5.4仿真实验及分析

第6章 总结与研究展望

6.1研究工作总结

6.2 本文的创新点

6.3进一步研究的方向

参考文献

附录

致谢

攻读硕士学位期间公开发表的论文