付费下载
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
基于最佳路径的警力网络资源调度研究
目前,城市灾害的管理已成为许多国家应对人为灾害的优先事项,中国也不例外。在紧急事件发生时,如何高效利用有限的资源,提高政府的反应能力和抗风险的能力,为市民提供更快捷的紧急救助服务,是现代城市管理中需要解决的紧迫课题,也是构建和谐社会的重要内容。随着城市规模的日益扩大,城市的紧急事件信息量也在成倍增长,尤其是警用信息量。地理信息系统(GIS)技术的成熟与发展,为在公安领域运用该技术来实现警情和警力资源的科学管理奠定了坚实的基础,已形成了一个独立的领域———警用GIS(PGIS)。PGIS主要包含接警辅助、处警辅助、警力资源展示、视频调用等功能模块。然而,当警情发生时,往往会出现以下情况:①接警人员缺乏对警情及警力资源分布等信息更为直观的了解;②在现有警力资源调度中,一般调用离警情发生地直线距离最近的警力去处理,而未考虑到该警力抵达警情发生地的实际距离可能远大于其他警力;③即使用到了最佳路径,也只是简单的最短路径不符合实际路况信息不能合理地利用和调度警力资源,从而延误警情处理,严重影响处警效率,因此现有的警力资源调度算法已经不能满足现代化大城市接、处警的要求。本文针对警用GIS系统的警力资源调度问题,在最佳路径计算时,引入了优先级队列,利用椭圆限制节点搜索的广度,并考虑到了警情与警力资源不在节点时的情况。实验证明本文算法能够满足实际需要。1元素的公共服务队列是以先进先出队列(FirstInputFirstOutput,FIFO)顺序访问元素的数据结构,从中删除最早的元素。实际应用中,队列常需要删除优先级最高的元素,这就是优先级队列,其主要操作是PQInsert和PQDelete。PQInsert只是简单地将元素插入到队列中,而PQDelete根据某些外部的评价因素来判断元素的优先级,并删除优先级最高的元素。如在警力资源调度所用的最佳路径中,一般来说越快到达目的地,所经路径就越符合需要,这里到达目的地的时间就成为了判断最佳路径的标准。替代队列里常采用先到先服务的事物处理机制,警力资源调度选择路径时就根据路径耗费时间来处理优先级队列。在优先级队列中删除元素时,可能会有多个优先级相同的元素,此时,可将同一优先级的元素按其到达先后顺序进行服务。本文中,假设没有优先级相同的元素。优先级队列PQueue的数据结构如下:2理想路径搜索方法2.1交通网络模型分析要实现最佳路径分析,必须先将道路网络抽象化为网络图再通过图论中的网络分析理论找到最佳路径。一般情况下,点数据、线数据及其拓扑关系组成了网络。对于交通网络,每一个交叉路口可抽象为一个节点对象,2节点之间的连线为路段,路段的长度、等级、车流量和限速等为该路段的权重,这种节点、路段及其相互之间的链接关系构成了交通网络的路网拓扑模型。路网中的节点的数据结构如下:路网中道路的数据结构如下:路网中交通规则的数据结构定义如下:最佳路径要求选择成本最小的路径,这种成本可以用顶点间路径的累积权值来度量。本文中的成本指的是时间,故最佳路径即为最快路径。PathInfo对象被存储在优先级队列中,可供访问队列中耗时最短的对象。网络图中2个顶点之间可能存在不同的路径,故2个PathInfo对象可能连接相同的顶点,却有不同的成本。如从顶点A到顶点D有3条路径,但各路径成本不同。由上述定义的优先级队列可知,PathInfo类通过比较成本值Cost来定义优先级,算法检查优先级队列中存储的PathInfo对象,并从中选择一个最佳路径。若顶点之间没有路径相通,则算法终止并弹出消息。2.2有相邻点扩展路径在算法开始之前,需要做一些预处理,如建立一个字典库,每个节点与哪些道路相连都加入该字典库;再以起点和终点为焦点画一个椭圆,地图上的所有在该椭圆内部的节点都加入到一个椭圆数组中。算法从生成第1个PathInfo对象开始,将Startv与自身连接,道路数据设置为null,初始成本为0。将这个对象插入到优先级队列中。为了寻找最佳路径,采用从优先级队列中反复删除对象的迭代过程。若对象的终止顶点为Endv,则得到最佳路径,其成本为数据值Cost;否则,要考察当前顶点Endv的所有相邻点以寻找从Startv开始的另一条扩展路径。其过程如下:步骤1系统初始化,建立节点字典库;若起点或终点不是原有节点,则按照非节点间的最短路径方法新建节点,并将路段截断,将对应关系加入字典库;以起点和终点为焦点画一椭圆,以下所讨论的节点,指的都是在椭圆内部的节点。步骤2生成一个PathInfo对象,该对象将Startv作为起点,Endv也作为起点,道路数据设置为null,初始成本Cost=0。将这个对象插入到优先级队列中。步骤3若优先级队列为空,则转向步骤5;否则,从优先级队列中删除一个PathInfo对象A,将A加入路径记录数组,若该对象的Endv等于终点,则过程结束,最小成本为该对象的Cost,转向步骤7。步骤4若对象A的Endv不等于终点,从字典库中找出与该节点相连的所有道路,对其中的每一条道路先从交通规则表Pathnode中判断该条路此时是否能够通行,若能通行,则判断道路的另一节点是否在椭圆内,若在椭圆内,则新建一个PathInfo对象B,B的Startv等于A的Endv,B的RoadSegment等于该段道路,B的Endv等于道路的另一个节点,通过时间和道路编号调用实际路况信息,返回该段道路此时的实际车速(如果无法得到实际车速,则以道路的等级赋于一个默认速度),以该段道路的长度除以实际车速得到所需时间t,B的Cost等于A的Cost+t,将PathInfo对象加入优先级队列转向步骤3。步骤5扩大椭圆,转向步骤2;若椭圆已经是最大,则转向步骤6。步骤6弹出“起点和终点之间找不到路径”对话框。步骤7从路径记录数组中找出最佳路径所经过的道路及PathInfo对象,得到最佳路径。2.3传统的最佳路径算法警情具有随机性和不可预测性,其在道路网络图中可能既不是节点,也不在线路上。同时由于警情规模的不同,使得所需要的警力资源也呈现出近似随机的状态,进而出现警力资源与警情既不是道路网络图中的节点,也不在道路网络图中线路上的情况。传统的最佳路径算法都只考虑了道路网络上的节点或线路上的任意点之间的距离,无法计算随机的警情与警力资源间的最佳路径。本文的做法是找到警情与最近警力资源线路的垂足,并将此作为替代点,然后按照最佳路径改进算法,找出替代点之间的最佳路径作为警情与警力资源之间的最短路径。3实验和结果(1)数据(2)试验过程(3)结果4实验数据及分析本文全面考虑了道路信息,选择出更加符合实际情况的路径,优化了警力资源配置和出警,对最佳路径进行优化,使计算速度更快。采用分布式部署方案,将数据存放在服务端,算法部署在客户端,较大程度上减轻了服务器的压力,提高了运行速度;服务端的数据采用序列化二进制进行传输,加快了传输速度;且首次传输时将数据备份,以后再传输则不需要反复读取,加快了响应速度。该方法已应用于深圳市公安局指挥中心。以深圳市区所有道路为网络拓扑数据,共有节点90362个,路段数97360条,其中单行道40933条,限时路段2063条。利用vs2005C#和PGIS平台编写实验程序,在酷睿双核2.93GHz/2GBRAM的台式机上运行,并将运算结果显示于地图上。平均地区运算时间为0.453s,其中最短耗时0.156s,极端情况下,选取深圳市最远地区的2个点计算0.728s,所得结果与人工经判断基本相同,如图1所示。图1中,警情发生地用E
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 催办项目收尾工作的进度通知函4篇
- 市场活动推广费用核对回复函5篇
- 事业单位人事岗面试专业面试强化训练
- 事业单位护理岗面试2026经典考题强化训练试卷及解析
- 事业单位财会岗面试高频考题2026题库及答案
- 人力资源部2026年员工职业晋升考核通知函4篇范文
- 请求协助完成项目报告确认函(7篇范文)
- 航空机务团队协作与维护绩效表
- 2026事业单位人事岗面试高频考题题库及解析
- 事业单位财会岗面试高频考题题库及解析
- 2025年《治安管理处罚法》知识竞赛试题库及答案(完整版)
- (新教材)2025年部编人教版三年级上册语文第五单元复习课件
- 植物学课件马炜梁主编教学
- 腰部支具的正确使用方法
- 电影放映人员上岗证考试题库及答案
- JG/T 220-2016铜铝复合柱翼型散热器
- 高频手术电刀临床应用与操作规范
- 清华大学出社机械制图习题集参考答案第三机械制图清华大学答案
- 专题03 阅读填空20篇(中考真题+各区名校模拟)2023年广州中考英语冲刺专项训练(解析版)
- 《-电力系统分析(上)》试卷
- 19R505-19G540室外管道钢结构架空综合管廊敷设
评论
0/150
提交评论