交巡警服务平台的优化配置与调度

2015-11-28 03:06裴娅男
山西电子技术 2015年3期
关键词:封锁权值警务

裴娅男

(山西大学商务学院,山西 太原 030031)

交巡警是将交警和巡警合二为一的一种警务模式,世界上多数国家已经普遍采用这种警察勤务模式。我国现行采用了“交巡分离”的模式,存在诸多矛盾的同时,也存在着一系列的执法漏洞。我国首个交巡警服务平台在重庆市诞生,代替过去的交警和巡警,将交通管理、刑事执法、治安管理三大职能合为一体[1]。对于市区路况复杂,人口密度分布不同,各地案发率不同等诸多因素,合理的设置交巡警服务平台成为一个需要面临的实际课题[2]。

对于一个城市交通网络,路口和道路的特性非常适合用图论的相关理论来分析这类问题[3]。因此本文主要建立在图论学的基础上来实现警力资源的管辖范围配置、调度以及增补问题[4]。本文首先针对A 区设立警务平台,对各个平台管辖的道路范围采用最短路径法进行了划分[5]。之后本文又采用二分匹配法对市中发生重大事件时,警务平台快速封锁城区进行了优化调度[6]。

1 交巡警平台优化配置问题

图1 为A 城区交通网络和现有交巡警服务平台设置情况示意图。

图1 A 区交通网络示意图

图中实线表示市区道路;实圆点表示交叉路口的节点,没有实圆点的交叉线为道路立体相交;

“* ”表示出入城区路口节点;“○”表示现有交巡警服务平台设置点;“○*”表示出入城区路口处设置了交巡警服务平台。

本文就A 区现有交巡警平台,拟解决以下两个问题:

1)使A 区任意路段或路口发生事件,该管辖区内交巡警能够尽量在3 分钟内到达事发地,警车的速度为60 km/h。

2)对于重大突发事件,需要调度全区20 个交巡警服务平台,对进出该区的13 条交通要道实现快速全封锁。实际一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。

2 交巡警平台的管辖范围优化配置

2.1 城市交通网络抽象化

本文将该区域的城市交通网络抽象模型化为一个无向图,利用图论方面知识解决问题。首先将已有模型抽象化,将城市交通网络中每一个路口看做图中的结点;对于相邻路口间的道路将其视作边。

所建立的无向图记为G=(V,E),其中V 中的元素即所有路口的代号,称为节点,E 中元素称为边,且与V 中一对元素相连。

2.2 各边权值的确立

首先要将各条道路的距离计算出来,即抽象化图中各边的权值,设权值矩阵为w。计算公式如下:

式中,(xi,yi)表示第i 个路口的坐标,wij即表示路径i↔j 的权值,即i,j 两个路口间的距离。

2.3 最短距离法分配管辖范围

最优的平台分配方案是所有交叉节点到管辖其的服务平台所用路程之和应最小。设各路口到各交巡警平台的路径长度为dij,i∈[1,20],设D 为所有交叉节点到隶属的服务平台之间的路程之和。设Dij表示各路口节点与其对应的最近服务平台之间的距离,对于每个k 值仅有唯一的i 值与之对应。因此目标函数为:

DT表示最短路径的总和且xij≥0。

建立的线性规划问题模型为:

基于以上模型,采用最短路径法求解各警务平台的管辖范围,算法如下:

1)找出第a 个路口到所有平台的最短路径

将第a 个路口作为起始点,将所有的交巡警服务平台作为终点,求解各个路口到所有服务平台的最短路径,采用Dijkstra 算法。

Step 1 将所求最短路径的路口设为结点a,集合S={1,2,…,92}表示所有的92 个结点。

Step 2 建立最短路径数组d。令路口到自己的权值da(a)=0;若路口a 与第i 个结点之间不存在边,则令da(i)=+∞;若路口a 与第i 个结点之间存在边,则令da(i)=Wa→i。其中Wa→i表示路口a 到i 的权值,即距离。

Step 3 在S 中,令da(j)=min{da(i),i∈S},令S=S-{j}。若S 为空集,则算法结束,否则进行Step4。

Step 4 对所有的其他路口i∈S,如果存在边j→i,那么令最短距离da(i)=min{da(i),da(j)+Wj→i},之后返回Step3,直至找出最短路径da(i)。

经过上述步骤,可以求得第a 个路口到所有其余路口的最短路径,再由a 到其余路口的最短路径中选出第a 个路口到所有服务平台的最短路径集合Wa↔k。

