交巡警服务平台的设置与调度问题 国奖文

《交巡警服务平台的设置与调度问题 国奖文》由会员分享，可在线阅读，更多相关《交巡警服务平台的设置与调度问题 国奖文（22页珍藏版）》请在金锄头文库上搜索。

1、2011高 教社 杯全 国大 学生 数学 建模 竞赛承 诺 书我们仔 细阅读了 中国大学 生数学建 模竞赛的 竞赛规则 .我们完 全明白， 在竞赛开 始后参赛 队员不能 以任何方 式（包括 电话、电 子邮件、 网上咨询 等）与队外 的任何人 （包括指 导教师） 研究、讨 论与赛题 有关的问 题。 我们知道，抄袭别人的成果是违反竞赛规则的 ,如果引用别人的成果或其他公开的资料（包括网上查 到的资料 ） ，必须 按照规定 的参考文 献的表述 方式在正 文引用处 和参考文 献中明确 列出。我们郑 重承诺， 严格遵守 竞赛规则 ，以保证 竞赛的公 正、公平 性。如有 违反竞赛 规则的行 为，我们将 受

2、到严肃 处理。我们参 赛选择的 题号是（ 从 A/B/C/D中选择 一项填写 ） ： B我们的 参赛报名 号为（如 果赛区设 置报名号 的话 ） ： 13254038所属学 校（请填 写完整的 全名 ） ： 三峡大 学参赛队 员 (打印并 签名 )： 1. 龚健2. 张玲珍3. 张伟朋指导教 师 或 指导教 师组负责 人 (打印并 签名 )： 指导教 练组 日期： 2011 年 9月 12日赛区 评阅编号 （由赛区 组委会评 阅前进行 编号 ） ：2011高 教社 杯全 国大 学生 数学 建模 竞赛编 号 专 用 页赛区 评阅编号 （由赛区 组委会评 阅前进行 编号 ） ：赛区 评阅记录 （可

3、供赛 区评阅时 使用 ） ：评 阅人 评分 备注全国 统一编号 （由赛区 组委会送 交全国前 编号 ） ：全国 评阅编号 （由全国 组委会评 阅前进行 编号 ） ：1交巡 警服 务平 台的 设置 与调 度问 题 摘 要本文主要解决的是交巡警服务平台的设置与调度问题 。 对于一个城市的交巡警服务平台 网， 我们 根据 原始 数据利 用 MATLAB软件 进行了 统计分 析，得 出全市 6个城 区特别是 A城区的各交通节点间距离等相关数据信息。对于 A城区中分配管辖范围问题 ， 我们提出有效覆盖率 、 盲区和度等概念 ， 建立了以有效覆盖率为目标函数的单目标优化模型 ， 求解得到 20个服务平台具

4、体管辖范围 （ 见表 1） ，盲区 6个，有效线覆盖率为 88.93%，有效点覆盖率为 93.48%。对于 A区快 速全封 锁 13条要 道问题 ，我们 建立 0-1规划 模型， 采用木 桶原理 中的短板 效应原 则，直 接代入 求解得 出 13条交 通要道 的最短 封锁时 间为 8.015分钟 ，各服务台工作量均衡度为 2.326，并且具体的各服务台调度方案如下表 2：表 2： 13个交通 要道的封 锁具体情 况（时间 单位：分 钟）路口号 12141621222324282930384862平台 A10A16A9 A14A13A1 A12A15A7 A8 A2 A5 A4时间 7.5876

5、.7421.5333.2650.9064.6753.5924.7528.0153.0613.9822.4760.350对于 A区确定增加服务平台问题：我们以有效线覆盖率和均衡度作为目标函数 ， 建立多目标非线性动态最优化模型 ， 采用贪心算法思想 ， 得到增加 4个平台时 ， 有效点覆盖率可达 100%，工作量均衡度为 1.80，新增 5平台时有效点覆盖率可达 100%，工作量均衡度为 1.62。比较之下取增加 4组为最佳，具体增加的位置见模型三结果。对于研究全市交巡警服务台网问题 ： 我们在分配辖区问题的基础上 ， 采用有效接警时 间 尽量 少 原则 和 就近 原 则， 建 立优 化 模型

