交通网络限制条件下的最短路问题研究

摘要

一直以来，最短路算法是计算机科学、数学、地理信息系统和交通科学研究的热点，与最短路算法相关的问题多种多样，近年来随着地理信息系统(GIS)与智能交通系统(ITS)的结合，最短路问题在交通地理信息系统中有着十分重要的位置，尤其是对于出行者信息服务系统(ATIS)更是不可或缺的一部分。
　　 本文以交通网络为研究对象，研究城市道路交通网络在限制条件下的单源最短路径问题，探求在不同限制条件下最短路径探索的实现方法，并基于此方法给出程序实现。本文涉及的限制条件，不仅包括了道路交通网络本身的限制条件(通行限制、转向限制(延误)以及道路等级、道路交通状况)，还包括了面向用户服务的可供最短路探索需求者自定义的限制条件(限高、限宽和限载)。
　　 程序所采用的最短路算法是基于邻接表网络存储结构和单队列的程序运行结构的Dijkstra算法，程序在实现上分两个部分，程序l用于最短路探索方法的研究，实现在自建的虚拟路网下的最短路探索，其网络的存储方式为完全意义上的拓扑结构存储，点与边的关系在拓扑文件中严格对应，当网络拓扑结构发生改变时，必须改变拓扑文件的存储才能够使得最短路探索得以正确执行；程序2采用了拓扑存储与路径探索相分离的方式，使得路径探索可以不完全依赖于拓扑结构，当实际路网拓扑结构发生变化的时候，可以仅仅通过对路段属性的调整来实现探索过程的变更，同时程序结合了GIS二次开发组件提供的读取和显示图层的功能，开发了可视化的应用程序，将文中所涉及的各种交通网络限制条件下的最短路探索一一实现，并对其以具备实际应用意义的Shapefile格式的路网进行了测试，测试结果表明，程序能够在各种限制条件下正确得到符合路网本身和查询用户要求的最短路径。

目录

文摘

英文文摘

声明

第1章 绪论

1.1. 课题研究背景

1.2. 交通网络限制条件下最短路问题的研究现状

1.2.1. 问题的提出

1.2.2. 国内外研究现状

1.3. 论文的研究内容

1.3.1. 研究目标

1.3.2. 研究内容

1.3.3. 技术路线

1.3.4 论文的组织结构

第2章 基本概念与算法

2.1. 图论中的最短路问题

2.1.1. 图、赋权图

2.1.2. 子图

2.1.3. 有向图与无向图

2.1.4. 图论中的最短路问题与Dijkstra算法

2.2. 数据结构与最短路算法

2.2.1. 最短路算法的分类体系

2.2.2. 三种主流最短路径算法

2.2.3. 三种效率较高的串行标号算法

2.2.4. 解决SP-Turn问题的弧标号算法与节点标号算法

2.3. 地理信息系统

2.3.1. 网络分析

2.3.2. 地理信息系统中的路径分析

第3章 交通网络限制条件与最短路算法

3.1. 最短路问题

3.1.1. 问题描述

3.1.2. 交通网络中的最短路问题

3.2. 交通网络限制条件下的最短路问题

3.2.1. 通行限制

3.2.2. 转向限制

3.2.3. 必经点与回避点

3.2.4. 道路等级限制

3.2.5. 拥挤条件下的交通网络

第4章 虚拟交通网络中限制条件下的最短路径探索

4.1. 算法描述

4.2. 程序思想

4.3. 程序说明

4.3.1. 编程工具

4.3.2. 网络拓扑结构构建和载入

4.3.3. 最短路径探索

4.4. 限制条件实现方法

4.4.1. 包含在交通网络拓扑结构内的限制条件

4.4.2. 由用户自定义的的限制条件

4.5. 算例

4.5.1. 网络拓扑结构

4.5.2. 最短路问题求解

第5章 基于GIS的限制条件下的最短路探索程序

5.1. 开发工具

5.1.1. .NET Framework

5.1.2. ArcGIS Engine简介

5.1.3. ArcGlS Engine开发工具包

5.1.4. ArcGIS Engine运行环境

5.2. 地理数据模型

5.2.1. CAD数据模型

5.2.2. Coverage数据模型

5.2.3. Shapefiles数据模型

5.2.4. Geodatabase数据模型

5.2.5. 程序使用的矢量文件格式

5.3. C＃+ArcGIS Engine 9.2对交通网络限制条件下最短路算法的实现

5.3.1. 程序说明

5.3.2. 路段权重定义

5.3.3. 转向费用表生成与修改

5.3.4. 路段属性表的修改与合并

5.3.5. 单向交通与禁止通行限制条件的处理

5.3.6. 对必经点限制条件的处理

5.4. 交通限制条件下的最短路探索程序测试

5.4.1. 测试路网

5.4.2. 交叉口禁止左转下的最短路探索

5.4.3. 通行限制下的最短路径

5.4.4. 必经点与回避点最短路查询

5.4.5. 用户自定义限高、限宽、限载查询

5.5. 程序功能扩展：编译为dll

5.5.1. 吴江市公路信息服务系统

5.5.2. 将算法程序核心编译为dll文件

5.5.3. dll文件的调用

第6章 结论及展望

6.1. 结论

6.2. 主要创新点

6.3. 研究展望

致谢

参考文献

附录