城市交通应急状态下出行者最短路径选择研究

摘要

随着我国经济的快速发展，由于城市功能的多样化、设施的复杂化，以及城市对交通等基础设施的高度依赖性，在一定程度上，城市的脆弱性大大增加。城市道路交通系统作为城市公共基础设施，是城市的生命线，在应急状态下，道路系统部分损坏或行驶条件受到限制，因此，结合我国城市道路交通的实际状况，对此时的交通网络进行最短路径分析，并应用于城市应急系统，对提高应急状态下的通行能力和发挥城市应急系统的最大效率，具有重要意义。本文对交通限制条件下最短路径的算法进行了理论分析，并建立了交通限制条件下的最短路径算法模型。
　　本文介绍了交通网络的特点，分析了交通网络图的连通性。研究了应急状态下，城市道路网络图的连通性特点，从而确定道路的受破坏的程度。根据以上分析，将城市交通网络抽象为应急状态下的交通网络模型。
　　对交通网络的拓扑关系进行分析，在此基础上对于交通网络的存储结构进行了研究，重点研究了不同存储结构的特点和特性，在实现方法和时间复杂度方面对各存储方式进行了比较，针对交通网络图的特性，阐明了应急状态下交通网络图的存储结构的选取原则。
　　本文分析了单源点最短路径问题及经典Dijkstra算法的特点，重点分析了最短路径的搜索策略，用DKA优化了经典的Dijkstra算法，实现了算法的改进，从而确立了应急状态下的最短路径算法。
　　在最短路径的应用方面，根据地理信息系统（GIS）中对最短路径搜索功能实现的要求，编制了改进Dijkstra算法程序，采用城市道路网数据，对模型进行验证。

目录

城市交通应急状态下出行者最短路径选择研究

STUDY ON URBAN TRAFFIC OF EMERGENCY CIRCUMSTANCE SHORTEST PATH CHOICE WITH TRAVELLERS

摘要

Abstract

第1章 绪论

1.1 课题研究的目的和意义

1.2 国内外研究现状

1.2.1 国外研究现状

1.2.2 国内研究现状

1.2.3 国内外研究现状小结

1.3 主要研究内容和技术路线

第2章 应急状态下交通网络分析

2.1 交通网络的定义和特点概述

2.2 交通网络赋权图的特点

2.3 交通网络有向图连通度特性分析

2.4 应急状态下交通网络特性分析

2.4.1 交通限制条件下交通网络模型特性分析

2.4.2 应急状态下交通网络模型的确立

2.4.3 应急状态下交通网络的图的表示

2.4.4 应急状态下交通网络图的拓扑关系分析

2.5 本章小结

第3章 应急状态下最短路径算法研究

3.1 最短路径问题讨论

3.2 单源点最短路径问题（SSSP）算法

3.2.1 狄克斯特拉(Dijkstra )算法

3.2.2 Dijkstra算法复杂度分析

3.2.3 经典Dijkstra算法分析

3.3 图的常用存储结构

3.3.1 关联矩阵

3.3.2 邻接矩阵

3.3.3 邻接表

3.3.4 十字链表

3.3.5 邻接多重表

3.3.6 二数组法

3.4 图的存储结构比较分析

3.5 应急状态下最短路径算法的实现

3.5.1 经典Dijkstra算法的优化途径

3.5.2 最短路径搜索策略分析

3.5.3 常用的Dijkstra优化算法分析

3.5.4 应急状态下一种改进的Dijkstra算法

3.6 本章小结

第4章 改进的Dijkstra算法实现

4.1 地理信息系统（GIS）的开发方式

4.1.1 应用型地理信息系统（GIS）的开发方式

4.1.2 地理信息系统集成开发的方式

4.1.3 应用型GIS三种实现方式的分析与比较

4.2 SuperMap数据的组织与管理

4.3 改进最短路径算法的实现

4.3.1 基于DKA算法的最短路径分析程序的实现

4.3.2 应急状态下最短路径分析测试

4.4 本章小结

结论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

致谢