行人过斑马线被撞, 交通事故 如何调解，急等。_百度知道
行人过斑马线被撞, 交通事故 如何调解，急等。
当场脑袋没了直接死亡，现在交警要求尸首要先火化，否则不做调解，这样合理吗？正常要走什么程序，大概可以要求赔多少钱？谢谢行人过马路，被汽车撞飞出斑马线2米多
我有更好的答案
解不调解同火化尸体没有关系，同死者是什么人，所从事的职业有关。但国家有最低赔尝标准。只要司机承认人是他撞死的就可以了。至于赔多少钱
被扶养人无劳动能力又无其他生活来源的，计算二十年。但六十周岁以上的，按照受诉法院所在地上一年度城镇居民人均消费性支出和农村居民人均年生活消费支出标准计算。被扶养人为未成年人的，不知道你是哪里的，事故发生在哪里，无法为您估计数额。具体数额根据死者的户口（注意虽然死者是农村户口。重大事故、专业问题、死亡赔偿金按照受诉法院所在地上一年度城镇居民人均可支配收入或者农村居民人均纯收入标准，按二十年计算，只能告诉您大概原则。被扶养人还有其他扶养人的，赔偿义务人只赔偿受害人依法应当负担的部分，被抚养人的人数。被扶养人有数人的，年赔偿总额累计不超过上一年度城镇居民人均消费性支出额或者农村居民人均年生活消费支出额、精神损失费以及受害人亲属办理丧葬事宜支出的交通费、住宿费和误工损失等其他合理费用。其中；七十五周岁以上的，按五年计算。
被扶养人是指受害人依法应当承担扶养义务的未成年人或者丧失劳动能力又无其他生活来源的成年近亲属，除赔偿抢救期间的相关费用外，年龄每增加一岁减少一年，计算至十八周岁，也可以按照居民标准计算相关费用），当地统计数据。3：1，最好咨询或者委托当地专业律师代理。交通事故造成受害人死亡的、死亡补偿费，还应当赔偿丧葬费、被扶养人生活费（如有死者生前抚养的被抚养人）、本人的情况不同赔偿数额相差悬殊、工作生活的，但是长期在城市居住。但六十周岁以上的，年龄每增加一岁减少一年；七十五周岁以上的、丧葬费按照受诉法院所在地上一年度职工月平均工资标准，按五年计算，以六个月总额计算。2、被扶养人生活费根据扶养人丧失劳动能力程度法律上调节和火化没有直接的关系,和赔偿也没关系.各地
一、调解不调解同火化尸体没有关系，二、至于赔多少钱，首先要有交警的责任认定书，比如斑马线两边没有红绿灯的情况下，按交通法车应该让行人，车就可能全责。如果行人闯红绿灯，车就有可能不负责。所以你要收集好无相关厉害关系人提供的证据，或申请交警调取路口的录象或其他方式调查取证，总之公了要交警出具责任认定书，然后按标准赔付，交警不给责任认定书，你就找这个交警部门复议或它的上级部门复议
各地、本人的情况不同赔偿数额相差悬殊，不知道你是哪里的，事故发生在哪里，无法为您估计数额，只能告诉您大概原则。重大事故、专业问题，最好咨询或者委托当地专业律师代理。交通事故造成受害人死亡的，除赔偿抢救期间的相关费用外，还应当赔偿丧葬费、被扶养人生活费（如有死者生前抚养的被抚养人）、死亡补偿费、精神损失费以及受害人亲属办理丧葬事宜支出的交通费、住宿费和误工损失等其他合理费用。其中：1、丧葬费按照受诉法院所在地上一年度职工月平均工资标准，以六个月总额计算。2、被扶养人生活费根据扶养人丧失劳动能力程度，按照受诉法院所在地上一年度城镇居民人均消费性支出和农村居民人均年生活消费支出标准计算。被扶养人为未成年人的，计算至十八周岁；被扶养人无劳动能力又无其他生活来源的，计算二十年。但六十周岁以上的，年龄每增加一岁减少一年；七十五周岁以上的，按五年计算。
被扶养人是指受害人依法应当承担扶养义务的未成年人或者丧失劳动能力又无其他生活来源的成年近亲属。被扶养人还有其他扶养人的，赔偿义务人只赔偿受害人依法应当负担的部分。被扶养人有数人的，年赔偿总额累计不超过上一年度城镇居民人均消费性支出额或者农村居民人均年生活消费支出额。3、死亡赔偿金按照受诉法院所在地上一年度城镇居民人均可支配收入或者农村居民人均纯收入标准，按二十年计算。但六十周岁以上的，年龄每增加一岁减少一年；七十五周岁以上的，按五年计算。具体数额根据死者的户口（注意虽然死者是农村户口，但是长期在城市居住、工作生活的，也可以按照居民标准计算相关费用），当地统计数据，被抚养人的人数、年龄，当地生活水平等综合计算，计算出的总数在对方车辆交强险限额内的由保险公司全额赔偿，超过的部分按照事故责任比例赔偿.
三、或者你先试一下和对方协商，就是所谓的私了，他要给得起钱，你也没必要去麻烦交警了
为您推荐：
其他类似问题
您可能关注的内容
交通事故的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。座椅靠背怎么调节倾斜度_百度知道
座椅靠背怎么调节倾斜度
我有更好的答案
座椅太靠前或靠后都是不正确的，座椅太靠前四肢活动空间会减少，只是先确定靠背斜角度，会更方便调整座椅前后的合适距离。　　第三步：调整座椅前后除特殊身高的人群之外。　　第二步、增加跟车距离，夜间行车时，视线不良。配合方向盘的调整可以最终确定舒适1。在这种情况下，为避免危险，要注意适当增加跟车距离，以防止前后车相碰撞事故。3、尽量避免夜间超车，必须超车时，一般比较容易高速行车，因而很可能发生交通事故。在驶经弯道、坡路，调整的原则是手握九点位置时。4、桥梁、窄路和不易看清的地方更应降低车速并随时做好控制动或停车的准备，手臂能保持舒适的弯曲角度，这个角度一般在90-120度之间，腿膝关节依然呈自然的微微弯曲状态。整个过程可以顺便将方向盘调整到适合自己的高度：调整座椅靠背日常驾驶我们的座椅靠背倾斜角度100-110度、严格控制车速，这是保证夜间行车安全的根本措施。由于夜间道路上的交通量小。调整小常识，行人和自行车的干扰页比较少，当靠背倾角超过110度后椎间盘压力会显著减少，对于没有腰靠调整的车辆而言这是一个重要的参考数据，再进行超车第一步：调整座椅的高低合适的高度是获得良好驾驶视野的前提，应事先连续变换远、近光灯告知前车，在确定前车让路允许超越后，座椅调整时通常要将高度调整作为第一步，调整时需要保证头部与车顶至少留有一拳左右的距离，以免车辆颠簸时头部撞击到车顶、注意克服驾驶疲劳。夜间行车特别是午夜以后行车最容易疲劳瞌睡，常遇危险、紧急情况时，所以必须准备随时停车。2：确保右脚全力踩下刹车后。调整完高度后很多车主习惯先调整座椅的前后，再调整靠背，原则上这没有太大问题
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。君，已阅读到文档的结尾了呢~~
城市轨道交通客流密集度指数及其应用,城市轨道交通客流分析,城市轨道交通客流预测,重庆轨道交通客流量,轨道交通客流预测,上海轨道交通客流量,轨道交通客流分析方法,城市轨道交通客流组织,轨道交通客流分析,城市轨道交通客流
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
城市轨道交通客流密集度指数及其应用
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口当前位置： >>
毕业论文--110出警线路优化系统的设计与实现
摘要摘要随着社会的不断发展进步， 110 报警服务平台已经成为人民生活不可或缺的重 要安全保障。这一方面说明我国公安系统建设取得了巨大的进步；另一方面也意 味着公安系统承载的责任也愈加重大。如何进一步提高 110 出警平台的工作效率， 缩短出警车辆的时间消耗成为今后 110 警务平台建设的重要内容。基于上述考虑， 本文以山东省潍坊市的城市道路网络为基础设计并实现了最优路径优化模块，为 110 出警信息系统的构建提供基础，以达到提高 110 出警系统出警效率的目的。 为了提高 110 公安系统的出警效率， 本文对城市环境下的 110 出警路径优化算 法进行了研究。论文首先对路网数学模型进行了研究，根据地图学和图论的有关 原理，将地图数据划分为节点和路段两种类型，分析总结了各种存储结构的原理 和特点，最终采用邻接矩阵存储地图矢量数据。然后，论文从更加实际的角度出 发，探讨道路阻值的设定，采用 AHP 层次分析法对道路阻值权重进行初步的比较 设定，使影响道路畅通性的各种因素可以纳入优化模型。论文的关键部分是路径 优化算法的研究，首先介绍各种路径寻优算法的分类和特点，重点讨论了 Dijkstra 算法和 A* 启发式算法的原理和实现步骤，分析了两种算法各自的特点，并将 Dijkstra 算法和 A*启发式算法作为本案例的路径优化算法进行实现。最后以潍坊 市的道路网络作为数据背景进行编程实现，选取 MAPINFO 软件作为地图平台， 采用 MapBasic 二次开发语言进行算法编程，最终实现了潍坊城区的 110 出警线路 的优化选择。关键词：路径优化算法，层次分析法，Dijkstra 算法，A*启发式算法IAbstractAbstractWith 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.IIAbstractKetwords: Path optimization algorithm, Analytic Hierarchy Process(AHP), Dijkstraalgorithm, A* heuristic algorithmIII目录目录第一章 引言 .................................................................................................................... 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 最短路径算法 ....................................................................................................... 28IV目录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 参考文献 ........................................................................................................................ 57V
第一章 引言1.1 研究背景及意义 1.1.1 研究背景社会治安状况关系到每个公民的生命和财产安全，建设高效率的公安系 统是关系到人民能否安居乐业的重要问题。 20 世纪 80 年代以来，部分地方 公安机关根据社会治安形势发展的需要，建立了 110 报警服务平台，满足广 大人民群众在危急情况下的求助需要，并且不断提高公安系统处理紧急事件 的的反应能力，扩大了服务范围和服务质量。 1987 年以后公安部要求全国各 地公安系统普遍的建立 110 服务平台，自此 110 报警服务平台的发展步入了 正轨。2006 年，110 报警服务平台共出警 511 万人次，平均每分钟出警 10 次，各 类案件的侦破率也相应得到提高，由此可见 110 报警服务平台正发挥着越来越重 要的作用[1]。当 110 指挥中心接到群众报警后，部署警力能够在尽可能短的时 间内到达现场，不仅可以更大概率的捕获疑犯，控制现场秩序，还能尽 早的 控制现场获取第一手现场资料。因而 110 系统的反应速度在一定程度上决定 了公安机关破获案件的成功率，因此如何使 110 出警系统自动最优化出警路 线显得格外重要。提高出警效率，缩短出警车辆的路程耗时，应当利用现代 运筹学和信息管理科学进行最优规划设计，通过将城市地理信息数字化，借 助最优路径模型的测算进行通行道路的选择。随着信息化的普及和发展，为 了适应公安现代化建设的需要，应当充分利用先进的通讯手段和计算机网络 技术并结合各种科学发展的高新技术成果为公安系统服务。未来信息化、智 能化的 110 最优化调度系统将必然成为今后的发展趋势。 110 出警线路优化系统是应用地理信息技术提高城市治安工作水平和能力的 主要组成部分。具体来说，它就是在计算机软件和硬件的支持下，运用系统论、 信息论的理论和方法，结合计算机科学、计算机图形学、城市地理学、数据库技 术、现代通讯技术、网络技术和 GIS 技术产生的具有科学管理和综合分析功能的 软件系统。 110 出警线路优化系统针对于城市公安部门的工作需要具有城市路网的 空间内涵，同时具有集成化的优化分析功能，实现最优的调配。它能够提供业务1上的数据处理、统计、指挥调度以及实时处理、控制显示等功能，提高 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] 。本文所研究的公安最优路径系统属于交通路网的交通事故2应急救援系统的一个部分，交通路网优化研究是该系统的主要内容之一。 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]。国内同济大学的晏克非教授采用将路径归还过程划 分成小时间段，每一小时间段内将交通信息看作不变，研究了动态路径规划算法。 车辆路径问题是路线优化的一个重要分支， 目前其在物流中的应用具有相当的3广泛性并且具有重大的经济价值。早在 1962 年，Balinski 等人首先提出 VRP 的集 分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的 VRP 模型。 1974 年，Wren Gillett 等人提出 Sweep 算法（扫描法） 。1981 年，Christofields 等人 提出了 k 度中心树和相关算法。 1991 年， Gendrcau 等人将禁忌搜索方法应用于 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，具有优良的兼容性和匹配性，并接语言简单， 适合普通地信人员使用。 MAPGIS 是新一代面向网络超大型分布式地理信息系统基础软件平台。系统 采用面向服务的设计思想、多层体系结构，实现了面向空间实体及其关系的数据4组织、高效海量空间数据的存储与索引、大尺度多维动态空间信息数据库、三维 实体建模和分析，具有 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 平台 上开发用户定制的应用程序的编程语言。通过使用 MapBasic 进行二次开发，能够 扩展 MapInfo 功能，实现程序的自动重复操作并使 MapInfo 与其他应用软件集成。5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 警务系统的工作效率，更好的满足社会治安工作的需要。61.2 论文的主要工作本论文是从工作中的实际体会和所学专业知识出发，对目前潍坊市公安 系统出警调度系统现状所作的一些尝试和改进。目前我市 110 出警控制台还 是由人工进行调度，尽管采用电线杆标识编码进行位置锁定，使目标区域可 以及时确定，但人工调度毕竟无法在最短的时间内实现最优路径选择，因此 在警力出动的选定和最短路线选择等方面上还需要一定的人为主观因素的参 与。在信息化愈加发达的今天，将信息化技术和智能优化算法融入到公安系 统的日常工作，可以最大程度的减少人的工作强度，并且能够得到最优处理 结果。基于这一点，本文对 110 出警线路的优化模块进行了一定的尝试和改 进。 论文的主要内容包括 4 个方面。一是对路网数学模型进行了研究，路网存储 结构是信息化的基础工作，不同的存储结构对于系统的效率有不同的影响，本文 最终采用邻接矩阵存储地图矢量数据；二是从实际工作的需要出发，探讨道路阻 值的设定，使影响道路的畅通性的各种因素可以反映到优化模型之中；三是路径 优化算法的研究，总体介绍了路径最优搜索算法的基本内容，主要对盲目搜索算 法和启发式搜索算法进行了对比研究，以 Dijkstra 算法和 A*启发式算法作为代表 算法进行了分析；四是以潍坊市的道路网络数据为背景，进行算法实现和案例研 究，基于 MapInfo 和 MapBasic 软件平台进行二次开发，设计并实现了两种算法在 潍坊市城市交通路网环境中的运算。1.3 论文的章节安排本文通过对现有最优路径搜索算法进行研究，选择适合城市道路条件下 110 出警工作的最优算法，并利用地理信息系统软件平台进行实现，构造城市公安调 度系统的路径优化选择应用模块，从而达到提高 110 出警效率的目的。针对以上 研究目的和研究内容，全文共分为六章，具体如下： 第一章引言。阐述论文的研究背景和意义，介绍 110 出警线路优化信息系统 的发展现状及发展趋势，重点介绍了路径规划算法研究现状。 第二章城市路网信息的存储。介绍了各种城市路网矢量地图存储的数据结构， 最终选取邻接矩阵对城市道路信息进行储存。 第三章 110 出警路线中路径规划的权值评定。本文以优化道路网中路径的阻7抗权值为出发点，结合公安工作实际情况的特点，运用层次分析法（ Analytic Hierarchy Process，简称 AHP）综合评定道路的阻抗权值。 第四章 110 出警路线优化系统的最优路径算法研究。主要研究了盲目搜索和 启发式搜索两种算法的特点，并以 Dijkstra 算法和 A*启发式算法作为代表进行研 究，对二者的优缺点进行了比较，对算法的特点进行了分析。 第五章 110 出警路径最优化算法的实现。 针对潍坊市的路网环境， 基于 MapInfo 和 MapBasic 地理信息系统平台， 对第四章中介绍的 Dijkstra 算法和 A*启发式算法 分别进行了实现，通过案例研究比较两种算法的区别，从而为 110 出警线路优化 算法的选择提供了依据。 第六章总结和展望。对全文进行总结，并提出了有待深入研究的问题。8第二章 城市道路信息的储存2.1 引言道路信息的存储是指将地图上的有用信息转化为存储于计算机内存中的数 据，可以为路径算法的程序化提供数据支持。本文所需要的道路信息主要是城市 路网的矢量地图信息，提取城市路网信息是路径规划的前提和基础。本章的研究 内容主要是城市路网的矢量地图在计算机内存中的存储结构。目前图的存储结构 主要有四种分别是邻接矩阵、邻接表、邻接多重表和十字链表。这些存储结构有 各自的应用范围和不同的结构特点。通过比较各种存储结构的不同特点，从而选 取适合所选路径算法的存储结构，使算法的运行效率最高，是进行地图数字化和 编制算法首要工作。在众多有关路网数据结构的研究中，对传统的存储结构进行 了进一步拓展，添加了更为详细的路网结构的描述，例如道路的转向限制信息、 动态变化信息、分层信息等等，使得现代的路径算法能够更加贴近实际的交通情 况。考虑到不同的数据存储结构对路径规划算法性能影响是很大的，因此本文从 经典的路网结构中进行选取，使之满足案例研究中要实现的算法功能。本章主要 介绍了各种经典路网存储结构，并结合本文算法实例选取邻接矩阵作为本文算法 的地图存储结构。2.2 地图的存储方法交通路网在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。 进行路径优化算法首先要有数字化的对象，即把城市路网的信息进行数字化并存 储在计算机内存中，供路径规划算法使用。由于矢量地图存储数据量大，地图数 据关系复杂，不同的数据存储结构对路径规划算法性能也有不同的影响。因此如 何选择路径规划算法和相对应的存储结构，使整体的效率最高，也是一个需要解 决的问题[24]。 利用简洁的数据结构存储道路矢量数据可以方便数据库的维护以及优化算法 的性能。一般的先将道路网络分为线段和点，然后选择适当的存储方式进行编码 存储。网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示[25]。9计算机图最基本的两个属性是点和边。即点代表道路的交叉路口，边代表道路。 根据图的基本表示法，可以将城市道路网表示为： ?G ? ( N , R, P) ? ? ? N ? ?n1 , n2 , n3 ,...? ? ? ? R ? ?r1 , r2 , r3 ,...?（2.1）其中，G 为网络模型，N 是节点集合，R 是道路的集合， ni 表示某一节点， ri 表示路段， ni 和 ri 为结构体，可以包含更多的节点和路段的属性信息，在节点中， 可以增加与其关联路段的属性；在路段中，可以增加与其关联的节点信息。道路 的权值可以作为道路的内部属性存储。一般而言，无向图可以用邻接矩阵和邻接 多重表来表示，而有向图则可以用邻接表和十字链表表示，其优缺点的比较见表 2-1[25]。表 2-1 几种图的存储结构 名称 邻接矩阵 Adjacency Matrix 邻接表 Adjacency List 十字链表 Orthogonal List 邻接多重表 adjacency multilist 实现方 法 二维数 组 优点 1.容易判断两点间的关 系 2.容易求得顶点的度 链表 1.节省空间 2.容易得到顶点的出度 1.对空间要求较小 2.容易求得顶点的出度 和入度 1.节省空间 2.容易判断两点间的关 系 1. 不容易判断两点间 的关系 2. 不容易得到顶点的 入度 1.结构复杂 O(n+m) O(n*m) 或 缺点 1.占用空间大 时间复杂度 O(n2+m*n)链表见邻接表链表1.结构复杂见邻接表邻接矩阵是表示顶点之间相邻关系的矩阵。设 G=（V，E）是具有 N 个顶 点的图，则 G 的邻接矩阵可以被表示为 ?1 ? 若（vi ,vj）是E（G）中的边 ? A ?i, j ? ? ? ? ?0 ? 若（vi ,vj）不是E（G）中的边（2.2）当对网络 G 加上权重时，如相邻两节点的距离数据，那么邻接矩阵可以定义 为10? ?Wij ? 若（vi ,vj）是E（G）中的边 A ?i, j ? ? ? ? ?0或? ? 若（vi ,vj）不是E（G）中的边（2.3）在实际应用中可以直接使用二维数组作为网络图的邻接矩阵，并且无向图的 邻接矩阵是对称矩阵，因而可以对规模较大的邻接矩阵进行压缩存储，邻接矩阵 表示法的空间复杂度为 O(n2)。邻接矩阵是唯一一种可用矩阵表示的数据结构，因 此在软件实现中具有较大的优势，在 Dijkstra 算法中较为广泛，是 Dijkstra 算法的 基础存储结构[25]。 邻接表是一种存储拓扑网络数据的数据结构，它以一种链式存储方法保存网 络数据，与树型结构中的子链表相似，在路网相关算法中应用较为广泛。一般的， 将路网的顺序邻接链表与逆向邻接链表称为 Forward 表和 Backward 表。邻接表中 每个表节点均有两个域：一是邻接点域存放与 vi 相邻接的顶点 v j 的序号 j 。二是链 域。将邻接表的所有表节点链在一起。在节点查询中，邻接表中的查询时间复杂 度仅为 O(e n) ，在有向图的建立算法，其时间复杂度为 O(e ? n) 。该存储结构不存 在存储空间的浪费，当路段信息较多时效果较佳。邻接表数据结构是网络表达中 效率较高的一种数据结构，在最短路径算法中已经得到了广泛应用[25]。 十字链表也是一种链式存储结构，它通常用来描述有向图的结构。它可 以看作是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链 表中，对应于有向图中每一条弧都有一个节点，对应于每个定顶点也有一个 节点。邻接多重链表类似于有向图表示法中的十字链表，将无向图中表示同 一条边的两个节点合在一起，将得到无向图的邻接多重表。这两种网络存储 方式结构较为复杂，实现的运算量很大，因此只有在特殊情况下才会使用 [26] 。2.3 道路信息的存储在对网络拓扑关系的存储研究方面，绝大多数研究采用了邻接矩阵或者邻接 表等存储方式。如果采用邻接链表，可以一定程度上降低网络拓扑数据的复杂度， 但是在路径寻优算法中会增加程序的设计难度。邻接矩阵方法最为直观，虽然其 空间复杂程度较高，但是可以利用矩阵结构进行网络的存储，因而该结构的算法 适宜度高，可以应用到多种算法之中。 根据图的定义可知，图的逻辑结构可以分为两部分：V 和 E 的集合。因此， 用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或 弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无11向图邻接矩阵。邻接矩阵的定义还可以继续加以扩展，可以包括点的邻接、边的 邻接以及区域的邻接。具体思想是，首先提取路网中的所有节点，并在图层上创 建点对象，对每个点进行编号。然后将矩阵的行和列分别定义为地图点对象中的 编号，若两个点之间存在邻接关系，则在对应的行列交叉处标号为 1，若不邻接则 标号 0。有向图中则对应于将可到达标为 1，不可到达标记为 0。例如图 2-1 中无 向图 G5 和有向图 G6 的邻接矩阵可以分别表示为 Al 和 A2。图 2-1 邻接矩阵的的示例邻接矩阵有如下特点： （1）在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数 等均可省略） 。 （2）当邻接矩阵中的元素仅表示相应的边是否存在时，矩阵值可定义为值为 0 和 1 的枚举类型，1 代表相邻，0 代表不相邻。 （3）无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 （4）邻接矩阵表示法的空间复杂度为 S (n) ? O(n2 ) [27]。 在实际操作中，邻接矩阵还可以添加其他的相关信息，例如当采用点的邻接 矩阵作为路网存储结构时，可以将邻接关系 1 用距离关系来代替，如 Vi 与 Vj 相邻 接，可以将 Vi 与 Vj 之间的距离值作为矩阵中 Vi 与 Vj 行列点的数值，如此在路径优 化算法中可以直接获得路网中各个弧边的距离信息，方便算法的计算。采用邻接 矩阵方法来存储网络拓扑数据，虽然可以直接完成两个顶点是否存在一条网络边 的查询，但对最短路径算法最关键的关联节点查询，其复杂度均为 O(n) 。此外，12采用邻接矩阵存储网络拓扑数据的空间复杂度为 O(n2 ) 。 但由于邻接矩阵具有较好 的直观性的普适性，因而在最短路径算法中得到了广泛应用[27,28]。 在本文 110 出警线路最优路径搜索问题中，一般采用点对点的数据结构更加 合适，因为在目前的警务数据系统中，通过电线杆标记法已经可以确切的知道路 网中的点位置。考虑到本文主要研究的是两种经典路径最短算法，并且所采用的 是基于 MapInfo 和 MapBasic 的开发环境，该环境对于数据结构复杂度的支持相对 较弱，因而采用邻接矩阵结构的存储形式。一方面邻接矩阵可以清晰地表达网络 的拓扑结构，另一方面更加便于 Dijkstra 算法和 A*启发式算法的实现。2.4 本章小结本章首先介绍了图形学的基本理论，根据路网图形理论介绍了 4 种路网存储 结构的相关内容。并比较了邻接矩阵、邻接表、邻接多重表和十字链表等存储结 构的特点和适用范围。通过比较发现，邻接矩阵存储结构更加清晰，存储复杂度 对系统软件的需求更低、可操作性强、普适性好，适合于不复杂情形下的编程实 现。综合考虑本文采用的研究算法和软件平台的特点，最终选择邻接矩阵作为本 文研究对象的基础数据结构。13第三章 城市道路阻抗权重的确定3.1 引言110 公安报警服务平台已经成为城市居民生活中必不可少的保障因素， 基本上 所有的急发事故都会涉及到 110 工作的范畴。因而公安部门在接到报警电话后如 何及时将警力派往现场是治安工作效率的首要体现。其中减少道路中的时间消耗 是提高工作效率的关键，这就涉及到最短路径选取问题。在选择出警车辆从起点 到终点的最优路径时，所依据的原则是路径的交通阻抗最小（即时间最短原则） ， 而阻抗是受多种路网交通因素影响的。选取阻抗作为度量的主要考虑是 110 出警 状况与普通的物流需求不同，减少时间的消耗是 110 出警的首要目标。交通阻抗 衡量的主要因素是交通时间，它受到交通路网多方面条件的制约，例如道路距离 长度，道路畅通性、车流量的密集度以及路况条件等。因而可以通过对不同路段 情况进行因素分析，通过综合评价给与不同道路的阻抗系数，将阻抗系数反映到 路网信息上，就可以体现时间最优原则的要求。 由于不同车辆不同时间段，车辆在道路上的通行时间是有差异的。因而在对 最优路径算法的实践中往往通过分析路径的阻抗权值来决定。因此如何确定阻抗 权值，使权值的设置符合城市路网的系统状况，是进行地图数字化的重要基础工 作。权值设定的科学与否，将会直接影响算法的适用性和优化结果。进行阻抗权 值的设置首先要对城市路网中影响车辆通行的各种因素建立指标体系。该体系要 求能够基本包括实际工作中能够影响出警时间的影响变量。因为在实际城市交通 网络中，道路长度最短的路径不一定是耗时最短的。特别是 110 警力在到达出险 现场的过程中，需要考虑的影响因素更多，如车流量、车道数、是否有施工、行 人密度、障碍物、时间段、路面状况等等。这些因素中往往无法进行定量的描述， 带有很大的模糊性，用传统的方法很难进行合理的加权，因此本文考虑利用 AHP 层次分析法对各个要素进行加权处理，将最后加权的结果作为阻抗的权值。道路 阻抗权值在理想的情况下应以实际的行程时间作为路段的路阻。但考虑到时间的 不确定性以及实验数据的原因，可以用 AHP 法求得的加权系数来表示动态交通信 息，即将路段的加权长度等于路段的实际长度与加权系数的乘积。通过加权系数 的不同，能够有效的体现阻抗值的变化，例如原本很短的道路由于道路条件较差，14最终加权长度将大于实际距离较长但路况较好的道路，这样就可以体现时间最优 的原则。本章首先介绍了道路阻抗的定义，及其影响因素，并利用 AHP 法，提出 了基于 AHP 法的道路权值结构模型，对道路阻抗权值进行综合评定。3.2 道路阻抗值110 控制台接到报警后，从安排出警到抵达案发地点往往时间紧迫，稍有延误 后果可能是非常严重的。为了将损失降低到最低程度，公安部门需要解决的问题 是如何迅速调动警力赶赴案发现场，这就涉及到路径选取的目标取向问题。对 110 出警线路最优化的计算，是受路网交通状况影响的路径选择过程。路线选择的依 据不同，则结果也不会相同，在 110 出警路线的研究中更多是使用时间最短原则。 为了更加方便最优路径运算的需要，在这里引入阻抗的概念，阻抗是借用物理学 中的概念，主要以交通时间作为度量单位，表示在行程上所占用的时间。这样， 在 110 出警优化计算中对最优路径的取舍标准可以通过计算路径的阻抗值来决定。 考虑到运算的需要，可以将阻抗进行等价的变换分析，利用道路通达性来表示阻 抗的大小，因而首先要对路况进行权值的设定（该权值指代根据最优路径选取原 则设置的各种参数的加权值） 。要使权值的设置更符合实际的需要，必须全面考虑 交通环境对公安出警的不同影响，采用科学的评价体系进行加权综合。在城市交 通网络中，道路长度最短的路径不一定是耗时最短的[28~31]。如何设定最优路径阻 抗权值的评价指标体系也是设计权值的重要前提，影响 110 出警时间的因素很多， 如道路通达性、道路车道数、道路拥挤度、不同时段流量、路况等等。 从公安出警的实际特点出发，需要总结各种道路情况对出警效率的影响，得 出在最短的时间内对各种出警状况的有效的方案。在时间寻优算法中，道路阻抗 权值可以按道路通行时间作为路段的路阻（即道路通达性的时间描述，但往往实 际情况中时间度量不好把握） 。考虑本文主要是进行算法研究，以及所采用数据因 素的限制，本文通过阻抗权值的加权系数来反映道路网络的通达性信息，设定路 段的阻值等于路段的实际长度与加权系数的乘积。因而，可以理解，当路网中某 一地段发生交通堵塞时，反映在系统中该路段的通达性会降低，根据评价体系得 到的加权系数会变大，进而导致道路加权长度变长，即加权系数的增加，相应的 会导致加权长度的增加。例如道路拥堵情况越严重，则相应的路线阻值就应当提 高，对应于系统中就可以对路线长度设有一定的加成系数，反之则越小。通过采 用路段长度的加权系数可以达到与阻抗值描述道路堵塞情况的效果达到一致。随15着信息技术的不断发展，道路实时监控也逐渐达到普及。从技术上来说，已经达 到可以根据实时路况的信息对不同路段的拥挤度进行动态的跟踪，从而根据车辆 接受的交通路况信息来动态的确定加权系数的大小。在设置加权系数时，可以认 为设定系数的上下限的范围。例如发生相对堵塞的路段可以将其加权系数设为 9， 畅通路段的加权系数设为 1（根据实际情况进行设置） 。由于修路或其他原因导致 路段无法通行的，则设置其权值为无穷大，其他情况可以根据交通主管部门观测 到的实时路况的平均车速将路段的加权系数设为 1 和 9 之间的某个值。权值确定 后，把路段长度乘以加权系数即可得到时间最短原则下的道路加权距离[31]。从目 前算法研究的发展现状来看，在大多数的的算法研究中，往往仅根据根据道路的 长度作为最优路径的选取依据，虽然这种假定在算法研究中没有负面影响，但是 在现实情况中往往与实际不符。从网络分析的原则和目的出发，最短路优化就是 在网络中的起点和终点之间找一条阻碍强度最小的通行路径。阻碍强度不仅仅指 一般意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。 根据实际情况的不同，选取的标准也不尽相同。例如在各种城市应急系统（如 110 匪警、119 火警以及 120 医疗急救系统）等问题上，时间的因素是最重要的。而 GIS 的汽车导航系统中的网络分析功能往往是根据距离较短以便达到运费较少的 原则来设计的[32]。由于影响出警车辆到达时间的因素很多，实际长度最短的路径 不一定耗时最短，仅考虑道路长度得出的优化结果往往与真实情况差异很大，因 而有关研究文献中将车流量、车道数、道路等级、路面状况、时间段等因素都纳 入到道路网的信息中。通过对各种因素进行加权评价，得到路段阻值权值，进而 修正路网中路段的加权长度。在分析各种因素的权值之前，首先应该明确系统优 化的最终目标，即 110 出警最优路径规划的指向是距离最优还是时间最优。 在本文的研究中，假设若直接将实际通行距离最短作为路径优化的最优目标， 此时可以将路段实际长度设置为阻抗值。虽然该方案较为直观和简单，但实用性 较差（在具体的算法研究和比较中可以当做基础数据进行算法验证） 。因为以实际 距离最短作为目标只适用于畅通度极好的路网的情况，或者路网非常简单并且路 段差异度较大的情况。但是在对时间紧迫的 110 出警环境中，显然是不合理的。 在紧急情况下，距离最短已经失去了实际意义和应用的参考价值，因而不能作为 110 出警线路优化的目标。很明显出警时间最短应当作为阻值权重的首要目标。如 果考虑动态和静态路网的区别还可以设置不同的计算方案[33]。如静态情况下选择 平均时间作为目标取值；动态情况下以实际消耗时间作为取值，但动态情况下的 数据难以获得；借鉴交通时间与交通中其他因素之间关系来近似替代相应的阻值16等等。本文采用第三种模式，通过 AHP 法设置各种因素对交通时间的影响权值， 以达到拟合时间最短目标下的最优状况。 根据前文的论述选取平均车流量、道路车道数、道路路况情况、人员密集度 四个指标建立影响道路通达性的静态阻抗评价指标体系，实际中涉及的因素还有 很多，本文主要是进行方法研究，因此仅以静态条件的影响因素进行研究。下面 将利用 AHP 层次分析法建立各个指标的权重并进行评价。3.3 层次分析法层次分析法是美国运筹学家托马斯? 塞蒂（T.L.Saaty）教授在上世纪 70 年代初 期提出的一种定性与定量分析相结合的多准则决策方法。层次分析法（Analytic Hierarchy Process 简称 AHP）是将决策总是有关的元素分解成目标、准则、方案等 层次，在此基础之上进行定性和定量分析的决策方法。该方法是美国运筹学家匹 茨堡大学教授萨蒂于本世纪 70 年代初， 在为美国国防部研究&根据各个工业部门对 国家福利的贡献大小而进行电力分配&课题时，应用网络系统理论和多目标综合评 价方法，提出的一种层次权重决策分析方法。该方法将决策进行必要的因素分析， 将与决策总目标总是有关的元素分解成目标、准则、方案等层次，在此基础之上 进行定性和定量分析的决策方法[34]。层次分析法需要对复杂决策问题的本质、影 响因素及其内在的关系进行深入的分析，从概念模型出发构建出一个层次结构模 型，然后利用较少的定量信息（更多要靠主观经验和认识），把决策的思维过程 数学化，从而为求解多目标，多准则或无结构特征决策问题，提供一种简便的决 策方法。具体的说，它是指将决策问题的有关元素分解成目标、准则、方案等层 次，用一定的尺度标准对人的主观判断（应用如头脑风暴、德尔菲法、群决策方 法等）进行客观量化，在此基础上进行定性分析和定量分析的一种决策方法。它 把人的判断思维过程层次化、数量化，并用数学为分析、决策、预报或控制提供 定量的依据。它尤其适合于人的定性判断起重要作用、对决策结果难于直接准确 计量的场合[31]。在路径阻值权值的设置中，该方法可以综合各种不同的道路因素， 通过主观比较得到客观的阻值权重值，能够方便的为路网设置初始化的信息因子。173.3.1 层次分析法的基本原理在现实生活中，难免会遇到多属性决策的问题，比如高考志愿填报、商店选 址、投资计划等等。这些问题往往具有很多的影响因素，因而在决策者必须考虑 很多方面的因素或者判断准则，最终通过这些准则作出选择。比如当进行商店选 址的决策时，抉择者必须考虑被选地址的客流情况、交通情况、地价租金、临近 商铺以及外围环境等等。这些因素是相互制约、相互影响的，将这样的复杂系统 称为一个决策系统。在很多决策系统中因素之间的重要性比较往往无法用定量的 方式描述（例如交通与租金因素的比较） ，此时就需要将半定性、半定量的问题转 化为定量计算问题，这正是层次分析法所要解决的问题。层次分析法将复杂的决 策系统层次化，通过逐层比较各种关联因素的重要性来为分析、决策提供定量的 依据[32]。在社会、经济以及科学管理领域中经常存在由相互关联、相互制约的众 多因素构成的复杂而缺少定量数据的系统，层次分析法为分析解决这类问题的决 策和排序提供了一种新的、简洁而实用的建模方法。3.3.2 层次分析法的基本步骤一般的层次分析法建模可以分为四个基本步骤：建立递阶层次结构模型；构 造出各层次中的所有判断矩阵；层次单排序及一致性检验；层次总排序及一致性 检验[34]。 （一）建立层次结构模型 应用层次分析法分析决策问题时，首先要对该决策问题有清晰的了解，把问 题条理化、层次化，构造出一个层次清晰的结构模型。这样可以将复杂问题分解 为被称作元素的组成部分。然后按照各个元素的属性把元素进行分组，形成互不 相交的层次，上一层次的元素的宏观性较强作为准则层，对相邻的下一层次的元 素起支配作用；下层元素较为具体每一准则层里的下层元素的集合决定该准则的 取值，这样就形成了层次间自上而下的逐层支配的关系，这就是一种递阶层次关 系[29]，见图 3-1。划分准则时，要避免划分的过细过多，影响比较的准确性。这些 层次可以划分为三种类型： （1）最高层：该层次中只有一个元素，它是所需解决问题的预定目标和决策 的最终依据，因此也称为目标层。 （2）中间层：该层次中包含了为目标决策所涉及的中间环节，一般通过对目 标层按一定的划分准则进行分解，它可以由若干个层次组成，包括所需考虑的准18则、子准则，因此也称为准则层。 （3）最底层：该层次包括了目标决策可供选择的各种措施、备选方案等，是 较为细化的元素层，因此也称为措施层或方案层。图 3-1递阶层次结构模型示意图递阶层次结构具有如下 4 个性质： （1）递阶层次模型中的任一个元素一定从属并且仅仅从属于一个层次，不同层次 间的元素集的交集是空集。 （2）同一个层次中的任两个元素之间不存在从属或支配的关系，即层次的划分具 有一致性。 （3）第 n 层中的任一元素必然至少受 n ? 1 层中的一个元素支配，且只能受 n ? 1 层 中的元素支配；同时，第 n 层中的每个元素必然至少支配 n ? 1 层中的一个元素，且 只能支配 n ? 1 层中的元素，即上层支配下层。 （4）属于不相邻的两个层次上的任意两个元素之间不存在支配关系，即支配关系 具有不可跨越性[35]。 递阶层次结构中的层次数与决策问题的复杂度及问题分析的详尽程度有关， 虽然层次数的划分不受限制，但一般可以划分为 3 层，方便问题的决策。每一层 次中各元素所支配的元素一般不要超过 9 个。这是因为支配的元素过多会给两两 比较判断带来困难[35]。 （二）构造成对比较阵 层次结构模型建成之后，就可以对各层中的元素进行两两比较，构造比较判19断矩阵。从层次结构模型的第 2 层开始，对于从属于上一层每个因素的同一层诸 因素，用成对比较法适度的评级尺度构建成对比较阵，直到最下层。层次分析法 主要是对每一层次中各因素的相对重要性做出判断，这些判断通过引入合适的标 度用数值表示出来，写成判断矩阵。判断矩阵表示针对上一层次元素，本层次与 之有关元素之间相对重要性的比较[34,35]。判断矩阵是层次分析法的基本信息，也 是进行相对重要度计算的重要依据。下面介绍建立两两比较判断矩阵的方法。 设要比较的 n 个元素为 X ? {x1 ,?, xn } ，要得出对这 n 个元素对上层元素 Z 的 影响相对大小，可以采取对因子进行两两比较建立成对比较矩阵的办法。即分别 对两个元素 x i 和 x j 进行比较，以 aij 表示 x i 和 x j 对 Z 的影响大小之比，将比较结果 用矩阵 A ? (aij ) n?n 表示，称 A 为 Z ? X 之间的成对比较判断矩阵。根据定义可以得 出，若 x i 与 x j 对 Z 的影响之比为 aij ，则 x j 与 x i 对 Z 的影响之比应为 a ji ? 若矩阵 A ? (aij ) n?n 满足 aij ? 0 ， 并且 a ji ?1 。 aij1 （ i, j ? 1,2,?, n ） ， 则 A ? (aij ) n?n 称 aij为正反矩阵。进一步讲若正互反矩阵 A 中的元素满足：aij a jk ? aik ， ?i, j, k ? 1,2,?, n ，则称 A 为一致矩阵。应用一致矩阵的原因是，在对实际决策问题求解时，通过两 两比较的得到的判断矩阵并不一定是一致性，因而需要进行一致性检验。 在层次分析法中，为了使决策判断由定性比较转化为定量比较，形成数值判 断矩阵，通常根据一定的比率标度将判断定量化。通常可以分为 3 标度法、5 标度 法、7 标度法和 9 标度法，这些方法对应于对比分析所需要的精准程度，例如 9 标 度法就是引用数字 1~9 及其倒数作为标度[35]。下表 3-1 列出了 9 标度的含义：表 3-1 9 标度法的含义 定义说明 两个因素相比，具有相同重要性 两个因素相比，前者比后者稍重要 两个因素相比，前者比后者明显重要 两个因素相比，前者比后者强烈重要 两个因素相比，前者比后者极端重要 分别代表上述相邻判断的中间取值 两个因素相比，前者比后者的不重要性，其等级为相应重要性等级的倒数20标度 1 3 5 7 9 2，4，6，8 上述值的倒数在对较复杂问题进行决策时，其判断矩阵是往往要通过咨询多位专家进行评 价判断，也称之为德尔菲法。特尔斐法是一个使专家集体在各个成员互不见面的 情况下对某一项指标的重要性程度达成一致看法的方法。使用德尔菲法的原因是， 借助于专家渊博的知识和丰富的经验对因素间的关系作出较为准确的评价，使转 化的决策信息更加符合实际。 需要指出的一点是， 进行判别矩阵构件时， 作n ( n ? 1) 2次两两判断是必要的。若只作 n ? 1 个比较有可能会使任何一个判断的失误导致不 合理的排序，而个别判断的失误对于难以定量的系统往往是难以避免的。进行n ( n ? 1) 次比较可以提供更多的信息，通过各种不同角度的反复比较，从而导出一 2个合理的排序[34,35]。构造出判断矩阵后，即可以对判断矩阵进行单排列计算。 （三）层次单排序及一致性检验 建立判断矩阵，是将定性思维转化为定量判断的必要基础步骤，同时也是将 复杂问题简单化的一种处理方式。建立判断矩阵以后需要对判断矩阵的一致性进 行判断，进行一致性检验的原因是专家在判断指标重要性时，各个判断之间可能 存在不一致的情况。对于根据实际问题建立的判断矩阵往往由于各种原因会出现 判断不一致的情况，特别是在判断因素比较多的时候，判断矩阵的一致性往往无 法满足。而应用层次分析法，保持判断思维的一致性是至关重要的。虽然很多情 况下由于客观事物的复杂性和人们认知上的多样性，以及所分析的问题过于复杂， 要求每一个判断都有完全的一致性显然不太可能。但是要求判断矩阵具有相对的 一致性是可以达到的。为了保证应用层次分析法分析得到的结论合理，就需要需 要对构造的判断矩阵进行一致性检验。应用一致性检验可以有效的帮助决策者检 查并保持判断矩阵的一致性[35]。 进行一致性检验的总体过程是先计算成对比较矩阵的最大特征根及对应特征 向量，利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通 过，则将归一化的特征向量做为权向量；若不通过，则需重新构追成对比较阵。 根据矩阵理论， 如果 ?1 , ?2 ??n 是满足式 Ax ? ? x 的数， 也就是矩阵 A ? [aij ]n?n 的21特征根，并且对于所有的 aii ? 1 ，有 ? ?i ? n 。并且当矩阵 A 具有完全一致性时，i ?1n?1 ? ?max ? n ，其余特征根均为零；而当矩阵 A 不具有完全一致性时，则有 ?1 ? ?max ? n ，其余特征根 ?2 , ?3 ??n 有如下关系： ? ?i ? n ? ?max 。由此可以得出，i ?1 n当判断矩阵不具有完全一致性时，相应的判断矩阵的特征根会发生相应的变化， 因而我们就可以通过判断矩阵特征根的变化来检验判断矩阵的一致性程度。综上 所述，可以引入判断矩阵最大特征根以外的其余特征根的负平均值作为层次分析 法中度量判断矩阵偏离一致性的指标，即用CI ?? max ? nn ?1（3.1）度量决策者判断思维的一致性。 CI 值越大，表明判断矩阵偏离完全一致性的程度 越大； CI 值越小（越接近零） ，表明判断矩阵的一致性越好。可以看出，当判断 矩阵具有完全一致性时， CI ? 0 ，即当 CI ? 0, ?1 ? ?max ? n ，判断矩阵具有完全一 致性。 对于不同的决策问题，人们判断的一致性误差也会不同，特别是判断矩阵的 阶数发生改变时，CI 值的要求也会有所不同。因此为了比较不同阶的判断矩阵是 否具有满意一致性，需引入一种衡量机制。一般的通过引入平均随机一致性指标RI 值，作为衡量参数。 RI 值的计算是用随机方法构造 500 个样本矩阵，随机地从1~9 及其倒数中抽取数字构造正互反矩阵，求得该矩阵的最大特征根的平均值? 'max ，并定义RI ?? ' max ? nn ?1（3.2）RI 值的取值如表 3-2 所示[35]。表 3-2 平均随机一致性指标 RIN RI1 02 03 0.584 0.95 1.126 1.247 1.328 1.419 1.45在上表中，N 表示判断矩阵的阶数，容易理解当矩阵为 1，2 阶时判断矩阵总22是具有完全一致性的。当阶数大于 2 时，判断矩阵满足一致性要求的难度会越来 越大，因而对应的 RI 值也会逐渐增大，由于 RI 是随机状态下的一致性数值，因 而可以用来当做衡量其他判断矩阵的参考标准，即将判断矩阵的 CI 值与同阶平均 随机一致性指标 RI 之比作为一致性检验的标准，称为随机一致性比率，记为 CR 。 并规定，当CR ? CI ? 0.10 时， RI认为判断矩阵具有满意的一致性，否则就需要重新调整判断矩阵，然后再次 检验，直到符合标准为止。 经过对判断矩阵的一致性检验，就可以得到各个因素的权重值。具体方法是 求得判断矩阵 A 中最大特征向量 ?max 所对应的特征向量 W ，对 W 进行归一化后， 所得到的结果即为相应因素对于上一层次因素相对重要性的排序权值，也被称为 层次单排序。层次单排序的结果仅仅对应为判断矩阵建立时所在的层次，表示当 前层的元素对应于上层准则的权重。在计算矩阵的最大特征值和特征向量的时候， 由于判断矩阵本身误差性的存在，加上层次分析法的本质上对各种因素优先排序 权值上的定性表述。因而可以用一种近似但较为简单的方法进行计算。具体步骤 如下： （1） 计算判断矩阵每一行元素的乘积 M i ? ? aij ，j ?1 n。 i ?1, 2 ? , n,（2） 计算 M i 的 n 次方根 Wi ? n M i ， i ? 1, 2,?, n 。 （3） 对向量 W ? [W1,W2 ,?Wn ]T 进行归一化处理。Wi ?Wi?Wj ?1n，则 W ? [W1,W2 ,?Wn ]T 即为所求的特征向量。j（4） 计算判断矩阵的最大特征根 ?max ? ?i ?1n( AW )i ，其中， ( AW )i 表示向量 nWiAW 的第 i 个元素。该方法被称作方根法，是一种求解特征根和特征向量的简易方法，在精度要23求不高的情况下使用可以降低计算的难度。当然还有其他一些建议算法解决该类 问题，在此不做赘述，在计算软件较为发达的今天，可以应用 MatLab 等矩阵处理 软件进行求解。 （四）层次总排序及一致性检验 层次单排序中得到的是一组元素对其上一层中某元素的权重向量。对于层次 较多的决策问题，还需要将各个层次的子权重进行分解加权，得到每个元素对应 于总目标的权重。即通过已经的到的权重值自上而下地将单准则下的权重进行合 成。 具体方法是设最底层元素的上一层次（ A 层）包含 A1 ,?, Am 共 m 个因素，它 们的层次总排序权重分别为 a1 ,?, am 。最底层（ B 层）包含 n 个因素 B1 ,?, Bn ，它 们关于 Aj 的层次单排序权重分别为 b1 j ,?, bnj （当 Bi 与 Aj 无关联时，bij ? 0 ） 。则 B 层中各因素关于总目标的权重，即 B 层各因素的层次总排序权重 b1 ,?, bn ，可由公 式 bi ? ? bija j ， i ? 1,?, n 得到。具体见表 3-3。j ?1 m表 3-3 权重指标 B1 B2 … Bn A1 a1 b11 b21 … bn1层次总排序的方法 … … … … … … Am am b1m b2m … bnm B 层总排序A2 a2 b12 b22 … b2n?bj ?1mm1jajaj?bj ?12j?bj ?1mmjaj因为层次总排序是根据前面层次单排序所得结果的分解和加权，因此一致性 一般可以满足，但是由于各层次的非一致性误差仍有可能积累起来，引起最终分 析结果可能存在着非一致性。因此对层次总排序也需作一致性检验，检验仍像层 次总排序那样由高层到低层逐层进行。设 B 层中与 Aj 相关的因素的成对比较判断 矩阵在单排序中经一致性检验，求得单排序一致性指标为 CI ( j ) ， （ j ? 1,?, m ） ，24相应的平均随机一致性指标为 RI ( j )（ CI ( j )、RI ( j ) 已在层次单排序时求得） ， 则B 层总排序随机一致性比例为CR ?? CI ( j )a ? RI ( j )aj ?1 j ?1 mmj（3.3）j当 CR ? 0.10 时，认为层次总排序结果具有较满意的一致性并接受该分析结果。 在应用层次分析法分析实际问题时，需要关注两点问题一是跟据实际情况构 造出科学而又贴近实际的层次结构；二是如何使定性的因素变量转化为接近实际 的定量数据。层次分析法在一定程度上提高了决策的准确性，但是该方法也有一 定的局限性，例如层次分析法的理论基础是人的主观判断，人为因素对结果的影 响很大，虽然通过抑制性检验可以尽可能的排除思维判断中的非一致性因素，但 对于决策者认识的片面性没有办法进行改进。二是层次分析法只能属于较为粗略 的量化办法，不能用于精度要求较高的决策问题。对于本文要决策的问题，因为 所涉及的因素并不是非常复杂，并且对精度的要求也有限，因而层次分析法具有 较好的适用性。 通过前面层次分析法的处理，就可以得到每个因素对于总目标的影响权重， 然后就可以对每条路段的各个隐私进行评价打分，按照所得权重进行加权最终得 到道路的阻抗系数。3.4 层次分析法在阻值设置上的应用在路径优化算法中，应用层次分析法主要是为了设置道路阻抗，前面说过影 响道路阻抗的因素有很多，因而如何建立层次结构模型是十分关键的一步。根据 前文的分析，在本文中选取平均车流量、道路车道数、道路路况情况、人员密集 度四个指标建立影响道路通达性的静态阻抗评价指标体系，下面将利用 AHP 层次 分析法建立各个指标的权重并进行评价打分，得到路段的阻抗系数。 1.构建层次结构模型： 因为本文所要决策的问题相对简单，因而层次结构模型也不复杂，仅包括一 个最终目标，和四个影响因素。其中四个因素的选取依据是道路车道数和道路路 况情况反映道路的硬件条件，硬件条件越好越有利于通行；人员密集度和平均车 流量体现了交通的通行状态，车流量和行人流量越大，对车辆的交通起到阻碍的25作用。因此从硬件设施和通行状态两个方面考虑基本上可以体现路网的阻抗度。 具体结构见图 3-2。阻抗系数A平 均 车 流 量B1道 路 车 道 数B2道 路 路 况 情 况B3人 员 密 集 度B4图 3-2 道路阻抗评价的层次结构模型2.层次单排序并进行一致性检验 首先，对第一步层次模型中的 4 个变量两两进行比较，应用 9 标度法进行标 记，得到判断矩阵 A。? 1.3 3.0 ? ? 3.0 5.0 ? ? ? A= ? 0.0 1.0 ? ? ? ? 0.9 0.0 ? 利用 MatLab 的矩阵处理功能，得到矩阵 A 的特征值矩阵 D 和特征向量矩阵V。0 0 0 ?4.2622 ?0 - 0.0851 ? 1. D= ? ?0 0 - 0.0851 - 1.2417i 0 ? 0 0 - 0.1924 ?0 ? ? V= ? ? ? ? - 0.4102 - 0.8762 - 0.2425 - 0.4? 0.4- 0.7 0.8347 - 0.4i - 0.4i - 0.1i - 0.1i26? ? ? ? ? ? 0.5490 - 0.8177 - 0.4 ? ? ? ? ? ?由此矩阵计算得：?max ? 4.2622 , CI ? 0.0874 , RI ? 0.，所以，该判断 矩阵的一致性可以接受。因而对最大特征值所对应的特征向量进行归一化，即得 到各种因素的权重值。见表 3-4-1。A B1 B2 B3 B4 B1 1.00 3.00 0.33 0.20 表 3-4 判断矩阵及权重 B2 B3 B4 重要性权重值 0.33 3.00 5.00 0. 5.00 7.00 0. 1.00 7.00 0. 0.14 1.00 0.0449得到阻抗评价体系的权重以后，就可以对各个路段的实际情况进行阻抗值的 评定。例如对每一个指标都进行满分为 10 的打分（其中车道数和路况情况为负向 指标，得分越高表示条件越差，对阻抗的影响越大；车流量和行人密度为正向指 标，得分越高对道路阻抗影响越大） 。以东风街为例，东风街为 4 车道，车流量偏 多，路况情况良好，行人密集度较大。因而可以给与 8，1，1，7 的得分。将得分 乘以层次分析法得到的权重值进行加权，得到总得分为 3.0628。将各个道路分别 根据这四个因素进行打分，就得到初步的阻抗值系数。一般的道路阻抗系数对于 110 出警车辆的影响是有限的，因而我们设定阻抗系数的上限为 2，下限为 1。对 所有道路的初始阻抗值进行统一的归一化，设最高阻抗的道路值系数为 2，得分最 低的阻抗为 1。其他的按比例进行调整。这样将所得阻抗与道路的原始长度相乘， 即可得到道路相对距离。在进行路径寻优时，体现时间代价的最小原则。3.5 本章小结本章首先从 110 公安出警的实际特点出发，选取车辆的道路耗费时间最短作 为衡量线路优劣的选择标准，因而设置道路阻抗值作为评价道路通达性的指标。 由于影响道路通达性的因素很多，因此需要用到 AHP 层次分析法进行各个因素的 权重设置。文中给出了层次分析法的具体应用过程，选取平均车流量、道路车道 数、道路路况、人员密集度 4 个指标作为阻抗值的影响因子。利用 AHP 法对这四 个因子进行了权重设置，得到了最终的权重结果。最后介绍了指标体系的评价标 准和归一化方法。通过进行各种因素的分析，可以较合理的对各个路段进行必要 的修正，得到能够体现道路通达性的相对距离，为建立更合理的 110 出警线路优 化系统提供了条件。27第四章 110 出警线路优化算法4.1 引言最短路径问题是路线设计及分析等优化问题的基础，是交通、物流等网络分 析的核心内容之一。所谓的路径规划算法，是利用地图数据，搜索从起点到终点 的最优路径的算法。本文所研究的问题是如何选择到达报警位置的时间最短路径， 其根本思想也是最短路径的优化求解。最短路径问题在不同领域不同的环境中有 许多种类的算法和实现方式。针对道路环境较为稳定的情况下可以应用静态的路 径优化算法， 如本文将要用到的 Dijkstra 算法， 以及 Bellman-Ford-Moore 算法、 Floyd 算法、盲目搜索等。从算法的特点上讲路径算法又可以分为无信息搜索（又称为 盲目搜索）和启发式搜索两种，如本文所用到的 A*启发式算法就是启发式搜索的 代表，相应的 Dijkstra 算法是无信息搜索算法的代表。在不同的具体问题中，由于 路网环境不同，采用不同的路径搜索方法的效果可能存在很大的不同。本章分别 采用两种经典的路径寻优算法作为 110 出警线路寻优的案例实现算法，研究路网 图搜索的一般实现过程，并比较无信息搜索（ Dijkstra 算法）和启发式搜索（ A* 算法）的区别。4.2 最短路径算法最短路径是运筹学、图论等应用数学领域中的一个基本概念，一般的最短路 径算法可以分为盲目搜索和启发式搜索两大类。最短路径算法是图的搜索算法， 问题的求解实际上就是在这个图中找到一条路径可以从出发点到目标点，并 且要使出发点和目标点之间路径的总代价最低。一方面要完成探索最低代价的路 径，另一方面要做到运算快，占用计算资源少，算法的时间复杂度和空间复杂度 尽量低。 在应用盲目搜索进行求解的过程，一般是“盲目”的穷举，即不运用特别的 信息。盲目搜索包括宽度优先搜索、深度优先搜索和等代价搜索等。其中有界深 度搜索从某种意义上讲，具有一定的启发性。从搜索效率上看，一般来说，有界 深度优先搜索较好，宽度优先搜索次之，深度优先搜索较差。不过，如果有解，28那么宽度优先搜索和深度优先搜索一定能够找到解答，无论付出多少代价；而有 界深度优先搜索则可能失去某些解[37]。 启发式搜索主要讨论有序搜索（或最好优先搜索） 、最优搜索 A*算法和 AO* 算法。与盲目搜索不同的是，启发式搜索运用启发信息，引用某些准则或经验来 重新排列 OPEN 表中的节点顺序，使之搜索沿着某个被认为最有希望的前沿区段 扩展。正确选择估价函数，对于寻求最小代价路径或解树，至关重要。启发式算 法比盲目搜索有效地多，因而应用较为普遍。 图搜索策略是在图中寻找路径的方法。图搜索的一般过程如下： （1） （2） （3） （4） （5） （6） （7） 建立一个只含有起始点 S 的搜索图 G， 把 S 放到一个叫做 OPEN 的 未扩展节点表中。 建立一个叫做 CLOSED 的已扩展节点表，其初始为空表。 LOOP：若 OPEN 表是空表，则失败退出。 选择 OPEN 表上的第一个节点，把它从 OPEN 表移出并放进 CLOSED 表中，称此节点为节点 n 。 若 n 为一目标节点，则有解并成功退出，此解是追踪图 G 中沿着指 针 n 到 S 这条路径而得到的。 扩展节点 n 同时生成不是 n 的祖先的那些后继节点的集合 M。把 M 的这些成员作为 n 的后继节点添入图 G 中。 对那些未曾在 G 中出现过的 M 成员设置一个通向 n 的指针，把 M 的这些成员加进 OPEN 表。对已经在 OPEN 或 CLOSED 表上的每 一个 M 成员，确定是否需要更改通到 n 的指针方向。对已在 CLOSED 表上的每个 M 成员，确定是否需要更改图 G 中通向它的 每个后裔节点的指针方向[42]。 （8） （9） 按某一任意方式或某个试探值，重排 OPEN 表。 GO LOOP。以上搜索过程可以图 4-1 所示的程序框图来表示。 在这个过程中一般包括各种各样的图搜索算法。此过程生成明确的图 G（为 搜索图）和 G 的一个子集 T（成为搜索树） ，树 T 上的每个节点也在图 G 中。搜索 树是由步骤（7）中设置的指针来确定的。G 中的每个节点（S 除外）都有一个指 向 G 中一个父辈节点的指针， 该父辈节点就定义为树中那个节点的唯一父辈节点。 对任何节点的单独一条明显路径是用 T 来定义的；粗略的说，在 OPEN 表上的节 点都是搜索图的端节点，而在 CLOSED 表上的节点则不是。步骤（8）对 OPEN29表上的节点进行排序，以便能够从中选择一个“最好”的节点作为步骤（4）的拓 展使用。从图搜索的过程中可以看出，是否重新安排 OPEN 表，即是否按照某个 试探值重新对未扩展节点进行排序，将决定该图搜索过程是无信息搜索还是启发 式搜索。开始把 S 放入 OPEN 表中 是 OPEN 表是否为空 否 把第一节点 n 从 OPEN 表移至 CLOSE 表 是 n 为目标节点？ 否 把 n 的后继节点放入 OPEN 表的末端，提供返 回节点 n 的指针 成功 失败修改指针方向重排 OPEN 表图 4-1 图搜索的一般过程过程在路径搜索算法中， 最经典的算法盲目搜索算法是 Dijkstra 提出的按路径长度 递增的次序产生最短路径的方法，它是一个适用于所有弧的权为非负的最短路径 算法，可以给出从某定点到图中其他所有顶点的最短路径。A*算法则是一种典型 的启发式算法，通过设置启发函数，可以优先考虑代价最小的节点作为后继节点， 这样可以节省大量的搜索时间。下面将分别介绍 Dijkstra 算法和 A*算法。304.3 Dijkstra 算法Dijkstra 算法是图论学中求解最短路径问题最具代表性的最短路算法，在很多 专业课程中都有详细的介绍，如数据结构、图论、运筹学等。Dijkstra 算法是建立 在抽象的网络模型上，把道路抽象为网络中的边，以边的阻值来表示与道路的度 量，通过该算法来确定道路网络中从某点到其他节点的具有最小阻值的路径。该 阻值可以表示为距离、数量、费用、时间等等。通常把两点之间的阻值称为两点 之间的距离。传统的 Dijkstra 算法用于寻求从一固定起点到其余各点的最短路径， 它是按路径距离递增的次序产生最短路径的算法。Dijkstra 算法的基本思想是标记 源点到已得到点的最短路径，再寻找到下一个点的最短路径[39]。 Dijkstra 算法的基本思想是将路网假设成以固定起点为根的最短路径生成树。 该树到每个节点仅有一条路径，该路径即为根到该点的最短路径，很显然该树状 结构滤去了非最短路径，使起点到每一节点的路径都是唯一的，自然的起点到终 点的路径解释最短的。Dijkstra 算法中所求问题的路网结构中不存在负数。因此这 棵最短路径生成树在生成过程中将对各节点按其距固定起点的远近以及点间的邻 接关系来逐个地加入到树中，先从靠近起点的节点开始添加[36]。 Dijkstra 通常有两种表述方式， 一种用永久和临时标号方式(也被称为标号作业 法)，一种是用 OPEN，CLOSE 表方式，一般的通常采用永久和临时标号的方式， 下面对标号作业法进行介绍。 定义路网 G 中的任意(u，v)之间的路径的最小权称为点 u 和 v 之间的距离，计 作 dv 。设 S 是 V 的真子集，且 u0 ∈S。并记集合 T=VCS，S 表示已经纳入最短路 径的点的集合， V 表示全部点集合， T 则为没有最短路径标号的点集合。 若 P= u0 ...ui （ i ＝1，2，3…）是从 u0 到 T 的最短路径，则显然 u i ∈S，且 P 的( u0 ， u i )必然是 最短的 u0 到 u i 的路径。首先在所有与固定起点 u0 相邻接的点中找到距离起点最近 的点 u1 ，将该点设置为永久性标号，并纳入 S。同理由该点向外围扩散，寻找与起 点不相邻接的点是否与已标号点距离最近。假设这棵最短路径生成树的一部分已 经被找到（设为 k 个节点） ，此时，这 k 个节点到起点的最短路径长度将作为它们 各自的永久标号（标记各个节点到起点的距离 dum ， m ? 1...k ） 。同样道理，对没有 永久标记的节点 j ，可以首先构成 n 条从起点到它的路径，在这 n 条路径中必然存 在最短的一条，将其长度作为节点 j 的暂时标号（因为其前接节点还存在没有永久 标号的点，因此无法判断该标号是否最短） 。用同样的方法可以计算出其它未标号 节点的暂时标号，最后在所有的暂时标号中选择最小的一个，这个最小标号的节31点即为我们要找的第 k ? 1 个节点，将并将临时标号改为永久标号 dui ，添加进生成 树中。 重复上述过程即可得到所有节点的永久标号[37]， 此时终点 v 的标号即为最短 距离 dv 。 该方法的计算步骤可以表述为： （1）初始化。 设固定起点为 s ： ds =0，S= ? ，ds 表示该点到起点 s 的最短距离，S 表示已标 记点； 目前路网中的其他点还未计算，此时将起点 s 标号，并令 k ? s 。 （2）距离路径计算。 将所有已经标记的点 k 到其他临接的未标记的点 j 的距离记为 lkj ，并令d j ? min ?d j，d k ? lkj ?此时 d j 表示点 j 到起点 s 的最短距离。 （3）选取下一点。 选取 d j 最小所对应的点作为最短路径中的下一连接点 i ， 并对点 i 标记，i 计入 S。 （4）找到点 i 的前一点。从已标记的点中找到直接连接到点 i 的前一点 j? ，并 令 j? 作为路径中点 i 的前一点。 （5）如果所有点已标记，则退出算法，否则，记 k ? i ，转到（2）再继续， 直到所有点都已标记。 图 4-2 为求解两指定顶点 u0 和 v0 之间最短路径的 Dijkstra 算法。Dijkstra 算法 结束时,从 u0 到 v0 的最短距离由标号 dv0 给出[32]。 Dijkstra 算法是全向搜索方法，即搜索过程将遍历整个网络，所得到的结果也 必然是全域最优的，但是其时间复杂度也相当的高为 O(