B交巡警服务平台的设置与调度.docx
- 文档编号:14426794
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:42
- 大小:176.45KB
B交巡警服务平台的设置与调度.docx
《B交巡警服务平台的设置与调度.docx》由会员分享,可在线阅读,更多相关《B交巡警服务平台的设置与调度.docx(42页珍藏版)》请在冰点文库上搜索。
B交巡警服务平台的设置与调度
平顶山学院
数
学
建
模
比
赛
论
文
组员:
刘佳
刘豪
黄文涛
交巡警服务平台的设置与调度
摘要
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
本题根据已有的数据讨论了如何设置交巡警服务平台、各平台的管辖范围以及警务资源调度问题。
问题一
(1)、关于平台的分配管辖问题,根据题目中给出的每个相邻点的坐标,通过C++编程算出相邻两路口之间的距离。
再通过FLOYD算法求出任意两点之间的最短距离得出92*92的矩阵,从中提取92*20的矩阵。
再引入以三分钟到达为原则进行区域划分。
(2)、以“一个平台只能封锁一个出入口”为约束条件,因此直接封锁3个有交巡警服务平台的出入口。
另外的10个交通要道采用快速分配法通过编程先分配一个平台,剩余7个服务平台采用最短路原则分到各个路口,最终得出实现全封锁的最短时间为13.67分钟。
封锁出入口分配结果如下表:
封锁对应出入口的平台
路口
21
22
23
24
28
29
30
38
48
62
16
12
14
平台
13
11
10
9
15
6
8
7
20
1
2
5
18
34
1619
12
1417
(3)、是要在原有平台的基础上增加2-5个,以案发均衡量和出警时间为约束条件,建立模型求出结果,再对结果进行分析适当的增减平台,通过综合比较分析最终计算出分别在21、29、39、48、87节点处分别增加一个交巡警服务平台。
问题二
(1)、运用问题一的模型,计算出其余5个区的各个平台的工作量,再结合spss软件计算出方差和标准差,通过比较方差的大小找出分配不合理的区域,调整增加平台的个数,最终得出调整方案。
比较调整前后的工作量得出验证方案的可行性。
(2)首先把A区与其他城区相连的接口封住,然后通过时间步长确定最快的围堵方案,再根据一个平台只能封锁一个路口的原则,尽量缩短搜捕范围,最终得出在7.8min内可将嫌疑犯捕获。
关键字:
Floyd算法快速分配法时间步长法
目录
一、问题重述3
1.1背景分析3
1.2问题的提出3
二、问题分析3
2.1问题一分析3
2.2问题二分析4
三、模型假设4
四、符号说明4
五、模型的建立与求解5
5.1模型一的建立与求解5
5.1.1Floyd算法原理5
5.1.2基本模型的建立与求解5
5.1.3快速封锁的实现7
5.1.4新增加服务平台的分配8
5.2模型二的建立与求解11
5.2.1六区巡警平台的方案合理性的检验与改进11
5.2.2最佳围堵方案15
六、模型的评价与推广17
6.1模型的评价17
6.1.1模型的优点17
6.1.2模型的缺点17
6.2模型的推广17
七、参考文献17
八、附录18
附录一:
求任意相邻两点距离c++源程序(此处只给出A区的)18
附录二:
最佳围堵方案求解程序20
附录三:
增加的服务平台后各个交巡警服务平台的管辖节点23
一、问题重述
1.1背景分析
为了更有效地贯彻实施“有困难找警察”职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的,根据城市的实际情况与需求就合理调度警务资源、管辖范围设置、交巡警服务平台分配提出了以下问题。
1.2问题的提出
问题一
1、根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况及相关的数据信息。
请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。
2、对于重大突发事件,如何调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。
(一个平台的警力最多封锁一个路口)
3、由于现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加2至5个平台,请确定需要增加平台的具体个数和位置。
问题二
1、针对全市(主城六区A,B,C,D,E,F)的具体情况,按照设置交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案(参见附件)的合理性。
如果有明显不合理,请给出解决方案。
2、如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯,请给最佳围堵方案。
二、问题分析
2.1问题一分析
(1)、为了保证交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警到达事发地,就要求得各交巡警服务平台三分钟内所能到达的平台数,将其归属为对应的平台管辖。
根据题目中给出的每个相邻点的坐标,通过C++编程算出相邻两路口之间的距离。
再通过FLOYD算法求出任意两点之间的最短距离得出92*92的矩阵,从中提取92*20的矩阵。
以三分钟到达为原则进行区域划分。
(2)、当重大事故发生时,需封锁13条交通要到,而实际中每个平台的警力只能最多只能封锁一个路口,而从图中可以看出有些平台本身就设在了路口,即该路口就可由该平台直接封锁住,题中要求实现快速全封锁,所以以最后一个封锁节口的时间,作为全封锁的时间。
先利用matlab数学软件,求出除去本身设有平台的3个出路口,剩下所有出入口中,最后一个出入口被封锁的时间即为该封锁方案的封锁时间,再比较每种封锁方案的时间大小,选取时间最少的,就是我们选取的快速全封锁的方案。
(3)、考虑到实际情况,我们根据3分钟内赶到案发现场及工作量最小原则增加2-5个平台。
根据任务一中的分配结果,其中28,29,38,39,61,92这六个节点,任何一个服务台都不能在3分钟之内到达,而10平台工作量过于小,1、7、13、18、20这五个平台工作量相对较大。
添加的平台需要改进这些问题。
2.2问题二分析
(1)、分析研究该市现有交巡服务平台设置方案的合理性,要判断是否合理,我们必须遵循设置平台的原则和任务。
根据实际情况一般各城区的服务平台管辖本所在城区,但当有重大刑事案件时应全力配合搜捕嫌疑犯。
据此我们先将主城区的六个区单独分析,根据各个城区的平均工作量和方差来衡量,分配的是否合理。
再把六个城区综合起来比较,验证其设置的合理性,假如不合理则根据交巡服务台的原则和任务,增加或减少服务平台使得设置的服务平台更加合理。
(2)、若地点P出发生刑事案件,3分钟之后才接到报警,犯罪嫌疑人已驾车逃跑,则须调度全市的交巡警服务平台的警力快速搜索疑犯。
基于此种情况,首先应确定疑犯逃跑的大致范围,在范围之内则派附近的警力沿各个方向去追捕,在范围之外则封锁各个路口。
为了不要扩大范围,应最快封锁进入其他城区的入。
三、模型假设
(1)相邻两个节点之间的道路近似认为是直线。
(2)服务平台接到报警后准备时间忽略不计。
(3)警车的速度保持固定,为60km/h。
(4)路段上不发生案件。
(5)假设每个路段道路都是畅通的,不会出现堵车现象。
四、符号说明
(1)
表示接警后的最大距离
(2)
表示第
个节点案发率
(3)
表示警车的平均行驶速度
(4)
表示往返案发现场所用的时间
(5)
表示各节点到每个服务平台的最短距离
(6)
表示第j个平台与第i个路口的距离
(7)
表示处理每个案发时间所需要的时间
五、模型的建立与求解
5.1模型一的建立与求解
5.1.1Floyd算法原理
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵
开始,递归地进行n次更新,即由矩阵
,按一个公式,构造出矩阵
;又用同样地公式由
构造出
;……;最后又用同样的公式由
构造出矩阵
。
矩阵
的i行
列元素便是
号顶点到
号顶点的最短路径长度,称
为所有点对的最短距离矩阵。
由于问题还要考虑工作量的分配,其中工作量
我们用办公时间来衡量,其中办公时间分为来回案发现场的时间
也就是去案发现场的两倍,以及每天处理案件的时间,即案发率
×平均每个案件花费的时间
。
工作量模型:
5.1.2基本模型的建立与求解
首先我们利用弗洛伊德算法算出各个点之间的最短距离,得到一个
的上三角矩阵,由于路径具有双向性,所以原图的距离矩阵是对称的,将所求得的矩阵对折得到原图的距离矩阵A。
题目要求警车在接警后三分钟内赶到,警车在接警后的平均行驶速度为
,接警后的最大距离为:
经过点在图中标出(如图一),可知前二十各节点刚好设置了服务平台,及前二十个节点应属于各自服务平台管制所以以下分析我们将不考虑前二十点。
对距离矩阵A做以下处理:
(1)前二十行去掉且留下前二十列;
(2)矩阵A的对角线元素取值为0;
(3)矩阵A中令每一行中最小的且小于3
的为保持不变;
(4)其余各点均取0;
得到处理后的0-1矩阵
其中:
表示
节点属于
服务平台管辖范围内;
表示警车从
节点不属于
服务平台管辖范围内。
对问题的求解就可转化成线性规划问题,我们的目标函数就是要使得各服务平台到各节点的最短距离,即所需时间最短。
而题目中的约束条件不仅要求警车在接警后三分钟之内要赶到现场。
由于计算机的局限性,要同时满足这两个条件是比较困难的,甚至是无法实现的。
为此我们先考虑全部的警车尽可能在三分钟之内赶到案发现场的情况。
同时假设所有的点都能够满足这一条件,在这种假设条件下,每一个节点都尽可能被覆盖。
基于以上分析,我们建立如下的基本模型:
目标函数:
通过SPSS得到各服务平台所管辖的节点,结果如下表所示:
表5-1A区各服务平台所管辖的节点
平台号
1
2
3
4
5
6
7
8
9
10
节点号
169687172737475
239
40434470
3
5455656667
4
636462576076
5
4953515256
6505859
7
30474861
8
323346
93435
45
10
工作量
140.15
121.41
114.33
131.35
112.29
93.99
138.25
103.69
110.02
24
平台号
11
12
13
14
15
16
17
18
19
20
节点号
112627
1225
1321222324
14
15282931
16363837
174142
18818283899084
1977798078
20888785869192
工作量
74.08
63.58
140.50
75
122.84
111.66
86.58
144.17
81.89
140.89
5.1.3快速封锁的实现
由问题分析中我们已经提到,我们可假设已有交巡警平台的路口直接由所在平台去封锁,剩下10个路口,先分配10个交巡警服务平台,多余7个之后再按最短距离分配到任意7个路口,加强封锁力度。
这里的封锁时间为:
最后一个出入口封锁住所花费的时间。
模型建立与求解
主要思路:
从17个平台中选取10个平台分配到10个路口,要使得其封锁住时的时间最小。
这里介绍一种快速分配法:
步骤1:
(1)、计算每个平台到每个路口的最短路径,形成距离矩阵
其中
表示第
个平台到第
路口的距离。
(2)、从
中选取最小的值
,即表示第第
个平台分配到第
路口
(3)、
所在的行列的所有值赋为
。
(4)、是否所有路口都分配了平台?
是,结束;否,返回步骤
(2)。
上述步骤结束后,得到一个分配方案,这个方案显然不是最优的,需要逆向修正。
具体步骤如下:
步骤2:
(1)、寻找已得到分配方案中的最大距离
,在原始的距离矩阵中,将所有大于
的值赋为
。
(2)、在
所在行中,寻找最小的距离
,将
代替
。
(3)将
中的第
行第
列赋为
,新矩阵
重复步骤1,得到新的分配方案,如果新的分配方案的最大距离没有降低,则认为已找到最佳方案;没有重复步骤
(2)。
通过编程得到10个服务台分别分到10个路口的方案如下表:
表5-210个服务台分配到10个路口的方案
路口
21
22
23
24
28
29
30
38
48
62
平台
13
11
10
9
15
8
7
2
5
4
距离km
2.708
7.096
11.13
13.668
4.752
10.49
0.583
3.982
2.476
0.35
由表5-2可知13个路口全部封锁住至少需13.668分钟
为了加强警力,我们根据最短路径原则,结合matlab将剩余的7个平台分配到任意路口,得到的较优方案如下表:
表5-317个服务台分配到10个路口的方案
路口
21
22
23
24
28
29
30
38
48
62
16
12
14
平台
13
11
10
9
15
6
8
7
20
1
2
5
18
34
1619
12
1417
5.1.4新增加服务平台的分配
根据问题分我们可根据尽量使各服务平台的工作量尽量平衡和各节点至少有一个服务平台能在案发3分钟之内赶到现场这两个原则来增加服务平台。
通过计算任务一中已分好的各区域的工作量,我们得到表一中的工作量并求得各交巡警服务平台的工作量的折线图如下:
图5-1A区每个服务平台的工作量
其中平均工作量=106.5341标准差=31.62084变异系数=1.128052。
由第一问分析可知,28、29、38、39、61、92这六个节点内发生突发事件,任何一个服务台都不能在3分钟之内赶到现场,这样会影响办事效率。
而根据上图我们可知10平台工作量过于小,1、7、13、18、20这五个平台工作量相对较大。
设置交巡平台为的就是使人们的安全系数得到提高,所以我们应尽量使得各节点有平台3分钟之内能到达,即根据这个原则,我们可知在28、29、38、39、61、92附近分别设置一个服务平台,同样应考虑要提高警察的工作效率,我们应尽量在发案率高的地方和能管辖的区域尽量大的地方设置平台。
综合这些要求进行数据分析我们分别在29、48、39、87处各设置一个交巡服务平台。
当然加了服务平台附近的服务平台的工作量可能会减小。
由此我们根据任务一方法,我们得到各服务平台所管辖的各个节点如下表:
表5-4增加5个平台后,各服务平台所管辖的节点
平台号
1
2
3
4
5
6
7
8
9
10
增加29
增加87
节点号
16968
71737475
2434470
72
35455656667
46364625760
54953515256
6505859
7304732
83346
93435
45
10
2829
87928891
工作量
124.87
95.22
114.33
112.85
112.29
93.99
122.46
78.52
110.02
24
42.4
63.85
平台号
11
12
13
14
15
16
17
18
19
20
增加48
增加39
节点号
112627
1225
1321222324
14
15
31
163637
174142
1881828390
197779787680
2085868489
4861
3839
工作量
74.09
63.58
126.5
37.5
61.44
111.66
86.58
115.27
82.96
111.81
35.8
63.85
为了直观好分析,我们将各区域的工作量用折线图表示且如下图所示:
图5-2增加4个平台后A区每个服务平台的工作量
其中平均工作量=86.28757875标准差=31.14712891。
经过添加平台后,平均工作量和方差有明显的减小。
说明添加后是平台的分配更加的合理。
由上图可看出1、7、13的工作量还是比较大,而10、14、29、39、48、47的工作量比较小是因为这两个节点和其他节点离得较远,不符合3分钟原则,导致其工作量相对比较小。
再考虑1、7、13工作量的大小和各服务台的离散程度即遇到突发重大案件时更加有利于封口,我们选择在21点再增设一个服务平台,则13号平台只需管13、22、23、24其余两点由21管,其它服务平台不变。
由此得出的工作量的折线图如下:
图5-3增加5个平台后A区每个服务平台的工作量
由于受距离的限制,我们可撇开10、11、12、14、15、21、29、39、48、87来看,我们会发现其他相对节点比较密集的区域内的平台工作量相对分配比较均衡,则此种增加平台的方案是比较合理的,较符合设置平台的原则和任务。
5.2模型二的建立与求解
根据问题分析,我们将该城市分解成6个城区,即在问题一的基础上增加了5个城区,根据交巡警服务平台的原则与任务,通过以下步骤来判断平台设置方案的合理性。
步骤1:
首先用Matlab将附图2按城区划分,提炼出六个城区的各自的交通网络和现有的服务平台设置的示意图。
步骤2:
判断各城区之间的服务台的数量是否合理
步骤3:
若步骤2判断不合理,则对其进行修正;若合理,再根据第一问的方法分析其它五个城区交巡服务平台的分布情况,判断各城区内部服务台的工作分配的合理性,不合理则对不合理的城区进行调整。
5.2.1六区巡警平台的方案合理性的检验与改进
根据第一问的模型,用floyd算法求出B,C,D,E,F五个区域任意两点之间的最小距离,算出每个交巡警服务平台所管辖的节点,节点安排分布可见附录。
每个交巡警服务平台的工作量如下表所示:
表5-5其余5个区各个交巡警服务平台的工作量
B
C
D
E
F
平台
工作量
平台
工作量
平台
工作量
平台
工作量
平台
工作量
93
110.55
166
128.41
320
205.63
372
36.00
475
279.07
94
461.84
167
258.23
321
229.69
373
137.11
476
238.59
95
299.28
168
84.03
322
69.40
374
95.55
477
426.80
96
433.70
169
55.44
323
112.37
375
100.96
478
324.41
97
125.06
170
213.18
324
126.32
376
39.00
479
221.23
98
325.10
171
287.27
325
33
377
68.65
480
144.53
99
140.42
172
132.85
326
82.90
378
92.90
481
152.57
100
78.92
173
267.36
327
143.80
379
259.27
482
127.74
180
537.08
328
274.45
380
293.53
483
83.41
181
163.57
381
106.71
484
105.86
182
339.97
382
287.93
485
58.71
383
259.32
384
174.33
385
254.71
386
143.71
根据表中的数据求出各个区域的方差与平均数的大小:
表5-66个区域的标准差与平均值
区域
平均
方差
A
106.5341
31.62084
B
246.8653
152.5691
C
217.1063
120.0445
D
141.9552
79.887
E
156.6494
91.44017
F
196.6338
113.1134
从表中的数据可以看出,每个区域的方差都比较大,而且存在部分的交巡警服务平台无法在3分钟到达案发节点,所以可以看出全市各个区域的交巡警服务平台存在不合理性。
对于以上不合理得安排,本文根据第一问增加交巡警服务平台的标准,对每个区域增加交巡警服务平台,考虑到接警后3分钟赶到案发节点,本文以3分钟赶到案发现场的覆盖率达到100%作为首要条件,接着考虑最短路径问题。
根据以上的条件约束。
增加的服务平台后各个交巡警服务平台的管辖节点可见附录。
表5-7其余5个区增加交巡警服务平台的分布
区域
B
C
D
E
F
增加平台的编号
122123124
183184185
258267
571
390392458
459464
487504509
512517
增加服务平台后,各个服务平台的工作量的分布如下表所示:
表5-8增加服务平台后,各个服务平台的工作量的分布
B
C
D
E
F
平台
工作量
平台
工作量
平台
工作量
平台
工作量
平台
工作量
93
76.05945
166
128.418
320
134.7926
372
36.000
475
279.0709
94
150.1158
167
258.2385
321
229.6999
373
101.111
476
223.1223
95
125.0562
168
84.03874
322
69.40000
374
73.42707
477
147.9372
96
197.5628
169
55.44072
323
112.3764
375
100.9617
478
181.4293
97
89.06213
170
213.1818
324
126.3237
376
39.0000
479
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 巡警 服务 平台 设置 调度