交通网络分析中的最优路径算法研究

摘要

最优路径算法是交通网络分析中路径分析的核心。当前对交通网络动态最优路径问题的研究有两大方向，一是传统静态最优路径算法在交通网络中的应用。二是通过对道路交通流的建模，运用动态规划、变分理论、随机过程理论等知识建立影响交通流的各要素间的依赖关系，再求解最优路径。前者基于一种静态的路段权值假设，即该路径的权值在最优路径算法求解过程中保持不变。而这种假设在交通网络中是不成立的。交通网络的一大特征正是时变性和不可预知性。若以道路的通行时间来表示该路的权值，则同样一条道路的权值可能因为一天中的不同时刻而有很大的差别，从而最优路径可能也不止一条。静态最优路径算法无法解决这个问题。后者往往由于模型一般比较复杂(模型越是接近实际的交通流状况就越复杂)而难于求解。 本文针对最优路径算法在实际应用(如导航应用)中的特点，提出了分时分段计算动态最优路径的思想，即在对应时段对应路段应用得到的交通信息指导路径寻优；并依据该思想提出了动态最优路径算法和自适应的动态最优路径算法。前者依据各路段的权值在一天中对应时段的统计分布状况，根据车辆到达路口的时间，通过查表的方式计算出一个全局的最优路径，该算法用以解决成批派车的点到点之间最优路径问题。后者依据车辆到达路口的时间，实时接收该时刻各路段的权值分布情况，选出一条最优路径到达下一个路口；在下一个路口继续应用该策略直到到达目的地，该算法可以解决具有随机出行特征的单车实时选择最优路径问题。

目录

文摘

英文文摘

中国科学技术大学学位论文相关声明

第一章绪论

1.1 ITS简介

1.1.1 ITS的由来

1.1.2 ITS的组成

1.2 GPS、GIS简介

1.2.1 GPS简介

1.2.2 GIS简介

1.2.3 GIS-T简介

1.3交通网络分析中动态最优路径算法研究意义

1.4最优路径算法的研究现状

1.4.1静态最优路径算法的研究现状

1.4.2动态最优路径算法的研究现状

第二章矢量地图综述

2.1矢量地图的基本概念

2.1.1电子地图及其分类

2.1.2矢量地图在GIS中的应用

2.2 GPS实验室开发的矢量地图与GIS系统

2.2.1系统组成

2.2.2地图矢量库

2.2.3地图数据库

2.3交通矢量地图的生成

2.4地图矢量库的存储组织

第三章A*算法

3.1最优路径的数学模型

3.2 A*算法概述

3.2.1 A*算法的基本思想

3.2.2 A*算法原理

3.3 A*算法性质

3.3.1评估函数的选取

3.3.2 A*算法的可接纳性

3.2.3 A*的最优性

3.4 A*算法的变种

第四章静态最优路径

4.1松弛运算

4.1标号算法

4.1.1 Dijkstra算法

4.1.2 Floyd算法

4.1.3各类标号算法复杂度之比较

4.2A*算法应用于矢量地图的分析

4.2.1 A*算法的应用分析

4.2.2应用于矢量地图的A*算法可接纳性的简要证明

4.3静态最优路径的程序实现

4.3.1算法步骤

4.3.2矢量地图的数据结构

4.3.3 A*算法涉及的数据结构

4.3.4 A*算法的函数说明

4.3.5实验结果

第五章动态最优路径

5.1动态最优路径问题类型

5.2动态最优路径的求解思想

5.3动态交通网络的表示及性质

5.3.1动态交通网络的表示

5.3.2动态交通网络的性质

5.4动态最优路径求解方案

5.4.1时段的划分

5.4.2路段行程时间的确定

5.4.3车载型最优路径计算的系统配置示意图

5.4.4时间最优路径的计算方法

5.4.5模拟的实验效果图

5.5自适应动态最优路径算法

5.5.1自适应动态最优路径算法的必要性

5.5.2自适应解决方案

5.5.3自适应动态最优路径算法的模拟效果图

第六章总结与展望

参考文献

致谢

附录