交巡警服务平台的设置与调度.docx
《交巡警服务平台的设置与调度.docx》由会员分享，可在线阅读，更多相关《交巡警服务平台的设置与调度.docx（39页珍藏版）》请在冰点文库上搜索。
交巡警服务平台的设置与调度
交巡警服务平台的设置与调度
交巡警服务平台的设置与调度
摘要
本文建立了交巡警服务平台设置与调度的优化模型，将出警时间和工作量作为考虑因素，设置城市交巡警服务平台，分配各平台的管辖范围，并在发生突发事件时对警务资源进行调度。
针对问题一的第一小问，根据出警时间的条件限制，初步确定城区A中20个服务平台对92个交叉路口节点的相应管辖范围，以交巡警服务平台的工作量方差最小为目标进行优化，使用lingo程序求解得到20个交巡警服务平台的管辖范围，工作量方差为2.9479。
对于第二小问，从全区20个交巡警服务平台中选取13个平台对全区13个交通要道实现了全封锁，以服务平台到达节点的最长时间最短为目标，用lingo求得封锁时间为8.015分钟，并给出了具体的封锁方案（即选定的13个交巡警服务平台与13个被封锁要道的一一对应关系）。
对于第三小问，由于存在工作量不平衡和出警时间过长的情况，以交巡警服务平台的工作量方差最小为目标，经分析至少需要增加4个平台（节点编号分别为29,39,48,91）才能满足出警时间限制，经lingo求解得到具体服务平台分配方案，且最小方差为1.99。
针对问题二的第一小问，在全市范围内，以出警时间限制和各服务平台均衡工作量为依据，使用lingo程序计算，得到工作量方差为27.21，且有138个节点不满足出警时间要求，可知现有交巡警服务平台设置方案是不合理的。
经lingo程序计算至少需要增加54服务平台才能使这138个节点满足出警时间要求，经优化使用lingo程序求得增加平台后的方差为5.098，明显优于原方案，此分配方案更加合理。
但是由于实际警力资源的限制，增加54个平台的个数相对较多，对此我们给出对现有警力配置，重新分布并适当增加平台数目的数学模型。
对于第二小问，该模型利用蚁群算法[1]的思想，通过matlab程序模拟犯罪嫌疑人的逃窜路线，文中定义了一个新名词，即封堵有效性，以此为依据，提出一个有效且合理的嫌犯围堵方案，并且对该方案进行了可行性分析和封堵有效性检验，结果显示该模型很好。
封堵有效性包括两方面：
一是封堵任务顺利完成，封堵圈无疏漏；二是确认犯罪嫌疑人仍在封堵圈之内。
关键字：
全局最优多目标规划方差封堵有效性
一、
问题重述
1.1问题引言
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。
由于警务资源是有限的，则需根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。
1.2题目所给信息
（1）该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图以及相关的数据信息；
（2）全市包括主城六区A，B，C，D，E，F；
（3）警车的时速为60km/h；
1.3需要解决的问题
（1）
为A城区20个交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。
对于重大突发事件，调度A区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。
（2）
按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。
如果有明显不合理，给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二、问题分析
根据城市的实际情况与需求，对城市交巡警服务平台进行分配，使其在发生突发事件时可以对警务资源及时合理的进行调度。
问题一，主要是对该市中心A城区的所有交巡警服务平台位置分布进行优化。
可分为三个问题：
1、根据城区A的20个交巡警服务平台以及92个交叉路口节点的分布情况，确定各交巡警服务平台的管辖范围。
由于出警时间存在限制，故需在满足时间条件的基础上，使92个交叉路口节点尽可能的分配给所有服务平台，同时必须满足一个节点只能由一个交巡警服务平台来管辖。
2、针对重大突发事件，要求合理调度城区A的20个交巡警服务平台警力资源对全区13条交通要道实现全面封锁，同时一个平台的警力最多封锁一个路口。
对此，问题可转化为，从20个交巡警服务平台中寻找13个平台对相应的13各交通要道进行封锁的问题，运用全局最优的规划方法使封锁时间最短。
3、根据现有交巡警服务平台的分布情况，由第一小问可知，存在总体工作量不均衡以及个别平台出警时间过长的情况，为此考虑增加2至5个平台，来处理该问题。
首要条件必须满足出警时间的限制，其次尽可能地均衡各平台的工作量。
问题二，对全市所有交巡警服务平台的位置分布进行优化。
可分为两个问题：
1、按照设置交巡警服务平台的原则和任务，从出警时间、工作量均衡两个方面进行考虑，分析该市现有交巡警服务平台设置方案的合理性。
如果不合理，可通过增加平台或移动平台处理该问题。
2、犯罪嫌疑人从P点开始逃窜，交巡警服务平台在三分钟后开始进行围堵。
对此，以P点为中心，犯罪嫌疑人3分钟所能逃窜的最大路程为基准向外辐射邻接节点，找出所有外层端点，所涵盖的范围即为犯罪嫌疑人可能到达的最大逃窜区域。
以该区域为基础，逐步分析该区域之外的相邻节点，判断该节点能否在第一时间被封锁，以此达到合围的目的。
三、模型假设
1、不考虑警务人员的拦截能力。
2、犯罪人员的驾车速度近似等于警车时速60km/h。
3、不考虑白天晚上时间与路况的区别。
4、警务人员出警时均从交巡警服务平台出发。
5、每个交巡警服务平台的职能和警力配备基本相同。
6、相邻两节点间的道路为直线。
四、符号说明
：
表示节点i的横纵坐标
：
交巡警服务平台的平均发案率
：
第i个交巡警服务平台的发案率
五、模型建立与求解
4.1模型I
4.1.1前期准备
（1）根据A区92个节点坐标，用matlab作出交通网络图（见程序1），如图1：
图1A区的交通网络与平台设置的示意图
其中图中实线表示市区道路；实圆点“·”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；星号“*”表示出入城区的路口节点；圆圈“○”表示现有交巡警服务平台的设置点；圆圈加星号“○*”表示在出入城区的路口处设置了交巡警服务平台。
（2）求出全市582个节点的距离矩阵
由附件2可得到582
582的0-1邻接矩阵
，其中
i=1，2…582，j=1，2…582
根据两点间距离计算公式：
和Floyd算法，通过matlab编程（见附录程序2，3）得到任意两节点间的距离。
4.1.2模型的建立与求解
通过分析可知，该问题的关键在于出警时间小于3分钟的情况下，对A区的20个服务平台确定其可管辖的范围。
（一）初步划分管辖范围
对于附表2中全市582个节点的距离矩阵，从中提取
的距离矩阵，其中92为A区中92个交叉路口节点，20为A区中的交巡警服务平台，截取前5个节点的距离矩阵如下表1：
表1A区部分交叉路口节点与服务平台距离（mm）
编号
1
2
3
4
5
6
7
1
0
18.98749
38.83884
45.35217
93.74289
95.37518
115.0035
2
18.98749
0
21.11654
56.85068
78.33711
98.42077
97.28119
3
38.83884
21.11654
0
40.43385
57.22058
77.30423
76.16465
4
45.35217
56.85068
40.43385
0
49.20044
50.02301
76.5669
5
93.74289
78.33711
57.22058
49.20044
0
29.42629
27.36647
编号
8
9
10
11
12
13
14
1
90.22625
92.25438
146.4957
190.8793
222.3615
220.0175
160.2847
2
72.50394
74.53207
128.7734
173.157
204.6392
201.03
141.2972
3
51.3874
53.41554
107.6568
152.0404
183.5227
187.4051
127.6723
4
83.27283
89.86668
144.108
188.4916
219.9738
209.8179
150.0851
5
35.35685
46.95427
100.4161
144.7997
176.2819
186.5506
129.6963
编号
15
16
17
18
19
20
1
142.4932
92.86812
35.91205
25.64572
17.58346
52.63199
2
124.7709
73.88063
25.91112
43.8476
36.57095
70.83387
3
103.6543
60.25566
47.02765
58.9491
41.94257
85.93536
4
114.7507
82.66853
74.70525
63.84362
46.83709
67.9888
5
65.55023
62.27967
104.2482
112.2343
95.22781
117.0395
警车时速60km/h，地图比例为1:
100000，即1mm对应100米，那么可将要求的出警时间3分钟，转化为行驶距离3km,使用地图比例尺换算成地图上的距离为30mm（以下可将时间与距离进行等价代换）。
若节点到平台的距离小于30mm，说明该节点在此服务平台的管辖范围内，记
=1，否则
=0。
定义：
i=1,2…92，j=1,2…20
通过matlab编程（见程序4），得到一个0-1矩阵
，即得到初步划分城区A各服务平台管辖范围。
（二）逐步优化管辖范围
通过对矩阵
数据观察可知，存在三种情况，节点仅对应一个服务平台，节点不在任何一个服务平台的管辖范围内和节点同时在多个服务平台管辖范围内的情况，易知第一种情况不需再对其进行优化。
下面针对剩下两种情况进行优化：
节点不在任何服务平台的管辖范围内
观察矩阵
的数据，其中节点28，29，38，39，61，92不在这20个平台中任一个平台的管辖范围内。
此时根据就近原则，筛选出距离每个节点路程最近的服务平台（见程序4），则该节点可视为在此服务平台的管辖范围内。
结果如下表3：
表2最短距离确定服务平台
节点标号
28
29
38
39
61
92
对应服务平台标号
15
15
16
2
7
20
节点同时在多个服务平台的管辖范围内
以均衡各服务平台的工作量为目标，求20个服务平台发案率的方差最小作为最终结果，对此情况进行优化，具体步骤如下：
第一：
根据矩阵
以及附件2中给出的各节点案发率，用matlab列出各节点的发案率矩阵，并求得平台的平均发案率
：
其中，
表示第i个节点的案发率，n为平台总数。
则平台的平均发案率
为6.225。
第二：
为平衡各平台的工作量，使平台发案率的方差最小，列出如下目标函数：
同时，对于矩阵
，仍需满足一个节点只能在一个平台的条件，如下式：
i=1，2……92
第三：
由以上对目标的分析，通过lingo编程可得最终服务平台分配方案（见程序5），如下表3：
表3交巡警服务平台分配方案
平台编号
管辖的节点编号
平台编号
管辖的节点编号
平台编号
管辖的节点编号
平台编号
管辖的节点编号
平台编号
管辖的节点编号
1
19，69,73,
75，77,79,
80
5
6,49,50,53,56
9
16,36,45，46
13
13,21,22,23,24
17
2,40,
41,42，72
2
1,3,17,39
6
4,48,51,52,58,59
10
10
14
14
18
83,84,85,87,88,90,91
3
43,44,
54，55,68,70,76
7
30,34,47,
61
11
11,26,27
15
15,28,29,
31
19
64,67,71,74,78,
81,82
4
4,57,60,62,63,65,66
8
7,9,32,37
12
12,25
16
8,33,35,38
20
18,20,86,89,92
由此即可得到在满足3分钟内有交巡警到达事发地以及各平台工作量均衡的条件下，中心城区A的20个交巡警服务平台管辖范围，并求得方差为2.9479。
4.2模型II
4.2.1模型分析
根据题目约束，一个平台的警力最多封锁一个路口，且由图1可得对13条交通要道的封锁即为13个出入城区的路口节点的封锁，那么，本问题的关键即为在全区20个交巡警服务平台中寻找13个服务平台，以对该区的13个出入城区的路口节点实现全封锁，且必须满足时间最短。
4.2.2模型的建立与求解
有题可知13个出入城区的路口点，若使13个交巡警服务平台实现全封锁，必须满足13个服务平台中到达时间最长的点也对出入城区的路口点实现封锁。
其中一个交通要道对应一个服务平台，而一个服务平台至多对应一个交通要道，可列出下式：
i=1,2…13,j=1,2…20
其中，
表示第I条交通要道到第j个交巡警服务平台的距离
且交巡警服务平台警力的合理调度方案如下表4：
表4全区封锁警力调度方案
服务平台
3
4
5
7
10
11
12
13
14
15
16
18
9
封锁要道
16
48
30
29
22
24
12
23
21
28
14
62
38
4.3模型III
4.3.1问题分析
由题意可得，为使资源得到充分利用，在增加平台尽可能少的基础上，首先满足每个平台出警时间全部在3分钟内（路程为3公里）增加相应平台，其次在增加平台后对工作量进行均衡。
在模型I的最终求解结果中，以方差最小为目标函数，20个平台的工作量已经得到尽量均衡，那么针对出警时间过长的情况找到六个亟待改进的问题节点，将其作为目标点，分别是28号节点、29号节点、38号节点、39号节点、61号节点和92号节点。
那么在这些目标点或目标邻近点处增加服务平台，使A区20个平台到达相应节点的时间在3min之内。
4.3.2模型的建立与求解
（一）增加平台
由图1可知，根据目标点的聚集情况划分出四个区域：
{28,29}、{38,39}、{61}、{92}
以这四个目标区域为中心，3公里路程为半径，向外辐射邻近节点，这样就得到了四个可供安置平台的目标结点选择范围，分别标记为：
p1={28,29}、p2={38,39,40}、p3={48,61}、p4={87,91,92}
由此，以这些点为中心，路程长度3公里为半径进行区域覆盖，要求所覆盖的区域内包含的非平台结点越多越好，以此为依据选定目标安置点建立平台。
这里对可能出现的情况做出规则限定：
1、不允许跨平台设置覆盖点，即如果某个点的覆盖区域内有其他平台，则将跨过该平台之后才能覆盖的点剔除该区域；
2、面对未决点，即点的覆盖区域范围内包含的非平台点数目相同，在要求的情况下无法确定哪个点为安置点的时候，遵循以下原则：
1）设置平台的新结点要求尽可能靠近市中心；
2）设置平台的新结点要尽可能地与其他平台分散开，不要出现平台扎堆现象；
3）以上两条先执行条件1），若条件1）无法明确满足再执行条件2）。
根据上述设置新平台结点的规则，得到下表5：
表5候选节点覆盖范围内拥有的非平台节点数
节点标号
28
29
38
39
40
48
61
87
91
92
覆盖范围内结点数
2
2
4
4
8
10
2
14
14
6
非平台结点数
2
2
4
4
6
7
2
12
12
6
剔除跨平台的非平台
结点后的结点数
2
2
4
4
4
4
2
12
12
6
为使增加平台个数尽可能少，对平台个数进行逐个分析：
当增加2个服务平台时，将其放置在以上任何候选节点，都不能满足使这两个平台到6个目标点的时间同时在3min以内。
当增加3个服务平台时，同
，无法保证这3个平台到6个目标点的时间同时在3min之内。
当增加4个服务平台时，将其分别设置在p1，p2，p3，p4的可选范围内，即可满足这4个平台到6个目标点的时间同时在3min之内。
通过对A区图1的比对以及各节点坐标数据进行分析，可知29号比28号更靠近市中心，91号比87号更靠近市中心。
由上述规则可以得到，在四个目标区域内分别设置四个交巡警服务平台的设置点分别为：
29号结点、39号结点、48号结点、91号结点。
（二）均衡工作量
此时，平台总数达到24个，再次利用模型I，遵循发案率方差最小的思想，建立目标函数，如下式：
i=1，2……92
其中
表示服务平台的平均发案率，其值为5.1875，
表示第i个节点的案发率，n为平台总数。
即可得到工作量均衡情况下的交巡警服务平台的分配方案（见程序6），见下表6：
：
表6服务平台分配结果
平台节点号
管辖的节点号
1
1，18,65，77，79
2
2，44,69,70,78
3
3，54,55,64,76
4
4，57,60,62,63
5
4，57,60,62,63
6
6,47,52,56
7
5,9,33
8
16,35,37,46
9
7,32,45
10
10
11
11,26,27
12
12,25
13
13，21,22,23,24
14
14
15
15，31
16
8,34,36
17
17,41,42,72
18
20,71,74,80,84
19
19，66,67,68,73,75
20
81,82，83,88,90,91
21
28,29
22
38，39,40,43
23
30，48,49，61
24
85，86,87,89,92
并求得方差为1.99，波动值不大，分配结果较好。
4.4模型IV
4.4.1问题分析
本问题是针对全市六个区交巡警服务平台的设置进行合理分析，按照交巡警服务平台的设置原则和任务，从出警时间和工作量均衡角度，运用模型III的思想分析现有设置方案的合理性，并通过增加平台的方案给予解决。
4.4.2模型的建立与求解
（1）合理性分析
对于以上平台设置方案，从两方面对其合理性进行分析：
首先出警时间必须满足3分钟原则。
对于某一个节点，若其不属于任一个服务平台，表示不满足时间限制，即为不合理点。
通过matlab编程可得该市共存在138个不合理点（见程序7）。
可知不合理点占总节点的比例为23.7%，不合理点相对较多。
其次可得服务平台的方差为27.21，该方差值也相对较大，表示各个交巡警服务平台的平均发案率波动相对较大，各平台工作量不均衡。
由以上分析可判断，该市现有交巡警服务平台设置方案是不合理的。
（2）解决方案
根据模型III的思想，选取增加服务平台的方法来满足时间与工作量均衡的限制，方法如下：
首先对138个不合理点根据模型III的划分原则进行划分，共可划分为17个区域，根据模型III的服务平台划分原则，可增加54个服务平台（见附表1），至此138个不合理点即可全部满足3min的时间限制。
其次，增加服务平台后全市共存在192个服务平台，将这些服务平台的管辖范围进行重新划分，以均衡各平台的工作量，建立如下目标函数：
i=1，2……582
求得交巡警服务平台的方差为5.098（见程序8），并获得最终平台设置方案，截取部分数据，见下表7（详见附表1）：
表7最终部分平台设置方案
平台
管辖节点
平台
管辖节点
平台
管辖节点
平台
管辖节点
平台
管辖节点
平台
管辖节点
1
1
96
127
180
180
383
470
184
187
408
413
1
18
96
128
180
270
384
465
184
188
419
418
1
19
97
97
180
297
384
468
199
199
419
419
1
73
97
129
180
298
384
472
199
208
420
420
2
3
97
130
180
306
384
473
201
200
421
379
2
17
97
131
180
310
385
385
201
201
421
417
2
69
97
137
181
266
385
449
201
202
421
421
2
75
97
148
181
267
385
450
204
203
439
439
4.5模型V
4.5.1问题分析
第五问提出了一个实际需要解决的问题，即在某个节点处发生案件需要的围堵方案。
从案件发生开始，到之后接到报警，交巡警服务平台第一时间接到布防通知，马上封锁目标节点。
这里要求安排方案，让所有交巡警服务平台在第一时间能够知道自己需要布防的节点位置。
由此分析布防的基本思想：
首先需要满足以下基本原则：
（1）必须在最快时间完成围堵方案，即最后一个待封锁路口完成围堵封锁任务的时间要尽可能的短；
（2）在时间短的前提下，尽可能少的调动警力资源；
（3）在遇到多个节点可以被一个平台实施封锁的情况下，优先选择后续分支较多的节点路口进行封锁；
（4）在遇到一个节点可以被多个平台实施封锁的情况下，优先满足原则
（1），其次满足原则
（2）。
4.5.2模型准备
下面对一些基本变量以及参数进行定义：
t：
事件发生到接到报警的间隔时间；
：
犯罪嫌疑人驾车逃窜的速度，
；（在假设中指明）
：
警车速度，
；
；表示罪犯逃窜t时间的路程；
：
抢点时间；
4.5.3模型建立
（1）事发地点（某个节点）标记为P，以P节点为中心，犯罪分子h时间所能逃窜的最大路程为指标q，确定一个以p点为中心的区域，标定该区域内的所有外层节点（与该区域外部节点相邻的节点或城市的边界节点），将这些节点构成的集合记为Q；
（2）以Q中的每一个节点为端点，向外辐射其邻接节点，若节点为普通节点，记为起始节点，
升级会员 