交巡警服务平台的设置与调度

交巡警服务平台的设置与调度 一 问题重述 有困难找警察 是家喻户晓的一句流行语 警察肩负着刑事执法 治安 管理 交通管理 服务群众四大职能 为了更有效地贯彻实施这些职能 需要 在市区的一些交通要道和重要部位设置交巡警服务平台 每个交巡警服务平台 的职能和警力配备基本相同 由于警务资源是有限的 如何根据城市的实际情 况与需求合理地设置交巡警服务平台 分配各平台的管辖范围 调度警务资源 是警务部门面临的一个实际课题 试就某市设置交巡警服务平台的相关情况 建立数学模型分析研究下面的 问题 1 附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个 交巡警服务平台的设置情况示意图 相关的数据信息见附件 2 请为各交巡警 服务平台分配管辖范围 使其在所管辖的范围内出现突发事件时 尽量能在 3 分钟内有交巡警 警车的时速为 60km h 到达事发地 对于重大突发事件 需要调度全区 20 个交巡警服务平台的警力资源 对进 出该区的 13 条交通要道实现快速全封锁 实际中一个平台的警力最多封锁一个 路口 请给出该区交巡警服务平台警力合理的调度方案 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际 情况 拟在该区内再增加 2 至 5 个平台 请确定需要增加平台的具体个数和位 置 2 针对全市 主城六区 A B C D E F 的具体情况 按照设置交巡 警服务平台的原则和任务 分析研究该市现有交巡警服务平台设置方案 参见 附件 的合理性 如果有明显不合理 请给出解决方案 如果该市地点 P 第 32 个节点 处发生了重大刑事案件 在案发 3 分钟后 接到报警 犯罪嫌疑人已驾车逃跑 为了快速搜捕嫌疑犯 请给出调度全市交 巡警服务平台警力资源的最佳围堵方案 二 模型假设 1 每个交巡警服务平台的职能和警力配备基本相同 2 警车的行驶速度恒定 不考虑实际交通状况的影响 3 交巡警服务平台接到报警后能立即出警 中间没有延误 4 每个节点只能被一个服务平台管辖 5 一个平台的警力最多封锁一个路口 三 符号说明 ij x 服务平台管辖第个路口节点的决策变量 i Aj ij t在中心城区 A 中 从第 个服务平台到第个交叉路口节点的最短ij 时间 j w中心城区 A 的第个交叉路口节点的发案率 j 1 T在中心城区 A 内平均每个案件的出警时间 2 T在中心城区 A 内封锁 13 个出入城区的路口节点的最短时间 J中心城区 A 的 13 个出入城区的路口节点标号的集合 i q第 个服务平台的工作强度 i k 第区分配的服务平台资源比率 k 四 问题分析 在城市规划中 交巡警服务平台的布局是一项非常重要的内容 长期以来 由于种种原因 目前的城市建设大多对警务资源的规划缺乏科学性 交巡警服 务平台的选址 管辖区域的划分多依据经验进行 大多数城市均不同程度地存 在服务平台布局不合理 管辖范围分配不均 警务资源调度困难等问题 另外 警务资源常常是有限的 设置交巡警服务平台也需要大量成本 所以更有效地 分配和调度警务资源对于城市的长治久安有着重要的意义 本文着力解决的是 合理地确定交巡警服务平台的数量及其位置 合理分配各平台的管辖范围以及 当重大突发事件发生时快速有效地调度警务资源这三方面的问题 1 对于问题一 在问题一中又有三个子问题需要解决 第一是要对中心城区 A 的 20 个现有交巡警服务平台分配管辖范围 首先假 设每个交叉路口节点要么被其中一个服务平台完全管辖 要么被完全不管辖 即覆盖度是二元的 所以考虑到用 0 1 整数规划模型 要使得案发后的损失减 低到最小 就要求警方在接到报警后能在最短的时间内到达事故现场 这样就 确定了平均每个突发事件警方出警时间的目标函数 第二是当重大突发事件发生后 要对中心城区 A 的 20 个交巡警服务平台的 警力资源进行调度 从而对进出该区的 13 条交通要道实现快速全封锁 同样考 虑使用 0 1 整数规划模型 因为要求对交通要道实现全封锁 所以问题的关键 是合理调度警务资源使得封锁全部要道所需的总时间达到最小 也就是使得出 警时间最长的服务平台所需的时间尽可能的小 第三是针对现有的中心城区 A 的 20 个交巡警服务平台进行分析后 需要新 增加 2 5 个服务平台以解决工作量不平衡和部分路口节点出警时间过长的问题 这属于交巡警服务平台选址问题 一方面考虑采用集合覆盖模型 1 目的是在 满足所有节点 3 分钟内都有警方到达的条件下 使新增设的服务平台数目尽可 能得小 从而降低了建设成本 另一方面也要考虑新增设服务平台后 能够解 决服务平台工作量不平衡的问题 所以把尽可能均衡各个服务平台工作量作为 第二个目标 因此考虑需要建立一个两目标的 0 1 整数规划模型 2 对于问题二 问题二中有两个问题需要解决 一是根据已有的数据 评价全市六个区内 现有的交巡警服务平台的数目和布局的合理性 如果不合理就给出解决方案 二是当该市 P 处发生重大刑事案件时 调度全市警力资源设计出最佳的围堵方 案 对于第一个小问题 要先按照设置交巡警服务平台的原则和任务 对全市 的交巡警服务平台的数目和布局讨论其合理性 交巡警服务平台的选址应遵循 尽量使每个交巡警服务平台的工作量基本均衡和每个节点突发事件发生时在 3 分钟内有警力到达的原则 所以选用各个服务平台平均每天的工作强度 平均 每天处理的突发事件数 的方差和服务平台的覆盖率 区域内 3 分钟内有警方 到达事发地的节点占区域内总结点的比率 为指标来进行评价 如果在全市范围内现有交巡警服务平台设置方案存在明显的不合理性 那 么可能存在如下两种原因 第一 该市分配给各个区的交巡警服务平台比率不 合理 第二 各个区内的交巡警服务平台选址方案不合理 对于第二种原因 在第一问第三个子问题中对 A 区交巡警服务平台设置方案已经做过详细讨论 可推广到其他几个区中 现在设法解决由第一种原因引起不合理性的问题 据 此 我们提出了依据各区域人口密度 各区域公路总长度以及各区域平均每天 总的发案率为三个评判指标 在全市范围内重新分配警力资源 也就是重新分 配每个区服务平台数量的解决方案 对于第二个小问题 首先分析出 在案发后的 3 分钟内 警方还未接到报 警 即使嫌疑人开车驶过服务平台 警方不能识别出嫌疑人 而 3 分钟后警方 已接到报警 设此时警方掌握了足够证据 故可以假设 3 分钟后只要警方与嫌 疑人相遇就能够将其抓获 警方在接到报警后 根据嫌疑人可能逃跑的路径 可以估计出嫌疑人逃跑的大致范围 所以问题就转化为 投入最少的警力以最 快的速度形成包围圈 并确保嫌疑犯在这段时间内无法跑出包围圈 即可认为 围堵方案成功 5 模型的建立与求解 5 1 问题一 5 1 1 管辖范围分配模型 目标函数 根据题目要求及实际情况只需各交巡警服务平台到事故节点时间最短 其速度假设匀速 60km h 即路程最短 而此问中各节点对应交巡警平台是 独立的 因此只需求出节点到各交巡警平台的最短路程即可 故目标函数 得到 72 行一列的矩阵 就是 11 21 1 2 12 22 2 72 172 272 72 min ij j i j llll llll L llll 20 20 20 每个节点到每个平台的最小值 约束条件分析 a 为了节约警力资源规定每个节点只归属于一个服务平台 b 某节点发生事故后 3 分钟内需有交巡警到达事发地 即出事地点距服务 平台路程不超过 3km 为计算方便 根据图中数据的比例尺 将 3 分钟等 效为长度数字 30 20 1 1 30 i j j i ji j x x L 约束条件 模型求解 算法思想 用附录中给出的坐标数据求出各交通节点间距离 然后构建带 权的邻接矩阵 利用 Floyd 算法 2 3 求出各节点之间的最路程离及路径 找出每个节点到 20 个服务平台的最短距离 则这个节点就归属于该服务平台 程序实现流程 由节点坐标 及交通路口 线路计算出 直达矩阵 由直达矩阵 求出 Floyd 算 法所需的邻 接矩阵 在 matlab 中调用 floyd 算法程序求得 任意两节点最短路 程及路径矩阵 用 excel 将节点 到的平台最小 路程及对应的 平台号找出 1 计算出各交通路口的直达矩阵代码见附录 1 2 带权的邻接矩阵代码见附录 3 利用 Floyd 算法求出各节点间最短路程即路径的代码见附录 4 对于节点到每个平台的最短距离用 excel 排出结果如下 表 1 各节点到平台的最短距离 平台节点 最短距离 km 平台节点 最短距 离 km 平台节点 最短距离 km 1671 6195490 4913230 500 1681 2075500 5013242 385 1690 5005510 5115284 752 1711 1405520 5215295 701 1731 0295530 5316360 608 1740 6265560 5616371 118 1750 9305580 5816383 406 1761 2835590 5917410 850 1780 6407300 3017420 985 2393 6827320 3218800 806 2401 9147470 4718810 670 2430 8007480 4818821 079 2440 9497610 6118830 539 2700 8608330 3319770 985 2721 6068460 4619790 447 3542 2719310 3120841 175 3551 2669340 3420850 447 3651 5249350 3520860 360 3661 8409450 4520871 465 4571 86811260 2620881 295 4601 73911270 2720890 949 4620 35012250 2520901 302 4631 03113210 2120911 599 4641 93613220 2220923 601 5 1 2 对 13 条交通要道的封锁问题 要对该区的 13 条交通要道实现快速全封锁 即要求最后一个被封锁的路口 所用时间最短 同时交警全区调度总路程最短 即节约了警力资源 目标函数 min 13 60 St 总调度路程 1320 11 i ji j ij Sa x 最后一个被封锁路口所用时间 max i j tt 约束条件 a 一个平台最多封锁一个路口 即每个平台最多被调用一次 b 每个路口都要被封锁 20 1 13 1 1 1 i j j i j i x x 约束条件 模型求解 算法思想与算法实现 1 用 matlab 求出出入要道到各个平台的最短路程 建立 13 20 的矩阵 2 建立优化模型用 lingo 求解 代码见附录 求解结果服务平台对应的封锁要道如下 表格 2 对交通要道封锁优化结果 求解出封锁十三个交通要到的总调度路程 交通要道封锁的平台距离 km封锁的时间 分钟 121200 141400 1674 1595594 159559 211610 0066310 00663 22113 2695573 269557 23130 50 5 24108 2436358 243635 28154 7518424 751842 29910 7244110 72441 3083 060823 06082 3823 9821863 982186 4862 5064112 506411 6240 350 35 51 555km 1320 min 11 min i ji j ij Sa x 最后一个被封锁的时间 T 10 72min 5 1 3 平台增加 1 模型分析 在现有的情况下 有的交巡警服务平台由于周围节点密集 使得其工作量 较大 有的地方平台距离节点较远 导致出警时间过长 超过 3 分钟 因此增 加平台后 要使得出警时间缩短 缓解某些平台工作量过大的状况 建立评价指标 减小原先某些平台的工作量 使得各个平台工作量的方差 减小 即方差越小工作量越相对平均 方差 其中 2 20 1 20 jj j j wE w D w 20 1 20 j j j w E w 2 约束条件即添加原则 a 出警时间缩短 控制在三分钟内 使得原先 3 分钟不能到达的节点现在 可以到达 b 按照交巡警平台设置的原则及实际情况 新增加的平台应该在发案率较 高的节点 c 在工作量最大的平台周围增添新平台以减少工作量 d 同等条件下 选择新增的平台要离原有平台尽量的远 以增大它的辐射 区域 3 模型求解与评价 根据上面两问中统计出的结果 结合交通分布图 使用上面列出原则 对 A 区平台设置进行分析求解 过程如下 a 由于节点 39 出警时间超过了 3 分钟 可以考虑在其周围添加平台 根 据给出的发案率数据 可以将平台设置在 39 或 40 而设置在 39 后 38 40 节 点将归属于平台 39 可以缓解 2 16 的工作量 显然更优 所以在