交巡警服务平台的设置与调度优秀论文.docx
- 文档编号:3479832
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:27
- 大小:84.65KB
交巡警服务平台的设置与调度优秀论文.docx
《交巡警服务平台的设置与调度优秀论文.docx》由会员分享,可在线阅读,更多相关《交巡警服务平台的设置与调度优秀论文.docx(27页珍藏版)》请在冰点文库上搜索。
交巡警服务平台的设置与调度优秀论文
交巡警服务平台的设置与调度(优秀论文)
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
B
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名):
参赛队员(打印并签名):
1.
2.
3.
指导教师或指导教师组负责人(打印并签名):
年月日
赛区评阅编号(由赛区组委会评阅前进行编号):
交巡警服务平台的设置与调度
摘要
本题主要讨论城市中的交巡警服务平台的设置和具体调度问题,在确定各平台管辖范围和增加平台的位置、数量等相关问题时,通过对已知条件中点的坐标,和相应道路信息,对已知条件进行合理的处理,得到我们需要的数据,然后进一步进行分析,获得合理的设置与调度方案。
对于问题一:
1.1是关于A区中20个交巡警服务平台的分配管辖范围问题,首先求出相邻两路口节点之间的距离,建立92*92的邻接矩阵,然后在Matlab软件下采用Floyd算法求出任意两个点之间的最短距离,从中提取出92*20的矩阵,再引入0-1整型规划模型,最后建立以总路程最小为目标函数,以各个平台发案率均衡为约束条件,建立优化模型,最后使用Lingo编程实现区域的自动划分,最终求出A区各个服务台的管辖范围。
1.2是关于如何封锁A区中13个交通要道口问题,本文以“一个平台的警力最多封锁一个路口”为约束条件,以“最后到达的警力所花时间的最小值(时间转化为路程)”为目标函数,建立相关模型,求出最优解,最终的结果见表2;
1.3是要在原有平台数的基础上增加2—5个平台,以发案均衡量和出警时间
为约束条件,建立模型求出结果,再对结果进行分析适当的增减平台数使目标最
优,最终的求解结果见表3。
对于问题二:
2.1我们综合实际情况,把发案率,人口,路口节点数,管理面积作为交巡警服务平台的工作量的相关因子。
依据各因子对工作量的影响程度,赋予一定权值,建立评判函数,判断该市各区现有设置方案的合理性,得出c、d、f为不合理区域。
对不合理区域,需增加平台数,建立以增加平台数尽可能少,工作量尽可能均匀为目标建立了多目标非线性优化模型,进行合理分配。
2.2依据预处理距离,可以得到嫌疑犯在短时间内逃得最远距离,在保守的方案下可以确定一个相对全市较小,但又比较保守、可靠的围堵范围,以围堵时间最快为目标函数,建立0-1规化模型,得出最佳围捕方案。
关键词:
邻接矩阵、Floyd算法、最优解、0-1规化模型
一、问题重述
“有困难找警察”,是家喻户晓的一句流行语。
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
为了更有效地贯彻实施这些职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的,如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
已知某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问题:
(1)由该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图,以及相关的数据信息,为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。
对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口,给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加2至5个平台,确定需要增加平台的具体个数和位置。
(2)针对全市(主城六区A,B,C,D,E,F)的具体情况,按照设置交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案的合理性。
如果有明显不合理,给出解决方案。
如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯,给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二、问题分析
此题是研究交巡警的合理分配和调度的数学建模问题。
需要我们通过建立合理的数学模型,进行多目标优化,对交巡警进行合理的分配。
对于问题一:
1.1本问主要解决的是A区每个交巡警服务平台的管辖范围,也就是每个节点归哪个交巡警服务平台管辖的问题。
因为每个交巡警服务平台的职能和警力配备基本相同,所以要考虑每个平台工作量的均衡下能在最短时间内到达突发事件现场,主要考虑的方向是各个平台管辖范围内的总的时间最短(最短时间可转化为出警的最短路程)与均衡每个平台的发案率这两个因素,显然,这是个双目标问题,为了方便求解,把双目标函数单一化,将各个平台发案率的均衡转化为约束条件建立模型,进而划分出区域。
其中,我们引入了0-1规划模型,采用了Floyd算法求出图中任意两个站点之间的最短距离,再根据所建立的模型划分出具体区
1.2本问主要解决的是在最短时间内封锁13个交通要道的问题,也就要求从20个交巡警平台中找出13个平台用最短时间去封锁交通要道。
由题目可以知道当A区重大突发事件时,需要调度全区20个交巡警服务平台的警力资源,现有20个交巡警服务平台的警务资源可供调度,且一个平台的警力最多只能封锁一个路口。
为此我们采用以到达路口时最长的为标准(时间可以转内化为路程),建立目标函数为该标准最小,即最大距离最小化问题,以一个平台的警力最多封锁一个路口为约束条件的模型。
利用Lingo编程从而得出该去交巡警服务平台警力合理的调度方案。
1.3本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。
这是一个典型的优化问题,由题目以及第一问可以知道A区交巡警服务平台分布不均匀以及有没能在题目要求下受到管辖的节点,因此,我们考虑到发案率、距离、与其它平台的覆盖率、人口密度,按照重要的程度不同,经过调研后假设它们各自的权值,然后将各自发案率、距离、与其它平台的覆盖率、人口密度分别乘以相应的权值,综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域,即各个交巡警服务平台所管辖的节点,最后可以得到交巡警服务平台以及相应添加的平台。
对于问题二:
2.1在这个问题中,我们基于统计基理分析,对全市进行分区分析,统计出与工作相关的一些因素,建立了以各个交巡警平台管辖的面积、人口、节点数以及各个区的总发案率为变量的评判函数,判断出各个区域的合理性,对不合理的区域进行优化,并给出合理的解决方案。
2.2我们基于保守方案的分析,当警方接到报案后,不考虑反应时间,立即对逃犯进行封堵。
基于floyd的数理统计,计算出p点距全市各个路口的最小距离,确定一个保守的可靠相对较小的围堵范围,类似于问题1.2建立的优化模型用lingo软件编程得到最好的围堵方案。
三、模型假设
1、假设警车在出警时的速度恒为60km/h,且不会出现故障问题;
2、假设在接到报案后,准备时间为0,即直接出发。
;
3、假设在发生案件时交巡警都是从平台处出发的,不考虑在远离案发点的节
点或路段出发;
4、假设犯罪嫌疑人的逃逸速度不大于60km/h;
5、所有交巡警服务平台的配置是基本相同的;
6、假设两个节点之间的路径为两点间的直线距离;
7、假设每个路段道路畅通,可以双向行驶,没有堵车现象。
四、符号说明
i:
全市第i个路口节点
j:
第j个交巡警服务平台
k:
第k个出入市区的路口节点
:
表示第i个路口的发案率
:
第i个路口节点到第j个交巡警服务平台的最短距离
v:
犯罪嫌疑人的车速
:
第j个城区所需的平台个数(j=1,2,3,4,5,6)
r:
每个区的路口总数
五、模型的建立及求解
问题一
1.1、Floyd算法原理与步骤
1、邻接矩阵
根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图,及相关的数据信息,将路口节点看为图中的顶点
,构造图形的邻接矩阵A=(
),其中
是连接图中顶点
与
边的数目。
用MATLAB编程(代码见附录一)运算得图形的邻接矩阵A=(
)
2、边权矩阵
对图中连接相邻顶点
与
的每一条边,用欧氏距离
作为边权值,用MATLAB编程(代码见附录二)运算得边权矩阵D=
。
3、Floyd算法
取图的边权矩阵D=
,进行n(n=92)次更新,按递推公式,构造出矩阵
;又用同样地公式由
构造出
;最后用同样的公式由
构造出矩阵
。
矩阵
=(
)=(
)的i行j列元素便是顶点
与
的最短路径长度,称
为图的距离矩阵,具体算法如下:
步骤1:
令k=0,输入边权矩阵
步骤2:
令k=k+1,计算
k=1,2,3,…()式中
步骤3:
如果k=n,终止算法;否则,返回步骤2,上述算法的最终结果
中元素
就是从顶点
与
的最短路程,计算结果运用MATLAB(代码见附录三)可求得最短路矩阵
。
优化后的92个节点到20个交巡警服务平台的最短距离列表如下:
表1最短距离矩阵
节点
距离
平台
节点
距离
平台
节点
距离
平台
1
0
1
25
17.889
12
49
5
5
2
0
2
26
9
11
50
8.4853
5
3
0
3
27
16.433
11
51
12.293
5
4
0
4
28
47.518
15
52
16.594
5
5
0
5
29
57.005
15
53
11.708
5
6
0
6
30
5.831
7
54
22.709
3
7
0
7
31
20.557
9
55
12.659
3
8
0
8
32
11.402
7
56
20.837
5
9
0
9
33
8.2765
8
57
18.682
4
10
0
10
34
5.0249
9
58
23.019
5
11
0
11
35
4.2426
9
59
15.209
5
12
0
12
36
6.0828
16
60
17.392
4
13
0
13
37
11.182
16
61
41.902
7
14
0
14
38
34.059
16
62
3.5
4
15
0
15
39
36.822
2
63
10.308
4
16
0
16
40
19.144
2
64
19.363
4
17
0
17
41
8.5
17
65
15.24
3
18
0
18
42
9.8489
17
66
18.402
3
19
0
19
43
8
2
67
16.194
1
20
0
20
44
9.4868
2
68
12.071
1
21
27.083
13
45
10.951
9
69
5
1
22
9.0554
13
46
9.3005
8
70
8.6023
2
23
5
13
47
12.806
7
71
11.403
1
24
23.854
13
48
12.902
7
72
16.062
2
节点
距离
平台
73
10.296
1
74
6.265
1
75
9.3005
1
76
12.836
1
77
9.8489
19
78
6.4031
1
79
4.4721
19
80
8.0632
8
81
6.708
18
82
10.79
18
83
5.385
18
84
11.75
20
85
4.472
20
86
3.606
20
87
14.65
20
88
12.95
20
89
9.487
20
90
13.02
20
91
15.99
20
92
36.01
20
4、管辖范围的确定
本文的覆盖半径用距离来表示,因为应急限制期限定在3min之内,结合警车的速度及地图的比例尺转化为图上距离30mm。
目标是使各服务平台在服务时间最短的前提下,覆盖所有可能的事发地点,并且每个可能事发地点都要求有且只有一个服务平台对其服务。
建立模型如下:
目标函数:
约束条件:
上式中
表示第j个节点是否属于第i个交巡警服务平台的管辖范围,如果属于则
=1,否则
=0;约束条件
表示第j个节点必须属于某一交巡警平台管辖范围。
通过模型的建立及lingo编程(代码见附录四)求解可知,A区每个交巡警服务平台的管辖范围划分结果最优如下表:
表2各服务台管辖范围
交巡警服务台编号
管辖区域
1
1686971737475
2
240437072
3
34454556567
4
45760626364
5
5495051525356
6
65859
7
730474861
8
8323346
9
93545
10
103134
11
112627
12
122425
13
1323
14
142122
15
152829
16
1636373839
17
17414292
18
18818283849091
19
197677787980
20
208586878889
在路程已知的基础上,可以求得28、29、38、39、61、92号节点到各自最近的巡警服务台的时间是超过3分钟的。
1.2、
本问要求调度20个交巡警服务平台的警力资源,对进出的13条交通要道实现快速全封锁,且一个平台的警力最多封锁一个路口,所以要求最后一个到达的应该最小,因此,建立模型如下(程序见附录五):
目标函数:
约束条件:
=1代表第j个服务平台到第k个出入市区的路口节点;
=0代表第j个服务平台不到第k个出入市区的路口节点;其中j=1,2,……20;k=1,2,……13。
由lingo编程可得,计算结果经整理如下表所示:
表3调度方案
交通要道路口
12
14
16
21
22
23
24
28
23
30
38
48
62
需要调动的平台
13
16
3
14
10
12
11
15
7
5、
6、8
1、2
4、9
17、18、19
1.3、
该题是要求在原有平台的基础上增加2至5个,使得改变现有的平台工作量
不均衡,时间过长的实际情况,该模型可描述为:
在一个有N个节点的道路网络中,从M个备选的节点中选取p个节点建立设施,在一定约束条件下使得目标函数最大或者最小,因此我们既要考虑时间(路程),又要考虑发案率,从而建立模型如下:
目标函数:
约束条件:
当
=0时,
,否则为
。
增加五个平台,由lingo程序(代码见附录六)求解知,其标号与坐标如下表:
表4
服务平台
横坐标:
X
纵坐标:
Y
28
243
328
29
246
337
39
371
333
61
335
395
92
444
360
问题二
2.1、
由题目中所提供的全市六区交通网与平台设置的数据可知,全市六区的警务平台都分布在各区的案发率较高的路口上,以达到缩短出警时间的目的,这一点是合理的,在对各区人口数、面积、平台数、分点个数,进行统计分析得到如下结果如下表所示:
表4
区域
A
B
C
D
E
F
平均值
人口(万人)
60
21
49
73
76
53
55.33
交巡警平台个数
20
8
17
9
15
11
13.33
节点数
92
73
154
52
103
108
97
面积(平方公里)
22
103
221
383
432
274
239.17
发案率之和(次数)
124.5
66.4
187.2
67.8
119.4
109.2
112.41
各平台管理的平均人数
3
2.62
2.88
8.11
5.0
4.8
4.41
各平台管辖范围的平均面积
1.1
12.8
13
42.55
28.8
24.90
20.53
各平台管辖的平均节点
4.6
9.1
9.29
5.77
6.86
9.81
7.54
各平台平均处理案件量
6.22
8.3
11.01
7.53
7.96
9.92
8.49
在此建立多目标判定函数:
y=β1*x1+β2*x2+β3*x3+β4*x4
其中x1变量为各平台管理的平均人数,x2为各平台管辖范围的平均面积,x3为各平台管辖的平均节点,x4为各平台平均处理案件量。
基于模糊原理,不妨将各目标变量的权重定位β1=β2=β3=β4=1,得出判定结果如下表:
(精确到小数点后三位)
表5
A
B
C
D
E
F
平均值
目标函数值
14.925
32.925
35.953
63.978
48.693
49.473
40.991
由上表可发现,D、E、F三区的判定函数值都偏高于全市平均判定函数值,该三区的警务平台分配存在不合理,依据警务平台到各节点的时间最短为目标函数,由问题
(一)所建立的模型得各警务平台的管辖范围(表6)。
该表表明三区平台分配不合理主要由于个别警务平台的任务分配不均衡,任务量大。
对此本文采用增加警务平台的解决方案,由问题(1.3)所建立的多目标优化模型,得到优化结果为:
D、E、F分别增加1个,2个,3个平台数,其位置分别为353,408,463,403,421,456号节点。
表6优化分配表
D区优化前后的对比
优化前
优化后
交巡警平台
处理的路口
交巡警平台
处理的路口
320
6
320
6
321
12
321
8
322
1
322
1
323
4
323
4
324
4
324
4
325
0
325
3
326
2
326
1
327
5
327
5
328
9
328
6
353
4
E区优化前后的对比
优化前
优化后
交巡警平台
处理的路口
交巡警平台
处理的路口
372
0
372
1
373
3
373
3
374
7
374
7
375
7
375
7
376
0
376
1
377
1
377
2
378
2
378
2
379
7
379
7
380
10
380
8
382
13
382
5
383
11
383
3
384
6
384
5
385
8
385
6
386
7
386
7
408
7
463
8
F区优化前后的对比
优化前
优化后
交巡警平台
处理的路口
交巡警平台
处理的路口
475
11
475
7
476
12
476
10
477
28
477
12
478
14
478
6
479
9
479
9
480
6
480
6
481
6
481
6
482
4
482
6
483
2
483
2
484
3
484
4
485
2
485
2
403
7
421
13
456
3
由上表的优化前后的对比可发现:
优化后的各交巡警平台的任务量、出警时间基本达到均衡,所以该模型是切实可行的。
2.2、
根据假设,我们取犯罪嫌疑人的逃逸速度最大等于60km/h.由于案发地32号节点距离出入A区的30号、48号、16号路口的距离分别为1.7、2.4、3.3分钟的车程,所以该嫌犯在案发3分钟后有逃出A区的可能,为了达到快速搜捕嫌犯的目的,围堵的范围越小越好。
在巡警接警后嫌犯只可能在A、C、F三区,所以将A、C、F三区定位最终围捕范围。
出入A、C、F三区的路口节点号分别为12、14、21、23、24、28、29、177、202、203、248、264、317、483、541、572、578这十八个节点。
由问题(1.2)所给出的模型以及在已知路程的基础上可以求出相应的到达时间,应用lingo软件编程得最佳围捕方案如下表:
表7
序号
围堵节点
到达时间
12
12
0
14
14
0
372
21
2.51867
11
23
4.6751
13
24
2.38537
15
28
4.75184
173
29
7.92872
175
177
9.02130
177
202
6.4609
178
203
4.44777
167
248
3.67875
166
264
6.62234
181
317
5.47516
483
483
0
481
486
3.94653
484
541
7.04178
485
572
1.65529
479
578
5.75752
由上表可知到达封锁地点的时间是9.02分钟,而案发后嫌犯21号节点最快逃出A、E、F三区最短时间为13.3分钟,所以该围堵方案是合理的。
六、模型评价与改
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 巡警 服务 平台 设置 调度 优秀论文