毕业论文--110出警线路优化系统的设计与实现

摘要 I 摘要 随着社会的不断发展进步 110 报警服务平台已经成为人民生活不可或缺的 重要安全保障 这一方面说明我国公安系统建设取得了巨大的进步 另一方面也 意味着公安系统承载的责任也愈加重大 如何进一步提高 110 出警平台的工作效 率 缩短出警车辆的时间消耗成为今后 110 警务平台建设的重要内容 基于上述 考虑 本文以山东省潍坊市的城市道路网络为基础设计并实现了最优路径优化模 块 为 110 出警信息系统的构建提供基础 以达到提高 110 出警系统出警效率的 目的 为了提高 110 公安系统的出警效率 本文对城市环境下的 110 出警路径优化 算法进行了研究 论文首先对路网数学模型进行了研究 根据地图学和图论的有 关原理 将地图数据划分为节点和路段两种类型 分析总结了各种存储结构的原 理和特点 最终采用邻接矩阵存储地图矢量数据 然后 论文从更加实际的角度 出发 探讨道路阻值的设定 采用 AHP 层次分析法对道路阻值权重进行初步的 比较设定 使影响道路畅通性的各种因素可以纳入优化模型 论文的关键部分是 路径优化算法的研究 首先介绍各种路径寻优算法的分类和特点 重点讨论了 Dijkstra 算法和 A 启发式算法的原理和实现步骤 分析了两种算法各自的特点 并将 Dijkstra 算法和 A 启发式算法作为本案例的路径优化算法进行实现 最后以 潍坊市的道路网络作为数据背景进行编程实现 选取 MAPINFO 软件作为地图平 台 采用 MapBasic 二次开发语言进行算法编程 最终实现了潍坊城区的 110 出 警线路的优化选择 关键词 关键词 路径优化算法 层次分析法 Dijkstra 算法 A 启发式算法 Abstract II Abstract With the development and progress of our society 110 service platform has become an indispensable security to people s life safety On the one hand it means the public security system of out country has made a tremendous progress On the other hand it means the responsibility of the public security system bearing becomes more and more important So how to improve the work efficiency of 110 Police Platform and shorten the time consuming of police vehicles becomes the important part of building 110 platform in future Based on the above considerations this thesis designs and achieves the optimal path optimization module and set the stage for building the information system for 110 to go to patrol on basis of urban road network of Weifang in Shandong province It will increase the efficiency of the 110 police system In order to improve the work efficiency of 110 Police Platform this thesis researches the arithmetic path optimization of 110 to go to patrol in the city proper At first the thesis researches into the road network model divides map data into two types which are node and section according to the principle of cartography and graph theory and summarizes the principles and characteristics of storage structures which leads to store map vector data by adjacency matrix Second from a more practical point of view it researches into how to set road resistance and sets the weights of road resistance initially by use of AHP which brings various aspects influencing road smoothness into optimization model Then the most important part of this thesis is the research of path optimization It introduces classifications and characteristics of every kind of path searching firstly and focus on the discussion of principles and implementation steps of Dijkstra and A heuristic algorithm then analyzes own characteristics of two algorithms At the end we achieve those two algorithms as path optimization Finally we make use of MapBasic secondary development language to program the algorithms set data in road network of Weifang on MapInfo and achieve the optimization of the line for 110 to go to patrol in the city proper of Weifang Abstract III Ketwords Path optimization algorithm Analytic Hierarchy Process AHP Dijkstra algorithm A heuristic algorithm 目录 IV 目录 第一章第一章 引言引言 1 1 1 研究背景及意义 1 1 1 1 研究背景 1 1 1 2 国内外研究现状 2 1 1 3 研究意义 6 1 2 论文的主要工作 7 1 3 论文的章节安排 7 第二章第二章 城市道路信息的储存城市道路信息的储存 9 2 1 引言 9 2 2 地图的存储方法 9 2 3 道路信息的存储 11 2 4 本章小结 13 第三章第三章 城市道路阻抗权重的确定城市道路阻抗权重的确定 14 3 1 引言 14 3 2 道路阻抗值 15 3 3 层次分析法 17 3 3 1 层次分析法的基本原理 18 3 3 2 层次分析法的基本步骤 18 3 4 层次分析法在阻值设置上的应用 25 3 5 本章小结 27 第四章第四章 110 出警线路优化算法出警线路优化算法 28 4 1 引言 28 4 2 最短路径算法 28 目录 V 4 3 DIJKSTRA算法 31 4 4 A 算法 33 4 5 本章小结 38 第五章第五章 110 出警路径最优化算法的实现出警路径最优化算法的实现 40 5 1 引言 40 5 2 地图数字化 40 5 2 1 数字化平台 41 5 2 2 路网信息的提取 42 5 3 算法实例研究 47 5 3 1 Dijkstra 算法 47 5 3 2 A 算法 50 5 3 2 结果分析 52 5 4 本章小结 53 第六章第六章 总结和展望总结和展望 54 致谢致谢 56 参考文献参考文献 57 1 第一章 引言 1 1 研究背景及意义 1 1 1 研究背景 社会治安状况关系到每个公民的生命和财产安全 建设高效率的公安系统 是关系到人民能否安居乐业的重要问题 20 世纪 80 年代以来 部分地方公 安机关根据社会治安形势发展的需要 建立了110 报警服务平台 满足广大 人民群众在危急情况下的求助需要 并且不断提高公安系统处理紧急事件的的 反应能力 扩大了服务范围和服务质量 1987 年以后公安部要求全国各地公 安系统普遍的建立 110 服务平台 自此 110 报警服务平台的发展步入了正轨 2006 年 110 报警服务平台共出警 511 万人次 平均每分钟出警 10 次 各类案 件的侦破率也相应得到提高 由此可见 110 报警服务平台正发挥着越来越重要的 作用 1 当 110 指挥中心接到群众报警后 部署警力能够在尽可能短的时间内 到达现场 不仅可以更大概率的捕获疑犯 控制现场秩序 还能尽早的控制现 场获取第一手现场资料 因而 110 系统的反应速度在一定程度上决定了公安 机关破获案件的成功率 因此如何使110 出警系统自动最优化出警路线显得 格外重要 提高出警效率 缩短出警车辆的路程耗时 应当利用现代运筹学和 信息管理科学进行最优规划设计 通过将城市地理信息数字化 借助最优路径 模型的测算进行通行道路的选择 随着信息化的普及和发展 为了适应公安现 代化建设的需要 应当充分利用先进的通讯手段和计算机网络技术并结合各种 科学发展的高新技术成果为公安系统服务 未来信息化 智能化的110 最优 化调度系统将必然成为今后的发展趋势 110 出警线路优化系统是应用地理信息技术提高城市治安工作水平和能力的 主要组成部分 具体来说 它就是在计算机软件和硬件的支持下 运用系统论 信息论的理论和方法 结合计算机科学 计算机图形学 城市地理学 数据库技 术 现代通讯技术 网络技术和 GIS 技术产生的具有科学管理和综合分析功能的 软件系统 110 出警线路优化系统针对于城市公安部门的工作需要具有城市路网 的空间内涵 同时具有集成化的优化分析功能 实现最优的调配 它能够提供业 2 务上的数据处理 统计 指挥调度以及实时处理 控制显示等功能 提高 110 公 安部门的指挥决策水平和整体作业能力及反应速度 1 1 2 国内外研究现状 1 1 2 1 城市公安 GIS 发展现状 城市公安 GIS Geographic Information System 地理信息系统 是城市 应急联动系统中非常重要的组成部分 城市应急联动系统是保障城市公共安全 的综合救援体系及集成技术平台 是集通信 计算机 网络 地理信息 全球 定位 图形图像 视频监控 数据库与信息处理等多种技术为一体的通信 信 息及指挥系统平台 2 3 城市公安 GIS 起源于上世纪 60 年代 原西德研制的 IMPOL 警察信息系统可以算做是最早的公安 GIS 之后到 90 年代 挪威主持开 发的 POS 系统是将 GIS 真正应用于治安管理并取得成功的系统 4 我国公安 GIS 的发展和应用始于 1990 年 其主要目的是提高公安系统的执行效率 公安部研 究开发的服务于警用业务的指挥调度系统 首先在各省会城市和开封 深圳等试 点城市进行试运行 这是我国首次把 GIS 技术应用于城市治安管理系统 受当时 的数据和技术条件的限制 该系统仅仅在少数几个试点城市应用 但是从此之后 其它各城市便开始研制和开发各自的治安管理系统 1995 年公安部以郑州 南宁 大连和厦门作为试点城市 建立了以城市公安 GIS 为中心的 110 接处警系统 4 5 目前类似火灾救援 医疗救护等应急活动 都发展了各自的信息化调度系统 其 核心思想也是路径优化的算法 随着各种应急体系的不断完善 各种应急体系也 不断的相互融合 逐步形成了城市统一的应急联动系统 城市应急联动系统一般包括城市生活中各种紧急事件的应急服务 例如 110 报警服务台 火警 急救 交警 消费者投诉电话 法律援助电话等指挥 平台 这样通过将各个社会保障部门的信息进行集成能够使各个部门共享各种 资源 实现跨部门 跨地区的统一指挥协调 对于提高各部门对突发事件的反 应能力提供了必要的条件 6 从我国城市应急联动系统的发展上来讲 我国在 应急救援工作上的研究刚刚起步 目前已建成或即将建成的城市应急联动系统 可 24 小时受理市民的各种报警与求助电话 系统可对现场的公安 交警 消 防和救护资源进行指挥控制 从国内的目前应急联动实践情况来看 应急联动 系统建设的基本技术已经基本满足需求 但在关键技术上还有待于进一步的创 新 6 本文所研究的公安最优路径系统属于交通路网的交通事故应急救援系统 3 的一个部分 交通路网优化研究是该系统的主要内容之一 1 1 2 2 路径规划算法发展现状 最短路径问题是路线设计及分析等优化问题的基础 其算法是交通网络分析 的核心 最短路径问题也一直是运筹学 交通工程学 计算机科学 地理信息学 等学科的一个研究热点 国内外众多专家学者对该领域进行了深入研究 7 经典 的图论与不断发展完善的计算机数据结构算法的有效结合使得新的最短路径算法 不断涌现 各具特色 所谓的路径规划算法 是利用地图数据 搜索从起点到终 点的最优路径的算法 当具体应用在不同的方面时有许多不同的算法和实现 常 用的静态路径规划算法包括 Dijkstra 算法 Bellman Ford Moore 算法 Floyd 算 法 盲目搜索和 A 启发式算法等 在经典 VRP Vehicle Routing Problem 车 辆路径问题 的基础上 车辆路径问题在学术研究和实际应用上产生了许多不同 的延伸和变化形态 5 110 出警线路优化信息系统中的最优路径规划问题就是搜索网络中两点之间 通行能力最强的路径 其核心是最短路径算法问题 最短路径是运筹学 图论等 应用数学领域中一个基本概念 关于它的算法研究己得到相关领域学者的长期关 注 并已有许多的研究成果 Dijkstra 算法是图论学中求解最短路径问题的经典算法 Dijkstra 算法建立在 抽象的网络模型上 把道路抽象为网络中的边 以边的权值来表示与道路相关的 参数 算法确定了赋权网络中从某点到所有其它节点的具有最小权的路径 Dijkstra 算法在理论上是正确的 但在实际应用中不尽人意 对于最短路径问题 也提出了许多新的算法 为最优路径的选择提供了更多的选择空间 国外的路径规划 多集中在经典的静态路径规划 Eiger 等人证明了当效用函 数是线性的或指数时 Dijkstra 算法可以在静态路网中计算出最短路径 8 9 Hall 等人证明了标准的求最短路径的规划算法 如 Dijkstra 算法 在动态路网中规划 的路径不是最优的 10 Pearl 等人成功采用 A 算法用于路网的路径规划 并分析 了算法的复杂性 对于动态路径规划 11 Wellman 等人提出了一种校正路径规划 算法 适用于地图包含随机的相容条件 12 Miller Hooks 和 Mashmassani 提出了 在离散时间不稳定随机情况下 最小期望代价路径的搜索算法 证明了算法的存 在性 并和其他算法进行了比较 13 14 国内同济大学的晏克非教授采用将路径归 还过程划分成小时间段 每一小时间段内将交通信息看作不变 研究了动态路径 规划算法 4 车辆路径问题是路线优化的一个重要分支 目前其在物流中的应用具有相当 的广泛性并且具有重大的经济价值 早在 1962 年 Balinski 等人首先提出 VRP 的集分割 直接考虑可行解集合 在此基础上进行优化 建立了最简单的 VRP 模型 1974 年 Wren Gillett 等人提出 Sweep 算法 扫描法 1981 年 Christofields 等人提出了度中心树和相关算法 1991 年 Gendrcau 等人将禁忌k 搜索方法应用于 VRP 16 1996 年 J Lawrence 将遗传算法用于 VRP 的研究 并 可有效求解带时间窗的 VRP 鉴于传统的遗传算法是个大范围 粗粒度的寻优算 法 Barnier 将其与约束满足问题 CSP 的技术相结合 通过遗传算法来处理 CSP 参数的子域 从而减小搜索空间 降低 CSP 问题目标函数和遗传算法约束的 复杂度 17 在我国 张丽萍等通过引入新颖交叉算子 构造了一种改进遗传算法 此算 法摆脱了对群体多样性的要求 不存在传统遗传算法常见的早熟收敛问题 可以 有效求得 VRP 的优化解 5 纪寿文等根据深圳市科技园的实际路网图 采用神经 网络的方法对运输车辆优化调度进行了试验研究 6 王正彬等在分析 VRP 现有启 发式算法的基础上 建立了考虑线路安排的物流配送方案模型 并提出了求解该 问题的种搜索算法 18 陈湘州等引入一种进化逆转算子 改进了遗传算法求解 VRP 时的局部搜索能力 19 顾志康等针对染色体中某些需求点编号可能重复出现 的情况 设计新的染色体结构 并通过基因的混合交叉方法进行基因重组 有效 提高了搜索到最优配送路径的概率 20 崔雪丽等基于近些年出现的新型智能优化 思想 人工蚂蚁系统 给出了一种可快速求解 VRP 的蚁群搜索算法 7 章兢等 构造了一种免疫克隆算法来求解 VRP 并在算法中引入了克隆选择 克隆删除 受体编辑 体细胞高频变异 抗体循环补充等思想 21 华中科技大学李宁等人将 粒子群算法运用于车辆路径优化问题 并进行了实验研究 证明了粒子算法在求 解车辆路径问题的有较好的性能 22 党建英等利用蚁群算法进行模糊运算 以寻 求最小成本的最佳车辆路径 23 这些都为 110 出警最优路径的选择提供了更多的 备选工具 1 1 2 3 路径优化的相关技术 研究城市路径优化问题 离不开信息技术的支持 特别是电子地图处理工具 目前 地图处理工具种类繁多 如 MAPGIS ArcGIS MapInfo 等 特别的 MapInfo 软件自带二次开发软件 MapBasic 具有优良的兼容性和匹配性 并接语 言简单 适合普通地信人员使用 5 MAPGIS 是新一代面向网络超大型分布式地理信息系统基础软件平台 系统 采用面向服务的设计思想 多层体系结构 实现了面向空间实体及其关系的数据 组织 高效海量空间数据的存储与索引 大尺度多维动态空间信息数据库 三维 实体建模和分析 具有 TB 级空间数据处理能力 可以支持局域和广域网络环境 下空间数据的分布式计算 支持分布式空间信息分发与共享 网络化空间信息服 务 能够支持海量 分布式的国家空间基础设施建设 ArcGIS 产品线为用户提供一个可伸缩的 全面的 GIS 平台 ArcObjects 包含 了大量的可编程组件 从细粒度的对象 例如 单个的几何对象 到粗粒度的对 象 例如与现有 ArcMap 文档交互的地图对象 涉及面极广 这些对象为开发者 集成了全面的 GIS 功能 每一个使用 ArcObjects 建成的 ArcGIS 产品都为开发者 提供了一个应用开发的容器 包括桌面 GIS ArcGIS Desktop 嵌入式 GIS ArcGIS Engine 以及服务端 GIS ArcGIS Server MapInfo 是美国 MapInfo 公司的桌面地理信息系统软件 是一种数据可视化 信息地图化的桌面解决方案 它依据地图及其应用的概念 采用办公自动化的操 作 集成多种数据库数据 融合计算机地图方法 使用地理数据库技术 加入了 地理信息系统分析功能 形成了极具实用价值的 可以为各行各业所用的大众化 小型软件系统 MapInfo 含义是 Mapping Information 地图 信息 即 地 图对象 属性数据 MapInfo Professional 是一套强大的基于 Windows 平台的地图化解决方案 可 以方便地将数据和地理信息的关系直观的展现 其复杂而详细的数据分析能力可 帮助用户从地理的角度更好地理解各种信息 可以增强报表和数据表现能力 找 出以前无法看到的模式和趋势 创建高质量的地图以便做出高效的决策 凭借其 新特性和增强功能 MapInfo Professional 使得桌面地图化和分析功能更快和更容 易 并可延伸至整个企业 MapInfo Professional 提供一整套功能强大的工具来进行复杂的商业地图化 数据可视化和 GIS 功能 通过 MapInfo Professional 可连接本地及服务器端的数据 库 创建地图和图表以揭示数据行列背后的真正含义 也可以定制 MapInfo Professional 以满足用户的特定需要 支持 Oracle8i 完全读 写 通过 OCI 对 Oracle8i 及通过 ODBC 对其它数据源的实时访问 MapBasic 是 Mapinfo 自带的二次开发语言 它是一种类似 Basic 的解释性语 言 利用 MapBasic 编程生成的 mbx 文件能在 Mapinfo 软件平台上运行 早期的 Mapinfo 二次开发都是基于 MapBasic 进行的 MapBasic 是理想的在 MapInfo 平 6 台上开发用户定制的应用程序的编程语言 通过使用 MapBasic 进行二次开发 能够扩展 MapInfo 功能 实现程序的自动重复操作并使 MapInfo 与其他应用软件 集成 MapBasic 功能强大 用户仅用几行代码即可在应用软件中实现图层叠加 并具备其他地理功能 MapBasic 程序易于与用诸如 Visual Basic C PowerBuilder 和 Delphi 等语言编写的应用软件集成 MapBasic 已经 被世界上数百个第三方厂商认可 MapBasic 是一种功能强大 结构与 Basic 语言相似的语言 无论是熟练的还 是刚入门的程序员 都能使用该语言根据用户的需求开发出功能更加强大的桌面 地图信息系统应用软件包 无论您是希望分销 还是为了您自己使用而设计应用 软件 MapBasic 都是一个不可缺少的工具 MapBasic 具有五个方面的特点 它是一种类 Basic 语言 帮助用户开发 MapInfo 应用软件 支持 OLE Automation 和 DDE 技术使之易于与其他应用软件 相连接 包含嵌入的 SQL 语句以具有更强大的数据查询功能 地理操作和功能帮 助能扩展应用软件的功能 已有上千种使用 MapBasic 开发出的 能够解决商务 问题的应用软件 因此可以利用 MapBasic 进行算法的编程 而不借助于其他运 筹软件的辅助 有利于提高运算的效率 1 1 3 研究意义 随着生活节奏的不断加快 高效率的交通需求促使交通物流技术飞速发展 作为现代经济社会不可或缺的公安保障体系 同样应当吸取现代科学带来的技术 成果 与时俱进 提高效率 110 报警服务平台是与人民生活衔接最为紧密的系 统之一 提高 110 公安系统的工作质量和效率是创建和谐社会的必然要求 随着科学技术的飞速发展 信息化成为时代的主旋律 如何将信息化应用到 社会服务中去 形成生产力的转化 是科学技术变为生产力的关键环节 因此 通过将物流优化技术和信息化技术相结合 形成具有智能化 自动化的 110 出警 线路优化系统 将会对于提高公安系统的工作效率有明显的促进作用 本论文将信息技术 运筹学和地理学等理论知识相结合 应用到 110 公安调 度系统 通过对潍坊市 110 出警现状的调查和分析 研究一套适合城市最优出警 路线的选择方法 并利用地理信息系统专用软件 MapInfo MapBasic 开发出 可以应用于公安调度系统的算法模块 实现出警路线的自动化优化选择 从而达 到提高 110 警务系统的工作效率 更好的满足社会治安工作的需要 7 1 2 论文的主要工作 本论文是从工作中的实际体会和所学专业知识出发 对目前潍坊市公安系 统出警调度系统现状所作的一些尝试和改进 目前我市110 出警控制台还是 由人工进行调度 尽管采用电线杆标识编码进行位置锁定 使目标区域可以及 时确定 但人工调度毕竟无法在最短的时间内实现最优路径选择 因此在警力 出动的选定和最短路线选择等方面上还需要一定的人为主观因素的参与 在信 息化愈加发达的今天 将信息化技术和智能优化算法融入到公安系统的日常工 作 可以最大程度的减少人的工作强度 并且能够得到最优处理结果 基于这 一点 本文对 110 出警线路的优化模块进行了一定的尝试和改进 论文的主要内容包括 4 个方面 一是对路网数学模型进行了研究 路网存储 结构是信息化的基础工作 不同的存储结构对于系统的效率有不同的影响 本文 最终采用邻接矩阵存储地图矢量数据 二是从实际工作的需要出发 探讨道路阻 值的设定 使影响道路的畅通性的各种因素可以反映到优化模型之中 三是路径 优化算法的研究 总体介绍了路径最优搜索算法的基本内容 主要对盲目搜索算 法和启发式搜索算法进行了对比研究 以 Dijkstra 算法和 A 启发式算法作为代表 算法进行了分析 四是以潍坊市的道路网络数据为背景 进行算法实现和案例研 究 基于 MapInfo 和 MapBasic 软件平台进行二次开发 设计并实现了两种算法 在潍坊市城市交通路网环境中的运算 1 3 论文的章节安排 本文通过对现有最优路径搜索算法进行研究 选择适合城市道路条件下 110 出警工作的最优算法 并利用地理信息系统软件平台进行实现 构造城市公安调 度系统的路径优化选择应用模块 从而达到提高 110 出警效率的目的 针对以上 研究目的和研究内容 全文共分为六章 具体如下 第一章引言 阐述论文的研究背景和意义 介绍 110 出警线路优化信息系统 的发展现状及发展趋势 重点介绍了路径规划算法研究现状 第二章城市路网信息的存储 介绍了各种城市路网矢量地图存储的数据结构 最终选取邻接矩阵对城市道路信息进行储存 第三章 110 出警路线中路径规划的权值评定 本文以优化道路网中路径的阻 抗权值为出发点 结合公安工作实际情况的特点 运用层次分析法 Analytic 8 Hierarchy Process 简称 AHP 综合评定道路的阻抗权值 第四章 110 出警路线优化系统的最优路径算法研究 主要研究了盲目搜索和 启发式搜索两种算法的特点 并以 Dijkstra 算法和 A 启发式算法作为代表进行研 究 对二者的优缺点进行了比较 对算法的特点进行了分析 第五章 110 出警路径最优化算法的实现 针对潍坊市的路网环境 基于 MapInfo 和 MapBasic 地理信息系统平台 对第四章中介绍的 Dijkstra 算法和 A 启发式算法分别进行了实现 通过案例研究比较两种算法的区别 从而为 110 出 警线路优化算法的选择提供了依据 第六章总结和展望 对全文进行总结 并提出了有待深入研究的问题 9 第二章 城市道路信息的储存 2 1 引言 道路信息的存储是指将地图上的有用信息转化为存储于计算机内存中的数据 可以为路径算法的程序化提供数据支持 本文所需要的道路信息主要是城市路网 的矢量地图信息 提取城市路网信息是路径规划的前提和基础 本章的研究内容 主要是城市路网的矢量地图在计算机内存中的存储结构 目前图的存储结构主要 有四种分别是邻接矩阵 邻接表 邻接多重表和十字链表 这些存储结构有各自 的应用范围和不同的结构特点 通过比较各种存储结构的不同特点 从而选取适 合所选路径算法的存储结构 使算法的运行效率最高 是进行地图数字化和编制 算法首要工作 在众多有关路网数据结构的研究中 对传统的存储结构进行了进 一步拓展 添加了更为详细的路网结构的描述 例如道路的转向限制信息 动态 变化信息 分层信息等等 使得现代的路径算法能够更加贴近实际的交通情况 考虑到不同的数据存储结构对路径规划算法性能影响是很大的 因此本文从经典 的路网结构中进行选取 使之满足案例研究中要实现的算法功能 本章主要介绍 了各种经典路网存储结构 并结合本文算法实例选取邻接矩阵作为本文算法的地 图存储结构 2 2 地图的存储方法 交通路网在数学和计算机领域中被抽象为图 所以其基础是图的存储表示 进行路径优化算法首先要有数字化的对象 即把城市路网的信息进行数字化并存 储在计算机内存中 供路径规划算法使用 由于矢量地图存储数据量大 地图数 据关系复杂 不同的数据存储结构对路径规划算法性能也有不同的影响 因此如 何选择路径规划算法和相对应的存储结构 使整体的效率最高 也是一个需要解 决的问题 24 利用简洁的数据结构存储道路矢量数据可以方便数据库的维护以及优化算法 的性能 一般的先将道路网络分为线段和点 然后选择适当的存储方式进行编码 存储 网络在数学和计算机领域中被抽象为图 所以其基础是图的存储表示 25 10 计算机图最基本的两个属性是点和边 即点代表道路的交叉路口 边代表道路 根据图的基本表示法 可以将城市道路网表示为 123 123 GN R P Nn n n Rr r r 2 1 其中 G 为网络模型 N 是节点集合 R 是道路的集合 表示某一节点 i n 表示路段 和 为结构体 可以包含更多的节点和路段的属性信息 在节点 i r i n i r 中 可以增加与其关联路段的属性 在路段中 可以增加与其关联的节点信息 道路的权值可以作为道路的内部属性存储 一般而言 无向图可以用邻接矩阵和 邻接多重表来表示 而有向图则可以用邻接表和十字链表表示 其优缺点的比较 见表 2 1 25 表 2 1 几种图的存储结构 名称 实现方 法优点缺点时间复杂度 邻接矩阵 二维数 组 1 容易判断两点间的关 系1 占用空间大O n2 m n Adjacency Matrix2 容易求得顶点的度 邻接表链表1 节省空间 1 不容易判断两点间 的关系 O n m 或 O n m Adjacency List2 容易得到顶点的出度 2 不容易得到顶点的 入度 十字链表链表1 对空间要求较小1 结构复杂见邻接表 Orthogonal List 2 容易求得顶点的出度 和入度 邻接多重表链表1 节省空间1 结构复杂见邻接表 adjacency multilist 2 容易判断两点间的关 系 邻接矩阵是表示顶点之间相邻关系的矩阵 设 G V E 是具有 N 个顶 点的图 则 G 的邻接矩阵可以被表示为 1EG 0EG A i j ij ij 若 v v 是 中的边 若 v v 不是 中的边 2 2 当对网络 G 加上权重时 如相邻两节点的距离数据 那么邻接矩阵可以定义 11 为 EG 0EG ij W A i j ij ij 若 v v 是 中的边 或若 v v 不是 中的边 2 3 在实际应用中可以直接使用二维数组作为网络图的邻接矩阵 并且无向图的 邻接矩阵是对称矩阵 因而可以对规模较大的邻接矩阵进行压缩存储 邻接矩阵 表示法的空间复杂度为 O n2 邻接矩阵是唯一一种可用矩阵表示的数据结构 因此在软件实现中具有较大的优势 在 Dijkstra 算法中较为广泛 是 Dijkstra 算 法的基础存储结构 25 邻接表是一种存储拓扑网络数据的数据结构 它以一种链式存储方法保存网 络数据 与树型结构中的子链表相似 在路网相关算法中应用较为广泛 一般的 将路网的顺序邻接链表与逆向邻接链表称为 Forward 表和 Backward 表 邻接表 中每个表节点均有两个域 一是邻接点域存放与相邻接的顶点的序号 二 i v j vj 是链域 将邻接表的所有表节点链在一起 在节点查询中 邻接表中的查询时间 复杂度仅为 在有向图的建立算法 其时间复杂度为 该存储结 O e n O en 构不存在存储空间的浪费 当路段信息较多时效果较佳 邻接表数据结构是网络 表达中效率较高的一种数据结构 在最短路径算法中已经得到了广泛应用 25 十字链表也是一种链式存储结构 它通常用来描述有向图的结构 它可以 看作是将有向图的邻接表和逆邻接表结合起来得到的一种链表 在十字链表中 对应于有向图中每一条弧都有一个节点 对应于每个定顶点也有一个节点 邻 接多重链表类似于有向图表示法中的十字链表 将无向图中表示同一条边的两 个节点合在一起 将得到无向图的邻接多重表 这两种网络存储方式结构较为 复杂 实现的运算量很大 因此只有在特殊情况下才会使用 26 2 3 道路信息的存储 在对网络拓扑关系的存储研究方面 绝大多数研究采用了邻接矩阵或者邻接 表等存储方式 如果采用邻接链表 可以一定程度上降低网络拓扑数据的复杂度 但是在路径寻优算法中会增加程序的设计难度 邻接矩阵方法最为直观 虽然其 空间复杂程度较高 但是可以利用矩阵结构进行网络的存储 因而该结构的算法 适宜度高 可以应用到多种算法之中 根据图的定义可知 图的逻辑结构可以分为两部分 V 和 E 的集合 因此 12 用一个一维数组存放图中所有顶点数据 用一个二维数组存放顶点间关系 边或 弧 的数据 称这个二维数组为邻接矩阵 邻接矩阵又分为有向图邻接矩阵和无 向图邻接矩阵 邻接矩阵的定义还可以继续加以扩展 可以包括点的邻接 边的 邻接以及区域的邻接 具体思想是 首先提取路网中的所有节点 并在图层上创 建点对象 对每个点进行编号 然后将矩阵的行和列分别定义为地图点对象中的 编号 若两个点之间存在邻接关系 则在对应的行列交叉处标号为 1 若不邻接 则标号 0 有向图中则对应于将可到达标为 1 不可到达标记为 0 例如图 2 1 中 无向图 G5和有向图 G6的邻接矩阵可以分别表示为 Al和 A2 图 2 1 邻接矩阵的的示例 邻接矩阵有如下特点 1 在简单应用中 可直接用二维数组作为图的邻接矩阵 顶点表及顶点 数等均可省略 2 当邻接矩阵中的元素仅表示相应的边是否存在时 矩阵值可定义为值 为 0 和 1 的枚举类型 1 代表相邻 0 代表不相邻 3 无向图的邻接矩阵是对称矩阵 对规模特大的邻接矩阵可压缩存储 4 邻接矩阵表示法的空间复杂度为 27 2 S nO n 在实际操作中 邻接矩阵还可以添加其他的相关信息 例如当采用点的邻接 矩阵作为路网存储结构时 可以将邻接关系 1 用距离关系来代替 如与相邻 i V j V 接 可以将与之间的距离值作为矩阵中与行列点的数值 如此在路径优 i V j V i V j V 化算法中可以直接获得路网中各个弧边的距离信息 方便算法的计算 采用邻接 13 矩阵方法来存储网络拓扑数据 虽然可以直接完成两个顶点是否存在一条网络边 的查询 但对最短路径算法最关键的关联节点查询 其复杂度均为 此外 O n 采用邻接矩阵存储网络拓扑数据的空间复杂度为 但由于邻接矩阵具有较 2 O n 好的直观性的普适性 因而在最短路径算法中得到了广泛应用 27 28 在本文 110 出警线路最优路径搜索问题中 一般采用点对点的数据结构更加 合适 因为在目前的警务数据系统中 通过电线杆标记法已经可以确切的知道路 网中的点位置 考虑到本文主要研究的是两种经典路径最短算法 并且所采用的 是基于 MapInfo 和 MapBasic 的开发环境 该环境对于数据结构复杂度的支持相 对较弱 因而采用邻接矩阵结构的存储形式 一方面邻接矩阵可以清晰地表达网 络的拓扑结构 另一方面更加便于 Dijkstra 算法和 A 启发式算法的实现 2 4 本章小结 本章首先介绍了图形学的基本理论 根据路网图形理论介绍了 4 种路网存储 结构的相关内容 并比较了邻接矩阵 邻接表 邻接多重表和十字链表等存储结 构的特点和适用范围 通过比较发现 邻接矩阵存储结构更加清晰 存储复杂度 对系统软件的需求更低 可操作性强 普适性好 适合于不复杂情形下的编程实 现 综合考虑本文采用的研究算法和软件平台的特点 最终选择邻接矩阵作为本 文研究对象的基础数据结构 14 第三章 城市道路阻抗权重的确定 3 1 引言 110 公安报警服务平台已经成为城市居民生活中必不可少的保障因素 基本 上所有的急发事故都会涉及到 110 工作的范畴 因而公安部门在接到报警电话后 如何及时将警力派往现场是治安工作效率的首要体现 其中减少道路中的时间消 耗是提高工作效率的关键 这就涉及到最短路径选取问题 在选择出警车辆从起 点到终点的最优路径时 所依据的原则是路径的交通阻抗最小 即时间最短原则 而阻抗是受多种路网交通因素影响的 选取阻抗作为度量的主要考虑是 110 出 警状况与普通的物流需求不同 减少时间的消耗是 110 出警的首要目标 交通阻 抗衡量的主要因素是交通时间 它受到交通路网多方面条件的制约 例如道路距 离长度 道路畅通性 车流量的密集度以及路况条件等 因而可以通过对不同路 段情况进行因素分析 通过综合评价给与不同道路的阻抗系数 将阻抗系数反映 到路网信息上 就可以体现时间最优原则的要求 由于不同车辆不同时间段 车辆在道路上的通行时间是有差异的 因而在对 最优路径算法的实践中往往通过分析路径的阻抗权值来决定 因此如何确定阻抗 权值 使权值的设置符合城市路网的系统状况 是进行地图数字化的重要基础工 作 权值设定的科学与否 将会直接影响算法的适用性和优化结果 进行阻抗权 值的设置首先要对城市路网中影响车辆通行的各种因素建立指标体系 该体系要 求能够基本包括实际工作中能够影响出警时间的影响变量 因为在实际城市交通 网络中 道路长度最短的路径不一定是耗时最短的 特别是 110 警力在到达出险 现场的过程中 需要考虑的影响因素更多 如车流量 车道数 是否有施工 行 人密度 障碍物 时间段 路面状况等等 这些因素中往往无法进行定量的描述 带有很大的模糊性 用传统的方法很难进行合理的加权 因此本文考虑利用 AHP 层次分析法对各个要素进行加权处理 将最后加权的结果作为阻抗的权值 道路 阻抗权值在理想的情况下应以实际的行程时间作为路段的路阻 但考虑到时间的 不确定性以及实验数据的原因 可以用 AHP 法求得的加权系数来表示动态交通 信息 即将路段的加权长度等于路段的实际长度与加权系数的乘积 通过加权系 数的不同 能够有效的体现阻抗值的变化 例如原本很短的道路由于道路条件较 15 差 最终加权长度将大于实际距离较长但路况较好的道路 这样就可以体现时间 最优的原则 本章首先介绍了道路阻抗的定义 及其影响因素 并利用 AHP 法 提出了基于 AHP 法的道路权值结构模型 对道路阻抗权值进行综合评定 3 2 道路阻抗值 110 控制台接到报警后 从安排出警到抵达案发地点往往时间紧迫 稍有延 误后果可能是非常严重的 为了将损失降低到最低程度 公安部门需要解决的问 题是如何迅速调动警力赶赴案发现场 这就涉及到路径选取的目标取向问题 对 110 出警线路最优化的计算 是受路网交通状况影响的路径选择过程 路线选择 的依据不同 则结果也不会相同 在 110 出警路线的研究中更多是使用时间最短 原则 为了更加方便最优路径运算的需要 在这里引入阻抗的概念 阻抗是借用 物理学中的概念 主要以交通时间作为度量单位 表示在行程上所占用的时间 这样 在 110 出警优化计算中对最优路径的取舍标准可以通过计算路径的阻抗值 来决定 考虑到运算的需要 可以将阻抗进行等价的变换分析 利用道路通达性 来表示阻抗的大小 因而首先要对路况进行权值的设定 该权值指代根据最优路 径选取原则设置的各种参数的加权值 要使权值的设置更符合实际的需要 必 须全面考虑交通环境对公安出警的不同影响 采用科学的评价体系进行加权综合 在城市交通网络中 道路长度最短的路径不一定是耗时最短的 28 31 如何设定最 优路径阻抗权值的评价指标体系也是设计权值的重要前提 影响 110 出警时间的 因素很多 如道路通达性 道路车道数 道路拥挤度 不同时段流量 路况等等 从公安出警的实际特点出发 需要总结各种道路情况对出警效率的影响 得 出在最短的时间内对各种出警状况的有效的方案 在时间寻优算法中 道路阻抗 权值可以按道路通行时间作为路段的路阻 即道路通达性的时间描述 但往往实 际情况中时间度量不好把握 考虑本文主要是进行算法研究 以及所采用数据 因素的限制 本文通过阻抗权值的加权系数来反映道路网络的通达性信息 设定 路段的阻值等于路段的实际长度与加权系数的乘积 因而 可以理解 当路网中 某一地段发生交通堵塞时 反映在系统中该路段的通达性会降低 根据评价体系 得到的加权系数会变大 进而导致道路加权长度变长 即加权系数的增加 相应 的会导致加权长度的增加 例如道路拥堵情况越严重 则相应的路线阻值就应当 提高 对应于系统中就可以对路线长度设有一定的加成系数 反之则越小 通过 16 采用路段长度的加权系数可以达到与阻抗值描述道路堵塞情况的效果达到一致 随着信息技术的不断发展 道路实时监控也逐渐达到普及 从技术上来说 已经 达到可以根据实时路况的信息对不同路段的拥挤度进行动态的跟踪 从而根据车 辆接受的交通路况信息来动态的确定加权系数的大小 在设置加权系数时 可以 认为设定系数的上下限的范围 例如发生相对堵塞的路段可以将其加权系数设为 9 畅通路段的加权系数设为 1 根据实际情况进行设置 由于修路或其他原因 导致路段无法通行的 则设置其权值为无穷大 其他情况可以根据交通主管部门 观测到的实时路况的平均车速将路段的加权系数设为 1 和 9 之间的某个值 权值 确定后 把路段长度乘以加权系数即可得到时间最短原则下的道路加权距离 31 从目前算法研究的发展现状来看 在大多数的的算法研究中 往往仅根据根据道 路的长度作为最优路径的选取依据 虽然这种假定在算法研究中没有负面影响 但是在现实情况中往往与实际不符 从网络分析的原则和目的出发 最短路优化 就是在网络中的起点和终点之间找一条阻碍强度最小的通行路径 阻碍强度不仅 仅指一般意义上的距离最短 还可以引申到其它的度量 如时间 费用 线路容 量等 根据实际情况的不同 选取的标准也不尽相同 例如在各种城市应急系统 如 110 匪警 119 火警以及 120 医疗急救系统 等问题上 时间的因素是最重 要的 而 GIS 的汽车导航系统中的网络分析功能往往是根据距离较短以便达到运 费较少的原则来设计的 32 由于影响出警车辆到达时间的因素很多 实际长度最 短的路径不一定耗时最短 仅考虑道路长度得出的优化结果往往与真实情况差异 很大 因而有关研究文献中将车流量 车道数 道路等级 路面状况 时间段等 因素都纳入到道路网的信息中 通过对各种因素进行加权评价 得到路段阻值权 值 进而修正路网中路段的加权长度 在分析各种因素的权值之前 首先应该明 确系统优化的最终目标 即 110 出警最优路径规划的指向是距离最优还是时间最 优 在本文