基于大数据的可靠最短路径研究

发布时间：2018-03-29 17:14

本文选题：路径规划　切入点：时间可靠性　出处：《北京交通大学》2017年硕士论文

【摘要】：随着经济社会的发展,城市规模的不断扩大,城市人口显著增长,机动车保有量显著增加,城市交通供需矛盾导致的拥堵问题日渐突出。如何提高城市居民的出行效率,缓解城市交通拥堵,成为交通科学关注的一个重要科学问题。其中,如何准确的找到可靠最短路径引起了交通科学领域研究者的普遍关注。本文目标是为出行者提供出行时间依概率可靠的路径规划方案。(1)总结了三种典型的可靠最短路径模型(TTB模型、METT模型、MMD模型),通过分析各模型的适用条件,发现鲁棒性下的MMD模型在高延迟路网中会产生过多可选择路径(通过在测算路网中放大各个路段的最大延迟倍数,算法就会生成过多的路径选择),从而导致最可靠路径的信息被掩盖。通过比较鲁棒性模型和非鲁棒性模型的关联性,发现可以利用概率分布函数拟合最大延迟参数,保证MMD模型只产生一条可靠路径。(2)考虑实际交通状况与不同居民的出行需求,提出了 3种改进的启发式函数的定义。1、回避拥堵。利用路段的实际距离与其对应的85%车速,估算路段出行时间;通过Dijkstra最短路径估算当前节点至终点的最少出行时间。2、路段历史平均出行时间最短。利用路段不同时间间隔下平均通行时间的最小值,估算路段出行时间;通过Dijkstra最短路径估算当前节点至终点的最少出行时间。3、躲避信号交叉口。考虑到信号灯等待时间,对于一次出行的总时间有较大影响,我们提出了以经过的交叉口数作为路径通行时间估计的启发式函数。(3)利用北京市浮动车数据,通过拟合数据说明对路段通行时间正态分布假设的合理性;通过对比静态下早、晚高峰时段不同风险态度人群面对同一OD对的路径选择,发现北京晚高峰时段交通拥堵更严重;研究还发现,三种改进的启发式函数定义均能有效降低算法复杂度,并提高计算效率。特别是定义(2)和定义(3),可以将计算效率提高到原算法计算效率的10倍。本文利用北京市交通实际数据对可靠最短路径的模型与算法展开了深入研究。总结了不同模型之间的特点,针对TTB模型下的A*启发式算法提出三种改进方式,并利用实际路网进行了验证。本文的研究工作,将为城市居民获得出行时间依概率可靠的路径规划方案提供理论基础。
[Abstract]:With the development of economy and society, the urban scale is expanding, the urban population is increasing significantly, the number of motor vehicles is increasing significantly, and the congestion problem caused by the contradiction of urban traffic supply and demand is becoming more and more serious. How to improve the travel efficiency of urban residents? Alleviating urban traffic jams has become an important scientific issue in traffic science. Among them, How to find the reliable shortest path accurately has aroused the widespread concern of the researchers in the field of transportation science. The aim of this paper is to provide the travelers with the travel time according to the probability of reliable path planning scheme. Short path model TTB model METT model MMD model, through the analysis of the applicable conditions of each model, It is found that the MMD model under robustness can produce too many alternative paths in high delay road networks. By comparing the correlation between the robust model and the non-robust model, it is found that the probability distribution function can be used to fit the maximum delay parameters. To ensure that only one reliable path is generated in the MMD model, taking into account the actual traffic situation and the travel needs of different residents, the definition of three improved heuristic functions is put forward to avoid congestion. The actual distance of the road section and the corresponding 85% speed are used. Estimating the travel time of road section, estimating the minimum travel time from the current node to the end point by Dijkstra shortest path, and the average travel time of the road section is the shortest. Using the minimum value of the average travel time at different time intervals, the travel time of the road section is estimated. The shortest path of Dijkstra is used to estimate the minimum travel time from the current node to the terminal, and to avoid the signalized intersection. Considering the waiting time of the signal light, it has a great influence on the total travel time. We propose a heuristic function of using the number of intersection passes as the heuristic function to estimate the passage time.) using the floating vehicle data in Beijing, we illustrate the rationality of the assumption of normal distribution of road passage time by fitting the data. It is found that traffic congestion is more serious in Beijing during late rush hour when people with different risk attitudes face the same OD pair. The study also finds that the three improved heuristic function definitions can effectively reduce the complexity of the algorithm. The computational efficiency can be improved by 10 times that of the original algorithm, especially the definition of 2) and the definition of "3". In this paper, the model and algorithm of reliable shortest path are deeply studied by using the actual traffic data in Beijing. The characteristics of different models are summarized. This paper proposes three improved methods for the A- heuristic algorithm based on TTB model and verifies it by using the actual road network. The research work in this paper will provide a theoretical basis for urban residents to obtain a reliable path planning scheme of travel time depending on probability.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491

【参考文献】