交通网络分析中的最优路径算法研究(硕士论文).pdf

中国科学技术大学硕士论文摘要
摘要
最优路径算法是交通网络分析中路径分析的核心。当前对交通网络动态最优
路径问题的研究有两大方向,一是传统静态最优路径算法在交通网络中的应用。
二是通过对道路交通流的建模,运用动态规划、变分理论、随机过程理论等知识
建立影响交通流的各要素间的依赖关系,再求解最优路径。前者基于一种静态的
路段权值假设,即该路段的权值在最优路径算法求解过程中保持不变。而这种假
设在交通网络中是不成立的。交通网络的一大特征正是时变性和不可预知性。若
以道路的通行时间来表示该路的权值,则同样一条道路的权值可能因为一天中的
不同时刻而有很大的差别,从而最优路径可能也不止一条。静态最优路径算法无
法解决这个问题。后者往往由于模型一般比较复杂(模型越是接近实际的交通流
状况就越复杂)而难于求解。
本文针对最优路径算法在实际应用(如导航应用)中的特点,提出了分时分
段计算动态最优路径的思想,即在对应时段对应路段应用得到的交通信息指导路
径寻优;并依据该思想提出了动态最优路径算法和自适应的动态最优路径算法。
前者依据各路段的权值在一天中对应时段的统计分布状况,根据车辆到达路口的
时间,通过查表的方式计算出一个全局的最优路径,该算法用以解决成批派车的
点到点之间最优路径问题。后者依据车辆到达路口的时间,实时接收该时刻各路
段的权值分布情况,选出一条最优路径到达下一个路口;在下一个路口继续应用
该策略直到到达目的地,该算法可以解决具有随机出行特征的单车实时选择最优
路径问题。
关键词:A*算法动态最优路径算法自适应动态最优路径算法矢量地图全球卫
星定位系统地理信息系统智能交通系统
I
中国科学技术大学硕士论文 Abstract
Abstract
The shortest path algorithms are the core of path analysis of work
analysis. The current research of the dynamic shortest path algorithms has two
orientations. One the application of traditional static shortest path algorithms and the
other puting the shortest path with the application of kinds of knowledge
through modeling the transportation environments. The first method bases on the
fixed weigh hypothesis of the path which doesn’t coincide the fact that the transport
network is a work with a varied and unpredictable weigh of each path in
all time. The dynamic shortest paths may vary with different time in a day, so static
shortest path cannot solve this new problem. The second method often cannot get the
accurate solution for plicated model.
This thesis raises a new strategy pute the dynamic shortest path in
work according to the characters of a real time environment. That is
searching the shortest path in the light of the position and the arrival time through the
acquirement of real time information of transportation. The thesis also gives two
algorithms which adapt to different circumstances. The dynamic shortest path
putes the global shortest path through