交巡警服务平台的设置与调度问题的研究.docx
《交巡警服务平台的设置与调度问题的研究.docx》由会员分享，可在线阅读，更多相关《交巡警服务平台的设置与调度问题的研究.docx（37页珍藏版）》请在冰点文库上搜索。
交巡警服务平台的设置与调度问题的研究
交巡警服务平台的设置与调度问题的研究
摘要
今年以来，全国各地出现了各种重大犯罪案件，为了保障广大人民群众的生命财产安全，加强社会嫌疑人员的监控与防范。
这就需要加大警力部门对各交通要道的巡逻力度。
本文要解决的就是现有交巡警服务平台对交通道路分布情况的问题。
在确保各种安全保卫工作正常进行的情况下，使得调度的警力最少，并使警员在接到险情时能够尽快赶到事发现场。
根据附件中的各路口节点的坐标以及所给各节点之间的相邻关系，用MATLAB求得任意两相邻节点间的距离，再利用Floyd算法求得任意两点间的最短距离。
在建立模型的过程中采用赋权值，并结合线性规划和0-1规划，最后整体分析交巡警服务平台的合理性，从各个方面加以分析，综合各种因素的影响，提出相关合理性的建议。
在问题的分析中，平台管辖范围的确定是先由Floyd算法得出最短路径，再通过对比穷举的方法，来确定各平台最优的范围；封锁时采用了0-1规划的整体优化方法，并进行进一步的局部优化，得出最合理的设计路线；对于增加平台数则运用发案率与所选地址的关系，通过筛选覆盖法，得出最佳合理个数；根据全市交巡警安排的原则，可以用来分析交巡警设置方案的合理性；对嫌疑犯的追捕采用先疏后密的围捕方法，逐层缩小围堵范围，将疑犯逼入死角，从而快速有效的将其抓获。
关键词：
交巡警平台MATLABFloyd算法最短路径
、
一、问题的背景
近十年来，我国科技带动生产力不断发展，国家经济实力不断增强，然而另一方面安全生产形势却相当严峻，每年因各类生产事故造成的人员伤亡、经济损失，尤其是在一些密集点，作为人类经济、文化、政治、科技信息的中心，由于其“人口集中、建筑物集中、生产集中、财富集中”的特点，一旦发生重大事故，将会引起相当惨重的损失。
为了保障安全生产、预防各类事故。
我国正在各省（市）目标点逐步设立交巡警平台。
交巡警平台是将刑事执法、治安管理、交通管理、服务群众四大职能有机融合的新型防控体系。
在人流量极大、治安状况比较复杂、交通持续比较混乱的事故多发地带产生强大的司法制衡力、社会治安的驾驭力、打击犯罪的冲击力。
保证在事故发生的第一时间感到现场，大力的减少了社会上各种混乱行为的发生，使居民的生命财产安全得到保障。
而每个交巡警服务平台的职能和警力都基本相同，由于警务资源有限，你且各路口的发案率不同。
这就需要警务部门根据城市的实际情况与需求来合理地设置交巡警服务平台、分配各平台的管辖范围和调度警务资源。
二、问题的重述与分析
现就某市设置的交巡警服务平台的有关情况，建立数学模型分析研究这些问题：
（一）、对于该市中心城区A的交通网络及现有的警务平台，根据所给附图和相关数据，为各交巡警服务平台分配管辖范围，当他们所管辖的范围内出现突发事件时，能够尽量在3分钟内有交巡警到达事发地进行处理；然而对于重大突发事件，应该快速对交通要道实现封锁。
但在实际中一个平台的警力最多能够封锁一个路口，该城区A有13条交通要道，需要调度全区20个交巡警服务平台的警力资源对其实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，这就需要设计出该区交巡警服务平台警力合理的调度方案。
由于实际情况需要在A区适当增加平台并确定其具体个数和位置，以便能有交巡警快速赶到事发地。
（二）、根据全市的具体情况，分析该市现有交巡警服务平台设置方案的合理性，如果有明显不合理，给出解决方案。
如果该市地点P处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
设计调度全市交巡警服务平台警力资源的最佳围堵方，以便快速搜捕嫌疑犯。
三、模型假设与符号说明
模型假设：
1.交巡警在接到报警后到出发的时间忽略不计；
2.交巡警在赶往事发地点时道路恒畅通（无交通事故，交通堵塞等情况发生），警车在这过程中行驶正常；
3.在整个路途中，通过各种通讯工具，所经过的路程都是最短路程；
4.在整个路途中，警车在拐弯时所需的时间忽略不计；
5.假定所有的事发地点都是在道路上，且案件的发生在道路上任一点都是等概率事件；
6.各个所划分的管辖区域，在较短时间内，最多会发生一个突发案件。
符号说明：
表示第
个平台到第
个交通要道的最短距
表示是否经过
平台到
交通要道这条最短路径，
=1表示经过，
=0
表示不经过
表示
区交通要道的个数
表示
区交巡警平台的个数
表示警车从
平台到
交通要道的概率
设施总数
四、模型的建立与求解
对问题
（一）
第1问：
根据问题
（1）中所给附件示意图，及相关数据信息，对所给
区地图中的所有交通网络节点和交巡警服务平台利用Mtalab软件进行编号（程序见附录一），如图
（1）所示：
图
（1）
根据已经求出的相邻路口的距离，用matlab软件计算（）出任意两点之间的距离，并且得到一个92*92的距离矩阵：
（1）
然后将
中不相邻路口间距离0改为无穷大Inf，从而得到任意两个路口间的权值矩阵：
（2）
这样主要是要解决剩余的72个点如何合理的分配给平台管理的问题。
通过题目中给出的数据，利用MATLAB的编程求出各个节点之间的距离,要使每个平台所需要达到的合理的管辖范围，可以使用相关的图论软件利用FLOYD算法，可以得到各个节点到每个平台的最短路径，再通过穷举筛选的方法可以找到到各个平台路径小于3
的节点数，即各平台所管辖的范围。
（见附录1）
由于平台的管辖范围可能存在着重复覆盖的区域，但重复区域内的同一点到不同平台之间的距离可能不同，这时需要对所得到的管辖点进行重新筛选，每个节点选择它到平台距离最近的那个平台，这样才得到每个平台的最优覆盖范围。
形成的最优范围覆盖节点的如表
（1）：
表1
节点路口
服务平台
1
1
67
68
69
71
73
74
75
76
78
2
2
39
40
43
44
70
72
3
3
54
55
65
66
4
4
57
60
62
63
64
5
5
49
50
51
52
53
56
58
59
6
6
7
7
30
32
47
48
61
8
8
33
46
9
9
31
34
35
45
10
10
11
11
26
27
12
12
25
13
13
21
22
23
24
14
14
15
15
28
29
16
16
36
37
38
17
17
41
42
18
18
80
81
82
83
19
19
77
79
20
20
84
85
86
87
88
89
90
91
92
实际得到的管辖范围中也有分配不到的点，从所得到的程序及图
（1）中，不难看出有些点即使是最近的平台也很难在3分钟内出警到达，从上面的表格
（1）中得到那些点分别为28，29，38，39，61，92.这时采用就近的原则，将其分别配给距离它们最近的平台，用以达到所有节点都被管辖的目的。
通过上诉表格可以绘出各个平台的覆盖范围，从图和表格中清晰的看出除了6个覆盖不到的点无法满足交巡警在3分钟之内达到外，其他的点均是选择了据他最近的平台，这样使出警的时间与管辖的分配都到达了最优化。
图
（2）
第2问：
调度方案
对进出该区域的交通要道实现快速全封锁，主要目的是让违法犯罪分子无可乘之机，当在某处发生重大事件后，理应在最短的时间内，对嫌疑人的活动范围进行控制，使嫌疑人的活动范围越小越好，尽量将其控制在自己的辖区里，以便于事件的调查处理。
基于此，当A区发生重大事件后，可调度全区的20各服务平台的警力，对进出该区的13条交通要道进行快速全封锁。
在一个平台的警力最多封锁一个路口前提下，要给出该区服务平台警力的合理调度方案，旨在合理调度20个服务平台的警力实现对这13交通要道的13个进出区路口的快速封锁。
为了应对重大突发事件而进行快速封堵交通要道，就需要对各个平台进行合理的调度，由于调度上的时间关系，平台到各个交通要道就需要寻求最短路径，使总的调度行程最短。
在上述中，可以通过MATLAB得出20个平台分别到13个交通要道的最短路程，这样得到了260个数据，得到的最短路径表格如下：
（见附录1、2、3、4）
表2
由于需要给出交巡警服务平台警力合理的调度问题，我们以13条交通要道为基点，对20个平台进行分析，建立0-1矩阵模型对20个交巡警服务平台和13个交通要道进行处理，
由此得
（3）
（4）
通过以上公式
（1）和
（2），利用LINGO求解可以得到每个交通要道的最短路径分配，从中找到每个平台所对应的交通要道，由运行程序中得到下列对应数据（程序见附录11）：
表3
服务平台
交通要道
最短路径
12
12
0.000
9
14
82.740
16
16
0.000
14
21
32.650
10
22
77.080
13
23
5.000
11
24
38.053
15
28
47.518
8
29
104.930
7
30
5.830
2
38
39.822
5
48
24.758
4
62
3.500
上表得出的是整体的优化路劲方法，得出
461.87
再进一步的对数据进行分析，可以发现这个所得出的结果并不是最优的，还可以对其进行进一步的局部优化：
得出目标函数为
（5）
（6）
由LINGO软件求解可以得出更优的选择方案，如下表所示（程序见附录12）：
表4
服务平台号
交通要道节点号
最短路径
2
38
39.8220
4
62
3.5000
5
48
24.7580
7
29
80.1550
8
30
30.6085
9
16
15.3254
10
25
77.0800
11
24
38.053
12
12
0.0000
13
23
5.0000
14
21
32.6500
15
28
47.5180
16
14
67.4170
第3问：
增设平台
A地区按交通事故发案率的大小及对应的坐标位置划分为若干个需求区域，并且每个区域都可以作为增建服务平台的选址点。
假定原有服务平台设一个平均响应距离和时间及案发率的限制，若在平均响应距离和时间及案发率外，原有服务平台能够为需求区域提供服务，则称该区域为现有安全区域，则不考虑这一区域内新建服务平台，如果得出结论与之相反，则在这一区域内增设服务平台。
在这里我们就可以用到0-1覆盖矩阵表示这种关系，行表示需求区域，列表示设施选址点，若区域被设施覆盖，则矩阵中相应的值为1，否则为0。
区域覆盖模型是研究在满足去除安全区域的所有需要点的前提下进行的。
为了方便给出模型的公式表达，先介绍一些指标：
表示选址点
;
表示需求区域
；决策变量
若点有设施，
=1；若j点没有设施，
。
表示平均响应时间限制，
表示选址点
到需求区域
的时间，则覆盖区域
的点集合可表示为
。
表示设施总数，则集合覆盖模式的公式为：
（5）
（6）
上述模型考虑每个服务点的管辖范围是相同的，因此只需要求出建设服务点区域的最小值，若考虑安置管辖范围不同，则模型可表示为：
（7）
s.t.
（8）
式中
表示设施建设区域。
第一个约束条件要求所有需求都必须被特定距离内的设施满足，其中，若设施
能满足
区域服务需求，则
；否则
。
集合最大模型的解可能并不唯一。
为了节约资源对于需求区域和可建服务平台一定要做到最优利用率，通过0-1覆盖矩阵直接观察就可以解决问题，也可以使用整数线性规划软件Lingo,将上述数学公式输入软件来解决。
现实生活中有些问题较为庞大，直接寻找最优解比较繁琐，也容易出错。
而采取一些简化措施可以将问题简化，从而较容易地求解。
（1）若需求区域
仅仅被设施点
覆盖，则
就成为基本设施点。
当
是基本设施点时，为使区域
被覆盖，则
出必须安置设施，而在
处安置设施后，其可覆盖的所有区域均能满足需求，因此可以除去基本设施
的列及其覆盖的需求区域的行。
（2）若设施
覆盖的区域是设施
覆盖区域的自己，那么就称
是手控制列。
矩阵中，列
值为1的行，列
对应的值为1。
应为安置在
处的设施可以同时满足设施
覆盖区域的需求，可以将列
从矩阵中一移去。
（3）若覆盖区域
的每个设施
也全都覆盖区域
，则城
是受控行。
矩阵中，行
值为1的列，行
对应的值也为1。
当建设的设施能够覆盖区域
时，区域
也会被覆盖，因此，可以将行
从矩阵中移去。
区域覆盖模型的具体化简步骤如下：
第一步，找出原有服务平台设施点，将该列和其覆盖区域对应的行从矩阵中移除；第二步，找出受控列，将其从矩阵中移除；第三步，找出受控行，将其从矩阵中移除；第四步，重复第一步至第三步，知道矩阵被移除完或无法使用简化策略。
化简完成后应有部分矩阵剩余。
这就需要结合其他的方法解决（如分支界定的线性规划方法）。
不过通常情况下，问题化简到最后可以通过观察直接得出结果。
经过计算得出的结果为，建设四个服务平台为最佳方案.
表5增设平台的具体位置
路口节点平台号
路口节横坐标
路口节纵坐标
29
246
337
38
371
330
48
315
374
87
448
381
对问题
（二）
第1问：
针对全市六个区域的具体情况，按照设置交巡警服务平台的原则和与任务，交巡警平台的设置主要遵循以下原则：
（1）重点犯案率设置原则
警车在服务平台所属范围大于它在任一相邻知道上的出警范围。
警车在规定时间内行驶的距离一定（即3分钟3公里），根据出警范围的定义，在某点出具有独立路径数的数目越多，则交巡警服务平台的出警范围越大。
将图论理论引入到警车的出警范围计算中，将该区域的道路堪称简单的无向图，进行部分简化后，可认为；图中某点处，潜在的自由度越多，警车的出警范围就越大。
根据不同节点的案发率不同出警的次数也不同，案发节点越高的区域，其区域内的服务平台出警率越高。
知道仅仅具有向前和向后两个自由度；而路口的自由度大于等于2；因此，警车在路口的出警范围大于它在任意相邻直道上的出境范围。
（2）道路长度覆盖原则
在某一个静止状态，至少一个警车能按时赶往某个一般部位的概率，等于该服务平台区域划分方案中的总范围与该区域道路总长度的百分比。
为警车按时赶到某一处节点j的概率模型
（9）
式中t（i，j）为警车i赶到事发地点j的所需要的时间。
式
（1）表示评估警车的出警效果是一个0—1模型，即当警车能在3分钟内赶到出事地点时，才能有效处理当前时间；否则不能有效处理当前时间。
在全体服务平台中对于所管辖的区域至少有一个服务平台能够及时作出处理。
（10）
式（10）表明，该区域道路有
的概率警车能在三分钟内赶到，也就是位于交巡警的管理区域。
（3）平台管理的范围原则
通过对所给的表格中的数据的分析，可以用MATLAB进行求解6个区域的每个节点到其所有平台的最短距离（程序见附录10）
从中选择那些在平台范围外的节点，即无论从哪个区区管辖都不能管道，因此,可
借用问题一中的方法来筛选那些不合理的点。
见附录
再找到这么多不合理的点，通过不合理的点即可判断出平台范围的合理性。
第2问:
六、模型的评价
需要另外考虑的因素和对应的解决方案：
考虑到具体交巡警服务情况的复杂性，我们还需考虑以下几个因素：
1．该城市的巡逻方式仅有警车，虽然能将巡逻范围大大扩大，但是警员坐在汽车里远离市民，对社区情况和案件的了解情况不如徒步巡逻的效果好，同时警车巡逻时，只能在道路上行驶，对应图中的非道路区域没有进行巡逻，使非街道区域成为巡逻盲区；
2.对于突发事件的处理问题；
3.各交巡警员之间在一些未被覆盖的区域如何合作才能使整体的巡逻效果取得比较好的成效；
4.交巡警巡逻频率的选取问题。
针对以上问题，我们提出以下几个解决方案：
1.为了了解社区情况和将巡逻范围扩大到非街道区，可以采用警车加徒步巡逻或摩托车方式进行巡逻，这样做会使整个巡逻范围扩大，必会大大增加巡警人数，在制定巡逻方案时，需要综合考虑，选取最合适的巡逻方案；
2.当有突发事件发生时，要突破分区限制，各分区需要通力合作，还要求巡警
及时掌握准确信息，向上级部门汇报，随机应变地解决所遇到的问题；
3.在警员人数有限的情况下，需要各分区巡警明确巡逻目的，踏实工作，明确
责任制，做好本职工作，使人民生命财产安全得到最大限度的保障；
4.巡逻频率太高，会影响到人民的正常工作和生活（报纸刊登有相关消息），
如果巡逻频率太低，将降低市民的安全感，同时给一些违法犯罪分子予可乘之机，所以要合理安排巡逻方案，将巡逻频率控制在一个适当的范围内。
七、模型的推广
通过对交巡警服务平台的设置与调度的方案，可以将其应用到空运，海航等方面中选择恰当的路线来节省时间和资源；在物资的运输过程中如何选择运输工具，各种运费的权数不一样，要求的运费最低及时间最短等问题。
参考文献
[1]马莉编著.Matlab数学实验与建模，北京：
清华大学出版社，2010
[2]姜启源，谢金星，叶俊编.数学模型（第三版），北京：
高等教育出版社，2003
[3]韩忠庚编著.数学建模方法及其应用，北京：
高等教育出版社，2005
[4]袁新生，邵大宏，郁时炼主编.LINGO和Excel在数学建模中的应用，北京：
科学出版社，2007
附录1（pictrue.m）
labelx=[A区路口的横坐标X
];
labely=[A区路口的纵坐标Y
];
text（labelx+1,labely+1,num2cell（1:
92））;
holdon
disjoint=[...];%A区路线起点与终点
c=[413403383.5381339335317334.5333282247219225280290337415432418444];
d=[359343351377.5376383362353.5342325301316270292335328335371374394];
e=[219280337251234225212243246314371315381];
f=[316292328277271265290328337367330374381];
fori=1:
size（disjoint,1）
x1=labelx（disjoint（i,1））;
y1=labely（disjoint（i,1））;
x2=labelx（disjoint（i,2））;
y2=labely（disjoint（i,2））;
a=[x1,x2];b=[y1,y2];
plot（x1,y1,'b*',x2,y2,'b*',c,d,'ro',a,b,e,f,'r*'）;
plot（x1,y1,'b*',x2,y2,'b*'）;
end
附录2（dist.m）
functionm=dist（a,b）%a为横坐标，b为纵坐标,且均默认为列向量；
fori=1:
size（a,1）
forj=1:
size（b,1）
m（i,j）=（（a（i）-a（j））^2+（b（i）-b（j））^2）^0.5;
end
end
附录3（disjoit.m）
functiont=disjoit（c）%求顶点的关联矩阵
fori=1:
size（c,1）
ifc（i,1）<93&c（i,2）<93%c矩阵为全市交通路口的连接矩阵
t（c（i,1）,c（i,2））=1;
t（c（i,2）,c（i,1））=1;
end
end
附录4（floyd.m）
function[d,r]=floyd（D）%d是矩离矩阵,r是路由矩阵
n=size（D,1）;
d=D;
fori=1:
n
forj=1:
n
r（i,j）=j;
end
end
fork=1:
n
fori=1:
n
forj=1:
n
ifd（i,k）+d（k,j）d（i,j）=d（i,k）+d（k,j）;
d（j,i）=d（i,k）+d（k,j）;
r（i,j）=r（i,k）;
end
end
end
end
附录5（police.m）
functionw=police（z）%将距离向量转为权向量
fori=1:
size（z,1）
forj=1:
size（z,2）
ifz（i,j）==0
z（i,j）=inf;
end
end
end
w=z;
附录6（quyu1）
functionT=quyu1（A,B,d）
fori=1:
size（A）
forj=1:
size（B）
T（i,j）=d（A（i）,B（j））;
end
end
附录7（zcx1.m）
%求距离矩阵的初始值
a=[A区路口横坐标X];
b=[A区路口纵坐标Y];
c=[…];%A区路线起点与终点
A=[1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20];
B=[…];%A区被服务的点
m=dist（a,b）;
t=disjoit（c）;
D=t.*m;
w=police（D）;
[d,r]=floyd（w）;
T=quyu1（A,B,d）
附录8（zcx2.m）
%求各巡警平台到需围堵路口的最短距离
a=[…];%A区路口的横坐标
b=[..];%A区路口的纵坐标
c=[…];%A区路线起点与终点
m=dist（a,b）;
t=disjoit（c）;
D=t.*m;
w=police（D）;
[d,r]=floyd（w）;
A=[1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20];
B=[12
14
16
21
22
23
24
28
29
30
38
48
62];
fori=1:
size（A,1）
forj=1:
size（B,1）
v（i,j）=d（A（i）,B（j））;
end
end
升级会员 