2011高教社杯全国大学生数学建模竞赛B题论文要点.pdf
《2011高教社杯全国大学生数学建模竞赛B题论文要点.pdf》由会员分享,可在线阅读,更多相关《2011高教社杯全国大学生数学建模竞赛B题论文要点.pdf(14页珍藏版)》请在三一文库上搜索。
1、摘要 本文就某市的实际情况与需求,合理的建立了有关交巡警服务平台设置与调 度的模型,通过图论模型、规划模型以及计算机程序的结合,对题中所述问题进行 了求解,获得了比较满意的结果。 对于问题一,首先将出警时间的约束转换为距离约束,分别利用朴素的覆盖点 集以及微变量逐次调控的方法,得出了该问题的预分配方案以及最后的优化方案。 问题一的第二个子问题是匹配问题,我们通过 0-1 变量 match来标记每个交 巡警服务平台是否参与道路的封锁。则当封锁路口时,需要全部13 个路口全部 封锁才能达到目的。 警车到达节点所花费的时间应该以最后一个到达对应的节点 的警车所需要的时间来决定。于是借助MATLAB
2、程序来解决此问题,由上文可得 目标函数为: 1 max cost( , )( , ) n i j i jmatch i j,得到一个最佳的调度方案, 封堵完 成的最短时间约为8 分钟。 第三个子问题作为对第一个子问题的优化补充,我们基于前面的结果对各站点 的工作量进行尽量的均衡分配,根据再分配的结果,在满足各个服务站点工作量平 衡的前提下,得出结论分别要在编号为42,57,62,90的四个交点上添加4 个新的服 务站。 对于问题二,采取与问题一的第三个子问题相同的原则和任务要求,针对全市 现有的服务平台数量进行平台管辖范围的分配,分配原理与问题一的第一个子问题 基本类似,只是数据规模的一个扩大
3、问题。而在后来的模型优化过程中,我们引入 人口密度的因素,对现有服务平台管辖范围进行重新分配。并利用工作量的均衡性 来度量设置方案合理性。 最后,对于问题二的最后一个子问题,我们建立了最佳围堵方案模型。考虑到 警力资源的限制, 不可能完全将该区域的任何一个点都围堵住,这时就需要在原有围 堵的基础上改进方案,在那些未被围住的点继续以3 分钟的圈往外延伸。最后得出 合理的围堵方案。 关键词: 0-1 规划变量微调工作量均衡度 一、问题重述 警察肩负着刑事执法,治安管理,交通管理,服务群众四大职能。为了更有 效地贯彻实施这些职能, 需要在市区的一些交通要道和重要部位设置交巡警服务 平台。如何根据城市
4、的实际情况与需求合理地设置交巡警服务平台,分配各平台 的管辖范围,调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问 题: (1)附件 1 中的附图 1 给出了该市中心城区A的交通网络和现有的20 个交 巡警服务平台的设置情况示意图。请为各交巡警服务平台分配管辖范围,使其在 所管辖的范围内出现突发事件时,尽量能在3 分钟内有交巡警到达事发地。 对于重大突发事件,需要调度全区20 个交巡警服务平台的警力资源,对进 出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个 路口,请给出该区交巡警服务平台警力合理的调度方案
5、。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际 情况, 拟在该区内再增加2 至 5 个平台,请确定需要增加平台的具体个数和位置。 (2)针对全市的具体情况,按照设置交巡警服务平台的原则和任务,分析 研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理, 请给出解 决方案。 如果该市地点 P处发生了重大刑事案件, 在案发 3分钟后接到报警, 犯罪嫌 疑人已驾车逃跑。 为了快速搜捕嫌疑犯, 请给出调度全市交巡警服务平台警力资 源的最佳围堵方案。 二、问题假设 (1) 每个交巡警平台的职能与警力的配置相同; (2) 不考虑警车启动与停止,路上受到阻碍所花费的时间; (3
6、) 假设巡警都按最短路径到达各案发路口; (4) 假设犯罪案件都在路口上发生; (5) 道路均为双向; (6) 假设城区内道路无限速; (7) 假设犯罪案件不会在同一时间内发生多起; (8) 交巡警服务平台的节点的犯罪案件的解决不花费时间; (9) 假设犯罪车辆逃跑与警车的追赶速度相同; 三、符号说明 s1:交巡警管辖距离; v1:警车的平均速度; v2:嫌疑人逃跑的平均速度; t0:警车到达案发路口的时间限制; li:各点到管辖它的交巡警平台的距离; :各点的发案率; Ai:各点的工作量; zi:各节点到管辖它的交巡警服务平台的距离; xi:第 i 个节点的横坐标; yi:第 i 各节点的纵
7、坐标; d:两节点之间的距离; cost (i ,j ) :i ,j 两点的实际最短距离; 四、模型预处理 (1)交巡警服务平台的管辖范围: 该问题要求在道路交点出现突发事件时,交巡警尽量能在 3 分钟内到达事发 点。由于警车的时速均衡且为60km/h,所以可以将时间限制转换为距离限制, 由于 110 svt ,可求出交巡警在时间限制内管辖范围的最大半径为3km。为了 处理方便,我们使得交巡警服务平台以一整段路为标准来管辖各路段。同时根据 附件 2 所给内容,基于各个路口的发案率,假设案件均发生在交叉路口。由此, 即可将路段管理转化为对路口的管辖。当突发事件发生时, 警车立即出动至所管 辖的案
8、发点。 (2)交巡警服务平台布置的合理性: 该问题主要考虑的是交巡警服务平台的工作量均衡问题,由于A 区不同地 域节点的密度不同, 而且发案率也不相同, 所以工作量可以表示为li与的乘积, 即 ii Al。对每个交巡警服务点所管辖的范围以交点为单位,按照工作量均 衡的原则去逐个改变交点所属的辖区,最终使各个交巡警平台的工作量达到最优 均衡状态。 五、问题一的解决 问题 1.1 由于两节点间的距离公式为: 22 ()() ijij dxxyy, 借助 C语言程序(见 附录 1) ,可得到各交巡警服务平台(共20 个,编号 1-20)到各节点(共 72 个, 编号 21-92)的距离小于 3km的
9、各节点编号,得到下表 交 巡 警 服 务 平台编号 可管辖的节点编号 1 42 43 44 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 2 40 41 42 43 44 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 3 38 39 40 43 44 54 55 63 64 65 66 67 68 69 70 75 76 4 54 55 56 57 58 60 62 63 64 65 66 67 68 75 76 77 5 30 32 33 46 47 48 49 50
10、51 52 53 56 57 58 59 61 6 30 32 47 48 49 50 51 52 53 56 57 58 59 61 7 30 31 32 33 34 35 46 47 48 49 8 30 31 32 33 34 35 36 37 45 46 47 48 49 52 53 56 9 31 32 33 34 35 36 37 45 46 10 无 11 21 25 26 27 28 12 24 25 28 13 21 22 23 24 14 26 15 31 16 32 33 34 35 36 37 45 46 17 40 41 42 43 44 67 68 69 70 71
11、 72 73 74 78 18 42 68 69 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 19 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 20 80 81 82 83 84 85 86 87 88 89 90 91 表 1 对于表 1,有以下四种特殊情况: 1. 同一个节点被分到不同的交巡警服务平台管辖范围之内; 2. 有些节点没有被交巡警服务平台所管辖; 3. 有些
12、交巡警服务平台没有管理任何节点; 4. 有些距离交巡警服务平台3km以内的节点实际路程大于3km 。 对于 1,在处理时,先按照每个交巡警服务平台所管辖的节点的多少将其进 行升序排列, 优先处理管辖的节点较少的平台,每处理完一个平台之后, 删除后 面平台所管辖的与之重复的节点, 然后重新按照每个平台所管辖的交点的多少将 其进行升序排列,重复进行判断和删减,直到所有重复的点都被删除。 对于 2,将没有被交巡警服务平台所管辖的节点划到离其最近的交巡警服务 平台的管辖范围内。 对于 3,暂不考虑,在问题1 的第三小问中解决。 对于 4,在解决 1 之前,结合附录1 中的图 1,将距离某个交巡警服务平
13、台 实际路程大于 3km的节点在表 1 中将其编号删除。 根据上述方法把表1 处理后,得到表 2,其中 28,29,38,39,61,92没有任何 交巡警服务平台可以在规定的半径内管辖它们,所以将这六个点划归到离它们最 近的交巡警服务平台管辖。 交巡警服务平台编号可管辖的节点编号 1 无 2 38 69 71 73 74 75 78 3 28 29 44 54 55 67 68 76 4 57 58 60 62 63 64 65 66 5 49 53 6 47 48 50 51 52 56 59 7 30 32 8 无 9 无 10 无 11 26 27 12 25 61 13 21 22 2
14、3 24 14 39 15 31 16 34 35 36 37 45 46 17 77 79 80 18 无 19 无 20 81 82 83 84 85 86 87 88 89 90 91 92 表二 这样分配管辖范围都可以使每个交巡警服务平台的警车在有事故时能够尽 快到达事发地点。 但忽略了每个服务站工作负担的因素,导致某些工作站工作压 力过大,而且有的交巡警服务平台没有工作机会,这个问题将会在第三小问中解 决。 问题 1.2 抽象为一个 20 对 13 的匹配问题来求解, 其中对于每个交巡警服务平台是否 参与道路的封锁用户0-1 变量 match 来标记(若第i 个交巡警服务平台负责第j
15、 个出口处的堵截,则match(i,j)=1,反之则为 0) 。要求各节点警力到达封锁路口 所花费的时间应尽可能短。当封锁路口时,需要全部13 个路口全部封锁才能达 到目的。警车到达节点所花费的时间应该以最后一个到达对应的节点的警车所需 要的时间来决定。 借助 MATLAB 程序(见附录 2)来解决此问题,由上文可得目标函数为: 1 maxcost( , )( , ) n i j i jmatch i j 约束条件为: 1. 每一个服务站最多出动去一个路口(i,j 的组合唯一); 2. 每个通往其他区的路口都要有相应的服务站的警车去封锁; 3. 各节点警力到达封锁路口所花费的时间应尽可能短。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2011 高教 全国大学生 数学 建模 竞赛 论文 要点
链接地址:https://www.31doc.com/p-5193827.html