交警平台的布局.doc

2010高教社杯全国大学生数学建模竞赛承 诺 书本文仔细阅读了中国大学生数学建模竞赛的竞赛规则.本文完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。本文知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。本文郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，本文将受到严肃处理。本文参赛选择的题号是（从A/B/C/D中选择一项填写）： B 本文的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 南方医科大学 参赛队员 (打印并签名) ：1. 王沛沛 2. 姚慧 3. 麦金玲 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012年 8 月 14 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：18交巡警服务平台的设置与调度摘 要“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。在警务资源是有限的情况下，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文为某市分析了其交巡警服务平台的相关问题。 对于问题一，本文着重分析了该市的A区交巡警服务平台的设置与调度问题。对于 第一个小问，本文根据附件所给的92个节点的坐标运用了最短路径算法来计算A区任意两节点之间有公路的距离，并以此构造了92*92的无向图权矩阵。为给交巡警合理分配管辖范围，使其在突发事件时尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，本文用编程筛选出每个交巡警服务平台找出与每个交巡警平台距离少于三千米的节点，发现有的节点有不止一个平台与它的距离在3千米以内，因此本文在excel中做了进一步的筛选，找出与节点距离最近的平台并并将此结点归纳到这个交巡警服务平台的管辖范围之内。然而，本文发现有警车在3分钟之内无法到达的盲点，对于这些盲点，本文将他们分配给距离他们最近的交巡警平台。第二个小问，在突发情况下，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。由于实际中一个平台的警力最多封锁一个路口，本文只要保证警车封锁最后一个路口的最长距离的时间要最短，本文采用了lingo软件的0-1规划模型来分析 。第三个小问，本文发现不同的交巡警管辖范围内由于发案率不同而造成了不同的交巡警服务平台的工作量不同，且有些地方存在出警时间过长的实际情况，本文考虑在突发情况下平台的管辖区域没有盲点的要求，在第一小问的条件下，决定在28,38,61,92这几个路口处增设平台，然后用lingo软件进行0-1规划，将平均工作量方差作为目标函数，求其最小值，综合比较得出增加了的平台的管辖范围 。 问题二，第一个小问要求本文对全市的交巡警服务平台的设置情况进行评价，对设置不合理的，给出合理的方案方案。本文选择了人口密度、各区平均案发率这两方面因素来评价。本文赋予这两个因素的权重都为0.5，定义为评价各区交巡警平台设置的合理性程度，越大则设置越合理。对于存在不合理，对于实际已存在的交巡警平台，我们考虑到经济利益，不可能重新分配平台，而只能进行增设平台处理，增设平台依据各区分配的评价标准的方差最小原则，用matlab优化工具箱中的求解有约束非线性最小值问题的fmincon函数进行优化。第二小问，考虑到犯罪嫌疑人作案前定事先做好犯案后的以最快速度逃离该市的准备，因此本文用最短路径算法算出作案人从P点逃向市区出口的最短路线即作案人员的可能逃跑路线。并且分析其作案三分钟后可能到达的交叉节点，求距离此节点最近的交警到达此节点的时间。比较能否在作案人之前到达此节点，将其围堵。若不能，就在此节点的下一节点进行同样的比较，直到找到可以围堵住作案人的节点。关键词：图论模型，Floyd算法一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。附件1：A区和全市六区交通网络与平台设置的示意图。附件2：全市六区交通网络与平台设置的相关数据表（共5个工作表）。 2、 问题分析 对于问题一，本文着重分析了该市的A区交巡警服务平台的设置与调度问题。对于 第一个小问，本文根据附件所给的92个节点的坐标运用了最短路径算法来计算A区任意两节点之间有公路的距离，并以此构造了92*92的无向图权矩阵。为给交巡警合理分配管辖范围，使其在突发事件时尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，本文用编程筛选出每个交巡警服务平台找出与每个交巡警平台距离少于三千米的节点，发现有的节点有不止一个平台与它的距离在3千米以内，因此本文在excel中做了进一步的筛选，找出与节点距离最近的平台并并将此结点归纳到这个交巡警服务平台的管辖范围之内。然而，本文发现有警车在3分钟之内无法到达的盲点，对于这些盲点，本文将他们分配给距离他们最近的交巡警平台。第二个小问，在突发情况下，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。由于实际中一个平台的警力最多封锁一个路口，本文只要保证警车封锁最后一个路口的最长距离的时间要最短，本文采用了lingo软件的0-1规划模型来分析 。第三个小问，本文发现不同的交巡警管辖范围内由于发案率不同而造成了不同的交巡警服务平台的工作量不同，且有些地方存在出警时间过长的实际情况，本文考虑在突发情况下平台的管辖区域没有盲点的要求，在第一小问的条件下，决定在28,38,61,92这几个路口处增设平台，然后用lingo软件进行0-1规划，将平均工作量方差作为目标函数，求其最小值，综合比较得出增加了的平台的管辖范围 。 问题二，第一个小问要求本文对全市的交巡警服务平台的设置情况进行评价，对设置不合理的，给出合理的方案方案。本文选择了人口密度、各区平均案发率这两方面因素来评价。本文赋予这两个因素的权重都为0.5，定义为评价各区交巡警平台设置的合理性程度，越大则设置越合理。对于存在不合理，对于实际已存在的交巡警平台，我们考虑到经济利益，不可能重新分配平台，而只能进行增设平台处理，增设平台依据各区分配的评价标准的方差最小原则，用matlab优化工具箱中的求解有约束非线性最小值问题的fmincon函数进行优化。第二小问，考虑到犯罪嫌疑人作案前定事先做好犯案后的以最快速度逃离该市的准备，因此本文用最短路径算法算出作案人从P点逃向市区出口的最短路线即作案人员的可能逃跑路线。并且分析其作案三分钟后可能到达的交叉节点，求距离此节点最近的交警到达此节点的时间。比较能否在作案人之前到达此节点，将其围堵。若不能，就在此节点的下一节点进行同样的比较，直到找到可以围堵住作案人的节点。3、 模型的基本假设1、 每个交巡警服务平台的职能和警力配备基本相同。2、 所有案件都发生在节点处。3、 重大刑事案件犯罪嫌疑人事先做好作案后的逃跑准备。4、 假设在任意节点处建立新的交巡警平台的花费相同。5、 假设作案人的逃跑速度与警车的速度相同。4、 符号说明5、 模型的建立与求解5.1 为各交巡警服务平台分配管辖范围由于警务资源是有限的，根据该城市A区的实际情况与需求合理地给各个交巡警服务平台分配管辖范围、调度警务资源对警务部门有着重要的意义。使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。下图是A区的交通网络与交巡警服务平台分布的示意图：图 1 A区的交通网络与平台设置的示意图5.1.1 用floyd算法求得每两个交叉路节点的最短距离1) Floyd算法的的原理Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。算法的思想是直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), , D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.算法的具体步骤：【d(i,j) 表示i到j的距离， path(i,j)表示i到j的路径上i的后继点; 输入带权邻接矩阵a(i,j)】a.赋初值 对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.b.更新d(i,j) , path(i,j) 对所有i,j, 若d(i,k)+d(k,j)d(i,j),则 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+1c.重复b.直到k=n+1（具体matlab程序见附录1）2） 由于地图距离和实际距离的比例是1:100000,即1毫米对应100米可以看出，所以先将所有的数据转化为实际距离。然后每个用floyd算法即可求出任意两交叉路节点的最短路程。（具体程序见附录2）5.1.2 给每一个交巡警平台分配管辖范围1)上面已经做出任意两交叉节点的最短距离，根据附件三可以看出，A区的所有交巡警服务平台都在前20个交叉节点，用matlab筛选出每个交叉节点距离最近的交巡警服务平台（前20个交叉结点），该交叉节点被管辖的即为本文筛选出来的最近的那个服务平台。下表即为每个节点所属的管辖平台：交叉节点所属管辖平台时间（min）交叉节点所属管辖平台时间（min）交叉节点所属管辖平台时间（min）21132.71 4591.10 6910.50 22130.91 4680.93 7020.86 23130.50 4771.28 7111.14 24132.39 4871.29 7221.61 25121.79 4950.50 7311.03 26110.90 5050.85 7410.63 27111.64 5151.23 7510.93 28154.755251.66 7611.28 29155.75351.17 77190.98 3070.58 5432.27 7810.64 3192.06 5531.27 79190.45 3271.14 5652.08 80180.81 3380.83 5741.87 81180.67 3490.50 5852.30 82181.08 3590.42 5951.52 83180.54 36160.61 6041.74 84201.18 37161.12 6174.19 85200.45 38163.41 6240.35 86200.36 3923.68 6341.03 87201.47 4021.91 6441.94 88201.29 41170.85 6531.52 89200.95 42170.98 6631.84 90201.30 4320.80 6711.62 91201.60 4420.95 6811.21 92203.60 表格 1从表格1可以看出，大多数交巡警平台到所管辖范围交叉节点的时间在3min之内，但是，由于各种条件的限制，有6个交叉节点不能够在3 min赶到，因此本文将这六个节点分配给距离它们相对比较近的交巡警平台管辖，具体的六个节点和分配方案如表格二所示：交叉节点282938396192交巡警服务平台1515162720到达时间4.75 5.70 3.41 3.68 4.19 3.60 表格 2虽然这6个交叉点出现突发事件时，不能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，但是它所属被管辖的交巡警已经是最近的了，在现有的这种情况下已经是最优的管理方案了。以下是20个平台所管辖的范围11 67 68 69 71 73 74 75 76 7822 39 40 43 44 70 7233 54 55 65 6644 57 60 62 63 6455 49 50 51 52 53 56 58 5966707 30 32 47 48 6188 33 46909 31 34 35 4510101111 26 271212 251313 21 22 23 2414141515 28 291616 36 37 381717 41 421818 80 81 82 831919 77 792020 84 85 86 87 88 89 90 91 925.2 实现13条交通要道快速全封锁的调度方案 对于重大突发事件,城市一般都需要调度城市警力资源,对一定的要道进行封锁。如何利用快速有效的算法实现警力的调度与指挥,对提高快速处理紧急事件和打击犯罪活动的能力具有重要的意义。根据题意，应在最短的时间内利用所有的警力资源对13个交通要道实现封锁。这是一个典型的0-1规划问题。 5.2.1 决策变量的选定A区现在拥有20个交巡警服务平台的警力资源，而要封锁的交通要道有13个，所以，创建一个的0-1矩阵X: 5.2.2建立目标函数要实现快速封锁，即要使每个出入城区的路口封锁的最大时间最小，因此(其中表示第个巡警台到第个交通要道的最短距离)5.2.3 寻找约束条件1） 由于每个平台的警力资源有限，所以一个平台的警力最多封锁一个路口，即2） 要实现封锁，则每一个交通要道至少有一个平台的警力，即3） 根据决策变量的定义，只能等于0或1。5.2.4 求解最优值根据上述的目标函数和约束条件，用LINGO（具体程序见附件3）编程即可求出X的最优值如下：下表是实现快速封锁后每个路口的警力部署情况：交通要道12141621222324警力部署1291613101411交通要道282930384862警力部署7158132,4,5,6,17,18,19,20表格 3此时的最时间最短，最短时间为8.57分钟，即发生重大事件之后，经过8分钟34秒即可对全区的13个交通要道实现封锁。5.3 增加2-5个平台以解决工作量A区不均衡和有些地方出警时间过长的问题5.4 优化该市现有交巡警服务平台设置方案根据问题二的要求，本文设定两个原则对方案的合理性进行分析，并对其中的不合理之处，给出了相应解决方案。5.4.1 评价该市平台设置方案的原则本文从全市各区的人口密度分布，各区平均发案率两个因素来评价该市平台设置的合理性，并赋予人口密度、平均发案率权重都为0.5，综合评价指标为，以的标准差大小来评定各区设置的合理性。1） 该市每个区的平均人口密度（万人/平方公里）。下表是该市每个区的平均人口密度城区ABCDEF2.7273 0.2039 0.2217 0.1906 0.1759 0.1934 2）该市每个区的平均案发率下表是该市每个区的平均案发率城区ABCDEF1.350.961.015.4.1 无量纲化处理（1） 把人口密度、平均发案率做无量纲化处理（2）无量纲化处理无量纲化处理的结果ABCDEF人口密度100.0400.0010.0190.009平均作案率0.63800.4490.56510.1455.4.2求各个区的综合评价指标及其偏差综合评价指标，偏差为其中为评价指标的平均值，本文认为其偏差越小越合理用matlab计算得到的具体结果如下ABCDEF1.63700.490.5671.0190.154偏差0.9930.6450.1550.0780.3740从表中可以看出 A区设置比较不合理。 5.4.3 不合理的解决方案 对于存在不合理的设置，对于实际已存在的交巡警平台，我们考虑到经济利益，不可能重新分配平台，而只能进行增设平台处理，增设平台依据各区分配的评价标准的方差最小原则，用matlab优化工具箱中的求解有约束非线性最小值问题的fmincon函数进行优化。分配结果如下：ABCDEF20817915155.5 围堵犯罪嫌疑人最佳方案考虑到犯罪嫌疑人作案前定事先做好犯案后的以最快速度逃离该市的准备，因此本文用最短路径算法算出作案人从P点逃向市区出口的最短路线及作案人员的可能逃跑路线。利用matlab编程得到的结果见附录32 33 34 10 26 11 22 372 456 373 437 416 415 101 102 103 154 114 115 95 136 135 134 96 142 145 146 147 150 151 32 33 34 10 26 11 22 372 456 373 437 416 415 101 102 103 154 114 115 95 136 99 148 149 152 15332 7 47 5 50 51 59 58 57 60 62 190 189 192 193 194 175 196 198 17732 7 47 5 50 51 59 58 57 60 62 190 189 192 193 194 175 196 198 199 200 201 20232 7 30 48 235 173 232 231 171 228 227 172 226 224 223 222 178 204 20332 7 30 237 236 245 246 241 273 182 272 271 270 269 268 267 262 263 26432 7 30 237 236 245 246 241 273 274 179 296 297 298 299 300 303 302 316 31732 31 15 28 371 370 369 366 365 324 363 32532 33 34 10 26 11 25 24 470 469 468 466 467 449 385 448 447 339 333 334 32832 33 34 10 26 11 25 24 470 469 468 466 467 449 385 448 447 444 33232 31 15 28 371 349 320 350 355 354 356 357 360 361 36232 33 34 10 26 11 22 372 456 373 437 416 415 101 102 103 93 104 121 122 125 132 100 388 387 32 33 34 9 35 36 16 14 459 458 378 423 379 421 417 41832 33 34 9 35 36 16 560 549 548 532 533 529 521 518 505 513 512 511 48332 33 34 9 35 36 16 560 549 548 532 533 534 535 536 528 538 539 540 54132 33 34 9 35 36 39 38 561 562 480 567 569 571 485 57232 7 47 5 50 51 59 58 57 60 62 190 189 192 193 194 175 196 183 581 580 479 577 573 578在案发3分钟后接到报警，此时犯罪嫌疑人可能到达的下一节点，经过分析，所走路线所走的路程围堵交巡警标号围堵用时1、323334106.1882103.22、3274753.876850.83、32730482354.12821734、327302372364.09141735、3231154.1386151.146、32333493536163.3016160.37、3233349353639386.494716六、模型的评价参考文献1 周开利，邓春晖等,MATLAB基础及其应用教程,北京：北京大学出版社,2007.3。2 姜启源,谢金星,叶俊,数学模型（第三版），北京：高等教育出版社,2003。3 2010上海统计年鉴，/tjnj/tjnj2011.htm，20114 孙明贵，会展经济学，北京：机械工业出版社,2006,3。附录1.Floyd算法的MATLAB程序：function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,endif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end 附件2:lenroad=zeros(928,1);for i=1:928 x1=NOTE(con(i,1),2); y1=NOTE(con(i,1),3); x2=NOTE(con(i,2),2); y2=NOTE(con(i,2),3); plot(x1,x2,y1,y2,-kp); hold on; lenroad(i)=cal_distance(x1,x2,y1,y2);endw=inf(582,582);for i=1:928 w(con(i,1),con(i,2)=lenroad(i)/10; w(con(i,2),con(i,1)=lenroad(i)/10;endfor i=1:582 w(i,i)=0;endD,path=floyd(w);xyz=;for j=1:92 for i=1:20 if D(i,j)=1);for(police(i):sum(cross(j):plan(i,j)=1);for(links:bin(plan);end32 33 34 10 26 11 22 372 456 373 437 416 415 101 102 103 154 114 115 95 136 135 134 96 142 145 146 147 150 151 32 33 34 10