当前位置： >>
2011年全国数学建模获奖论文
交巡警服务平台的设置与调度
交巡警服务平台的设置与调度摘 要当今社会， 交巡警在维护社会治安中有着极其重要的作用。在一些交通要道和重要 部位设置固定的交巡警服务平台是维护社会治安的重要手段。 每个交巡警服务平台的职 能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理 地设置交巡警服务平台、 分配各平台的管辖范围、调度警务资源是警务部门面临的一个 实际课题。 对于问题一，针对该城区A地图的特点，我们引进图论的知识。利用Matlab编程实 现Dijkstra算法，以3km为管辖范围，先求出A区内的1-20号交巡警服务平台各自管辖的 节点的情况。对于未被管辖到的节点，本文以最短路径优先原则去解决，令这些节点属 于离它们最近的平台的管辖范围。对于被重复管辖的节点，我们引入隶属度，制定被重 复管辖节点的分配原则。最后得到新的平台管辖范围表。 针对重大突发事件，我们从时间和路程的角度考虑，在20个平台中挑选出13个平台 出动警力赶赴13个进出A区的路口节点，使完成围堵的时间最小，同时使总路程尽可能 的小。根据Dijkstra算法原理利用Matlab编程得到出入口的围堵方案为：Q1-Q62、Q7-Q29、 Q11-Q23、 14-Q14、 19-Q22、 2-Q38、 8-Q30、 12-Q12、 15-Q28、 5-Q48、 10-Q24、 13-Q21、 Q Q Q Q Q Q Q Q Q Q16-Q16，成个过程所需要的时间为8.244min。 针对现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况， 我 们引入平台需求指标和不均衡度指标。根据这两个指标计算出 A 区中所需要增加的交 巡警服务平台个数为 4 个。 在选择具体的平台设置位置时，我们始终坚持最优原则并且 通过 Matlab 编程寻找出最佳安置节点分别为节点 71、节点 39、节点 92、节点 61。 对于问题二，通过对全市现有交巡警服务平台设置方案的分析，发现该设置方案存 在着明显的不合理性。再根据各区服务平台的警力负担，算出 A~F 区域的修正平台数 分别为：-9、-1、0、+3、+2、+3。最终得到了 A~F 各区修正后的服务平台号。 最后，对嫌疑犯的围堵方案分析，首先得到嫌疑犯 3 分钟、至少花 9 分钟、12 分 钟能够到达的节点位置作出一、二、三道防线。运用 Matlab 编程得到平台警力到达第 二道防线的时间约为 5.2min，到达第三道防线的时间约为 8.4min，与嫌疑犯到达二、 三道防线的最小时间 6 分钟、9 分钟作比较，判断出平台警力比嫌疑犯提早到达防线来 实现封锁的效果，再让第一道防线的警力作外扩搜捕，而让第三道防线作收缩搜捕，这 样来实现对目标点的围堵。关键词：Dijkstra 算法；隶属度；Matlab 编程；最短路径优先原则；1一、 问题重述交巡警属于人民群众公共安全保护系统的一部分，承担着十分重要的责任。警察肩 负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些 职能， 需要在市区的一些交通要道和重要部位设置交巡警服务平台。本文假定每个交巡 警服务平台的职能和警力配备基本相同。由于警务资源是有限的，那么根据城市的实际 情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务 部门面临的一个实际课题。 就某市设置交巡警服务平台的相关情况， 本文通过建立数学模型分析研究了下面的 几个问题。 问题一： (1). 附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服 务平台的设置情况示意图，其中相关的数据信息见附件 2。本文为各交巡警服务平台分 配了管辖范围， 使其在所管辖的范围内出现突发事件时， 尽量能在 3 分钟内有交巡警 （警 车的时速为 60km/h）到达事发地。 (2). 对于 A 区的重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源， 对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路 口，本文中给出了 A 区交巡警服务平台警力合理的调度方案。 (3). 根据 A 区中现有交巡警服务平台的工作量不均衡性和有些地方出警时间过长 的实际情况，拟在该区内再增加 2 至 5 个平台，确定需要增加平台的具体个数和位置。 问题二： (1). 针对全市（主城六区 A，B，C，D，E，F）的具体情况，本文按照设置交巡 警服务平台的原则和任务，分析研究了该市现有交巡警服务平台设置方案（参见附件） 的合理性。对于有明显不合理的情况，给出了解决方案。 (2). 如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接 到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，本文给出了调度全市交巡警服 务平台警力资源的最佳围堵方案。二、基本假设(1). (2). (3). (4). 事故发生只在路口节点处； 由于交巡警服务平台有先进的通讯设备，不考虑信息的传递的时间延差； 警车能由最短路径到达事发地； 警车能由最短路径到达事发地； 警车去事发现场时做匀速运动， 不考虑车辆的调头、 启动、停止时的加减速过程，不考虑路况、单行道、红绿灯。三、定义与符号说明? l (i, i ) ：表示该城市内任意相邻交叉路口见的距离；d (i, j ) ：表示任意两交叉路口间距离；di ?…? j ：表示任意两交叉路口通过路径“节点 i ―?―节点 j ”的路程；2K ? xi , yi ? 表示第 i 个交叉路口坐标 ( xi ? (0,500), yi ? (0,600)) ； K ( xi , yi ) 表示第 i 个交叉路口的邻接路口集合，坐标表示；Qi ：表示第 i 个交叉路口的节点；WQ j ：表示第 j 平台的警力总工作量；?Q ,Q ：表示第 k 个节点归属于第 j 个节点管辖的隶属度；j kW ：表示平台的总工作量的平均值；D ：表示平台工作量的均衡度；? ：表示平台的需求指标；?i ：无量纲化后第 i 块城区的面积 ?i ? A, B, C, D, E, F ? ；?i ：无量纲化后第 i 块城区的人口 ?i ? A, B, C, D, E, F ? ；? i ：无量纲化后第 i 块城区的总结点数 ?i ? A, B, C, D, E, F ? ；?i ：无量纲化后第 i 块城区内的总发案率 ?i ? A, B, C, D, E, F ? ；? i ：第 i 块城区的警力压力 ?i ? A, B, C, D, E, F ? 。四、问题分析4.1 问题一的分析 4.1.1. 对 A 区交巡警服务平台管辖范围的分析 首先，交巡警服务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有 交巡警（警车的时速为60km/h）到达事发地。基于题目中的这个要求，本文给出了一个 连接若干个交叉路口的节点的网络。在这个网络的两个任意指定的节点间，找出一条最 短路径，将实际问题转化为图与网络的基本问题。为求最短路径，我们采用广为人知的 Dijkstra算法，并给出了具体的算法步骤。 接着，在构造出算法步骤的基础上，实现Matlab编程求解最短路径及其长度。即可 以分别计算出A城区中1-20号平台以3km为管辖范围所能管辖到的交叉路口的节点情 况。进一步分析A城区的每个节点，无非就是两种情况：1. 节点不属于任何一个平台的 管辖范围；2.节点能被平台管辖到，但是能管辖它的平台个数不定。 对于情况1，本文以最短路径优先原则去解决，就是找到与这些节点距离最近的平 台，令这些节点属于离它们最近的交巡警平台的管辖范围。对于情况2中被重复管辖的 节点，本文引入隶属度，制定被重复管辖节点的分配原则。 4.1.2. 对A区重大突发事件调度方案的分析 对于重大突发事件， 需要调度全区20个交巡警服务平台的警力资源，对进出该区的 13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，并且各个服3务平台的巡警车是同时出发的。 我们从时间和路程的角度考虑，在20个交巡警服务平台 中挑选出13个平台出动警力赶赴13个进出城区的路口节点，使得完成围堵的时间最小， 同时使总路程尽可能的小。计算过程仍按照Dijkstra算法原理并由Matlab编程求解。 4.1.3. 对增加平台方案的分析 向 A 区内增加 2 至 5 个平台， 增加平台的具体个数和位置需要根据现有交巡警服务 平台的实际情况而定。 而这情况主要表现在工作量不均衡和有些地方出警时间过长这两 方面。 根据问题一第一小题中给出的分配方案，我们定义交巡警服务平台工作量的不均 衡度 D ，利用它从整体上来评价新增平台方案的优劣。 我们引入平台的需求指标 ? ，以此来确定增加平台个数的方案。然后，进一步来确 定安置平台的具体位置。 在位置的选择过程中，我们始终坚持最优原则并且通过Matlab 编程寻找出最佳安置节点。 通过比较增加平台前后不均衡度的变化，筛选出最优的增加 平台的方案。 4.2 问题二的分析 首先，根据 A 区域中交巡警服务平台的调度方案，我们可以类似地得到 B，C，D， E，F 区的交巡警服务平台的调度方案。从得到的调度方案中判断出该市现有交巡警服 务平台设置方案的合理性。若未出现不合理现象，那么该小问题回答完成，反之，我们 需要改进平台的设置。引入服务平台的警力压力 ? ，并且易发现 ? 与城区的面积、城区 的人口、总结点数、区域内的总发案率成正相关。据此我们可以得到每个区域所分得的 服务平台数的比值，再根据全市总服务平台数，就可以求出各区中分配到的平台数。在 这个基础上我们来对每个区域的服务平台进行分配。 在分配时考虑每个分区各自的均衡 性和出警时间长， 因此在需要增加服务平台的区域内我们采用与问题一中的第三小问的 类似的方法来解决。 而对于需要减少服务平台的区域而言，我们可以从每个平台所管辖 的节点个数和总发案率为依据，来减少平台。最终得到全市修改后的平台分布。 在围堵嫌疑犯时， 由于此问题是一个追捕围堵一个动态的嫌疑犯，我们首先要去得 到事发之后嫌疑犯 3 分钟可能到达的所有节点作为第一道防线， 然后预测嫌疑犯至少花 9 分钟、12 分钟能够到达的节点位置作为第二、三道防线。要使平台警力比嫌疑犯提早 到达节点位置来实现封锁的效果，运用 Matlab 编程得到平台警力到达防线的最小时间 方案。再让第一道防线的警力作外扩搜捕，而让第三道防线作收缩搜捕，这样来实现对 目标点的围堵。五、模型的建立与求解5.1 数据的处理 1. 区域 A 图像的处理 从附件 1 中的附图 1 给出的该市中心城区 A 的交通网络和现有的 20 个交巡警服务 平台的设置情况示意图，我们利用附件 2 中的相关数据将其进行标号。得到如图 1 所 示的交通示意图（具体程序见附录 1） 。4区 域 A的 交 通 网 络 示 意 图 400 20
84 89 6 50 57 62 88 59
4 5 52 83 63 48 47 49 56 19 80 82 77 79 18 53 81 30 64 76 78 75 54 7 66 65 681 92 67 32 8 69 74 73 55 3 31 33
9 35 37 17 36 39 40 38 16 41 61380路 口 的 纵 坐 标 Y(单 位 ： 百 米 )36034029 2815 1032012 25 24 27 11 26 14 21 13 22 23300280260 200250300 350 路 口 的 横 坐 标 X(单 位 ： 百 米 )400450图 1 区域A的交通网络示意图 图 1 中： (1). 实线表示市区道路； (2). 实圆点“?”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交； (3). 星号“*”表示出入城区的路口节点； (4). 圆圈“○”表示现有交巡警服务平台的设置点； (5). 圆圈加星号“○ ”表示在出入城区的路口处设置了交巡警服务平台。 * 图 1 中我们可以初步地看到：市中心区域 A 中，在右上角的道路比较密集，相应 的交叉路口的节点也就比较的多； 而左下角则道路比较稀疏，交叉路口也就相应地比较 少。根据各路口节点的发案率来看的话，在左下角的区域中发案率就比较低，也就是说 在左下角的这块区域中，由于发案而要出动巡警的压力相对来说就比较地小。因此，需 要的交巡警平台就比较少。 2. 道路长度 由原题中的道路数据可以知道各节点之间那些是有连线的， 在有连线的道路上根据 题目中的已知条件和两点之间的长度计算公式， 可以得到该城市内任意相邻交叉路口间 的距离：? l (i, i ) ? ( xi ? xi? ) 2 ? ( yi ? yi? ) 2 ，综合计算，可求得任意两交叉路口间距离为：? i?... j 2 2 ?? ( xi ? xi? ) ? ( yi ? yi? ) ? i d (i, j ) ? ? ?j ...i ? ( x j ? x ?j ) 2 ? ( y j ? y ?j ) 2 ?? ? j5当i ? j时； 当i ? j时。~ ~ 对于 i ：K ~ ? K i ， 即 K ( xi? , yi? ) ? K ( xi , yi ) ； 对于 j ：K ~ ? K j ， 即 K ( x ?j , y ?j ) ? K ( x j , y j ) 。 i j其中， K ? xi , yi ? 表示第 i 个交叉路口坐标 ( xi ? (0,500), yi ? (0,600)) ； K ( xi , yi ) 表示第 i 个 交叉路口的邻接路口集合，坐标表示 ( xi ? (0,500), yi ? (0,600)) 。 可以得到各个路径之间的距离，再用 Matlab 编程使之在地图的道路上标出各自的 76 距离。 13..5 64 截取第 1 个交巡警服务平台周围设置点的图形以示说明： 3669..831 362 66 3.. 358 15. 354 352 14.2 6.3 75 4..1 78 9.9 19.1 4.4721 811 5 6.265 74 4.0311 7371 图 2 第 1 个交巡警服务平台的设置点距离图（单位： ? 100 m ） 8.0623 70 在点 350 1 和点 69 之间道路的距离显示为 5，加上单位即两点之间的距离为 500 米。 400 405 410 415 和点 78 之间的距离为 640.31 米；点 420 425 同样的，点 1 和点 74 之间的距离为 626.5 米；点 1 5 11.6297 1 和点 75 之间的距离为 930.05 米。以此类推，可以得到市中心区域 A 的各道路间的距 72 离示意图（具体的图形见附录 1） 7.6158 。 8..2 问题一 8..1 A 区各交巡警服务平台管辖范围合理的分配方案 9..3 1. Dijkstra 算法 2 8 43 在分配A区各交巡警服务平台的管辖范围时，要遵守这样的原则和义务：交巡警服 务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速 为60km/h）到达事发地。由此，我们给出了一个连接若干个交叉路口的节点的网络，在 9.8489 这个网络的两个指定的节点间，找出一条最短路径。下面以交巡警服务平台设置点1为 例。 给定图 G ，以交叉路口的节点为图 G 的顶点,这些顶点包括交巡警服务平台设置点 19.144240.22441 (记为u1 ) 和不设交巡警服务平台的交叉路口的节点 (依次记为v1 ~ vn , n ? 1,?, i,?72) 。17各节点间的距离为图 G 相应两顶点间的边。对 G 的每一边 e ，赋与一个实数 w(e) ，称为26.8794边 e 的权，得到赋权图 ? G, E ? 。8.5本文中我们规定边 e 的权为任意相邻两个交叉路口间的距离，记为 l (i, 40.078416j ) 。下面我们需要求得指定两点间的最小权，即最短路径。将 u1 , vi 间路程的权记作 d (u1 , vi ) 。 为了计算出 u1 到 G 的其余各顶点的最短路径和路程 d (u1 , vi ) 。 首先我们构造出一个 赋权临接矩阵 W ? ? wij ?92?92 ，其中分量定义如下： (1). 若交叉路口 vi和v j 之间有直接的道路连接， 那么定义其边的权值为：w(e)i, j ? l (i, j) 。 (2). 若交叉路口 vi和v j 之间没有直接的道路连接，那么定义其边上的权值为 w(e)i, j ? ? 。 根据上面的定义我们可以得到：? w ? e ?i , j ? wij ? ? ? ? ? ei , j ? E; else。其次， 求最短路径本文采用众所周知的Dijkstra算法， 该算法的基本思想分别从图 G 中的顶点 u i 出发，找出到其他各交叉路口间的最短距离，构成一个最小生成树。现将该 算法叙述如下: 设 u1 直至 vi 前，会经过多个交叉路口，在选择哪一条路径前，我们先将各个有相邻 边的交叉路口之间的距离可以按从大到小排列如下：0 ? l1 ? ? ? l j ? ? ? li , ，从而在算法实现中我们将点的排序与代换法解方程同时进行。 下面是该算法的具体 步骤。 第一步：置 l1 ? 0 ， l j ? w(e)1 j , j ? 2,3,?, i ， P ? {1}, S ? {2,3?, i} ， 第二步：对 S ? ? ，使得 lk ? min{u j } 。置 P ? P ? {k }, S ? S ? {k } 。若 S ? ? ，终止；j?S否则,继续循环第二步。 第三步：对 ?j ? S , 置 l j ? min{l j , lk ? w(e)kj }，然后返回第二步。1 这个算法经过 n ? 1 次循环后必结束。 整个算法过程中， 2 步要做 (n ? 1)?( n ? 2) 次 第 2 1 1 比较，而第 3 步则分别要做 (n ? 1)(n ? 2) 次加法和 (n ? 1)(n ? 2) 次比较。因此，总的 2 2计算量 O(n3 ) ，依次求得 u1 到 G 的各顶点的最短路径和距离（其具体的算法程序见附 录 2）。 2. 各交巡警服务平台的管辖范围的分配 基于 5.2.1 中提到的原则，即当出现突发事件时，巡警车的时速为 60km/h，并且要 求尽量能在 3 分钟内到达事发地。也就是说，巡警车从各自的交巡警服务平台出发，到 达事发地至多经过 60km / h ? 3min ? 3km 的路程。那么，在这个过程当中巡警车所经过 的节点就属于各自的交巡警服务平台的管辖范围，而对超出这个范围的节点，将进一步7进行讨论。 根据 Dijkstra 算法并且利用 Matlab 软件得到 A 区 1-20 号平台各自以 3km 为 管辖范围所能管辖到的交叉路口的节点情况见附录 5，从中可以知道：在 Q1~20 平台以 3km 为管辖范围内 A 区仍旧有几个节点不能被包括。经过整理后可以知道这些不能到 达的节点共有 6 个，序号分别为：28,29,38,39,61,92。现将不能到达的道路交叉口分别 命名为： Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 。 为了处理这几个节点，本文采用最短路径优先原则找到与这些节点距离最近的平29 7.8102 台，使这些节点属于离它最近的交巡警平台所管辖。以节点 Q28 为例，将图 16. 1 区域 A 6 57 50 59的交通网络示意图中第 28 节点的图像扩大后得到下图 3。370360 74.32368.4 3.5 62 51 18. 8.2 14.3 12..3 52 5 4. 10.198 14. 5 56 47 49 7.2 9 53 24..5 6 5.831 54 20.7966 7350340 29 330 9. 320 12 310 17. 47.5184 1511.9 45. 11. 12.659 5.099 8. 9.9 33 38.8 46 11 11.2 42.4 6 29. 5..2 35 5 37 36 5.099 49.3 39 17... 1633.6 图 3 节点 Q28 的局部图（单位： ? 100 m ）35.3836从图 327 260 280 300 320 340 7.433 中我们可以看到 Q28 附近的交巡警服务平台有 Q15 和 Q7 ，其余的服务平台离 11 20.025 9 26 25 18.0278节点 Q28 相对来说都较远。可以计算出节点 Q28 与节点 Q15 之间的路程为： 1424 32.7 21 节点 Q28 与节点 Q7 之间的最短路径为 28→29→30→7，所以最短的路程： 18. 9.0554 5 d 23 28?29?30?7 32. ? 47.5184 ，? 9.4868 ? 74.3236 ? 5.831 ? 89.6414 。在这两条路线 d28?…-m ? ?d28?15 , d28?29?30?7 ?min 中选择较短的一条路径。此时，m 取 15。 也就是说， 节点 Q28 可以归类到平台 Q15 的管辖范围内。 因此我们将交巡警服务平台 Q15 的 管辖范围扩大到 47.m ? 4.75184km 。 由上方法类似可以得到，节点 Q29 距离最近平台也是 Q15 ，将交巡警服务平台 Q15 的8管辖范围扩大至 (9.4868 ? 47.5184) ?100m ? 5.70052km 。 同理，节点 Q38 距离最近的平台是 Q16 ，将交巡警服务平台 Q16 的管辖范围扩大至3.40588km 后能够将 Q38 管辖进去。距离 Q39 最近的平台是 Q2 ，因此再继续将 Q2 的管辖范围扩大至 3.68219km 。距离 Q61 最近的是 Q4 ，将 Q4 的管辖范围扩大至 5.21055km 。距 离 Q92 最近的是 Q20 ，将 Q20 的管辖范围扩大至 3.60128km 。 综上所述，交巡警服务平台 Q1 ~ Q20 中：Q4 的管辖范围是 5.21055km ，Q15 的管辖范 围是 5.70052km ，Q2 的管辖范围是 3.68219km ，Q20 的管辖范围是 3.60128km ，其余的管 辖范围都是 3.00km 。在这种分配方案下，除去 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 这几个 点外其余的都能够在 3min 钟之内赶到。 3. 被重复管辖节点的分配原则 以 3km 为管辖范围，据上述分析，很容易就发现，在节点密集的地区有很多节点 属于多个平台管辖范围，也就是说这些节点“被重复管辖”，这样不利于警力工作量的均 衡分配，也会造成警力资源的一定浪费。并且在实际生活中，节点被重复管辖的现象是 不允许出现的，所以我们对以上给出平台管辖范围作以下修正。 本文中， 我们制定了“被重复管辖节点的分配原则”。 首先， 我们定义警力工作量 WQ j 为第 j 个平台当前管辖范围内的发案率总和，也即WQ j ? ? wi1nQ j? j ? 1, 2,?20? ，其中， nQ j 为平台 Q j 当前所管辖的总节点数， wi 为第 i 个节点平均每天发生报警案件的 数量即发案率（次数） 。 将所得的 WQ j 无量纲化，采用归一化得无量纲化：?Q ?j?W ?QjWQ j?WQ j 26.7。max其次，有实际生活中可以知道，路程越远，那么巡警到达的时间越迟，也就不利于 交巡警平台的管辖。而根据警力工作量的定义可以知道：警力工作量越大，越不利于交 巡警平台的管辖。 这里需要将 d (Qj , Qk ) 也无量纲化，方法同上：? (Q j , Qk ) ??l (i, j )?max9d (Q j , Qk )?d (Q j , Qk ) 7.43236，其中，d (Qj , Qk ) 表示节点 Q j 和节点 Qk 之间的路程，?l (i, j )?max 表示任意相连交叉路口的 的距离。 因此本文引入隶属度 ?Qj ,Qk ，其计算公式为? Q ,Q ?j k1 ? j ? 1, 2,?20; k ? 1, 2,?92? 。 ?Q j? (Q j , Qk )那么很容易就得到如下结论： 若节点 Qk 在 s 个平台节点的管辖范围内， 那么分别求 出这几个平台的隶属度 ? ，选取隶属度最大的点作为节点 Qk 的服务平台(若有隶属度相 同的节点则随机选取服务平台。本文中由于实际条件的约束，不存在这种情况)。 下面以具体的节点 Q33 来加以说明。356 354 11. 350 348 346 344 342 340 320 325 图 4 330 节点 Q 34 5.. 的放大图 5 6..099 8.5 33 30.4 15.4 6 46 29.33340345通过上图 4 可以看到节点 Q33 被平台 Q8 、平台 Q9 同时管辖。根据前面的分析我们37 5.099先来计算出 Q8 ， Q9 的当前警力工作量和距离 Q33 的路程，得到：3635.0143d (Q9 WQ8 ? 22.8 ， d (Q8 , Q33 ) ? 0.82765km ， WQ9 ? 22.5 ，6.0828, Q33 ) ? 1.25913km ，由归一化得：16 ?Q ? 0.854 ，? (Q8 , Q33 ) ? 0.1114 ； ?Q ? 0.8426 ，? (Q9 , Q33 ) ? 0.1694 ，j934.0588通过隶属度的计算可以求得 ?Q8 ,Q33 ? 10.5113 ， ?Q9 ,,Q33 ? 7.0059 。显然 ?Q8 ,Q33 ? ?Q9 ,Q33 ，因 此节点 Q8 归属于平台 Q33 管辖。10如果节点被 h 次覆盖， ? j ? ??1,?2 ,…?h ?max ，那么由平台 Q j 管辖该节点。 根据以上隶属度的计算方法我们运用附录 6 中的程序，可以对 5.2.2 中被重复管辖 的节点进行合理的修正分配,最后得到的平台分配方案如下表 1 所示。 表 1 A 区域中平台管辖分配方案表 平台号 A 区域内的节点号 节点数 发案率 1 1、66、67、68、69、70、71、72、73、74、75、76 12 12 2 2、39、40、43、44 5 8 3 3、54、55、65 4 4.8 4 4、38、57、58、60、61、62、63、64 9 9.5 5 5、47、49、50、51、52、53、56、59 9 10.2 6 6 1 2.5 7 7、30、32、48 4 7.4 8 8、33、46 3 5 9 9、31、34、35、45 5 8.2 10 10 1 1.6 11 11、26、27 3 4.6 12 12、25 2 4 13 13、21、22、23、24 5 8.5 14 14 1 2.5 15 15、28、29 3 4.8 16 16、36、37 3 3.8 17 17、41、42 3 5.3 18 18、80、81、82、83 5 6.1 19 19、77、79 3 3.4 20 20、84、85、86、87、88、89、90、91、92 10 11.5 将上表中的数据由 Matlab 软件绘制得到图 5，其中不同的形状符号表示不同平台 所管辖的范围。11400203806 5 7 84 1 3 219 183603409 15 10 12 11 14 161732030028013260 200 250 300 350 400 450图 5 平台管辖分配方案图 在上图中有标序号的表示为平台，在平台附近的几个节点中，若节点上的图形与平 台节点上的图形相同则表示为该节点归属于相同符号的平台管辖。 5.2.2 A 区重大突发事件的合理调度方案 当 A 区发生重大突发事件时，需要调度全区 20 个交巡警服务平台的警力资源，对 进出该区的 13 条交通要道实现快速全封锁，即要对出入 A 区的 13 个路口节点进行封 锁，13 个节点标号分别 12、14、16、21、22、23、24、28、29、30、38、48、62。调 度的前提是一个平台的警力最多封锁一个路口，而调度的关键是能在第一时间将 13 个 节点封锁，换句话说在 20 个交巡警服务平台中挑选出 13 个平台出动警力赶赴 13 个节 点， 要使得赶到的时间最短， 同时总路程要尽量地小， 而总路程最小的合理方案由 Matlab 软件(附录 4)编程得表 2 如下： 表 2 总路程最小的合理方案 路程 路程 路线 路线 路线 路程/km /km /km Q1-Q62 0.35 Q2-Q40-Q39-Q38 3.982 Q5-Q47-Q48 2.476 Q7-Q30-Q29 8.015 Q8-Q33-Q32-Q7-Q30 3.061 Q10-Q26-Q11-Q25-Q24 8.244 Q11-Q22-Q13-Q23 4.675 Q12-Q12 0 Q13-Q22-Q21 2.708 Q14-Q14 0 Q15-Q28 4.752 Q16-Q16 0 Q19-Q22 3.270 在上表的中 Q1-Q62 表示出入口节点 Q62 由平台节点 Q1 来管辖， 所经过的线是由 Q1 直 接 到 达 Q62 ，总的路程是 0.35km ，在接到报警后约 1.17min 能够到达节点 Q62 。12Q2-Q40-Q39-Q38 表示出入口节点 Q38 由平台节点 Q2 管辖。 在接到报警后， 巡警车从节点 Q2 出发经过节点 Q40 、 Q39 ，最后到达 Q38 。总的路程为 3.982km，也即能够在 3.32min 内 赶到节点 Q38 。其余的路线也依次同上面的解释。根据 Dijkstra 算法原理可知,按照表 2 中所得到的路线调度方案，能够做到总路程最小。在这个围堵的过程中，各服务平台的 巡警车是同时出发的，所以完成围堵的时间即为最大路程所需要花费的时间。从表 2 中可以看到最大的路程为 8.244km ，因此整个围堵过程所需要的时间 T ? 8.244 。 5.2.3 增加平台缓解工作量不均衡与出警察时间过长情况的方案 由 5.2.1 最终给出的分配方案，我们定义 20 个平台工作量的方差为交巡警服务平 台工作量的均衡度，方差越小表示工作量的均衡度越好。反之，均衡度越差。 各个平台的总工作量 WQ j ? ? wi1 n? j ? 1, 2,? 20? 之前已经给过定义，通过它我们可以求得：1 20 W ? ?WQ j ， 20 1 D? 1 20 ? (WQ j ? W ) 。 20 1根据 5.2.1 中我们已经知道警车不能在 3 分钟内的节点有： Q28 、 Q29 、 Q38 、 Q39 、Q61 、 Q92 ，换而言之， Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 这 6 个节点是导致出警时间过长的关键。 增加 2-5 个平台要考虑平台工作量不均衡和出警时间过长两方面： （1）缓解工作量不均衡的情况，我们需要在 A 区的工作量最大且节点密集的地域 设置 1-4 个平台； （2）缓解出警时间过长的问题，需要在 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 节点上或 者节点附近增加 1-4 个平台。 如果同时考虑两个方面，那么增加的平台位置应该都是在 A 区的边境地域。因为Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 这些节点都在 A 区边境，而这样对分担警力工作量的作用微乎其微。由此，我们引入平台需求指标 ? ，它遵循下述两点原则： （1） 如果 20 个平台的工作量的不均衡度的方差越大，则越需要增加新的平台去缓 解不均衡的程度； （2）如果 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 节点离其最近的平台距离之和越大，则 越需要增加平台去缓解出警时间过长的问题。 故定义平台的需求指标 ? ：13?1 ?D? d? , ?2 ? D dQ j? ?，max其中， D ? 表示为 20 个平台管辖范围内最大 4 个发案率与最小 4 个发案率的方差，因为 D 其余的 12 个平台管辖范围内的发案率比较平稳； 表示为 20 平台管辖范围内的发案率 的方差； dQ j 表示为 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 节点离其最近平台的各个距离； d ? 表示为 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 节点离其最近平台的各个距离之和。 由表 1 和附件中数据可以得到 ?1 ? 2.1826 ， ?2 ? 4.6228 ，即 ?1 : ?2 ? 1: 2 。通过该 比值可以初步得出结论： 在增加平台时应优先解决出警时间过长的问题。基于这个结论 并且，我们合理地给出增加平台的个数方案如错误！未找到引用源。 ： 表 3 增加平台的个数方案 增加的平台总数 2 3 4 5 考虑工作量不均衡新设的平台数 1 1 1 2 考虑出警时间过长新设的平台数 1 2 3 3 现述新增平台的安置地点： （1）考虑工作量不均衡 新设的平台数为 1 时， 基于优先原则，新增的 1 个平台应该安置在已有的发案率最 大的平台管辖范围内。 表 4 1-20 平台各自管辖范围内的发案率 1 2 3 4 5 6 7 8 9 10 平台编号 管辖范围内的发案率 12 8 4.8 9.5 10.2 2.5 7.4 5 8.2 1.6 11 12 13 14 15 16 17 18 19 20 平台编号 4.6 4 8.5 2.5 4.8 3.8 5.3 6.1 3.4 11.5 管辖范围内的发案率 根据错误！未找到引用源。的案发率，在发案率最大的平台 1 管辖范围内选择一个 未设平台的节点作为安置地点，并且结合错误！未找到引用源。进行分析。14图 6 节点 1 管辖范围图 用新设的平台将平台 1 的总工作量分担，并且接近平分状态的效果最佳，由 Matlab 软件可以找到在上图中的节点 71 设立新平台效果最佳， 且通过计算得到此时 21 个平台 的均衡度 D21 ? 9.1956 ，与原先不添设平台的均衡度 D ? 9.3845 有所减小，说明均衡度 有所的改善，但很不明显。 新设的平台数为 2 时，同样由优先原则，新增的第 2 个平台应安置在已有的发案 率第二大的平台管辖范围内，即平台 20 的管辖范围内。同理由 Matlab 软件可以找到在 节点 90 设立新平台效果最佳，且通过计算 D22 ? 9.0512 ，与 D21 ? 9.1956 相比又有所下 降。 确定平台数为 1 还是平台数为 2，用均衡度相对减少率去比较：? 21 =D21 ? D ?100% ? 2.013% ， D D22 ? D ?100% ? 3.551% 。 D? 22 ?? 22 与 ? 21 的变化不大，即设两个平台与设一个平台的效应变化不大，故取考虑工作量不均衡新设的平台数为 1 个。 （2）考虑出警时间过长 如果只考虑考虑出警时间过长，将平台设在 Q28 、 Q29 、 Q38 、 Q39 、 Q61 、 Q92 节点 上效果是最佳的，但是由于数量有限最多有 3 个平台可以设在这些节点，需要在新设的 平台 Q? 、 Q? 、 Q? 、 Q? 、 Q? 、 Q? 中挑出效果最好的前三位。在这里又将“分担 38 61 28 29 39 9215Q39 Q92 Q 61 其他平台的工作量” 因素考虑进来， 分析得到效果最好的前三位依次是： ? 、 ? 、 ? ，由于考虑出警时间过长的方面比考虑工作量不均衡方面要优先， 故由错误！ 未找到引用 源。可得考虑出警时间过长新设的平台数最优为 3 个。 （3）综合个数和位置结论 综上（1）（2）所述，考虑工作量不均衡添设的平台数为 1 个，且设在节点 71； 、 考虑出警时间过长添设的平台数为 3 个，且设在节点 39、节点 92、节点 61。总之，增 加平台个数为 4 个和位置分别为节点 71、节点 39、节点 92、节点 61。 5.3 问题二 5.3.1 该市现有交巡警服务平台设置方案的分析 1. 全市各区现有交巡警服务平台管辖情况 根据 5.2.1 中的 A 区交巡警服务平台的调度方案，我们可以同理得到 B，C，D，E， F 区的交巡警服务平台的调度方案。由于全市六个区中的平台管辖范围所制成的表格过 于庞大，在本文中我们只给出 B 市的平台管辖范围，其余的见附录 7 全市各区域的 平台服务管辖范围。 表 5 B 区域内的平台服务管辖范围 平台 节点 发案 B 区域内的节点号 号 数 率 93 93、101、109、110、111 5 5 94、102、112、113、114、115、116、117、118、119、120、125、 94 19 15.7 126、127、128、129、130、131、133 95、103、121、122、123、124、132、134、135、136、137、138、 95 15 12.9 139、144、162 96 96、104、141、142、146、147、148、149、150、153、154、155 12 9.2 97 97、105、143、145、151、152、157、158、159、160、161 11 9.7 98 98、106、163、164、165 5 5.3 99 99、107、156 3 4.2 100 100、108、140 3 5 从上表 5 和附录 7 中的数据我们可以看到： 在问题一的“尽量能在 3 分钟内有交巡 警到达事发地”这个要求和根据 5.2.1 中所构造的隶属度这一原则下， 各交巡警服务平台 的管辖范围有着明显的不均衡性。 有的服务平台所管辖的节点数较多，并且总发案率也 相对地较高； 但是有的服务平台则刚好相反。因此可以初步判定现有交巡警服务平台设 置方案有着一定的不合理性。 下面我们从全市的角度出发去考虑重新分配各区的交巡警 服务平台数，来改进该市的交巡警服务平台设置方案。 2. 全市各区中分配到的平台数 根据附件中的数据，首先我们可以画出全市六个区的交通网络与平台设置示意图， 利用附录 8 中的 Matlab 程序可以得到下图 7。16600500C D E A F B0 50 100 150 200 250 300 350 400 450 5004003002001000图 7 全市六个区的交通网络与平台设置示意图 在上图 7 中星号“*”表示出入城区的路口节点；圆圈“○”表示现有交巡警服务平台 的设置点，其区域范围中心已用字母标出。从上图中可以看出 A，B，C，D，E，F 中 的区域可以看出：每个区域内的节点数不同，因此总的发案率也不同。一方面，从交巡 警的工作的均衡性来考虑的话， 每个区域内的平台数应该与该区域内的总发案率成正相 关。另一方面，由于每个区域的地域范围不同，人口数也不同，而从实际生活中来考虑 的话，对于地域范围越大，人口越多的区域，它所需要的平台数就越多。因此平台数的 分配应该与地域范围和人口数成正相关。 由附件中的数据我们可以直接得到每个区域内的人数、城区的面积；并且通过整理 后还可以得到每个区域内的总结点数、原有总平台数以及总发案率，具体的结果见。 表 6 六个区域的数据整理 六个城区 城区的面积 城区的人口 （平方公里） （万人） 总结点数 区域内的总 原有的平台 发案率 W 数 20 8 17 9 15 11A 22 60 92 124.5 B 103 21 73 66.4 C 221 49 155 189.6 D 383 73 52 67.8 E 432 76 103 117 F 274 53 107 109.2 将表 6 中的前四列数据进行无量纲化处理后得到下面这个矩阵17?? ? ? 0.05 ? 0.24 ? ? ? ? 0.51 ? 0.89 ? ?1.00 ? 0.63 ??0.79 0.28 0.64 0.96 1.00 0.7?0.59 0.47 1.00 0.34 0.66 0.69? ? 0.66 ? 0.35 ? ? 1.00 ? ， 0.36 ? ? 0.62 ? 0.58 ? ??其中，行分别表示城区的面积、城区的人口、总结点数、区域内的总发案率；列表示 A~F 这 6 个区域。那么，综合考虑到以上因素的话，我们定义 A 至 F 区的区域警力压 力 ?i ?i ? A, B, C, D, E, F ? ，定义如下：?i ? ?i ? ?i ?? i ? ?i ?i ? A, B, C, D, E, F ? ，计算后得到? A ? 0.52; ?B ? 0.34; ?C ? 0.79; ?D ? 0.64; ?E ? 0.82; ?F ? 0.65 .根据各区域间的警力压力比值我们来分配全市的 80 个交巡警服务平台，分配过程 中使得 第i个区域中的平台数 ? 警力压力 。 最终我们得到 A~F 所需要分配到的平台数分 别为：11、7、17、14、17、14。那么，对应到原始的平台数中可以绘制出表 7。 表 7 各区中需要修正的平台数 城区 原有的平台数 改进后的平台数 需要修正的平台数11 A 20 -9 7 B 8 -1 17 C 17 0 14 D 9 +3 17 E 15 +2 14 F 11 +3 3. 全市各区中的平台分配方案 (1). 区域 A 中的分配方案 由前面的分析，我们知道在区域 A 中需要减掉 9 个平台，这 9 个点的去除方法有 可以有多种方案。但是根据前面的区域警力压力指标来考虑的话，我们将 A 区域中的 20 个平台的当前连接点和区域总发案率进行一个排列，从低到高依次去掉 9 个平台。 而从表 1 A 区域中平台管辖分配方案表中的节点经排序后得到去掉的这 9 个平台的节 点号分别为：6、8、10、11、12、14、15、16、19。在去掉了这 9 个节点后，我们根据 5.2.1 中的理论过程，运行程序后可以得到剩余 11 个平台的管辖范围。 最后得到 A 区域中各个平台所管辖范围的分配如下所示： 表 8 重新分配后 A 区内节点的管辖范围 平台号 A 区域内的节点号 节点数 发案率 1 1、66、67、68、69、70、71、72、73、74、75、76、77 12 12182 2、39、40、43、44 5 8 3 3、54、55、65 4 4.8 4 4、38、57、58、60、61、62、63、64 9 9.5 5 5、47、49、50、51、52、53、56、59 9 10.2 7 7、8、15、28、29、30、32、48 4 7.4 9 6、9、10、14、16、31、33、34、35、36、37、45 5 8.2 13 11、12、13、21、22、23、24、25、26、27 5 8.5 17 17、41、42 3 5.3 18 18、19、79、80、81、82、83 5 6.1 20 20、84、85、86、87、88、89、90、91、92 10 11.5 (2). 区域 B、C 的分配方案 需要在区域 B 中的平台节点数减少一个，其操作的过程和区域 A 中的过程类似。 那么，很容易就知道区域 B 中需要减少的平台节点号为：99。将这个平台减少后运行 程序得到 99 号节点归 97 号平台管辖；107 号节点归 94 号平台管辖；156 号节点归 98 号平台管辖；其余的节点管辖归属仍旧不变，见表 5 B 区域内的平台服务管辖范围。 在区域 C 中，没有新加入的平台，也没有被舍去的平台。这说明从全市的总体上 来考虑的话，该区域的平台警力压力较为适中。并且，从区域 C 的局部上考虑的话， 各平台所分配的到节点数和法案率也较为均匀。因此 C 中的分配方案不变。 (3). 区域 D、E、F 的分配方案 在区域 D 中需要加入 3 个新增的节点，在加入新增节点时，参考 5.2.3 中 A 区域加 入平台的方法，对其加入新的平台。最终我们可以知道在 D 区域中的新增的 3 个平台 号分别为：342、346、356。 同样地，在区域 E、F 中分别加入 2 个和 3 个平台。加平台的方法也同 5.2.3 类似。 最后我们可以算得在区域 E 中的新增平台为：450、403；在区域 F 中的新增平台为： 530、520、494。 5.3.2 发生重大刑事案件时的最佳围堵方案 记嫌疑犯为目标点，由题意可得，交巡警是在 3 分钟后接到报警，若不考虑接收信 息的延时和准备工作耽误的时间，即警方是在目标点从节点 32 逃跑 3 分钟后，才从各 自的平台出发。这里假设目标点的车速与警车的车速相同也是 60km/h，且每个平台的 警力只能封锁一个节点。同时需要知道，全市的道路错综复杂，而未知目标点选择的逃 跑路线， 所以可以采取由与第一题的第二小问中类似的方法，但这里要求更加严密且需 要缩小搜捕范围来对目标点进行围堵。 (1). 第一道防线的节点位置 按 3 分钟后， 目标点可能到达的所有节点， 根据 Dijkstra 算法运用 Matlab 软件求出 这些节点，得到节点序号分别为：7，8，9，30，31，32，33，34，35，36，45，46， 47，48。 (2). 第二、三道防线的节点位置 以节点 32 为圆心作半径分别为 9km、12km 的圆（即防线圈） ，即目标点至少要花 9 分钟、12 分钟才能跑到二、三道防线的周线位置，运用 Matlab 软件可以得到图 8 如 下所示。19500C450400350AP300250250300350400450F 图 8 三道防线圈图 根据上图所示，应该选择防线圈周线附近的节点位置作为防线节点位置，由于找这 些节点的位置工作量较小，我们找得这些节点列成表 9 如下： 表 9 二、三防线节点序号以 9km 为半径的防线 的节点序号 213，174，172，227，241，240，239，29，20，26，14，560， 561，41，40，71，1，77，194，175以 12km 为半径的防线 210，222，170，273，25，21，486，491，531，532，534，535， 的节点序号 543，542， 569，568，183，198 第二、三道防线由于是我们预测目标点至少要花 9 分钟、12 分钟才能跑到二、三 道防线的周线位置， 所以在目标点跑了 3 分钟的时刻，第二道防线附近的平台收到命令 立刻赶往自己应该封锁的节点有 6 分钟的时长， 第三道防线附近的平台收到命令立即赶 往自己应该封锁的节点有 9 分钟的时长， 第二道防线附近的平台有比较足够的时间可全 部赶到自己的待命点待命， 而第三道防线附近的平台有绝对充分的时间全部赶到自己的 待命点待命。 由 Matlab 软件得到平台到防线节点的最短路程、最小时间方案，如下表 10 给出： 表 10 平台到防线节点的最短路程、最小时间方案 第一道防线的 Q ? Q 、Q ? Q 、Q ? Q 、Q ? Q 、Q ? Q 、Q ? Q 、Q ? Q 、 15 7 9 8 16 9 73 30 15 31 7 32 8 33 最短路程方案 Q10 ? Q34、Q16 ? Q35、Q36 ? Q14、Q45 ? Q3、Q46 ? Q4、Q47 ? Q5、Q48 ? Q6 第二道防线的 最短路程方案Q174 ? Q213、Q178 ? Q174、Q172 ? Q172、Q170 ? Q227、Q171 ? Q241、Q169 ? Q240、 Q238 ? Q239、Q239 ? Q29、Q20 ? Q20、Q11 ? Q26、Q14 ? Q14、Q402 ? Q560、 Q558 ? Q561、Q17 ? Q41、Q2 ? Q40、Q1 ? Q71、Q4 ? Q1、Q19 ? Q77、Q168 ? Q194、 Q175 ? Q17520第三道防线的 最短路程方案Q207 ? Q210、Q178 ? Q222、Q170 ? Q170、Q182 ? Q273、Q12 ? Q25、Q13 ? Q21、 Q494 ? Q486、Q481 ? Q491、Q530 ? Q531、Q548 ? Q532、Q176 ? Q534、Q536 ? Q535、 Q475 ? Q543、Q478 ? Q542、Q480 ? Q569、Q569 ? Q568、Q179 ? Q183、Q177 ? Q198上表中 Qi ? Q j 均为平台 i 到节点 j 的最短路径，也即在围堵嫌疑犯时交叉口 Q j 由平 台 Qi 去封锁围堵。通过计算得到第二防线全部待命所用时间：t2 ? t3 ??d (Q , Q )?2 i jmaxmax ? 8.4 min ? 9 min 。 1km / min 通过这样的防线设置， 目标点的搜捕范围基本上就被控制在第一道防线与第三道防 线的中间同心圆的部分， 然后让第一道防线的警力外扩搜捕，让第三道防线的警力收缩 搜捕， 使第一道防线与第三道防线的中间同心圆面积越来越小， 实现围堵目标点的目的。1km / min ?d3 (Qi , Q j )?? 5.2 min ? 6 min,六、模型的评价优点：1.在分配平台管辖范围模型中，从实际出发，各个交巡警服务平台不能重复管辖 节点的客观事实，引入隶属度思想将被重复管辖的节点进行了更合理的分配。 2.在对全市平台设置方案进行分析中添加用矩阵的运算，易于用数学软件求解。 缺点：1.在本论文的模型中的假设性太强，导致该模型运用到实际上会有一定的困难。 2． 在最后一个围堵模型中， 第一防线的外扩搜捕与第三防线的收缩搜捕过程中， 选择的路径只能是一条单一的路径，可能在这个时间差之内让嫌疑犯逃跑。七、参考文献八、附录21附录 1 A 区域的标点程序 %A区域各节点标号程序 clc clear csjd=[1 413 359 2 403 343 3 383.5 351 4 381 377.5 5 339 376 6 335 383 7 317 362 8 334.5 353.5 9 333 342 10 282 325 11 247 301 12 219 316 13 225 270 14 280 292 15 290 335 16 337 328 17 415 335 18 432 371 19 418 374 20 444 394 21 251 277 22 234 271 23 225 265 24 212 290 25 227 300 26 256 301 27 250.5 306 28 243 328 29 246 337 30 314 367 31 315 351 32 326 355 33 327 350 34 328 342.5 35 336 339 36 336 334 37 331 335 38 371 330 39 371 333 40 388.5 330.52241 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84411 327.5 419 344 411 343 394 346 342 342 342 348 325 372 315 374 342 372 345 382 348.5 380.5 351 377 348 369 370 363 371 353 354 374 363 382.5 357 387 351 382 369 388 335 395 381 381 391 375 392 366 395 361 398 362 401 359 405 360 410 355 408 350 415 351 418 347 422 354 418.5 356 405.5 364.5 405 368 409 370 417 364 420 370 424 372 438 368 438.5 373 434 376 438 3852385 440 392 86 447 392 87 448 381 88 444.5 383 89 441 385 90 440.5 381.5 91 445 380 92 444 360 ];%原始数据 plot(csjd(:,2),csjd(:,3),'b.');%描点 n=length(csjd(:,1)); pingtai=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 413,403,383.5,381,339,335,317,334.5,333,282,247,219,225,280,290,337,415,432,418,444 359,343,351,377.5,376,383,362,353.5,342,325,301,316,270,292,335,328,335,371,374,394]'; %个平台的原始数据 for i=1:20 plot(pingtai(:,2),pingtai(:,3),'r*');%将平台用红色*表示 end for i=1:n text(csjd(i,2),csjd(i,3),num2str(i));%在各节点上标号 end a=[1,1,2,3,3,4,4,5,5,6,7,7,8,8,9,10,11,11,12,14,15,15,16,16,17,17,17,18,18,19,20,21,22,23,24, 24,25,26,26,27,28,28,29,30,30,31,31,32,33,33,34,35,36,36,36,36,37,38,38,39,40,41,41,42,43, 43,44,45,46,46,47,47,47,48,49,49,50,51,51,52,53,53,54,54,55,56,57,57,57,58,60,61,62,62,63, 64,64,65,66,66,67,67,68,68,69,69,69,70,70,71,71,72,73,73,74,74,75,76,77,77,78,79,80,81,82, 82,83,84,85,86,86,87,87,88,88,89,89,89,90,91 75,78,44,45,65,39,63,49,50,59,32,47,9,47,35,34,22,26,25,21,7,31,14,38,40,42,81,81,83,79,86 ,22,13,13,13,25,11,27,10,12,29,15,30,7,48,32,34,33,34,8,9,45,35,37,16,39,7,39,41,40,2,17,92 ,43,2,72,3,46,8,55,48,6,5,61,50,53,51,52,59,56,52,54,55,63,3,57,58,60,4,59,62,60,4,85,64,65, 76,66,67,76,44,68,69,75,70,71,1,2,43,72,74,73,74,18,1,80,76,77,78,19,79,80,18,82,83,90,84, 85,20,87,88,88,92,89,91,20,84,90,91,92]; %连线的原始数据 na=length(a(1,:)); for i=1:na line([csjd(a(1,i),2),csjd(a(2,i),2)],[csjd(a(1,i),3),csjd(a(2,i),3)]); %连线 end for i=1:na d(i)=sqrt((csjd(a(1,i),2)-csjd(a(2,i),2)).^2+(csjd(a(1,i),3)-csjd(a(2,i),3)).^2);% 计算各个路线的距 离 %text((csjd(a(1,i),2)+csjd(a(2,i),2))/2,(csjd(a(1,i),3)+csjd(a(2,i),3))/2,num2str(sqrt((cs jd(a(1,i),2)-csjd(a(2,i),2)).^2+(csjd(a(1,i),3)-csjd(a(2,i),3)).^2))); %再连线上标上距离 end churu=[12,14,16,21,22,23,24,28,29,30,38,48,62];24%出入口原始数据 hold on for i=1:length(churu) plot(csjd(churu(i),2),csjd(churu(i),3),'ro'); %将出入口用红色圈表示 end c=zeros(n,n); for i=1: na c(a(1,i),a(2,i))=sqrt((csjd(a(1,i),2)-csjd(a(2,i),2)).^2+(csjd(a(1,i),3)-csjd(a(2,i),3)).^2); end c=c+c'; for i=1:n for j=1:n if c(i,j)==0 c(i,j)= end end end for i=1:n c(i,i)=0; end附录 2 dijkstra 算法程序 function [distance,path]=dijkstra(A,s,e) % [DISTANCE,PATH]=DIJKSTRA(A,S,E) % returns the distance and path between the start node and the end node. % A: adjcent matrix % s: start node % e: end node % initialize n=size(A,1); % node number D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node % the shortest distance for i=1:n-1 % BlueSet has n-1 nodes temp=zeros(1,n); count=0; for j=1:n if visit(j) temp=[temp(1:count) D(j)];25else temp=[temp(1:count) inf]; end count=count+1; end [value,index]=min(temp); j= visit(j)=0; for k=1:n if D(k)&D(j)+A(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end end end distance=D(e); % the shortest distance path if parent(e)==0, end path=zeros(1,2*n); % path preallocation t=e; path(1)=t; count=1; while t~=s && t&0 p=parent(t); path=[p path(1:count)]; t=p; count=count+1; end if count&=2*n, error(['The path preallocation length is too short.',... 'Please redefine path preallocation parameter.']); end path(1)=s; path=path(1:count); 附录 3 找出每个平台周围路程少于 3km 的点 %在此之前先运行附录1中的程序 k=1; z=5; % z从1开始取，一直取到20 for i=1:n [distance,path]=dijkstra(c,z,i); if distance&30 d(k,1)= d(k,2)=i; k=k+1; end end 附录 4 找出每个出入口的管辖平台26%在此之前先运行附录1中的程序 k=1; z=62; %将z每个出入口都运行一遍， %即z=12,14,16,21,22,23,24,28,29,30,38,48,62 pintai=[1,2,3,4,5,6,7,8,9,10,11,13,15,17,18,19,20]; for i=1:length(pintai) k(i)=dijkstra(c,z,pintai(i)); end [kk,p]=min(k); [distance,path]=dijkstra(c,z,pintai(p)) 附录 5 1-20 个平台以 3km 为管辖范围内的交叉路口节点情况 交巡警服务 区域内的节点号 平台编号 1 2 18 19 42 43 1 65 66 67 68 69 70 73 74 75 76 77 78 1 2 3 17 40 42 2 66 67 68 69 70 71 74 75 76 78 2 3 43 44 54 55 3 66 67 68 70 76 4 57 58 60 62 63 4 66 5 6 7 47 48 49 5 52 53 56 58 59 5 6 7 47 48 50 6 56 58 59 5 6 7 8 9 30 7 33 34 47 48 7 8 9 16 31 32 8 35 36 37 45 46 47 7 8 9 16 31 32 9 35 36 37 45 46 10 10 11 11 25 26 27 12 12 25 13 13 21 22 23 24 14 14 15 15 31 8 9 16 33 34 35 16 45 46 17 2 17 40 41 42 4327每区的 点数 44 71 79 43 72 64 64 50 51 31 33 33 64 72 80 44 73 65 65 51 52 32 34 34 2420 13 9 13 11 12 14 13 1 4 2 5 1 236 7037 7210 81819 201 77 85 1 69 78 18 8718 78 87 18 70 79 20 8819 79 88 19 71 80 81 8920 80 89 64 73 81 82 9071 81 90 65 74 82 83 9172 82 91 66 75 83 8473 83 67 76 8574 84 68 77 862222 13附录 6 最终个节点的管辖范围 clc clear csjd=[1 413 359 2 403 343 3 383.5 351 4 381 377.5 5 339 376 6 335 383 7 317 362 8 334.5 353.5 9 333 342 10 282 325 11 247 301 12 219 316 13 225 270 14 280 292 15 290 335 16 337 328 17 415 335 18 432 371 19 418 374 20 444 394 21 251 277 22 234 271 23 225 265 24 212 290 25 227 300 26 256 301 27 250.5 306 28 243 328 29 246 337 30 314 367 31 315 351 32 326 3552833 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76327 350 328 342.5 336 339 336 334 331 335 371 330 371 333 388.5 330.5 411 327.5 419 344 411 343 394 346 342 342 342 348 325 372 315 374 342 372 345 382 348.5 380.5 351 377 348 369 370 363 371 353 354 374 363 382.5 357 387 351 382 369 388 335 395 381 381 391 375 392 366 395 361 398 362 401 359 405 360 410 355 408 350 415 351 418 347 422 354 418.5 356 405.5 364.5 405 3682977 409 370 78 417 364 79 420 370 80 424 372 81 438 368 82 438.5 373 83 434 376 84 438 385 85 440 392 86 447 392 87 448 381 88 444.5 383 89 441 385 90 440.5 381.5 91 445 380 92 444 360 ];%原始数据 a=[1,1,2,3,3,4,4,5,5,6,7,7,8,8,9,10,11,11,12,14,15,15,16,16,17,17,17,18,18,19,20,21,22,23,24, 24,25,26,26,27,28,28,29,30,30,31,31,32,33,33,34,35,36,36,36,36,37,38,38,39,40,41,41,42,43, 43,44,45,46,46,47,47,47,48,49,49,50,51,51,52,53,53,54,54,55,56,57,57,57,58,60,61,62,62,63, 64,64,65,66,66,67,67,68,68,69,69,69,70,70,71,71,72,73,73,74,74,75,76,77,77,78,79,80,81,82, 82,83,84,85,86,86,87,87,88,88,89,89,89,90,91 75,78,44,45,65,39,63,49,50,59,32,47,9,47,35,34,22,26,25,21,7,31,14,38,40,42,81,81,83,79,86 ,22,13,13,13,25,11,27,10,12,29,15,30,7,48,32,34,33,34,8,9,45,35,37,16,39,7,39,41,40,2,17,92 ,43,2,72,3,46,8,55,48,6,5,61,50,53,51,52,59,56,52,54,55,63,3,57,58,60,4,59,62,60,4,85,64,65, 76,66,67,76,44,68,69,75,70,71,1,2,43,72,74,73,74,18,1,80,76,77,78,19,79,80,18,82,83,90,84, 85,20,87,88,88,92,89,91,20,84,90,91,92]; %连线 n=length(csjd(:,1)); na=length(a(1,:)); c=zeros(n,n); for i=1: na c(a(1,i),a(2,i))=sqrt((csjd(a(1,i),2)-csjd(a(2,i),2)).^2+(csjd(a(1,i),3)-csjd(a(2,i),3)).^2); end c=c+c'; for i=1:n for j=1:n if c(i,j)==0 c(i,j)= end end end for i=1:n c(i,i)=0; end %得到dijkstra函数中的距离邻接矩阵 gzl=[1.7,2.1,2.2,1.7,2.1,2.5,2.4,2.4,2.1,1.6,2.6,2.4,2.2,2.5,2.1,2.6,2.5,1.9,1.8,1.9];%工作量30juli=zeros(72,20); faan=[1.7,2.1,2.2,1.7,2.1,2.5,2.4,2.4,2.1,1.6,2.6,2.4,2.2,2.5,2.1,2.6,2.5,1.9,1.8,1.9,1.4,1.4,2.4, 1.1,1.6,1.2,0.8,1.3,1.4,2.1,1.6,1.5,1.4,1.7,1.4,1.1,0.1,1.2,1.4,1.7,1.4,1.4,1.7,1.1,1.4,1.2,1.6,1.4, 1.2,1.1,0.8,0.6,1.4,0.9,1,0.5,0.8,1.1,0.9,0.7,0.6,1.2,1.4,0.8,0.7,0.8,0.8,0.9,1.1,0.9,1.1,0.8,0.9,1. 1,0.8,1.1,0.8,0.8,0.8,0.8,1.4,1.1,0.9,1,1.2,1.4,1.1,0.9,1.4,0.9,0.9,0.8]; a0=zeros(92,1);jdh=zeros(92,1);%各节点发案率 for i=21:92 for j=1:20 juli(i,j)=dijkstra(c,i,j);%得到各节点与20各平台之间的距离 end [C,I]=max(1./(gzl.*juli(i,:)));%选取隶属度最大的平台号i和隶属度 a0(i)=C;jdh(i)=I;%第20+i个节点属于jdh(i)管辖。 juli(jdh(i))=juli(jdh(i))+faan(i); end 附录 7 全市各区域的平台服务管辖范围 平 台 区域内的节点号 号 93 93、101、109、110、111 94、102、112、113、114、115、116、117、118、119、120、125、126、 94 127、128、129、130、131、133 95、103、121、122、123、124、132、134、135、136、137、138、139、 95 B 144、162 区 96 96、104、141、142、146、147、148、149、150、153、154、155 域 97 97、105、143、145、151、152、157、158、159、160、161 98 98、106、163、164、165 99 99、107、156 100 100、108、140 166、183、256、257、258、259、260、261、262、263、264、265、 266、268、269、270、271、273、274、275、276、277、278、279、 166 280、281、282、283、284、285、286、288、289、292、293、294、 295、296、297、298、299、300、302、303、304、305、306、307、 309、310、311、312、313、314、315、316、317、318、319、320 167 167、184、267、272 C 168 168、185、206、207、208、209、210 区 169 169、186 域 170 170、187、239、240、241、242、243 171 171、188、232、233、247、248 172 172、189、234、235、244、245、246 173 173、190、249、250、251、252、253、254、255 174 174、191、228、229、230、231、236、237、238 175 175、192、211、212、213、214、215、216 176 176、193、200、201、202、203、204、20531节 点 数 5 19 15 12 11 5 2 3604 7 2 7 6 7 9 9 8 8D 区 域177 178 179 180 181 182 321 322 323 324 325 326 327 328 329 373 374 375 376 377 378 379 380 381 382 383 384 385 386 475 476E 区 域F 区 域477 478 479 480 481 482177、194、217、218、219 178、195、220、221、222、223、224、225、226、227、301 179、196、291、308 180、197、287 181、198 182、199、290 321、356、358、359、361、362、366、368、369、370、372 322、367 323、344、345、363 324、364、365 325 326、343、346、347、348、349、350、351、352、353、354、355、 357、360、371 327、337、338、340、341、342 328、333、334、335、336、339 329、330、331、332 373、437、438、456 374、427、431、432、433、434、435、436、457、458、459 375、424、425、426、428、429、430 376 377 378 379、417、418、420、421、422、423 380、394、396 381、390、391、392、393、395、397、398、399、400、404、405、 406、407、408、409、419、439 382、401、402、403、410、411、412、413、414、415、416 383、446、452、453、454、455 384、465、466、467、468、471、472 385、445、448、449、450、451、473、474 386 475、545、546、547、552、553、554 476、493、494、495、496、497、498、499、500、501、502、503、 504、507、508、519、520 477、505、506、509、510、512、513、514、515、516、517、518、 521、522、523、524、525、526、527、528、529、533、534、535、 536、537、538、539、540、541、542、543、544、551、555、556、 557、558、559、560、561、563、564、565、566、574、575 478、573、576、577、578、579、580、581、582 479、562、567、568、569、571 480、490、491、492、530、531、532、548、549、550 481、488、489 482、511325 11 4 3 2 3 11 2 4 3 1 15 6 6 4 4 11 7 1 1 1 7 3 18 11 6 7 8 7 1747 9 6 10 3 2483 484 485483、570 484、572 485、486、4872 2 3程序运行见附录 9。附录 9 是区域 F 的运行情况，其他区域运行类似。附录 8 全市全市六个区的交通网络与平台设置示意图 clc clear csjd=[acsjd bcsjd ccsjd dcsjd ecsjd fcsjd]; %为原始数据组，其中acsjd=[A区节点号，节点横坐标，节点纵坐标，节点所属区域， 发案度] plot(csjd(:,2),csjd(:,3),'b.'); hold on a=[1,1,2,3,3,……89,90,91 75,78,44,45,65……90,91,92]; b=[93,94,95,95,96……163,164,165 104,110,116,136,137……164,98,377]; c1=[166,166,167,167,168……319,319,320 265,181,250,255,189……181,313,350]; d=[321,321,321,322,323……370,371,372 356,358,368,367,363……29,28,23]; e=[373,373,373,374,375……474,475,475 431,438,456,436,424……340,555,565]; f=[476,477,478,478,479……581,581,582 545,501,542,566,577……582,183,578]; %a、b、c、d、e、f分别为连线的两个节点的原始数据 na=length(a(1,:)); for i=1:na line([csjd(a(1,i),2),csjd(a(2,i),2)],[csjd(a(1,i),3),csjd(a(2,i),3)],'Color','g'); end for i=1:length(b(1,:)) line([csjd(b(1,i),2),csjd(b(2,i),2)],[csjd(b(1,i),3),csjd(b(2,i),3)],'Color','g'); end for i=1:length(c1(1,:)) line([csjd(c1(1,i),2),csjd(c1(2,i),2)],[csjd(c1(1,i),3),csjd(c1(2,i),3)],'Color','b'); end for i=1:length(d(1,:))33line([csjd(d(1,i),2),csjd(d(2,i),2)],[csjd(d(1,i),3),csjd(d(2,i),3)],'Color','k'); end for i=1:length(e(1,:)) line([csjd(e(1,i),2),csjd(e(2,i),2)],[csjd(e(1,i),3),csjd(e(2,i),3)],'Color','b'); end for i=1:length(f(1,:)) line([csjd(f(1,i),2),csjd(f(2,i),2)],[csjd(f(1,i),3),csjd(f(2,i),3)],'Color','k'); end achuru=[12,14,16,21,22,23,24,28,29,30,38,48,62]; %A?????????????????? hold on for i=1:length(achuru) plot(csjd(achuru(i),2),csjd(achuru(i),3),'r*'); end qchuru=[151,153,177,202,203,264,317,325,328,332,362,387,418,483,541,572,578]; for i=1:length(qchuru) plot(csjd(qchuru(i),2),csjd(qchuru(i),3),'r*'); end %A?????????????????? text(csjd(32,2),csjd(32,3),'P','FontSize',18); text(300,340,'A','FontSize',18); text(csjd(130,2),csjd(132,3),'B','FontSize',18); text(290,475,'C','FontSize',18); text(csjd(350,2),csjd(350,3),'D','FontSize',18); text(75,150,'E','FontSize',18); text(380,180,'F','FontSize',18); %? ? ?¨???? apingtai=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]; bpingtai=[93,94,95,96,97,98,99,100]; cpingtai=[166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182]; dpingtai=[320,321,322,323,324,325,326,327,328]; epingtai=[372,373,374,375,376,377,378,379,380,381,382,383,384,385,386]; epingtai=[475,476,477,478,479,480,481,482,483,484,485]; plot(csjd(apingtai,2),csjd(apingtai,3),'ro'); plot(csjd(bpingtai,2),csjd(bpingtai,3),'ro'); plot(csjd(cpingtai,2),csjd(cpingtai,3),'ro'); plot(csjd(dpingtai,2),csjd(dpingtai,3),'ro'); plot(csjd(epingtai,2),csjd(epingtai,3),'ro'); plot(csjd(fpingtai,2),csjd(fpingtai,3),'ro'); 附录 9 区域 F 的运行过程 %加入附录 8 中的程序 b=[93,94,95,95,96??162,163,164; 104,110,116,136,137??163,164,98];34c=[166,166,167,167,168??236,237,237; 265,181,250,255,189??237,235,238]; e=[373,373,373,374,375??474,474,474; 431,438,456,436,424??447,473,471]; f=[476,477,478,478,479,479,480,482,482,484,484,485,485,485,486,486,487,488,488,489,48 9,490,490,491,491,491,492,492,493,493,494,494,495,496,496,497,497,498,498,499,500,500, 501,501,502,502,504,505,505,506,506,507,508,508,508,509,510,511,511,512,513,514,515,5 16,517,517,518,518,518,519,519,520,521,521,522,522,523,524,524,525,525,526,527,528,52 8,528,528,529,530,531,531,532,532,532,533,533,534,535,536,537,537,538,539,539,539,540, 540,542,542,543,543,544,544,545,545,546,546,547,548,548,549,549,550,550,551,551,552,5 53,553,554,556,557,557,558,560,560,561,561,562,562,563,563,565,566,567,567,568,568,56 9,569,570,572,572,573,574,575,576,577,577,580,580,581,581,582;545,501,542,566,577,580, 568,489,559,539,570,571,572,573,487,491,488,482,560,487,490,481,550,481,492,530,493,4 96,494,495,495,499,498,495,497,498,501,499,477,500,477,502,520,530,503,504,505,506,51 3,507,509,504,507,509,510,510,511,512,483,513,514,515,516,517,518,523,505,519,521,503, 520,521,522,529,523,527,524,515,525,514,526,512,525,527,529,536,538,530,531,481,532,5 33,547,548,529,534,535,536,537,538,478,539,526,540,478,541,484,543,565,536,544,476,55 5,535,546,547,552,534,549,552,481,550,551,559,552,556,553,476,554,555,554,558,564,559, 549,561,558,562,563,480,564,565,566,567,480,569,569,574,570,571,571,541,578,578,575,5 76,479,573,579,579,581,576,582,578]; %c???¨?????? ° nf=length(fcsjd(:,1));%=73 cf=zeros(nf,nf);%73*73???¨ ? for i=1: length(f(1,:)) %1??114 cf(f(1,i)-475,f(2,i)-475)=sqrt((csjd(f(1,i),2)-csjd(f(2,i),2)).^2+(csjd(f(1,i),3)-csjd(f(2,i),3)).^2) ; end cf=cf+cf'; for i=1:nf for j=1:nf if cf(i,j)==0 cf(i,j)= end end end for i=1:nf cf(i,i)=0; end fgzl=zeros(1,length(fpingtai)); for i=1:length(fpingtai) fgzl(i)=csjd(fpingtai(i),5); end fjuli=zeros(582-475-length(fpingtai),length(fpingtai));35ffaan=zeros(length(fcsjd),1); for i=1:582-475 ffaan(i)=csjd(474+i,5); end f0=zeros(length(fcsjd),1);fjdh=zeros(length(fcsjd),1); % m=length(bcsjd)-length(bpingtai); for i=length(fpingtai):length(fcsjd) % i=1:length(ecsjd)-length(epingtai) for j=1:length(fpingtai) fjuli(i,j)=dijkstra(cf,i,j); end [C,I]=max(1./(fgzl.*fjuli(i,:))); f0(i)=C;fjdh(i)=I; fjuli(fjdh(i))=fjuli(fjdh(i))+ffaan(i); end %B???¨?????? °36
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。