2)确定距离第a 个路口最近的平台

在Step 1 确定最短路径后,找出该路口到这20 个平台距离中的最小值,即离路口最近的平台。则第i 个路口所属的管辖主导为离其距离最短的平台。

3)求解所有路口所属的平台

重复第一步和第二步,直至求出所有路口所属的管辖范围,即其所属的服务平台。

2.4 计算结果

利用MATLAB 编程得到如表1 所示的结果。由表分析可得,每个路口均分别被分配到距离该路口最近的交巡警平台。

表1 交巡警服务平台管辖范围结果

上表中的数据进行归类,可以将每个路口点所管辖的范围以路口的形式表现出来,夹在相邻路口间的路线亦属于该巡警服务平台的管辖范围。对于相邻平台管辖边界之间夹的路段,将其分作两半划归为相邻的两个平台的管辖区域。表中未列出的0 至20 号路口均归属于其本身。

将归类后的数据用MATLAB 绘图如图2 所示。

图2 各服务平台管辖的路段范围示意图

3 重大事件路段最优封锁方案

建立邻接矩阵T={tij|i,j∈[1,92]},其中tij表示编号为i 的路口到编号为j 的路口所需的最小时间。i∈{12,14,16,21,22,23,24,28,29,30,38,48,62},即i 表示出入A 区的路口标号。j∈[1,20],即j 表示A 区各交巡警服务平台的路径标号。

3.1 最优封锁模型

需要遵循以下原则:

1)一个平台的警力最多封锁一个路口。

2)自开始行动至所有出入路口均被封锁时,所经历时间应尽可能小。

3)仅考虑当13 个进出口均被封锁时的耗时,而不是考虑如何使20 个平台均分配至进出路口。

在建立得到邻接矩阵T 后,设立Ti(k)以此来表示第i个交巡警平台到编号为k 的出入口的距离,由此目标函数即为:

其中,xik表示第i 个交巡警平台与编号为k 的出入口的0-1 权值,以此表示第i 个交巡警平台的警力是否分配到编号为k 的出入口。

Ti(k)由各平台到出入口的时间中的最小值决定,与此同时,由于编号为k 的节点并非所有节点,根据这两个条件,得到约束条件如下:

建立的模型为:

3.2 模型求解过程

具体求解步骤如下:

1)找出第a 个进出该区要道路口到所有交巡警服务平台的最短时间tij

求解各个服务平台到进出路口的最短时间时,同样采用Dijkstra 算法进行求解,算法步骤与最短路径法求解一致。

2)确定第a 个服务平台最近的进出路口

设立Ta(k)代表第a 个进出口最短时间集合Ta↔k中最小的数值,即适应于各进出路口的最优选择。

3.3 交巡警最优封锁方案

利用LINGO 求解,仅需8.016 min 可完成整个A 区的全封锁。具体调度方案如表2 所示。

表2 服务平台封锁出城口的最佳调度方案

图3 服务平台围堵城市出口的调度方案示意图

4 结论

绘制的调度方案如图3 所示,其中标有箭头的粗线即代表各警力分配点的调度路线。黑色粗箭头表示警务平台所言路径的封锁方向,旁边的编号对应于表2 中的路径编号。

按照上述方法解决了管辖范围分配问题并得出了最佳的调度方案。

[1]罗丽娅,唐洪,裴东海.交巡警合一警务体制改革探析[J].湖北警官学院学报,2014(5):10-13.

[2]谢彤.重庆市道路交通事故管理研究[D].重庆:重庆交通大学,2013.

[3]Thomas H.Cormen.算法导论[M].北京:机械工业出版社,2006.

[4]卢开澄,卢华明.图论及其应用[M].北京:清华大学出版社,1997.

[5]张福浩,刘纪平,李青元.基于Dijkstra 算法的一种最短路径优化算法[J].遥感信息,2004(2):38-41.

[6]于春田,李法朝.运筹学[M].北京:科学出版社,2006.

猜你喜欢
封锁权值警务
一种融合时间权值和用户行为序列的电影推荐模型
CONTENTS
《在被封锁的武汉,他运送的还有希望》新闻谈
基于权值动量的RBM加速学习算法研究
基于多维度特征权值动态更新的用户推荐模型研究
HIV感染的警务预防与处置
警务训练中腹痛的成因及预防
警务实战训练教学中开设
警务指挥与战术研究现状及发展趋势
二战以来三次岛屿封锁作战的战略决策及启示