基于最佳路径的警力资源调度算法

摘要：分析了现有警力资源调度中存在的问题，然后结合交通网络中交通规则和实时路况信息，提出了一种基于最佳路径的警力资源调度方案，并给出的详细的算法步骤。实验结果证明，该算法是可行的，能满足应用要求，并已应用于实际应用。

关键词：最佳路径；警力资源调度；优先级队列

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)29-7219-03

Police Resources Scheduling Algorithm Based on Optimal Path

LIU Li-juan

(Department of Computer Science, Xinyang Agricultural College, Xinyang 464000, China)

Abstract: This article analysed the scheduling problems of the existing police resources, and combined in the transport rules and the real-time traffic information of the transport network, and then it raised a scheduling scheme of police resources based on the best way, and gave the detailed steps of the algorithm. The experimental results show that the algorithm is feasible that it can meet the application requirements, and has been applied to practical applications.

Key words: optimal path; police resources scheduling; priority queue

随着经济的发展，城市规模的扩大，城市的紧急事件信息量也在成倍的增长[1-2]。面对日益增多的业务和性能需求，现有警用GIS系统最初的设计指标已经不能满足当前的需求，系统速度较慢、功能操作复杂等问题逐渐明显。对于提高处警和应急响应能力、公安指挥实战能力迫在眉睫。本文针对警用GIS系统的警力资源调度问题，通过提出一种最佳路径的警力资源调度算法，将案发地点、警车的位置自动捕捉到最佳的道路上，最快给予出警指示。通过实验证明，本文算法能够满足实际需要，并且已经应用于实践。

1 警力资源调度的周边资源搜索策略

接处警辅助处警时，需要调用GIS计算警情周边最快抵达的警力资源，得到周边的警力资源之后，再调度相关的警力资源进行处警，详细的周边资源搜索流程如下：首先搜索周边1000米范围内的警力资源，若没有找到警力资源，自动扩大搜索范围。然后在搜索结果中找出与警情同一巡区的警力资源，若没有同一巡区的警力资源，那么找到同一派出所的警力资源。最后计算警力资源与案发地点的最佳路径，并根据计算结果进行排序。排序时，按照同一警区、同一派处所、同一分局的优先序列进行排序，对于同一警区的警力资源按照路径距离从近到远进行排序，对剩余同一派出所的警力资源也按照路径距离进行排序。

2 基于最佳路径的搜索算法

2.1 数据结构

要实现最佳路径计算，核心是要具有路网及相应交通规则数据的支撑。首先对路网进行数据建模，采集基础道路信息，然后根据数据模型要求，采集路网的相关属性信息，如路段的限速，车辆限行，是单向道路还是双向道路，采集各个道路的交叉路口，以及各个路口的属性信息，如禁止左转，禁止掉头，红绿灯时长等信息。这种节点、路段及其相互之间的关系，以及各个属性构成了路网拓扑模型。

路网中的节点数据结构如下：

class Node

{int NodeID；

ICoordinate Coordinate； }

路网中道路的数据结构如下：

class RoadSegment

{ int RoadID;

string RoadName;

Node StartNode;

Node EndNode;

List Coordinates;

double RoadLength;

int RoadClass;

double TrafficRank;

int Direction; }

路网中的交通规则数据结构定义如下：

class PatchNode

{ int NodeID;

int FromRoad;

int ToRoad;

List RuleTimes;}

最佳路径数据结构如下：

class PathInfo

{ Node Startv;

Node Endv;

RoadSegment Road;

double Cost; }

PathInfo对象被存储在优先级队列中，该队列可以供我们访问队列中耗时最短的对象。在一个图中两个顶点之间可能存在不同的路径，所以两个PathInfo对象可能连接相同的顶点但却有不同的成本。由优先级队列的定义可知，PathInfo类通过比较Cost成本值来定义优先级，算法检查优先级队列中存储的PathInfo对象并从中选择一个具有最佳路径的。

2.2 最佳路径算法

我们采用从优先级队列中迭代删除对象的方法来寻找最佳路径。当PathInfo对象的终止顶点为Endv就得到成本为Cost值的最佳路径；否则，要考察当前顶点Endv的所有邻顶点以寻找沿另一条边扩展从Startv开始的路径。具体步骤如下：