6、四 ，得 出 增加 服 务区 数 为 ,B、 C、 E区 都 3个， C区 2个， F区 5个，具体位置和各区均衡度变化情况见模型四的结果。对于围堵罪犯方案问题 ， 考虑利用计算机仿真对围堵过程进行模拟 ， 当计算机模拟次数达到 10000次时，得到平均抓捕成功率为 100%，最短抓捕时间为 21.812分钟，所需交巡警平台数为 16个，调动率为 20%。关键 词： 覆盖 率 0-1规划 模型 多目 标动态规 划模型 贪心 算法 动态仿 真21.问 题重 述 问 题重 述 问 题重 述 问 题重 述警察在我们实际生活中起着十分重要的作用 ， 肩负有 刑事执法 、 治安管理 、 交通管理 、 服

7、务群众四大职能 。 为了更有效地贯彻实施这些职能 ， 需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同 。 由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台 、 分配各平台的管辖范围 、 调度警务资源是警务部门面临的一个实际课题 。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： 本文需解决的问题有： （ 1） 附件 1中的附图 1给出了该市中心城区 A的交通网络和现有的 20个交巡警服务平台的设置情况示意图 ， 相关的数据信息见附件 2。 请为各交巡警服务平台分配管辖范围 ， 使其在所管辖的范围

8、内出现突发事件时 ， 尽量能在 3分钟内有交巡警 （ 警车的时速为 60km/h）到达事发地 。对于重大突发事件，需要调度全区 20个交巡警服务平台的警力资源，对进出该区的 13条交通要道实现快速全封锁。 实际中一个平台的警力最多封锁一个路口 ，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况 ， 拟在该区内再增加 2至 5个平台，请确定需要增加平台的具体个数和位置。（ 2）针对全市（主城六区 A， B， C， D， E， F）的具体情况，按照设置交巡警服务平台的原则和任务 ， 分析研究 该 市现有交巡警服务平台设置方案 （ 参见

9、附件 ） 的合理性。如果有明显不合理，请给出解决方案。 如果该市地点 P（ 第 32个节点 ） 处发生了重大刑事案件 ， 在案发 3分钟后接到报警 ，犯罪嫌疑人已驾车逃跑 。 为了快速搜捕嫌疑犯 ， 请给出调度全市交巡警服务平台警力资源的最佳围堵方案。 2.模型 的假设与 符号说明2.1模型的假设假设 1：警车的时速为定值 60/kmh，不考虑车辆故障、道路堵塞等外在因素对出警速度产生的影响；假设 2：在出现突发状况时，认为在 3分钟内到达事发地的出警事件为有效出警，超 过3分钟为无效出警；假设 3：当两个的不同服务平台管辖范围出现重叠时，依据就近原则，选择距离路口较近的一方对该路口进行管辖；

10、假设 4：假设在制定全市巡警服务平台设置方案时，不考虑不同主城区之间服务平台的 调度联系 ； ：2.2符号说明符号 符号说 明m A区交巡警服务平台的数量，且 20=mn 进出 A区的交 通要道的 条数，且 13=n3N A区所有交通节点数之和 92=NS A区所有交通道路长度之和kn A区第 k个交巡 警服务台 辖区内节 点个数ks A区第 k个交巡 警服务台 辖区节点 道路长度 之和C 有效覆盖率，分为有效线覆盖率和有效点覆盖率jr 重复区域编号d 任意路口节点到交巡警服务平台的距离T 完成全封锁所需的时间ijt 第 i条交通要道中第 j个交巡警服务平台所消耗的时间t 所有交巡警服务平台工

11、作时间的平均值jt 第 j个 交巡警服务平台工 作时间总时间 A区所有交巡警服务平台工作量的均衡度kp 编号为 k的交通路口节点jq 编号为 j的交巡警服务平台 一次围堵方案里调动交巡警服务台的个数M 全区所有交巡警服务台的个数0v 罪犯开始逃跑到被抓捕全程的平均逃跑速度 仿真0N次，罪犯被抓捕成功的平均成功率ui 盲区编号3.问 题分 析 问 题分 析 问 题分 析 问 题分 析此题研究的是交巡警服务平台的设置与调度问题 。 由于警务资源有限 ， 根据城市的实际情况与需求要 ， 可以通过合理分配使得在保证有 效地履行职能的同时尽量避免警力4的闲置和浪费 ， 同时达到较优的出警效率 。 要 合

