数学建模交巡警平台

数学建模交巡警平台 2011高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料)，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设置报名号的话): 4240 所属学校(请填写完整的全名): 肇庆学院 参赛队员 (打印并签名) :1. 郑志强 2. 王成波 3. 陈奕华 指导教师或指导教师组负责人 (打印并签名): 张中峰 日期: 2011 年 9 月 12 日 赛区评阅编号(由赛区组委会评阅前进行编号): 2011高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号(由赛区组委会评阅前进行编号): 赛区评阅记录(可供赛区评阅时使用): 评 阅 人 评 分 备 注 全国统一编号(由赛区组委会送交全国前编号): 全国评阅编号(由全国组委会评阅前进行编号): 交巡警服务平台的设置与调度问题 摘要 本文是关于交巡警服务平台的设置及调度问题，涉及管辖范围的分配、警力资源的调度、现有交巡警平台设置 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的改进和对嫌疑犯的围堵等问题。 题目中的两个大问题可以分为5个小问题，即:(1.1)管辖范围的分配问题;(1.2)快速封锁问题;(1.3)增加警务平台问题;(2.1)警务平台设置的合理性问题;(2.2)重大案件的围堵问题。 对于问题(1.1)，我们以快速到达案发地点以及各警台每天处理案件的工作量尽量均衡为准则，利用Floyd算法(求警台到路口的最短路径)及Monte Carlo随机搜索算法，得到了很好的分配方案，工作量方差处于3到6之间，见表一至表四。 )，我们以最后一个出入A区的路口节点被封锁的时间最短为优先准对于问题(1.2 则，且同时考虑完成封锁的时间总和最小，得到一个警力调度的最优方案，完成封锁的时间为8.0155分钟。 对于问题(1.3)，我们在A区增加了29,39,61,87这4个警台，使得各警台的工作量尽量均衡且避免了到达某些案发路口时间过长的问题。 对于问题(2.1)，我们利用(1.1)中的方法得到各警台的最优分配方案后，再考虑到各区的人口密度对交通的影响得到A区最好增加警台，从而使得全市的警台设置比较合理。 对于问题(2.2)，由于是重大刑事案件，故我们在防止犯罪嫌疑人逃出该市的前提下，通过在关键的交通路口进行封堵，限制他/她的活动范围，达到快速搜捕的目的，封堵方案可见图三。 我们模型的一个很大优点就是用Monte Carlo算法来求解各区的最佳管辖范围分配方案，该算法能够快速的得到一个比较优的解，在我们求解问题(1.1)以及(2.1)的最优分配方案时，取10万个样本分析后，在个人电脑上运行所用时间约为10s。缺点是Monte Carlo算法求出的解不一定是全局最优的。 关键词:警力分配 ; 警力调度; Floyd算法; Monte Carlo算法 1 一、问题重述 众所周知，警察肩负着刑事执法、治安管理、交通管理、服务群众的责任。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。某市每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，现需要根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。 有以下几个问题要解决: (1.1)为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。 (1.2)对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，需要给出该区交巡警服务平台警力合理的调度方案。 (1.3) 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。 (2.1)针对全市(主城六区A，B，C，D，E，F)的具体情况，按照设置交巡警服 明显务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。若有不合理的，给出解决方案。 如果该市地点P(第32个节点)处发生了重大刑事案件，在案发3分钟后(2.2) 接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。 二、问题分析 问题(1.1):分配管辖范围 问题(1.1)是关于A区交巡警服务平台分配管辖范围的问题。考虑到在管辖范围内出现突发事件时，要尽量在3分钟内有交巡警到达发地，即要有警台离事发地的最短路径在3km之内，故我们要尽量把各个路口分配给离它的最短路径不超过3km的警台。对于警台与路口的最短路径长度以及路线，可以用Floyd算法来求得。 若有路口离最近的警台距离超过3km，则把它分配给最近的警台。考虑到实际中，离警台很近的路口通常由该警台负责，故即使它与其它警台的最短路径不超过3km，我们也应该考虑把它分给该警台。 这样一来，再以各警台每天处理案件的工作量尽量均衡为准则的话，就可以得到一个比较合理的分配方案。 问题(1.2):实现快速封锁 在发生重大案件时，要调度A区警力资源实现对A区13条交通要道实现快速全封锁。要使全封锁时间最短，意味着最后被封锁的交通要道路口时间应该尽可能短，也就是说，应该把13条要道路口对应的最近的警台中最远的那些路口优先考虑，然后尽量减少到所有站点的总时间，以达到资源利用的最优化。 问题(1.3):增加警台 以交巡警平台处理案件的工作量与出警时间这两个指标衡量现有交巡警服务平台的工作是否过于繁重。对于出警时间过长以及工作量明显过重的区域，应该考虑增加警台。 2 问题(2.1):交巡警服务平台设置方案的合理性 评价整个市交巡警服务平台设置方案的合理性，我们首先可以按照问题(1.1)中的想法来得到各区巡警管辖范围的一个比较好的分配方案，在该方案下，同时考虑人口密度对交通拥堵，以及例行巡逻的影响，对分配方案的工作量方差进行调整，从而给出一个各区工作量方差大小的比较，通过比较来判断全市警台设置方案的合理性。 问题(2.2):最佳围堵方案 由于是重大刑事案件，故我们在 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 围堵方案时要以在该市最终抓住犯罪嫌疑人为首要目标，即要堵住犯罪嫌疑人，使得他在该市处于被包围状态，这意味着要把一些主要干道，如出入该市的路口以及进出A区的路口进行封堵，同时再在一些有咽喉之地的路口抽调较近的警力进行封堵，使得嫌疑人的活动范围尽量小。 三、模型假设 1、相邻两个路口节点之间的道路总看做直线段。 2、警车的行驶速度恒定为60，即不考虑道路上交通状况对车速的影响。 kmh/ 3、警车总是选择最短的路径赶往案发地点。 、每个时间点每个警台负责的区域只发生一起案件,且在案件处理完毕之前不再发生案4 件。 、事故均发生在路口节点处。 5 6、交巡警的工作量是由例行巡逻和处理案件两部分组成。每个交巡警服务平台有警员负责例行的巡逻，有警员留在交巡警服务平台处于待命状态。 7、若无突发事件发生，每个交巡警服务平台负责例行巡逻的警员工作量相同。 8、每个交巡警服务平台所在街道节点属于该交巡警服务平台的管辖范围。 9、每个交巡警服务平台所在街道节点的发案率相当，近似认为每个交巡警服务平台处理该街道节点的工作量相同。 10、我们在文中说的交巡警服务平台的工作量即为该警台处理案件的工作量。 四、符号 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 路口节点与交巡警服务平台之间最短路径长度 dmin 从交巡警服务平台出发，警车到达路口节点的时间 t 标号为的路口节点的发案率 fkk 标号为的路口的发案比例系数 ,kk fk =,kA区平均发案率 标号为的交巡警平台 dJd 标号为的路口节点 Pkk 到的最短路径长度，单位km LJPdkdk 3 到的最短路径长度与的发案比例系数的乘积，即 SJPPSL=，,dkdkkdkdkk SS, ，其中求和对它所管辖区域内的所有路口节点进行 S,ddkdk 五、模型的建立与求解 (一)、建立路网 根据题目附录2中提供的A区的各节点坐标轴及节点编号，通过Matlab软件编程建立A区路网。得出A区路网下图: 编号1至20为交巡警服务平台 图一 (二)、问题(1.1):分配管辖范围问题的模型建立与求解 模型一:Monte Carlo模型 通过问题分析中对问题(1.1)的讨论，我们可以按以下的步骤来建立模型。 (1)利用Floyd算法得到A区各警台到A区所有路口的最优路径长度以及对应的路线。 (2)距离某警台很近的路口归该警台管辖。我们把离最近警台的最短路径不超过 的路口都分配给该警台管辖。 1km (3)离最近警台的路程超过3的路口节点分配给该警台管辖。 km (4)对于离最近的警台在1至3内的路口节点，利用蒙特卡罗算法，把它随机km 4 分配离它路程在1至3内的交巡警平台。运用蒙特卡罗算法，通过Matlab软件编程km 可得到许多分配方案即样本，算出它们的方差(定义见接下来的段落)，累积选取一定的数目的样本后，得到一个方差最小的作为我们的最优分配方案。 处理案件的工作量( 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化案件工作量) 给出分配方案以后，考虑到每个路口的发案通常是独立事件，所以我们以交巡警平台到路口节点的的最短路程乘上该路口的发案比例系数作为该交巡警平台对这个路口的标准化案件工作量，简称工作量。 以该交巡警平台管辖范围内所有路口的工作量的和作为该交巡警平台的工作量。 设为标号的路口节点的发案率，定义 fkk fk ,=k92 f/92,kk,1 为标号为的路口的发案比例系数。设为标号为的交巡警平台，为标号为的路dkJPkdk口节点，为对的工作量，为的工作量，为到的最短路径长度，则 SLJPSJJPdkdkdddkdk SS,SL,，, ， ， ,ddkdkdkkk J其中的求和对管辖范围的所有路口进行。 ,dk 这样一来，由蒙特卡罗算法给出一个分配方案，就可得到一个工作量向量 20201122(S-S)S,SS,SSSS,(,,,),工作量的样本方差，其中.我,,ii样12202020-1i=1i=1们的目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 即为 2minS. 样 5n,10取样本数目后，得到其中工作量的样本方差最小的方案: 交巡警平台编所管辖范围(用节点编号表示所管辖的区域) 号 A1 69 74 75 78 71 72 73 76 A2 43 44 70 39 A3 54 55 64 66 A4 62 57 60 63 65 A5 49 50 51 53 56 A6 52 58 59 A7 30 61 48 A8 33 46 32 37 47 A9 34 35 31 45 5 A10 无 A11 26 27 A12 25 A13 21 22 23 24 A14 无 A15 28 29 A16 36 38 A17 41 42 40 A18 80 81 83 82 84 88 90 A19 79 77 A20 85 86 89 92 87 91 表一 2minS对应的=5.6672. 样 从上表我们发现警台A10,A14不管辖除本身外的其它路口节点,出现这种情况的原因是 它们离其它路口都比较远.但在实际中我们总是希望它能至少管一个除本身外的其它路 口,如把离它最近的路口分一个给它,这就有了下面我们微调后的改进模型。 模型二:微调的Monte Carlo模型 方案一:将离交巡警平台A10最近的节点26分配给它管辖，其它不变,继续模型一中的 过程可得到下面的分配方案: 交巡警平台所管辖范围(用节点编号表示所管辖的区域) 编号 A1 69 74 75 78 68 71 72 73 76 A2 43 44 70 39 A3 54 55 64 67 A4 62 57 60 63 66 A5 49 50 53 58 A6 48 51 52 56 59 A7 30 61 31 A8 33 46 47 A9 34 35 32 37 45 A10 26 A11 27 A12 25 A13 21 22 23 24 A14 无 A15 28 29 A16 36 38 A17 41 42 40 A18 80 81 83 90 91 A19 77 79 65 82 6 A20 85 86 89 92 84 87 88 表二 2minS对应的=5.1943. 样 方案二:将离交巡警平台A14最近的节点21分配给它管辖，其它不变,继续模型一中的 过程可得到下面的分配方案: 交巡警平台所管辖范围(用节点编号表示所管辖的区域) 编号 A1 69 74 75 78 68 71 72 76 A2 43 44 70 39 A3 54 55 66 A4 62 57 60 63 64 A5 49 50 51 53 58 A6 47 52 56 59 A7 30 48 61 A8 33 46 32 45 A9 34 35 31 A10 无 A11 26 27 A12 25 A13 22 23 24 A14 21 A15 28 29 A16 36 38 37 A17 41 42 40 A18 80 81 83 73 82 84 91 A19 77 79 65 67 A20 85 86 89 92 87 88 90 表三 2minS对应的=4.6404. 样 方案三:节点26分配给交巡警平台A10管辖，节点21分配给交巡警平台A14管辖,其 2minS它不变,继续模型一中的过程可得到下面的分配方案.由于对应的=3.6502比较样 小，我们把由Floyd算法的到的具体路线也给出(见附录)。 交巡警平台所管辖范围(用节点编号表示所管辖的区域) 编号 A1 69 74 75 78 68 72 73 76 A2 43 44 70 39 A3 54 55 65 66 A4 62 57 60 63 64 A5 49 50 51 53 59 A6 52 56 58 7 A7 30 61 32 48 A8 33 46 47 A9 34 35 31 37 45 A10 26 A11 27 A12 25 A13 22 23 24 A14 21 A15 28 29 A16 36 38 A17 41 42 40 A18 81 80 83 82 84 91 A19 77 79 67 71 A20 85 86 89 92 87 88 90 表四 从这三个方案我们发现，适当的微调可以使得各警台的工作量更加均匀，从而在总工作量没太多变化的情况下让管辖区域分配方案更加合理。 (三)、问题(1.2)的模型建立与求解 实际中一个平台的警力最多封锁一个路口，我们以一个平台能封锁一个路口为标准。要实现对进出该区的13条交通要道实现快速全封锁，就要求最后到达封锁路口警务台所用时间最短。在满足最后到达封锁路口警务台所用时间最短这个原则后，需满足全部交巡警服务平台完成封锁时间总和最小。我们用floyd算法编程分别求出A区20个巡警平台到各个交通要道路口的最短时间如下表:(其中行表示需要封锁的路口节点，列表示交巡警平台编号) A区交巡警平台1至10到各个交通要道路口的最短时间(单位:分钟) 1 2 3 4 5 6 7 8 9 10 12 22.2362 20.4640 18.3523 21.9974 17.6281 17.6587 14.9149 14.0924 13.0107 7.5866 14 16.0285 14.1298 12.7673 15.0086 12.9697 13.0003 10.9013 9.4340 8.2743 12.7758 16 9.2868 7.3881 6.0256 8.2669 6.2280 6.2586 4.1596 2.6923 1.5326 6.9567 21 19.2935 17.3948 16.0323 18.2736 16.2347 16.2653 14.1663 12.6990 11.5393 9.5108 22 21.0963 19.1976 17.8351 20.0764 17.7495 17.7801 15.0363 14.2138 13.1321 7.7080 23 22.5018 20.6031 19.2406 21.4819 19.1550 19.1856 16.4418 15.6193 14.5376 9.1135 24 22.8933 21.1211 19.0094 22.6545 18.2852 18.3158 15.5720 14.7495 13.6678 8.2437 28 19.0012 17.2290 15.1173 16.2268 11.3068 11.3374 8.5702 10.2280 9.7757 14.1948 29 19.5159 17.7437 15.6320 15.5353 10.6153 10.6459 8.0155 10.4932 10.7244 15.1435 30 12.0835 10.3113 8.1996 8.1029 3.1829 3.2135 0.5831 3.0608 3.4923 7.9114 38 5.8809 3.9822 6.0939 4.8610 9.4211 9.4517 7.3527 5.8854 4.7257 10.1498 48 11.8502 10.3096 8.1979 7.3958 2.4758 2.5064 1.2902 3.0995 4.1994 8.6185 62 4.8853 6.0351 4.3934 0.3500 5.2549 5.3372 7.9915 8.6774 9.3367 14.7608 表五 8 A区交巡警平台11至20到各个交通要道路口的最短时间(单位:分钟) 11 12 13 14 15 16 17 18 19 20 12 3.7914 0 5.9771 11.9504 17.0296 14.5433 21.8921 24.2472 22.5466 26.9458 14 8.3374 11.9504 5.9733 0 13.2982 6.7417 14.9033 18.5145 16.9616 21.2131 16 11.3951 14.5433 12.7150 6.7417 6.5565 0 8.1616 11.7728 10.2199 14.4714 21 5.0724 8.6854 2.7083 3.2650 16.5632 10.0067 18.1683 21.7795 20.2266 24.4781 22 3.2696 6.8826 0.9055 5.0678 17.1510 11.8095 19.9711 23.5823 22.0294 26.2809 23 4.6751 6.4771 0.5000 6.4733 18.5565 13.2150 21.3766 24.9878 23.4349 27.6864 24 3.8053 3.5917 2.3854 8.3587 17.6867 15.1004 22.5492 24.9043 23.2037 27.6029 28 18.6332 21.7814 22.8083 18.0500 4.7518 11.3083 18.6571 21.0122 19.3116 23.0106 29 19.5819 22.7301 23.7570 18.9168 5.7005 12.1751 19.5239 21.5269 19.8263 22.3191 30 12.3498 15.4980 16.5249 11.4844 4.4015 4.7427 12.0915 14.0945 12.3939 14.8867 38 14.5882 17.7364 16.1209 10.1476 9.7496 3.4059 4.7557 8.3669 7.6392 11.0655 48 13.0569 16.2051 17.2320 12.1915 5.1086 5.4498 12.7986 13.6992 11.9986 14.1796 62 19.1992 22.3474 21.3319 15.3586 11.8099 8.6169 7.8205 6.7343 5.0337 6.4489 表六 从以上的最短时间找出20个警务台到每个出入口中所用时间最短的一个,13 个封锁路口即得13个最短时间。我们首先对比这13个最短时间，从数值最大的开始分配，显然这13个最短时间中有出现对应同一个巡警平台的。这时我们就要比较次短的时间，选择次短中最小的，使最终选择的时间的最大值达到最小。以此类推得出的封锁13条交通要道相对于的交巡警服务平台。再通过用floyd算法求具体最短路径。并根据确定好的封锁方案找出对应的路径。综上，得出A区对13条交通要道实施快速封锁的调度方案为如下表: 其中对13个交通要道完成全封锁的时间为8.0155分钟。各交巡警服务平台封锁所用时间总和为49.1233分钟。 封锁路口需要调动的警务台封锁路口所用最少时间 具体路径 编号 编号 单位:分钟 12 10 10?26?27?12 7.5866 14 16 16?14 6.7417 16 9 9?35?36?16 1.5326 21 14 14?21 3.2650 22 11 11?22 3.2696 23 13 13?23 0.5000 24 12 12?25?24 3.5917 28 15 15?28 4.7518 29 7 7?30?29 8.0155 30 8 8?33?32?7?30 3.0608 38 2 2?40?39?38 3.9822 48 5 5?47?48 2.4758 62 4 4?62 0.3500 表七 (四)、问题(1.3)增加警务平台的模型建立与求解 9 以交巡警平台工作量与出警时间这两个指标衡量现有交巡警服务平台的工作是否过于繁重。分别20个交巡警平台工作量和出警时间比较得出交巡警平台A20的工作量过大，交巡警平台A15的出警时间过长。 从问题(1.1)可知28,29，38,39,61,92无任何交巡警能在交巡警平台出发3分钟内到达，所以在A区增加2到5个平台应重点结合这6个道路节点考虑。 综上初步决定在以下四个区域增加平台，增加平台的区域如下图: 6120 858658Z603896885059578462519087915835246348194780825618774979763053816475787665468165926732748Z'6937333133557146704472243349424535291715373639401628413810 12 27 261125 1424 21 2213 23 图二 在节点20,92所处的区域，节点87离92距离最近，且能有效分担交巡警服务平台A20的工作量。 在节点39,38所处区域，节点39离节点38、40较近，能有效减少交巡警服务平台A17的出警时间。 在节点61所处的区域，由于节点61离交巡警服务平台较远，导致出警时间过长，所以在61节点安置交巡警服务平台。 在节点15,28,29所在区域，由于交巡警服务平台A15出警时间过长，无法有力监管节点28,29，所以在节点29安置交巡警服务平台。 所以最终确定安置87,61,39,29这4个平台。 (五)、问题(2.1)的模型:交巡警服务平台设置方案的合理性 通过问题分析中对问题(2.1)的讨论，我们可以按以下的步骤来建立模型。 (1)、我们按(1.1)中的Monte Carlo模型来给出B、C、D、E、F各区各警点的管辖范围(见附录)，以及对应的方差见下面的表格。A区的方差我们用以同样方式得到 10 的方案对应的方差。 所属区域 方差 A 5.6672 B 68.6704 C 104.1222 D 334.0086 E 471.3575 F 265.9463 表八 (2)、由于人口密度会影响办案，如造成交通拥堵影响办案时的车速等，故我们把人口密度考虑到各区的方差中来，得到修正的方差。再看一下它们的大小情况来推断它们的合理性。修正方式如下。 i区人口数,, 区人口密度 ，, i,1,2,...,6iii区面积 ,i,,人口密度比例系数 i6 /6,,ii1, 22minS,,,,，,修正方差，其中为区对应的方差 iiii样i修正 最后有 所属区域 方差(修正前) 方差(考虑人口密度修正后) A 5.6672 110.0823 B 68.6704 7.4546 C 104.1222 13.3673 D 334.0086 31.6882 E 471.3575 38.0980 F 265.9463 25.9858 表九 从修正方差我们可以看出来，A区比其它各区的要大很多，故应该考虑增加警台，如我们(1.3)给出的方案。 (六)、问题(2.2)重大案件的最佳围堵的模型建立和求解 为了快速搜捕嫌疑犯，需要调动全市交巡警服务平台的警力资源对重点路口实施快 11 速封锁。重点路口是指要进出某些区域的必经路口，如:市区进出口和各区的进出口。 本题实质是解决在抓住罪犯的前提下，使得逮捕罪犯的时间尽量快，追捕范围尽量小的问题。具体实施步骤有: (1)、抽调距离最近的交巡警服务平台封锁各重要路口，保证嫌疑犯处于包围圈中。 (2)、让嫌疑犯在犯案逃跑直至被逮捕前活动范围尽量小，即一方面使得活动的区 可采取封锁进入临近区的相连路口的方法控制嫌疑犯的活动范围。另一方数目尽量小， 面在可能活动的区内让活动范围尽量小。假设罪犯肇事后以120km/h的速度逃走，那么接到报案时罪犯能走最大路程6km.现在我们以案发地P为中心向外扩张6.5km，以确定罪犯还在包围圈里，然后快速封锁出这个包围圈的重要路口，最后进行全市快速追捕。具体方案分区封锁。 D区:因为从案发地点可能进入D区的路口只有路口349和369，又因为这距离太远，所以只需在路口349和369设置关卡。离这两个路口最近的交巡警平台分别是D2和D1，所以交巡警平台D2和D1的警员分别抽调到路口349和369以防止罪犯逃进D区。 E区:从A区进入E区的路口有12、14、21、22和24.由于3分钟后嫌疑犯可能已经越过A14，所以要在进入E区的路口457进行快速封锁，由最近的E3的警员在路口457设置关卡，也要在下一个路口22出设置关卡，由A13的警员负责。再由E7在原处设卡。 F区:因为案发地点距离F区比较近，而且F区街道较多、警力有限，不能预防罪犯逃到F区，所以只需在F区的出口设卡防止罪犯从F区逃往外地。具体是:由F10到路口540处设卡，F6到路口568处设卡，F11和F9在原处设卡。 C区:因为案发地点距离C区比较近，而且C区北面街道较多、警力有限，由于包围圈还没扩展到北面，所以要把罪犯限制在C区南面进行搜捕.具体如下:由C1到路口261设卡，C14到路口273设卡，C9到路口211设卡，C2、C17、C5和C13在原处设卡。 A区:由于大部分警力在A区，所以要在其他区设卡的同时A区在案发地点附近的交警进行全市追捕。 B区: 欲到达B区，必须经过E区，由于E区与A区相连接的道路已被封锁，所以嫌疑犯不可能到达B区。 路径 距离(km) A4?62 0.35 A13?22 0.9055 C1?261 4.8243 C9?211 2.3693 C11?176 6.718 C14?273 2.5866 D1?349 0.3606 D2?369 4.185 E3?457 2.816 E8?581 2.41 F6?568 1.9313 F10?540 3.3526 表十 因为封锁离案发地点较近的路口的距离都比较短，而且封锁距离较长的路口都离案发地点较远。综上所述，嫌疑犯突出包围圈的机会为零。故此方案合理可行。 12 图三 六、模型的评价 (一)、模型的优点: (1)本模型运用了蒙特卡罗算法和Floyd算法,能较好的处理数据，并在数据量很庞大时能比较快速的得到一个较优的方案。 (2)问题(1.1)、(1.2)、(1.3)、(2.1)、(2.2)的模型具有较好的推广性，可用于其他城市解决类似的问题，而且(1.1)的模型还可用于人力物力资源的分配问题，(1.2)的模型可以用于线路的安装建设、交通要道的选址问题等等，问题(2.1)的模型可以用作类似问题的评价。 (二)、模型的缺点: 蒙特卡罗算法得到的解不一定最优，在数据量比较小时，有一定的缺陷。 参考文献 [1] 熊晓雯，张斌，李厚森，110警车配置及确定巡逻方案的问题，数学的实践与认识，2010,40(15) [2] 黎志涛，沙志仁，伍洪俊，警车配置及巡逻方案研究，数学的时间与认识，2010,40 13 (15) [3]王海英、黄强、李传涛，图论及其Matlab实现，北京，北京航空航天大学出版社，2010年 [4]姜启源，谢金星，叶俊，数学模型(第三版)，北京，高等教育出版社，2003年 李南南，吴清，曹辉林，Matlab简明教程，北京，清华大学出版社，2006年 [5] 14 附录: 一、方案四的最短路径: 具体最短路径 交巡警平台编号 管辖节点编号 69 1?69 A1 74 1?74 A1 75 1?75 A1 78 1?78 A1 68 1?69?68 A1 72 1?69?71?72 A1 73 1?74?73 A1 76 1?75?76 A1 2?43 A2 43 2?44 A2 44 2?70 A2 70 2?40?39 A2 39 3?55?54 A3 54 3?55 A3 55 3?65 A3 65 3?65?66 A3 66 4?62 A4 62 4?57 A4 57 4?62?60 A4 60 4?63 A4 63 4?63?64 A4 64 5?49 A5 49 5?50 A5 50 5?50?51 A5 51 5?49?53 A5 53 5?50?51?59 A5 59 6?59?51?52 A6 52 6?59?51?52?56 A6 56 6?59?58 A6 58 7?30 A7 30 7?30?48?61 A7 61 7?32 A7 32 7?30?48 A7 48 8?33 A8 33 15 8?46 A8 46 8?47 A8 47 9?34 A9 34 9?35 A9 35 9?35?36?37 A9 37 9?34?31 A9 31 9?35?45 A9 45 26 10?26 A10 11?26?27 A11 27 25 12?25 A12 13?22 A13 22 13?23 A13 23 13?24 A13 24 14?21 A14 21 15?28 A15 28 15?28?29 A15 29 16?36 A16 36 16?38 A16 38 17?40 A17 40 17?41 A17 41 17?42 A17 42 18?81 A18 81 18?80 A18 80 18?83 A18 83 18?83?82 A18 82 18?83?84 A18 84 18?83?82?90?91 A18 91 19?77 A19 77 19?79 A19 79 19?77?76?75?68?67 A19 67 19?79?78?1?69?71 A19 71 20?85 A20 85 20?86 A20 86 20?89 A20 89 20?86?87?92 A20 92 20?86?87 A20 87 20?86?88 A20 88 20?89?90 A20 90 16 二、改进后的全市各交巡警服务平台设置方案: 警务台编号 所管辖范围(用节点编号表示所管辖的区域) B1 101 102 103 104 105 B2 106 107 108 109 110 122 123 117 119 120 121 B3 115 111 112 113 114 116 118 126 154 B4 134 138 139 142 124 151 127 128 131 B5 137 143 144 129 130 146 147 B6 163 164 155 156 157 158 159 160 161 162 165 B7 148 152 153 136 140 141 145 149 B8 132 125 133 135 150 警务台编号 所管辖范围(用节点编号表示所管辖的区域) C1 262 263 264 265 C2 250 248 251 252 259 261 249 255 258 260 C3 189 190 191 192 193 C4 254 C5 225 273 275 276 277 278 280 283 C6 216 230 231 215 240 253 241 242 245 246 C7 217 218 227 228 223 224 226 229 243 C8 233 235 236 238 239 247 232 234 237 244 C9 219 220 211 212 213 214 221 222 C10 196 197 183 199 194 195 198 C11 188 184 185 186 187 C12 200 201 202 C13 203 205 206 207 208 209 210 286 287 204 284 C14 296 285 288 279 281 282 289 290 291 292 297 306 307 268 269 299 300 301 302 303 304 312 313 C15 314 315 316 298 305 310 311 C16 317 318 319 266 267 308 309 C17 272 293 257 256 270 271 274 294 295 警务台编号 所管辖范围(用节点编号表示所管辖的区域) D1 347 348 349 350 370 371 D2 354 355 356 357 358 359 369 351 357 368 D3 361 367 D4 344 362 345 D5 364 365 366 D6 363 D7 343 346 352 353 360 D8 341 337 338 340 342 D9 329 330 331 332 336 339 333 334 335 17 警务台编号 所管辖范围(用节点编号表示所管辖的区域) E1 457 E2 438 437 456 E3 432 433 434 435 436 426 431 E4 424 425 426 427 428 429 430 E5 无 E6 416 E7 458 459 E8 417 418 419 420 421 422 423 E9 387 388 389 390 391 392 393 394 395 E10 398 399 405 397 400 401 404 406 E11 407 408 409 410 411 412 413 414 415 402 403 E12 460 452 455 464 469 453 454 461 462 463 470 E13 471 449 465 466 467 468 472 E14 448 445 446 451 474 450 473 E15 439 443 396 440 441 442 444 447 警务台编号 所管辖范围(用节点编号表示所管辖的区域) F1 555 556 557 559 561 550 558 563 564 565 544 545 546 553 533 534 535 536 543 547 548 551 F2 552 554 498 500 501 505 506 507 508 509 516 517 518 519 F3 522 523 529 493 494 495 496 499 502 503 504 520 521 542 512 513 514 515 524 525 526 527 528 537 538 F4 539 F5 580 575 578 582 573 576 577 579 581 F6 566 569 574 562 567 568 F7 531 486 490 491 492 497 530 532 549 F8 487 560 488 489 F9 510 511 F10 540 541 570 F11 571 572 三、部分源程序 function main3() %A区管辖范围分配方案程序 clc LJ=load('A_dis.txt'); b1=load('faanlv.txt'); [col,num]=size(LJ); nn=zeros(92,92); for i=1:col 18 nn(LJ(i,1),LJ(i,2))=1; nn(LJ(i,2),LJ(i,1))=1; end dis=zeros(92,92); for i=1:col B(LJ(i,1),LJ(i,2))=LJ(i,3); B(LJ(i,2),LJ(i,1))=LJ(i,3); end for i=1:92; for j=1:92; a(i,j)=B(i,j)*nn(i,j); end end a(find(a==0))=inf; for i=1:92; for j=1:92; if i==j; a(i,j)=0; end end end a(:,1); [D,path]=floyd(a); pp=zeros(20,23); dd=zeros(20,23); pp1=zeros(20,72); dd1=zeros(20,72); pp2=zeros(20,72); dd2=zeros(20,72); for i=1:20 t=1; for j=21:92 if (D(i,j)<=1) dd(i,t)=D(i,j); pp(i,t)=j; t=t+1; end end end for ii=1:20 19 for jj=21:92 if (D(ii,jj)>3) dd1(ii,jj-20)=D(ii,jj); pp1(ii,jj-20)=jj; end end end pp; pp1; dd; dd1; path; ddj=zeros(72,1); GSJ=zeros(20,25); pp(9,3)=0; pp(19,3)=0; pp; for i5=1:72 ddj(i5,1)=20+i5; end for i6=1:20 flg=0; for j6=1:23 if pp(i6,j6)~=0 flg=flg+1; GSJ(i6,flg)=pp(i6,j6); ddj(pp(i6,j6)-20,1)=0; end end end u=200*ones(1,72); v=zeros(1,72); for j8=1:72 for i8=1:20 if u(1,j8)>dd1(i8,j8) u(1,j8)=dd1(i8,j8); v(1,j8)=i8; end end end flg1=zeros(1,20); for j7=1:72 if v(1,j7)~=0& u(1,j7)~=0 flg1(1,v(1,j7))=flg1(1,v(1,j7))+1; 20 GSJ(v(1,j7),5+flg1(1,v(1,j7)))=j7+20; ddj(j7,1)=0; end end for ii1=1:20 for jj1=21:92 if D(ii1,jj1)>1&D(ii1,jj1)<=3&ddj(jj1-20,1)~=0 dd2(ii1,jj1-20)=D(ii1,jj1); pp2(ii1,jj1-20)=jj1; end end end js=0; ddj1=zeros(37,1); for i9=1:72 if ddj(i9)~=0 js=js+1; ddj1(js,1)=ddj(i9,1); end end js; GSJ; ddj'; ddj1'; dd2; pp2; ztm=zeros(37,5); js1=zeros(37,1); for ii2=1:37 flg2=0; for jj2=1:20 if pp2(jj2,ddj1(ii2,1)-20)==ddj1(ii2,1) flg2=flg2+1; ztm(ii2,flg2)=jj2; end end js1(ii2,1)=flg2; end ztm; js1; js2=zeros(37,1); zjs=zeros(37,1); %GSJ(10,1)=26;GSJ(11,1)=0;%微调项 GSJ(14,1)=21; 21 ZGSJ=GSJ; ZZGSJ=GSJ; fc=10000; qxs=sum(b1(1:92,1))/92; for nn1=1:100000 GSJ=ZGSJ; flg3=ones(20,1); fc1=0; for ii3=2:37 js2(ii3,1)=unidrnd(js1(ii3,1)); zjs(ii3,1)=ztm(ii3,js2(ii3,1)); GSJ(zjs(ii3,1),8+flg3(zjs(ii3,1),1))=ddj1(ii3,1); flg3(zjs(ii3,1))=flg3(zjs(ii3,1))+1; end X=zeros(20,1); for ii4=1:20 for jj4=1:25 if GSJ(ii4,jj4)~=0 X(ii4)=X(ii4)+D(ii4,GSJ(ii4,jj4))*b1(GSJ(ii4,jj4),1)/qxs; end end end fc1=var(X); if fc1