步骤1：建立节点及对应关系字典库，以起点和终点为焦点，做一个椭圆，以下步骤中所讨论的节点，都指的是在椭圆内部的节点。（若起点或终点不是原有节点，按照3.3的方法创建新节点，并将路段截断，将其对应关系加入字典库。）

步骤2：建立优先级队列，生成PathInfo对象，该对象将Startv设为起点，Endv设为终点，道路数据设为null，初始成本Cost设为0。并将这个对象插入到优先级队列中。

步骤3：从优先级队列中删除一个，将A加入路径记录数组。当优先级队列为空，转向步骤5；当该对象的Endv等于终点，转向步骤7。

步骤4：从字典库中找出与PathInfo对象A的Endv节点的所有道路，先根据交通规则Pathnode判断其中每一条道路是否能够通行。如果能够通行，再判断道路的另外一个节点是否在椭圆内，如果在椭圆内，则新建一个PathInfo对象B，设定B的Startv为A的Endv，B的RoadSegment为当前道路，B的Endv为道路的另外一个节点，通过时间和道路编号，调用实际路况信息，返回该段道路此时实际车速（如果无法得到实际车速，就以道路的等级，给道路赋一个默认速度），以该段道路的长度除以实际车速，得到所需时间t，B的Cost等于A的Cost加上t，将PathInfo对象B加入优先级队列。转向步骤3；

步骤5：扩大椭圆后，转向步骤2；如果椭圆已经是最大，则转向步骤6；

步骤6：结束算法。弹出对话框，“找不到最佳路径！”。

步骤7：从路径记录数组中挑出最佳路径所经过的道路及PathInfo对象，得到最佳路径，结束算法。

2.3 道路图层中两非节点间最佳路径

由于警情的随机性和不可预测性，会出现警情的发生地或警力资源既不是道路网络图层中的节点也不是道路网络图层中的线路。传统的最佳路径算法的都是在的节点或线路上任意点之间实现。这种不可预测的现象，使得无法计算出警情与警力资源间的最佳路径。本文的做法是以离警情及警力资源最近线路的垂足作为替代节点，然后利用3.2的方法，找出替代点之间的最佳路径作为警情与警力资源之间的最短路径。如图1所示，H为事故点位置，G为救援力量所在位置，由于H、G均不在道路网络图层上，所以不能直接计算H、G间的最短路径。于是找到离H、G最近的两条线路AC、EF，并确定两条线路上分别离H、G最近的店H'、G'，用H'、G'之间的最短距离替代H、G间的最短路径。

3 实验结果

以某市市区电子地图为例进行了实例模拟，先将地图按要求转化为路网拓扑数据，得到节点数90362个，路段数据达到97360条，其中单行道路段有40933条，限时路段有2063条。在地图上的不同位置与范围内进行测试，并将结果显示在地图上，所得结果与人工经验判断基本相同，如图2所示（警情点用E标示，警力资源点用S标示）。实验数据显示，求取一条最佳路径的平均时间为0.453秒，其中最短需要时间0.156秒，极端情况下，计算跨越深圳市最远的两个点之间最佳路径需要0.728秒，计算效率也能够满足应用要求。

4 结束语

本文提出的基于最佳路径的警力资源调度算法，主要特点：1）全面的利用道路信息，比直线距离和最短路径更为科学，能够选择出抵达警情地点更快的警力资源及其路径，优化警力资源配置和处警，提高处警效率。2）利用椭圆减小路径的搜索范围，使用字典型存储数据，使算法速度更快、更高效。3）采用分布式部署方案，很大的减轻了服务器的压力，提高方算法的运行速度。

参考文献：

[1] 俞艳,郭庆胜,何建华,袁艳斌.顾及地理网络特征的城市消防站布局渐进优化[J].武汉大学学报:信息科学版,2005(4):333-336.

[2] 郭先春.基于电子与GIS集成的智能消防报警系统的设计与实现[J].测绘通报,2010(10).

[3] 邓昌智,戴国忠,石磊.一种Post-WIMP界面:PGIS的实现[J].中国图象图形学报,2010(7).

[4] 张雅丽.警用地理信息系统的设计研究[J].中国人民公安大学学报:自然科学版,2009(4).

[5] 刘代波,侯孟书,武泽旭,屈鸿.一种高效的最短路径树动态更新算法[J].计算机科学,2011,38(7).