14队——集训 交巡警服务平台的设置与调度论文.pdf

2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承诺诺书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他公开的资料 包括 网上查到的资料 必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反竞赛规则的行为 我们将受到严肃处理 我们授权全国大学生数学建模竞赛组委会 可将我们的论文以任何形式进行公开展示 包括进 行网上公示 在书籍 期刊和其他媒体进行正式或非正式发表等 我们参赛选择的题号是 从 A B C D 中选择一项填写 B 我们的参赛报名号为 如果赛区设置报名号的话 所属学校 请填写完整的全名 参赛队员 打印并签名 1 黎澄生 2 黄北秀 3 李雪童 指导教师或指导教师组负责人 打印并签名 日期 年月日 赛区评阅编号 由赛区组委会评阅前进行编号 2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 交巡警服务平台的设置与调度 摘要 交通巡逻警察队是公安局的一个重要部门 承担着既管道路交通又管社会治安的双 重职能 本文研究了交巡警服务平台的设置与调度问题 其中包括合理地设置交巡警服 务平台 分配各平台的管辖范围 调度警务资源等问题 其研究目标是让交巡警更有效 地贯彻实施刑事执法 治安管理 交通管理 服务群众四大职能 对于问题一 建立了最短路模型 采用 Floyd 算法来求解 20 个交巡警服务平台到 72 个路口节点之间的最短距离 取距每个节点最近的平台作为管辖该点的平台 得出 平台的管辖范围 并满足在平台管辖范围内出现突发事件时 交巡警基本能在 3 分钟内 到达事发地 只有 28 29 38 39 61 92 号 6 个节点到最近平台的距离大于 3km 不满足要求 当发生重大突发事件时 为尽快实现快速全封锁 属于匹配与指派问题 建立了最 大时间最短模型 通过采用 0 1 整数规划来求解 得出最快全封锁时间为 8 015 分钟 同时建立行警总路径优化模型 采用 Floyd 算法 得出最短的总行警距离为 46 18849km 为使每个平台的工作量尽量均衡 假设交巡警员在现场处理一起突发事件的时间为 30 分钟 用日总工作时间来综合描述平台的工作量和出警时间 建立工作时间的最小 方差模型 最终求解得出需分别在 53 71 91 号节点处增设平台 对于问题二 为综合每个城区的人口 面积 交通网络及发案率等多种因素对分析 平台设置位置和数目的合理性的影响 选取平台平均处理案件数 人均发案率及节点到 最近平台距离中的最大值与城区面积的比值等作为决策变量并画出折线图 对该市现有 的交巡警服务平台进行合理性分析 得出只有 D 区和 E 区交巡警服务平台的设置相对 合理 而 A B C F 区平台的设置都不是很合理 需要增设平台数或调动平台位置 为使得解决方案更经济实用 只进行内部平台的调移 先预处理初步判断各区平台需要 的调动数量 然后建立距离方差最小模型 即使各区内部节点到平台最短距离的方差之 和最小 最后解得 A B C F 四区需调动的平台数分别为 5 2 5 7 个 在P点发生重大刑事案件后 为快速搜捕嫌疑犯 建立 递增包围圈 优化模型 先 求出随时间递增的包围圈路口节点 再采用0 1整数规划求出对应的最大限度节约警力 资源的调度方案 最后比较不同时刻包围圈节点数与围堵成功率 给出一个耗时比较短 为大约11分钟 包围圈节点数较少为34个 围堵成功率为100 的警力调度方案 关键词 关键词 Floyd 算法算法0 1 整数规划整数规划最小方差模型最小方差模型 递增包围圈递增包围圈 1问题的重述问题的重述 有困难找警察 是家喻户晓的一句流行语 警察肩负着刑事执法 治安管理 交通管理 服务群众四大职能 为了更有效地贯彻实施这些职能 需要在市区的一些交 通要道和重要部位设置交巡警服务平台 交巡警是交通警察与巡警合一的警务模式 交 巡警合一 并不是将交警 巡警部门简单合并 而是要实现 1 1 2 的效能 40 年 前 西方国家就已建立交巡警合一的警务模式 而我国在 13 年前才有了交巡警 全国 高速公路的交巡警和城市部分地区的交巡警总量达 12 万之多 近年来 京 津 沪 渝等地警方也实现了这一模式 2010 年 2 月 7 日 一支名为 交巡警 的全新警种在 重庆正式诞生 首批执勤的 150 个警务平台和 4000 名昼夜循环的交巡警 配备包括枪 支在内的 高精尖 装备 代替过去的交警和巡警 执行交通管理 刑事执法 治安管理 三大职能 1 每个交巡警服务平台的职能和警力配备基本相同 由于警务资源是有限的 如何根 据城市的实际情况与需求合理地设置交巡警服务平台 分配各平台的管辖范围 调度警 务资源是警务部门面临的一个实际课题 试就某市设置交巡警服务平台的相关情况 建立数学模型分析研究下面的问题 1 1问题一 问题一 根据附件 1 提供的该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设 置情况示意图及附件 2 的相关数据信息为各交巡警服务平台分配管辖范围 使其在所管 辖的范围内出现突发事件时 尽量能在 3 分钟内有交巡警 警车的时速为 60km h 到 达事发地 发生重大突发事件时 需要调度全区 20 个交巡警服务平台的警力资源 对进出该 区的 13 条交通要道实现快速全封锁 一个平台的警力最多能封锁一个路口 请给出该 区交巡警服务平台警力合理的调度方案 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况 为 更好地执行交巡警的职能 拟在该区内再增加 2 至 5 个平台 请确定需要增加平台的具 体个数和位置 1 2问题二 问题二 针对全市 主城六区 A B C D E F 城区的面积 人口 案发率及交通网 络等具体情况 按照设置交巡警服务平台的原则和任务 分析研究该市现有交巡警服务 平台设置方案的合理性 如果有明显不合理 请给出解决方案 如果该市地点 P 第 32 个节点 处发生了重大刑事案件 在案发 3 分钟后接到报 警 犯罪嫌疑人已驾车逃跑 为了快速搜捕嫌疑犯 请给出调度全市交巡警服务平台警 力资源的最佳围堵方案 2问题分析与假设问题分析与假设 2 1问题的分析问题的分析 2 1 1问题一 问题一 为各交巡警服务平台分配管辖范围 使其在所管辖的范围内出现突发事件时 尽量 能在 3 分钟内有交巡警 警车的时速为 60km h 到达事发地 也就是尽量使交巡警服 务平台到事发地的距离小于等于 3km 假设事发地在交通网络的路口节点处或路上 先 计算出相邻节点间的距离 再计算每个节点 不考虑在交巡警服务平台处的节点 沿交 通网络到每个平台的距离 选出距每个节点最近的平台 整理后即可对每个平台进行分 配管辖范围 当发生重大突发事件时 需要调度全区 20 个交巡警服务平台的警力资源 对进出 该区的 13 条交通要道实现快速全封锁 根据 木桶原理 封锁时间取决于某一交巡警 服务平台封锁某一交通要道的最大时间 要实现快速全封锁 就得使这个最大时间最短 因此先计算每个平台到每个出入城区的路口节点的距离 建立最大时间最短模型 采用 0 1 整数规划来求解 接着建立最短路径的优化模型 给出该区交巡警服务平台警力合 理的调度方案 因现有交巡警服务平台的工作量不均衡和有些地方出警时间过长 不能及时处理部 分突发事件 拟在该区内再增加 2 至 5 个平台 为此我们将工作量和出警时间结合在一 起用单一物理量表示 总工作时间 假设交巡警员在现场处理一起突发案件的时间为 30min 由每个节点处的案发率可计算出该点需要的节点总工作时间 同时需要计算交 巡警员沿交通网络到达所管辖节点的行驶时间 每个节点的以上两个时间加和之后的总 和就表示交巡警每天处理管辖区内案件所花的总时间 然后对每个平台的总工作时间进 行排序 选出负荷过重的平台 再建立时间方差最小模型 确定增设平台的节点及增设 平台的管辖范围 使各平台的工作量相对均衡 2 1 2问题二 问题二 因全市六区面积 人口 发案率 交通网络与平台设置等具体情况不同 分析研究 该市现有交巡警服务平台设置方案的合理性时 应综合考虑各种因素 计算每个平台平 均处理的案件数 人均发案率及节点到最近平台距离中的最大值与城区面积的比值 结 合画得的折线图 对该市现有的交巡警服务平台进行合理性分析 若每个区的上述值接 近平均值 则合理 不然就给出新的解决方案 新方案的目的是使各平台间的工作负荷 差值达到最小 可以建立时间最小方差模型来求解 如果该市地点 P 第 32 个节点 处发生了重大刑事案件 在案发 3 分钟后接到报 警 犯罪嫌疑人已驾车逃跑 假定嫌疑人的车速为 60km h 则案发 3 分钟后嫌疑人已 距 P 点 3km 为了快速搜捕嫌疑犯 首先必须确定尽可能少的围堵路口节点 并且这一 系列围堵路口节点能够形成一个无缝隙的包围圈 从而将在逃嫌疑犯控制在一个有效范 围内 其次需要给出明确的平台警力调度方案 并且能够使尽可能多的平台警力能够在 较短时间范围内到达围堵路口节点 可通过建立 递增包围圈 优化模型 先求出随时 间递增的包围圈路口节点 再采用 0 1 整数规划求出对应的最大限度节约警力资源的调 度方案 最后比较不同时刻包围圈节点数与围堵成功率 最终给出调度全市交巡警服务 平台警力资源的最佳围堵方案 2 2基本假设基本假设 1 假设交巡警在突发事件发生后立即赶往现场 并只能沿着交通网络行驶 且中 间没有意外事故等其他因素的耽搁 2 假设事件只发生在路上或路口节点处 不考虑其它地方发生的事件 3 假设交巡警员在现场处理一起突发案件的时间为 30min 每天的总工作量只考虑 由平台处赶往事发地的时间和现场处理案件的时间 4 假设犯罪嫌疑人一直匀速行驶 速度为 60km h 并忽略红绿灯 行人等因素的 影响 3符号的说明符号的说明 符号说明 i 自然数 节点的标号 i 21 92 j 自然数 交巡警服务平台的编号 j 1 20 i P j A分别是i节点和 j 平台的实际坐标值 ij S 实数 i节点沿交通网络到 j 平台的距离 j T 实数 j 平台的的日工作量 min 0 t 实数 0 t 表示警员在现场处理案件的时间 为 30min 0j x 实数 j 平台处节点的案发率 ji x 实数 j 平台所管辖的i节点的案发率 0 v 实数 警车开往事发地时的速度 为 3km min T 实数 平台的日平均工作量 min k T 实数 增设的k平台的日工作量 min n 自然数 增设的平台数 个 为 2 5 j m 自然数 j 平台管辖的节点总数 k 自然数 城区 为 1 6 的正整数 分别表示 A B C D E F 区 k m 自然数 k区的节点总数 个 kp x 实数 k区平台的平均处理案件数 件 kr x 实数 k区的人均发案率 ki x 实数 k区i节点的发案率 k P 自然数 k区平台总个数 个 k R 实数 k区人口数 万人 k S 实数 k区面积 平方公里 k 实数 k区各节点到最近平台距离的总方差 kij S 实数 k区i节点到最近 j 平台的距离 m k S 实数 k区i节点到最近 j 平台距离的平均值 m 4 4模型的建立与求解模型的建立与求解 4 1问题一 问题一 4 1 1管辖范围的分配 管辖范围的分配 为使交巡警在所管辖的范围内出现突发事件时 尽量能在 3 分钟内有交巡警 警车 的时速为 60km h 到达事发地 我们先计算出相邻节点间的距离 再计算每个节点 不 包含平台处的节点 到每个交巡警服务平台的距离 再取距每个节点最近的平台作为管 辖该点的平台 4 1 1 1 模型的建立 模型的建立 目标函数 min 20 1 92 21 ji jiij APS 1 约束条件 ts Nji j i 20 1 92 21 其中 i j 分别表示节点的标号和交巡警服务平台的编号 i P j A 分别是节点i和平台 j 的坐标值 ij S 表示i节点沿公路到 j 平台的距离 4 1 1 2 模型的求解 模型的求解 题目中给出了 A 区的交通网络与平台设置的示意图 在这个网络的任意节点间 找 一条最短路线 以求得最短的距离 属于图与网络模型中的最短路问题 本文采用 Floyd 算法 来求解最短路问题 以各交叉路口节点为图 G 的顶点 两交叉路口节点的连接线路为图相应两顶点间 的边 得图 G 对 G 的每一边 e 赋以一个实数 ew为线路的长度 称为 e 的权 得到 赋权图 G G 的子图的权是指子图的各边的权和 问题就是求赋权图 G 中两个指定的 节点 0 u 0 v 间的具最小权的轨 这条轨叫做 0 u 0 v 间的最短路 它的权叫做 0 u 0 v 间的 距离 假设图 G 权的邻接矩阵为 0 A 来存放各边长度 其中 ii a 0 ij a ji 之间没有 边 在程序中以各边都不可能达到的充分大的数代替 ii a ij w ij w 是各边的长度 Floyd 算法的基本思想是 递推产生一个矩阵数列 0 A 1 A k A n A 其中 jiAk表示从 顶点 i v 到顶点 j v 的路径上所经过的顶点序号不大于 k 的最短路径长度 nnnn n n aaa aaa aaa A 2 1 22 21 2 12 11 1 0 计算时用迭代公式 min 111 jkAkiAjiAjiA kkkk 中心城区 A 的 92 个路口节点分别标记为 i A 922 1 i 其中 i A 202 1 i是 20 个交通平台 i A 9222 21 i是路口节点 建立路口节点 i A之间的邻接距离矩阵 92 922 921 92 92 22 21 2 92 12 11 1 ddd ddd ddd DA 在 MATLAB 软件中用Floyd 算法编程 具体程序见附录 计算出任意两点之间的最 短距离矩阵 9292 ji DD 进而得出 20 个交通平台和 72 个路口节点之间最短距离矩阵 7220 ji dD 求解得具体结果如下表 4 1 所示 同时对表格信息分析处理后就可得出每个平台管 辖的节点范围 具体结果如表 4 2 所示 表 4 1 距每个节点最近的平台编号与两者距离表 节 点 标 号 到最近平台 的距离 km 平 台 编 号 最近平台到该 节点的时间 min 节 点 标 号 到最近平台 的距离 km 平 台 编 号 最近平台到该 节点的时间 min 212 71132 71571 8741 87 220 91130 91582 3052 30 230 50130 50591 5251 52 242 39132 39601 7441 74 251 79121 79614 1974 19 260 90110 90620 3540 35 271 64111 64631 0341 03 284 75154 75641 9441 94 295 70155 70651 5231 52 300 5870 58661 8431 84 312 0692 06671 6211 62 321 1471 14681 2111 21 330 8380 83690 5010 50 340 5090 50700 8620 86 350 4290 42711 1411 14 360 61160 61721 6121 61 371 12161 12731 0311 03 383 41163 41740 6310 63 393 6823 68750 9310 93 401 9121 91761 2811 28 410 85170 85770 98190 98 420 98170 98780 6410 64 430 8020 80790 45190 45 440 9520 95800 89190 89 451 1091 10810 67180 67 460 9380 93821 08181 08 471 2871 28830 54180 54 481 2971 29841 18201 18 490 5050 50850 45200 45 500 8550 85860 36200 36 511 2351 23871 47201 47 521 6651 66881 29201 29 531 1751 17890 95200 95 542 2732 27901 30201 30 551 2731 27911 60201 60 562 0852 08923 60203 60 表 4 2交巡警服务平台所管辖的节点范围表 平台 编号 所管辖的节点标号 管辖的节点 总数 个 平台 编号 所管辖的节点标号 管辖的节点 总数 个 1 67 68 69 71 73 74 75 76 78 91126 272 2 39 40 43 44 70 72 612251 354 55 65 6641321 22 23 244 457 60 62 63 6451400 5 49 50 51 52 53 56 58 59 81528 292 6001636 37 383 730 32 47 48 6151741 422 833 4621880 81 82 834 931 34 35 4541977 792 100020 84 85 86 87 88 89 90 91 92 9 4 1 2交巡警服务平台警力的合理调度 交巡警服务平台警力的合理调度 对于重大突发事件 需要调度全区 20 个交巡警服务平台的警力资源 对进出该区 的 13 条交通要道实现快速全封锁 根据 木桶原理 封锁时间取决于某一交巡警服务 平台封锁某一交通要道的最大时间 要实现快速全封锁 就得使这个最大时间最短 4 1 2 1 模型的建立 模型的建立 目标函数 N min 2 约束条件 tsN v xa j jiji 13 1 0 i 20 1 1 13 1 j ji x20 1 i 1 20 1 j ji x13 1 j 其中 ji a 表示第i平台与第 j 交通要道的最短距离 0 v 表示速度 N表示某一交巡 警服务平台封锁某一交通要道的最大时间 路口不进行封锁平台对第表示第 路口进行封锁平台对第表示第 jix jix ji ji 0 1 4 1 2 2 模型的求解模型的求解 由上述模型可知本问题属于运筹学中的匹配与指派问题 可以采用 0 1 整数规划 来求解 采用Lingo软件编程得到最优解为 8 015457 分钟 即最快全封锁时间N 8 015mi 具体调度方案如下 平台 编号 行警路径 交通要 道路口 编号 行警时间 min 路径长度 km 22 40 39 38383 98223 9822 44 57 58 59 51 50 5 47 48487 39597 3959 55 50 51 59 58 57 60 62625 25515 2551 66 47 48 30303 21353 2135 77 30 29298 01558 0155 99 35 36 16161 53251 5325 1010 26 27 12127 58667 5866 1111 25 24243 80533 8053 1212 25 24 13 23236 4776 477 1313 22 21212 70832 7083 1414 21 22225 06775 0677 1515 28284 75184 7518 1616 14146 74176 7417 表 4 3重大突发事件时交巡警封锁调度方案表 经过程序在 Lingo 软件的运行发现 每次运行的结果都存在差异 可知上述的解仍 不是问题的最优解 可在最快全封锁时间 N 8 015min 前提下 对总行警路径进行优化 使得总行警路径最短 4 1 2 3 模型的改进模型的改进 总行警路径优化模型 总行警路径优化模型 首先对交巡警平台与交通要道路口的距离矩阵进行预处理 0 0 9999 vNa vNaa a ji jiji ji 3 其中 ji a 表示第i平台与第 j 交通要道的最短距离N 8 015min v 1km min 9999 相当于一个无穷大量 因Lingo软件中无法设置inf 模型的建立 模型的建立 目标函数 ji ij ji xa 20 1 13 1 min 4 约束条件 ts 13 11 20 11 20 1 13 1 jx ix i ji j ji 模型的求解 模型的求解 可用上述求解方法在Lingo软件中编程求解 具体程序见附录 计算求得的最短的 总行警距离为 46 18849km 具体安排如下表 4 4 所示 平台 编号 行警路径 交通要道 路口编号 行警时间 min 路径长度 km 22 40 39 38383 98223 9822 44 62620 350 35 55 47 48482 47582 4758 77 30 29298 01558 0155 88 33 32 7 30303 06083 0608 99 35 36 16161 53251 5325 1010 26 11 22227 70797 7079 1111 25 24243 80533 8053 12121200 1313 23230 50 5 1414 21213 2653 265 1515 28284 75184 7518 1616 14146 74176 7417 表 4 4总行警路径优化后的封锁调度方案表 行警路径优化后平台的具体调动方案示意图如下图 4 1 所示 图 4 1平台封锁路口调动方案示意图 4 1 3平台的增设位置和数目 平台的增设位置和数目 假设交巡警员在现场处理一个突发案件的时间为 30min 由每个节点处的案发率可 计算出该点需要的节点总工作时间 同时计算交巡警员沿交通网络到达所管辖节点的行 驶时间 每个节点的以上两个时间加和之后的总和就表示交巡警处理管辖区内案件所花 的总时间 对每个平台的总工作时间进行排序后就可粗略知道需要在附近节点处增设平 台的平台 由此再建立时间最小方差模型以具体确定需要增设的平台位置及数量 4 1 3 1 模型的建立 模型的建立 目标函数 min 20 11 22 19 1 j n k kj TTTT n 5 ji m i jijj xtvSxtT j 1 0000 2 6 约束条件 j 12345678910 j m 9645805240 j 11121314151617181920 j m 2140232429 表 4 5j 平台管辖的节点总数 j m 注 j T 表示 j 平台的日工作量 min T 表示平台的日平均工作量 min k T表示增设平台的日工作量 min n表示增设的平台数 个 为 2 3 4 5 j m 表示 j 平台管辖的节点总数 取值如表 4 5 所示 0 t 表示警员在现场处理案件的时间 为 30min 0j x表示 j 平台处节点的案发率 ji x 表示 j 平台所管辖的i节点的案发率 0 v 表示警车赶往事发地时的速度 为 3km min 4 1 3 2 模型的求解 模型的求解 经 MATLAB 计算可解得下表 4 6 所示的各个平台的日工作量排序表 平台编号 平台处节点工 作量 min 平台总工作量 min 平台编号 平台处节点工 作量 min 平台总工作量 min 1048481678186 608 675751857190 685 147575451210 256 1272125 728772219 976 1954134 434263253 732 1178142 784963258 548 872154 6561366272 794 1775164 124563281 292 1563172 31151287 112 366183 0022057368 644 极差320 644方差6576 5 表 4 6各个平台的日工作量排序表 结合题目条件 由上表可知需要在管辖内的节点处增设平台的交巡警服务平台一定 有 20 号 1 号 可能有 5 号 13 号和 9 号 接着进行模型预处理剔除因地理位置因素 没有管辖其它节点的平台 即 10 号 6 号 14 号平台 再计算 20 1 5 13 9 号平 台的日工作量与日平均工作量的差值 具体结果如下表 4 7 所示 平台号工作量差值 min 所管辖的节点标号 20156 486184 85 86 87 88 89 90 91 92 174 95467 68 69 71 73 74 75 76 78 569 13449 50 51 52 53 56 58 59 1360 636121 22 23 24 946 390131 34 35 45 注 计算得总工作量前 17 名的平均工作量为 21 1579min 表 4 7前 5 名工作量与平均工作量的差值及管辖节点表 结合全市六区交通网络与平台设置的示意图可进行预处理 具体过程如下 20 号 由于 85 85 86 号节点与 20 号平台处于邻接位置 不需增设平台 1 号 由于 76 68 号节点与 49 71 73 74 号节点处于相对位置 而且后 4 者 的工作量大于前两者 故不选择在 76 78 号节点处增设平台 5 号 由于 58 号节点与 49 51 52 53 号节点相距较远 所以不应选择 58 号作 为平台的增设节点 13 号 由于 21 22 23 号均与原有平台邻接 不需增设平台 9 号 由于 31 34 35 号均与原有平台邻接 不需增设平台 故初步判定各平台管辖的节点中可能作为新增设平台的自身节点如下表 4 8 所示 平台编号新增设平台管辖的节点 含自身 及日工作量 5 节点标号52515049 工作量 min 19 99225 96834 8737 2 1 节点标号73697471 工作量 min 28 85434 134 38635 508 20 节点标号9092918487 工作量 min 29 3429 7629 8832 3636 234 表 4 8新增设平台所管辖的节点 含自身 及日工作量表 对于初步选取的这些节点 把这些节点的具体数据代入模型中并用 MATLAB 进行 求解得出共新增设 3 个平台 具体结果如下表 4 9 所示 同时得出增设平台前后原来各 平台的工作量方差折线图 如图 4 2 所示 增设平台的节点标号917153 新平台日工作量 min 148 628130 348124 676 方差贡献率28 99 10 08 8 36 坐标 445 380 415 351 348 369 增加平台后的总方差新总方差为 3324 3 比原来减小了 49 45 表 4 9增设平台的方差贡献率及总方差表 图 4 2增设平台前后原来各平台的工作量方差折线图 注 绿色直线含后面增设的 53 71 91 号平台的工作量变化即 21 22 23 号平台 从图中可以明显看出那些工作负荷量过大的平台在增设平台后明显减小了 其中 6 号 10 号 14 号平台由于特殊地理位置 处于交通网络比较稀疏的区域 没有考虑在 评价范围内 4 2问题二 问题二 4 2 1现有平台设置方案的分析 现有平台设置方案的分析 考虑到每个城区的人口 面积 交通网络 平台设置位置和数目及发案率等多种因 素的影响 我们选取平台平均处理案件数与人均发案率及节点到最近平台距离中最大值 与面积的比值对该市现有的交巡警服务平台进行合理性分析 4 2 1 1 模型的建立 模型的建立 目标函数 k m i kikp Pxx k 1 7 k m i kikr Rxx k 1 8 kij SSminmax 9 其中 k表示城区 为 1 6 的正整数 分别表示 A B C D E F 区 k m 表示k区的节点总数 个 kp x表示k区平台平均处理案件数 kr x表示k区人均发案率 ki x 表示k区节点发案率 kj P表示k区平台个数 个 k R表示k区人口数 万人 k S表示k区面积 平方公里 4 2 1 2 模型的求解 模型的求解 通过 EXCEL 及 MATLAB 可编程计算得结果如下表 4 10 所示 城区k123456 平台平均处理案件数 kp x5 4138 311 0117 5337 869 927 人均发案率 kr x2 0253 1623 820 9291 5712 06 节点到最近平台距离中最 大值与面积的比值 0 150 0430 0310 0290 0440 031 表 4 10城区平台设置合理性分析的参数值表 由 MATLAB 对上述结果可画得如下所示的折线图 图 4 3 城区平均平台处理案件数及人均发案率折线图 图 4 4 节点到最近平台距离中的最小值与城区面积比值的折线图 图 4 3 描述的是各区统计的整体平均状态 图 4 4 描述的是各区的内部状态 具体 分析如下 A 区 平台平均处理案件数和人均案发率都是接近或小于均值 但 A 区内部存在 极不平衡状态 聚集状态很严重 B 区 平台平均案件处理数接近均值 而人均案发率高于均值 节点到平台的最短 距离除以区域面积比 A 区以外其它区的均值要高一些 说明平台数不够 C 区 平台平均处理案件数和人均发案率都处于峰值 说明该区域的平台数量非常 有限 但 C 区内部状态比较均衡 不需要进行较大的调整 D 区和 E 区 二者的平台平均案件处理数 人均发案率和节点到最近平台距离的最 大值与面积的比值都接近均值 说明无论整体还是内部都比较均衡 F 区 平台平均案件处理数接近峰值 而人均发案率接近均值 说明该区的平台数 量很有限 节点到最近平台距离的最大值与面积的比值接近后 5 个区的均值 说明还是 比较均衡 综合以上分析可看出 只有 D 区和 E 区交巡警服务平台的设置相对合理些 而其 它 4 个区的设置都不是很合理 需要增设平台数或调动平台位置 在实际情况中 如果 通过增设平台来解决问题的话 需要大量增加平台费用和警员数量 对于城市来说不太 符合实际 因此我们拟对不合理的区域进行内部调动来实现 对城区现有平台的调动方案 对城区现有平台的调动方案 预处理 通过具体计算每个城区内节点到最近平台的距离 画出各区内各节点到平 台最短距离的降序变化趋势图来初步判断对各区的调动平台数 A 区 综上及问题一中对 A 区内部情况可知在现有平台设置情况下 A 区有六个 节点发生突发事件时 交巡警不能在 3min 内到达事发地 因此初步解决方案为对 A 区 内部 6 个平台进行合理的调动 B 区 图 4 5B 区各节点到平台最短距离的降序变化趋势图 从上图 4 6 可看出节点到平台最短距离的变化趋势很明显 前 3 名趋势较陡 后面 趋于平缓些 所以拟在前 3 名的节点附近调入平台 C 区 图 4 6C 区各节点到平台最短距离的降序变化趋势图 上图显示前 6 7 名的变化率比较大 说明内部有 6 7 个平台分布不均 因此拟内部 调动内部 6 7 个平台的位置 F 区 图 4 7F 区各节点到平台最短距离的降序变化趋势图 从上图可以看出节点到平台的最短距离中前 8 名左右相差较大 说明内部平台设置 不是很均衡 存在内部聚集状态 所以拟在该区进行 10 个左右平台的转移 模型的建立 模型的建立 为具体确定各区平台调动的位置及数量 我们建立距离方差最小模型 即内部节点 到平台最短距离的方差之和最小 目标函数 2 1 1 1 min m i kkijk SS m 10 mSS m i kijk 1 11 约束条件 k 表示k区各节点到最近平台距离的总方差 kij S表示k区i节点到最近 j 平台的距离 m k S 表示k区i节点到最近 j 平台距离的平均值 m 模型的求解 模型的求解 在 MATLAB 中用程序进行运算得出如下结果 城区 平台的调动总数 个 原平台编号转移目标处的节点标号 A 5 A7A47 A3A55 A2A44 A91A82 A15A28 B2 B2B 109 B1B 104 C5 C7C 229 C9C 201 C8C 234 C9C 212 C4C 240 F7 F6F 492 F5F 575 F7F 486 F2F 552 F6F 568 F4F 537 F8F 506 表 4 11各城区内部平台的调动表 4 2 2围堵犯罪嫌疑人的最佳调度方案 围堵犯罪嫌疑人的最佳调度方案 4 2 2 1 模型的建立 模型的建立 首先分析犯罪分子的可能位置 从而获得包围犯罪分子的路口集合 1 j a 表示当前 的时刻T 从案发后开始计时 可达路口 1 j 与P点的距离 则 1 j a 满足 3 1 vTaj 12 之后根据所有可达路口 1 j 求出和 1 j 相连通但在时刻T 不可到达的路口 2 j 即可以 包围犯罪嫌疑人的路口 则 2j a满足 2j a3 vT 13 要满足路口 1 j 与路口 2 j 相连则 2 1 jj A A为邻接矩阵 4 2 2 2 模型的求解 模型的求解 由 MATLAB 可得围堵犯罪嫌疑人的包围圈节点如下表 4 12 所示 采用问题一中的 0 1 整数规划方法可求出平台完全封锁包围圈节点的最短时间 将其与T 进行比较 计 算出封锁成功的包围圈节点个数为m 求出包围成功率 n m 然后计算出不同递增的T 下 的包围成功率 具体结果如下表 4 13 所示 最终形成的包围圈如图 4 8 所示 平台编号节点标号平台编号节点标号平台编号节点标号 131792137828 44180938326 10241811047535 1211822055234 13253202347729 1423221653732 2223722757538 1851711956836 8262291548631 167171751450633 168111761248430 24018177748537 170131788 表 4 12 平台所封锁的包围圈节点 围堵节点数 个 最短时间 min 围堵成功率 21561 90 24683 33 28785 71 401080 00 3811100 最短时间 t 11min 围堵成功率为 100 表 4 13不同时间内围堵节点数及成功率 图 4 8最终围堵包围圈示意图 5模型的检验模型的检验 1 对问题一中平台管辖范围的分配结果显示大部分节点发生突发事件时交巡警都 能在 3min 内到达 只有 28 29 38 39 61 92 号 6 个节点离最近平台的距离大于 3km 若发生突发事件时交巡警不能在 3min 内到达 说明模型总体上基本合理 2 在 A 区平台的增设模型中 求解结果显示增设平台后个节点到最近平台距离的 方差值明显减小了 说明方案相对合理 6模型的评价模型的评价 6 1模型优点 模型优点 1 求解发生重大突发事件时调度交巡警对交通要道路口进行封锁方案时 在最大 时间最短模型的基础上建立并求解了行警路径最短的优化模型 而且配有示意图说明 2 在解决市区主城平台设置不合理方案时没有新增设平台数 而是进行内部平台 位置的调动 对现实生活具有一定的参考价值 3 确定搜捕犯罪嫌疑人的最佳围堵方案中采用 递增包围圈 优化模型 比较新 颖有创意 6 2模型缺点 模型缺点 1 将平台工作量转化为时间时假设现场处理案件时间为 30min 准确性不确定 2 在问题一中选择增设平台的节点位置及管辖范围时 只考虑了原平台管辖范围 内的节点 没有考虑相邻管辖区的节点 3 对于问题二中假设嫌疑犯逃跑时的车速为 60km h 且只沿着交通网络逃跑 不太 符合实际 参考文献 1 交巡警平台 2013 8 12 MATLAB 在数学建模中的应用 北京 北京航空航天大学出版社 韩中庚 实用运筹学模型 方法与计算 北京 清华大学出版社 附录 附录 问题 1 1 计算A区任意两点之间的最短距离 clear all clc x y textread C Users dell Documents 节点横纵坐标 txt n n delimiter t sp ep textread C Users dell Documents startpoint txt n n delimiter t D zeros 92 92 for i 1 length sp D sp i ep i sqrt x sp i x ep i 2 y sp i y ep i 2 D ep i sp i sqrt x sp i x ep i 2 y sp i y ep i 2 end D zeros 92 92 for i 1 140 D A i B i sqrt X A i X B i 2 Y A i Y B i 2 D B i A i sqrt X A i X B i 2 Y A i Y B i 2 end n 92 D M max max D n 2 M为充分大的正实数 D D D 0 eye n M path zeros n for k 1 n for i 1 n for j 1 n if D i j D i k D k j D i j D i k D k j path i j k end end end end 问题 1 2 以最大封锁时间为优化目标 a 12 14 16 21 22 23 24 28 29 30 38 48 62 d zeros 20 13 for i 1 20 for j 1 13 d i j D i a j 10 end end Lingo 源程序及部分结果 model sets pt 1 20 lk 1 13 D pt lk a x endsets data a 222 3615273 160 2847372 92 86812205 192 9343927 210 962149 225 0175342 228 932028 190 0116023 195 1580619 120 8344452 58 80934932 118 5011476 48 85216716 204 6392212141 297247173 88063198173 9469026191 974659206 0300441 211 2097218172 2892962177 4357558103 112139139 82185925103 0953721 60 35067549 183 5226849127 672272860 25565768160 3219283178 3496847192 4050698 190 0931855151 1727599156 319219581 995602860 9383955881 97883576 43 93385175 219 9738302150 085145682 66853046182 7348011200 7625574214 8179426 226 5443309 162 2690872 155 3533786 81 02976186 48 60975773 73 95869405 3 5 176 281911 129 696286 62 27967084 162 3459414 177 4952363 191 5506215 182 8524116 113 0686519 106 1529433 31 82932662 94 21119111 24 75825881 52 55074784 176 58776 130 002135 62 58551981 162 6517904 177 8010853 191 8564704 183 1582606 113 3745009 106 4587923 32 13517559 94 51704008 25 06410777 53 37332351 149 1493579109 012209941 5955947141 6618653150 3626833164 4180684 155 719858685 7021836780 15456865 83095189573 5271149712 90201971 79 91721609 140 925056994 3394318826 92281672126 9890873142 1383822156 1937673 147 4955575102 2802537104 93181530 6081983458 8543369930 99467337 86 77282849 130 10714982 7420183815 32540322115 3916738131 3204744145 3758595 136 677649797 75722402107 24405734 9230364547 2569234941 99410426 93 36668122 75 86585214 127 7565893 69 5667001 95 10693385 77 07917747 91 13456261 82 4363528 141 9486453 151 4354783 79 1144577 101 4982204 86 18552552 147 6079781 37 9135282183 37297726113 950312150 7233218332 6955654546 75095059 38 05274077186 3322573195 8190903123 4980697145 8818324130 5691375 191 9915901 0 119 502818 145 4325522 86 8531626 68 82540622 64 77002108 35 9163002 217 8144974 227 3013304 154 9803098 177 3640725 162 0513777 223 4738302 59 7700210859 73279695127 149412127 083141529 055385138523 85372088 228 0832079 237 5700409 165 2490203 161 2081848 172 3200881 213 3179426 119 502818067 4166151632 6496554350 6774118164 7327969583 58651783 180 4992424 189 1667785 114 8431618 101 4753879 121 9142296 153 5851456 170 2960799132 980824965 56420975165 6304804171 5094053185 5647904 176 866580647 5184174857 0052504644 0147