交巡警服务平台的设置与调度.docx
《交巡警服务平台的设置与调度.docx》由会员分享，可在线阅读，更多相关《交巡警服务平台的设置与调度.docx（34页珍藏版）》请在冰点文库上搜索。
交巡警服务平台的设置与调度
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
B
我们的参赛报名号为（如果赛区设置报名号的话）：
122B03
所属学校（请填写完整的全名）：
浙江大学
参赛队员（打印并签名）：
1.陈敏学
2.李梅
3.
指导教师或指导教师组负责人（打印并签名）：
日期：
2011年9月11日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
交巡警服务平台的设置与调度
摘要：
应急服务设施的优化选址布局在城市规划建设中是一个非常重要的问题。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
本文针对不同情况下的不同目标要求，借助集合覆盖问题[1][2]，通过建立求解0-1组合优化模型，给出了合理设置交巡警服务平台、分配各平台的管辖范围的最优化的方案。
本文第一部分首先考虑市中心城区A的20个交巡警服务平台管辖范围分配问题。
首先将应急时间要求尽量能在3分钟内，转换成针对每个服务点可能的交巡警服务平台集合，目标函数设定为
，利用随机数模拟算法给出了一种最优平台分配方案，此时，得到出警平台管辖范围，具体分划见表3-1-1，并且算出了最大出警时间是4.1分钟，最小出警时间是2.1分钟。
本文第二部分考虑当重大突发事件出现时，若干交通要道封锁的及时封锁问题。
此时结合第一部分得到的交巡警各服务平台的管辖范围，按照服务方便、出警时间短的原则，同样利用随机数模拟法求的最优解，得出如表3-1-2的警力合理的调度方案。
根据前述计算结论，我们发现现有交巡警服务平台的工作量不均衡和有些地方出警时间过长，因此本文在第三部分，搜索在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
根据上面提到的建立求解0-1组合优化模型的原理，结合随机搜索算法，最终得出需要增加的平台个数为4个，具体位置标号分别为29，39，60，91，其坐标为（246,337），（371,333），（335,395），（445,380）。
并得出如表3-1-3的警力合理的调度方案。
本文第四部分讨论全市六个城区的交巡警服务平台的设置方案。
我们考虑了两种情形。
情形1：
在仅考虑人口密度和平均案发量时，结果得到其分配方法合理，各城区独立分配调度交巡警服务平台。
；情形2：
分析在案发量与距离下出警平台点的分配，情形2又可分为a：
各城区独立分配调度交巡警服务平台，结果得到现有的出警平台分配不合理，需要在A区至F区加标号分别29，39，60，91，222,247,339,357,445,450,473,509,538,566,580的新平台：
b：
容许在邻近的不同城区的之间交叉调度交巡警服务平台，得到现有的出警平台分配不合理，需要在A区至F区加标号分别为92，62，,110,152,214,257,538,577,582这些新平台.
最后本文讨论了嫌犯快速搜捕问题。
求解可得在接到报案后6分钟内围堵住嫌疑车辆。
其所需的出警平为:
12,13,20,97,99,180,174,167,175,325,319,318
372,378,380,387,481,479，486共20个出警平台。
关键词：
集合覆盖问题；优化选址；遗传算法；随机搜索算法
一、问题重述
1.1问题的提出
伴随着经济的发展和文明的进步，人民的生活水平在不断提高，紧接着，路网结构复杂、人口稠密、停车场严重不足，接送学生车辆占道停放等问题显著突出，造成交通系统混乱，严重制约和影响着经济的发展。
为了能够科学合理地缓解出现的各种情况，急需建立合理的城区交巡警服务平台的设置与调度机制。
交巡警，能够预防和制止犯罪，增强公众的安全感，为公众提供综合性服务。
“有困难找警察”，是家喻户晓的一句流行语。
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
现在，根据某市区的交巡警服务平台的现状（具体参数与情况示意图见附件），分别就该市中的A区和整个市区的交巡警现有的设置与调度机制进行分析与求解，建立数学模型优化交巡警服务平台的设置、管辖范围的分划以及警务资源的调度，具体从下面几个部分着手研究与探讨：
第一部分，附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。
请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
第二部分，对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
第三部分，根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
第四部分，针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。
如果有明显不合理，请给出解决方案。
最后，如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
1.2问题简要分析
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
交巡警，能够预防和制止犯罪，增强公众的安全感，为公众提供综合性服务。
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
对于第一部分，当在所管辖的范围内出现突发事件时，使其尽量能在3分钟内有交巡警到达事发地，那么如何分配交巡警服务平台的管辖范围？
参考了集合覆盖问题中的启发式算法，其中从某个解出发随机移除一定比例的列，再用贪心策略加入若干列。
考虑到模型的精简化以及本题的交巡警出警的时间限制。
本文建立了0-1整数规划模型，利用Matlab软件进行编程，可以算出各路口之间的距离以及各节点到最近邻交巡警服务平台的距离。
然后，可以得利用0-1矩阵，再运用随机数模拟法求的最优解，得到出警平台管辖范围。
对于第二部分，对于重大突发事件，需要进行路口封锁，该如何确定该区交巡警服务平台警力合理的调度方案？
由于需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，而实际当中每一个平台的警力最多只能封锁一个路口。
所以，我们结合上面得到的交巡警各服务平台的管辖范围，考虑按照最便、最快封锁的原则，建立目标函数，同样利用随机数模拟法求的最优解，即可以得出该区交巡警服务平台警力合理的调度方案。
对于第三部分，由于现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，该如何确定需要增加平台的具体个数和位置？
根据上面提到的0-1整数规划模型的理论，可以确定目标函数，应用随机搜索算法，找出在现有的出警平台中找出工作环境处于最弱的那个出警平台。
分别考虑在与这个平台相连的路口节点增加出警平台的情况，将其带入约束条件，得到可行解d，L的值，并与前面的值进行比较，得到最优的可行解，即增加平台。
又继续考虑增加另一个平台（不超过5个），将新的目标函数值与之前的目标函数值进行比较，直至目标函数值不再发生大的波动。
即可以最终确定需要增加平台的具体个数和位置。
对于第四部分，研究该市现有交巡警服务平台设置方案的合理性。
要判断交巡警服务平台是否和合理，于是可以考虑将全市平台的工作情况分为两块：
各区交巡警工作范围不交叉和各区交巡警工作范围交叉。
考虑到实际情况下，出警平台平均管理路口数和案发率的权重比重最大。
在引入权重量后，可算得新的H。
可得在仅考虑人口密度时分配给每个区域出警平台的个数是否合理。
同理，可以分析在案发量与距离下出警平台点的分配是否合理。
这里将问题分为了2部分分别进行分析：
在各区交巡警工作范围不交叉的情况下和在各区交巡警工作范围交叉的情况下。
最后，为了快速搜捕嫌疑犯，给定调度全市交巡警服务平台警力资源的最佳围堵方案。
首先考虑把嫌疑车辆围堵在A区域之内，当假设嫌疑车辆车速等于警车车速时，由于A区的出口只有标号13种，而此时嫌疑车辆可以行驶3km，由上面的数据可得到该罪犯是否可以经过A区的路口逃离，判断只发动A区的警力用来围堵够不够。
如果不够，则考虑调度全市交巡警服务平台警力资源围堵。
模拟可以得到3分钟后嫌疑犯可达到的圆形覆盖面积，由计算可以得到离P点距离为3km的所有交巡警服务平台，共M个，离P点距离为5km的所有交巡警服务平台，共N个。
现在考虑当LM+N时，即界1和界3的总服务台不足以围堵犯罪分子，就需要考虑再多一分钟围堵时间的圆域范围。
此时重复上述操作，即可以得到最佳围堵方案。
二、基本假设和符号说明
2.1基本假设
（1）假设城区所有道路畅通无阻；
（2）假设相邻两个交叉路口之间的道路为直线
（3）假设案发地点都在路口
（4）假设追击过程警车无故障发生
（5）假设各区域中的发案次数不包含重大突发事件
（6）假设权重系数β=0.8
2.2符号说明
序号
符号
含义
1
路口节点i与路口节点j的连接情况
2
X
路口各节点的邻接矩阵
3
Mi
第i次循环的可行解
4
路口节点i与路口节点j的距离
5
β
权重系数
6
dL
目标函数值
7
第i区域平均发案率
8
第i区域的平均出警平台管理路口数
9
第i区域的人口密度
10
ALJ
A区出警平台与管辖点的邻接矩阵
11
P
一个重大刑事案件发生点
12
V
警车车速
三模型的建立于求解
3.1管辖范围的分配与合理的调度方案
3.1.1交巡警服务平台分配管辖范围模型
（一）建立0-1整数规划模型
为了分配中心城区A（以下简称为A区）交巡警服务平台（以下简称为出警平台）管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，我们引用了0-1整数规划模型[3]。
分析附件2的A区各路口节点的坐标以及附图1，得到1至20号路口节点为出警平台，A区的总路口节点数为92个（包含出警平台），首先建立0-1矩阵[4]：
，i=1,2,…n,是路口标记数，j=1,2,…m出警平台标记数。
其中如果路口节点为出警平台，即i=j则，
。
因为A区有出警平台20个，路口92个，所以n=92,m=20。
所以由
可以建立得到一个
的0-1矩阵X，如下，矩阵X中的第i行表示第i路口，矩阵中的第j列表示第j个出警平台，通过矩阵可以知道路口节点与出警平台是否连接的情况。
，当i=j时
要得到最短出警时间，意味着总的出警距离最短，所以得到以下目标函数：
（1）
由于每个路口节点只所属一个出警平台，每个出警平台至少管理以个除自身外的路口，得到约束条件是：
（2）
（二）运用随机数模拟法求最优解
第1步，确定每个路口节点到出警平台的距离dij。
经过分析与简要处理附录2中的表格（全市总有582个路口节点）我们得到全市的582*582的邻接矩阵A，得到582*2的矩阵E用来表示508个路口节点的坐标，其中点E（i，1），E（i，2）分别表示第i个路口节点的横坐标与纵坐标。
通过matlab的编程，（参见附录
（二））可得到任意两个路口节点之间的最小路径。
从而自然中可得到每个路口节点到出警平台的距离dij的数据。
第2步：
进行随机数模拟，随机得到
=0或1这两个数，赋值给
的矩阵得到0-1矩阵X1。
第3步，在受约束条件
（2）的情况下,通过matlab软件计算得到目标函数
（1）中min的一个可行解为M1，保留此值。
第4步，重复第2步，得到一个新的
的0-1矩阵X2。
重复第3步，得到min的可行解为M2，取M1，M2中较小的记为M1，记使M1，M2较小的0-1矩阵为X1。
保留M1与X1的值。
第5步，多次循环进行步骤2,3,4。
可得到循环中使可行解最小化的0-1矩阵X1，此时既得到关于0-1整数规划的近似最优化的解M1。
由0-1矩阵的定义，通过矩阵X1可直观的分析得到，在达到近似最优化的解时每个路口与出警平台的连接情况。
根据以上1-5步骤的随机数模拟法算法，进行matlab编程，见附录（三）得到0-1矩阵，通过Excel的数据处理，得到出警平台管辖范围，见表3-1-1。
表3-1-1：
出警平台管辖范围
平台标号
分配管辖范围的
路口标号
管辖路口
总数
平台标号
分配管辖范围的
路口标号
管辖路口
总数
1
1,67,68,69,71,73,
74,75,76,78
10
11
11,26,27
3
2
2,39,40,43,
44,70,72
7
12
12,25
2
3
3,54,55,65,66
5
13
13,21,22,23,24
5
4
4,57,60,62,63,64
6
14
14
1
5
5,49,50,51,52,53,
56,58,59
9
15
15,28,29
3
6
6
1
16
16,36,37,38
4
7
7,30,32,47,48,61
6
17
17,41,42
3
8
8,33,46
3
18
18,80,81,82,83
5
9
9,31,34,35,45
5
19
19,79,77
3
10
10
1
20
20,84,85,86,87,88,89
90,91,92
10
3.1.2重大突发事件警力重大突发事件调度方案
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据以上问题的分析，建立以个新的0-1整数规划模型。
每个出入A区的13个路口节点需要一个出警平台封锁，由附件二，可得这13个出入A区的路口标号分别是：
12,14,16,21,22,23,24,28,29,30,38,48,62，引用3.3.1中的0-1矩阵定义。
当i=12,14……这13个出入A区的路口标数值用随机数模拟得到1或0，其余的i=0，根据这个定义得到新的0-1矩阵。
由此可得到新的目标函数是：
（3）
，当i=j时
。
因为封锁所有A区的出入口，所以有约束条件:
（4）
根据以上的模型，运用随机数模拟法求最优解，如同3.3.1的算法，利用计算机模拟，可得近似最优化的解时的0-1矩阵。
通过Excel的数据处理，给出封锁A区进出路口交巡警服务平台警力合理的调度方案。
如下表3-1-2：
表3-1-2：
出警平台封锁入口方案
出入口标号
出警平台
12
12
14
3
16
19
21
20
22
14
23
13
24
11
28
15
29
16
30
8
38
2
48
7
62
4
3.1.3均衡交巡警服务平台的工作量模型
由于考虑到现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，因此要确定需要增加平台的具体个数和具体位置，以缓解交巡警的整体状况。
在这个模型中不考虑这重大突发事件调度的情况。
采用0-1整数规划模型，综合利用随机数模拟算法其进行求解。
根据上面提到的0-1整数规划模型的理论，此处确定：
约束条件为：
（5）
将交巡警服务平台的工作量和出警时间长短两个评价因子作为我们优化的目标函数,具体如下:
出警最短时间意味着最短距离，考虑到要使交巡警的出警时间最短，可以确定目标函数为:
（6）
工作量的不均衡，导致了某些路口的交巡警长时间出于工作的紧张状态，而另外一些路口的交巡警则比较空闲，所以这里必须考虑工作量的平均分配，其实就意味着服务平台的工作量的目标函数即为：
（7）
Cij为路口i的发案数。
首先用引进一个权重系数β，使最目标函数综合和为
（8）
假设此处权重系数β=0.8，应用Matlab[5]随机数模拟算法：
第1步：
找出在两个评价因子的综合情况下，在现有的出警平台中找出工作环境处于最弱既值dL最大的那个出警平台设为为Q。
由3.3.1可知与该平台Q相连的所有路口节点标号，设分别为：
a1,a2,…aN。
如图3.1.1
图3.1.1
第2步：
分别考虑增加出警平台与a1,a2,…aN的情况，加设一个出警平台后。
将其带入上面的约束条件（5），得到可行解最目标函数（8）dL的值，以此运行，得到最优的可行解，则为平台就设置到该路口
将上面新的目标函数值与最初的原始目标函数值进行比较，可以明显的观察到目标函数值在缩小率。
第3步：
重复第1，2步骤2-4次就是该区内再增加2至5个平台的情况。
观察目标函数值在增加到第几个新出警平台时，目标函数值的缩小率在5%之内。
通过对上述模型的matlab程序求解，可得到在增加5个新平台后目标函数值的缩小率为4.82%在5%之内。
所以得到均衡化模型只要新增4个出警平台，其路口节点标号分别为29，39，60，91，其坐标为（246,337），（371,333），（335,395），（445,380）.
得到模拟后增加至24个出警平台的情况，如表3-1-3：
表3-1-3：
均衡后出警平台管辖范围
平台标号
分配管辖范围的
路口标号
管辖路口
总数
平台标号
分配管辖范围的
路口标号
管辖路口
总数
1
1，68，69，74,75,78
6
13
1322,23,
3
2
2,70,44,73
4
14
14,21
2
3
3,55,65
3
15
15,27
2
4
4,60,62,63,
4
16
16,39,38,40
4
5
5,52,56,49,53
5
17
17,40,41,42,43,72
6
6
6,50,51,60
4
18
18，81,82,83，92
5
7
7,30,31,47,48
5
19
17,79,80
3
8
8,32,33,46
4
20
18,80,81,82,83
5
9
9,34,35,36,45
5
29
19,79,77
3
10
10,29
2
60
60,58,57,59
4
11
11,25,26,27
4
64
66,76
2
12
12,28,24
3
91
91,90,87,88
4
3.2判断平台设置的合理性和确定最佳围堵方案
3.2.1判断该市现有交巡警服务平台设置方案的合理性
按照设置交巡警服务平台的原则和任务，我们确定了2个评价因子判断该市现有交巡警服务平台设置方案（参见附件）的合理性，分别是人均工作量P和服务平台的平均出警时间Q[6]。
要判断交巡警服务平台是否和合理，于是将全市平台的工作情况分为两块：
各区交巡警工作范围不交叉和各区交巡警工作范围交叉。
（一）:
在仅考虑人口密度和平均案发量时分析分配给每个区域出警平台的个数是否合理
根据附件2得到每个不同区域中出警平台平均管理路口数如表3-2-1
表3-2-1出警平台平均管理路口
全市六个城区
出警平台
总路口数
平均平台管理路口数
A
20
92
4.6
B
8
73
9.1
C
17
154
9.1
D
9
52
5.8
E
15
103
6.9
F
11
108
9.8
得到不同区域中的人口密度如表3-2-2
表3-2-2人口密度
城区的面积（平方公里）
城区的人口（万人）
人口密度（万人/平方公里）
22
60
2.727272727
103
21
0.203883495
221
49
0.221719457
383
73
0.190600522
432
76
0.175925926
274
53
0.193430657
分别计算出每个区域A-F中出警平台需处理的平均案发量情况，在表3-2-3中呈显
表3-2-3平均案发量情况
全市六个城区
案发率（次数）
A
6.255
B
8.300
C
11.012
D
7.530
E
7.96
F
9.927
用
表示第i区域平均发案率，
表示第i区域的平均出警平台管理路口数，
表示第i区域的人口密度。
表示第i区域的总路口数。
求解
=
，经过运算得到除A区的H外，其余各区的H基本相同。
考虑到实际情况下，出警平台平均管理路口数和案发率的权重比重最大。
在引入权重量后，可算得新的H得到A-F区域的H≈15。
所以综上可得，在仅考虑人口密度时分配给每个区域出警平台的个数是比较合理的。
（二）分析在案发量与距离下出警平台点的分配是否合理
（1）在各区交巡警工作范围不交叉的情况下：
分别计算出每个区域A-F中出警平台平均管辖距离情况，在表3-2-4中呈现
表3-2-4平均管辖距离
全市六个城区
平均管辖距离（千米）
A
22
B
103
C
221
D
383
E
432
F
274
（1）在各区交巡警工作范围不交叉的情况下：
（a）对于A区而言：
运用上题中的交巡警服务平台分配管辖范围模型，可以得到出警平台管辖范围，A区出警平台与管辖点的邻接矩阵ALJ，在
升级会员 