12、理地设置交巡警服务平台 ， 分配各平台的管辖范围并调度警务资源 ， 就要找出分配和调度的科学依据 ， 即需要建立合理的指标和方案。对于问题一： 针对辖区分配问题 ： 要对各交巡警服务平台分配管辖范围 ， 以达到在 3m in 内达到其管辖范围事发地点的目的 ， 首先需要对题目所提供的原始数据进行处理 ， 将 A区交通网络与平台的位置通过点和线在原始坐标轴上体现 ， 处理后可以得到任意路口节点及服务平台的坐标及距离 ， 则可以利用 MATLAB绘图工具将 A区中的 20个交巡警服务平台 及13个个出入口的坐标在图上表示出来，并可以通过程序的实现，将 A区全部 92个交通路口节点在坐标图上标出 。

13、 第二步 ， 由于需要利用距离来判断是否处于管辖范围 ， 所以必须根据题目所要求的时间限制 3分钟及已知的出警速度，得出其管辖距离的上限 ， 根据 原 图 上 已 有 的 点 以 及 点 之 间 距 离 的 计 算 方 法 可 以 得 到 每 个 服 务 平 台 能 够 到 达 的 路 口节点，观察比较每个服务平台所对应的路口节点，就可以得到两类特殊的路口节点 ： 一类是所有服务平台均无法在 3分钟内到达的节点（即盲区 ） ；另一类是同时处于不同的服务平台能到达的范围内（即重复区 ） 。利用 MATLAB可将盲区在坐标图中标示出来 。 要保证路口节点处于能到达的范围内 ， 就可以通过坐标图对管

14、辖范围进行划分 ， 可以利用画图工具将每个服务平台所管辖的节点以分块的形式标示出来 ， 易于辨识 。 选定所有管辖范围后 ， 就可以比较容易地求出盲区所在节点 、 覆盖率 、 重复率 。 又由于交巡警在出警 时 将 出 警 路 程 考 虑 成 线 更 具 有 实 际 意 义 ， 所 以 需 要 在 求 出 考 虑 以 点 为 对 象 的 覆 盖 率（点覆盖率）的同时求出以线为包含对象的覆盖率（线覆盖率 ） 。通过计算 3分钟内所有平台能到达的路线的长度之和以 及 A区所有路线的总长度 ， 二者的比值即为线覆盖率 。考虑到在 3分钟这一时间约束下不可能保证所有平台的交巡警均能及时到达事发地 ，

15、即点覆盖率达不到 100（ %） ，可以求出所有平台均能到达各自管辖范围的最短时间。针对快速全封锁问题 ： 在一个平台警力最多封锁一个路口的情况下 ， 要考虑调度 20个平台对 13个路口实现快速封锁，可以先对每个平台单独考虑，此时任意一个平台均存在两个结果 ： 封锁一个路口 、 没有封锁 。 符合 0-1规划模型的一般特点 ， 所以考虑建立 0-1模型来求解 。 根据实行封锁的时间的要求 ， 可分析属于优化问题 ， 此时可引用 “ 短板效应 ” 来考虑出警时间，即在封锁 13条交通要道过程中，所消耗时间的长短取决于封锁单条要道所耗时间最长的一者 。 因此可以考虑以 “ 最长时间最短 ” 作为

16、该调度方案的目标函数 ， 此时约束条件存在两种情况 ： 一个服务平台 （ 的警力 ） 最多封锁一条要道（ 0条或者 1条 ） 、一条要道调度多个服务平台（的警力）去封锁。针对增加服务平台问题 ： 要给出增加平台的个数和具体位置 ， 就要分析增设平台的依据和评判标准。首先，工作量可以通过该平台管辖范围内发案率的累积量来评判 ， 工作量的均衡则可以通过各平台工作量的方差来衡量 。 同时 ， 由于需要保证出警的有效性 ，因此需要利用覆盖率来参与计算 。 由于覆盖率涉及到点覆盖率和线覆盖率两种 ， 因此需要分别考虑 。 建立以出警时间 、 均衡度 、 覆盖率为目标的多目标优化模型 ， 其中覆盖率首先考虑较简单的点覆盖率，计算出 增加平台数及对应位置，然后考虑计算线覆盖率时的增加方案 ， 针对两种方案中的结果 ， 考虑通过对比增减平台时目标函数的数值变化来验证增加平台的合理性。对于问题二： 针对全市调整服务平台问题： 分析题目要求可知，设置交巡警服务平台的原则和任务是方案的前提 。 原则可以理解为以下三条 ： 1.在全市发案率较高的城区需