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

发布时间：2018-01-13 06:03

本文关键词：基于时间依赖的车辆路径问题研究　出处：《山东师范大学》2014年硕士论文　论文类型：学位论文

【摘要】：社会经济的飞速发展，带给交通运输行业巨大的冲击力。道路拥堵问题正日渐严重，道路拥堵消耗了大量的机会成本。避免道路拥挤的有效措施是设计合理的出行路线，道路的拥挤依赖于人们的出行时间。道路交通流变化清楚地显示，拥挤出现的时间和地点。根据交通流的可预测性和规律性，预估出现拥挤的区域和时间。论文对时间依赖性车辆路径问题（TDVRP）的研究充分利用交通流的这一特点构建时间依赖性交通网络，，同时采用启发式算法作为这一问题的主要解决方法。这一研究有助于企业进行高效精准的运输，提升了企业的竞争力，也对人们的简单快速出行提供了一些帮助。当前对于时间依赖性车辆路径问题的解决主要是将道路上的速度进行变化，构造一些拥挤区域，缺乏对时间依赖性网络的研究，因此对于时间依赖性网络的研究还存在以下问题：（１）如何构造时间依赖性网络，寻找在时间依赖性网络的基础上解决车辆路径问题的有效方法。（２）构造时间依赖性网络时，寻找确定造成网络时间性变化的关键因素。（３）时间依赖性车辆路径问题的解决方法与传统的车辆路径问题的解决方法存在哪些区别。本文从分析交通流的变化趋势开始，分析总结交通流变化的时间特点以及交通流变化与速度的关系。通过交通流的变化估算道路拥挤的时间变化，以此理论为基础对所要研究的道路网上的每条路线进行分析标注。逐步构建具有时间特性的道路网络。在构建时间依赖性网络时，文中认真分析了国内外有关TDVRP中时间依赖性网络的研究，在此基础上充分利用交通流的变化趋势对于拥挤的影响，构建了具有时间依赖性、动态的交通网络。该网络可以根据目标区域交通流的变化趋势做出调整，使之贴近真实的路网环境。时间依赖性网络是解决时间依赖性问题的关键，在进行路线构造时路线会随着网络的调整发生变化。为提高解决时间依赖性车辆路径问题的有效性，在解决的方法上选择启发式算法，该种发法能够有效控制可行解的质量，快速有效的解决问题。文中对TDVRP的路线构造主要有路线构造算法，路线优化算法。对于含有时间窗的TDVRP路线构造增加服务时间窗的改善算法。通过编程实现对时间依赖性网络的构建，并对带有时间窗的TDVRP和不带有时间窗的TDVRP进行求解，结果表明本文提出的方法能够获得有效的可行解。本文通过深入分析交通变化的时间特性，以贴近现实的数学模型，精准简便的求解方法，详细描述了时间依赖性车辆路径问题的求解过程，为实现交通运输行业中的精准运输，改善城市环境污染，缓解城市交通压力提供了参考和借鉴。
[Abstract]:With the rapid development of social economy, the transportation industry has a huge impact. The problem of road congestion is becoming more and more serious. Road congestion consumes a lot of opportunity cost. The effective measure to avoid road congestion is to design a reasonable travel route. Road congestion depends on people's travel time. The change of road traffic flow clearly shows. Time and place of congestion. According to the predictability and regularity of traffic flow. In this paper, the time-dependent vehicle routing problem (TDVRP) is studied to make full use of the characteristics of traffic flow to construct time-dependent traffic network. At the same time, heuristic algorithm is used as the main solution to this problem. This research helps enterprises to carry out efficient and accurate transportation, and improve the competitiveness of enterprises. It also provides some help for people to travel easily and quickly. At present, the main solution to the time-dependent vehicle routing problem is to change the speed on the road, construct some crowded areas, and lack the research on time-dependent network. Therefore, the study of time-dependent networks also has the following problems: 1) how to construct the time-dependent network and find an effective method to solve the vehicle routing problem based on the time-dependent network. 2) in constructing time dependent networks, the key factors to determine the temporal changes of networks are sought. 3) what are the differences between the time-dependent vehicle routing problem and the traditional vehicle routing problem. This paper begins with the analysis of the changing trend of traffic flow, analyzes and summarizes the time characteristics of traffic flow change and the relationship between traffic flow change and speed, and estimates the time change of road congestion through the change of traffic flow. On the basis of this theory, each route of the road network to be studied is analyzed and annotated. The road network with time characteristics is constructed step by step, and the time-dependent network is constructed. In this paper, the domestic and foreign research on time-dependent network in TDVRP is carefully analyzed, and on this basis, the influence of traffic flow trend on congestion is fully utilized, and a time-dependent network is constructed. Dynamic traffic network, which can be adjusted according to the changing trend of traffic flow in the target area, so as to make it close to the real road network environment. Time-dependent network is the key to solve the time-dependent problem. In order to improve the effectiveness of the time-dependent vehicle routing problem, the route will change with the adjustment of the network. The heuristic algorithm is chosen to solve the problem, which can effectively control the quality of feasible solution and solve the problem quickly and effectively. In this paper, the main route construction algorithm for TDVRP is route construction. Route optimization algorithm. The improved algorithm of adding service time window to TDVRP route construction with time window. The construction of time-dependent network is realized by programming. The TDVRP with time window and TDVRP without time window are solved. The results show that the proposed method can obtain effective and feasible solutions. Through in-depth analysis of the time characteristics of traffic changes, in order to close to the reality of the mathematical model, accurate and simple method to solve the time-dependent vehicle routing problem is described in detail. It provides reference and reference for realizing accurate transportation in transportation industry, improving urban environmental pollution and relieving urban traffic pressure.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U492.22

【参考文献】