《高教社杯全国大学生数学建模竞赛B题一等奖》由会员分享，可在线阅读，更多相关《高教社杯全国大学生数学建模竞赛B题一等奖（17页珍藏版）》请在金锄头文库上搜索。
1、高教社杯全国大学生数学建模竞赛B题省一等奖 作者： 日期：2 2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/
2、C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： B甲00226 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：12交巡警服务平台的设置与调度摘要对于给各个交巡警服务平台分配
3、管辖范围的问题，首先运用Dijkstra算法求出A区交通网络中的任一路口节点到其他路口节点的最短路经值，再从道路的两个节点出发，选出具离它最近的交巡警服务平台，那么此道路就由所选的服务平台来管辖，这样可以依次选出各条道路所对应的交巡警服务平台，那么各交巡警服务平台相对应的管辖范围就能划分出来。对于调度20各服务平台来封锁13条交通要道，也即13个路口节点的情况，假设每个路口节点只需一个服务平台的警力资源来封锁，建立一个有路程约束的最佳调度方案，得出进出城区的标号为12、14、16、21、22、23、24、28、29、30、38、48、62的路口节点分别由标号为12、9、16、14、10、13、
4、11、15、7、8、2、5、4的交巡警服务平台的警力资源来封锁。对于在A区增设交巡警服务平台的情况，首先定义和路径有关的出警时间、和发案率及道路长度有关的工作量，进而根据出警时间和工作量来决定增设平台的具体个数和位置。得出需要在标号为30、53、90、74的路口节点各增设一个平台。对于分析研究该市全市交巡警服务平台设置方案合理性的问题，建立一个包含发案率、交通流量及人流量的评价指标值，根据各个指标的权重，运用综合评价的方法来评价服务平台设置是否合理。得到该市现有交巡警服务平台设置不合理。在一地点发生案件，犯罪嫌疑人由事发点驾车逃跑，设计一个调度全市交巡警服务平台警力资源的围堵方案，在警力资源一
5、定的情况下，要尽量使此次行动所花时间短，同时能够尽量保证围堵成功。建立一个由事发点向外放射的放射性网状图，确定一番逃跑的所有路径，进行分析，得到一系列围堵点为：378，372，321，320，173，16，168，169，12，14，16，21，22，24，28，29，30，48，62。一 问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众的职能。市区的一些交通要道和重要部位都设有交巡警服务平台。而合理的设置交巡警服务平台、分配各平台的管辖范围及调度警务资源是警务部门面临的问题。现给出以下问题：（1）某市中心城区A区的交通网络和现有的20个交巡警服务平台的设置情况示意图已知，要求为各平台
6、分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车时速为60km/h）到达事发地。已知一个平台的警力最多封锁一个路口，有重大突发事件时，需调度20个服务平台的警力资源来封锁进出城区的13条交通要道，要求给出合理的调度方案。现有交巡警服务平台的工作量不均衡和有些地方出警时间过长，所以拟在该区增加2到5个平台，确定增加平台的具体位置和个数。（2）按照设置交巡警服务平台的原则和任务，分析研究该市全市交巡警服务平台设置方案的合理性，如有不合理，给出解决方案。如果该市地点P发生了重大刑事案件，案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警
7、服务平台警力资源的最佳围堵方案。二 模型假设1. 由于事发地点可能发生在道路的任何一点，为简化起见，我们假设事发点聚集为道路中点。2. 假设应急警力到达事发点的车辆行驶速度恒定，与道路上的交通状况无关，即对于因交通事件引起的周围道路拥堵，因应急车辆选择应急车道而不影响应急警力到达事件现场的俗的。3. 一条道路只能归一个交巡警平台所管辖，而不存在两个或多个交巡警平台共同管理一条道路的情况。4. 假定各个划分区域在较短时间内最多发生一个案件，且警察接到报警后立刻出警，忽略其反应时间。三 问题分析3.1 问题分析此问题要求为各交巡警服务平台设置管辖范围，同时必须要考虑的因素是某一范围内交巡警服务平台
8、到案发地点的总路线尽可能短。假设某条道路的任意一点案发概率相等，将道路从两边节点向中间无限缩短成一点，看为在道路的中点，由事发地点来选择距其最短的交巡警服务平台，也即由事发地点所属道路的两个节点来选择交巡警服务平台，根据节点到交巡警服务平台所用时间尽量在3分钟以内，即它们之间的距离尽量在3000米以内，且尽量短，那么事发地点所属的整条道路都由所选的平台来管理。我们可以根据以上分析来分配各服务平台的管辖范围。对于有重大突发事件封锁13条交通要到的情况来说，需要封锁的是进出城区的13各路口节点。我们假设只出动13个服务平台来封锁道路，所以每个路口节点有一个服务平台的警力资源，可以将它看作一个最优化
9、问题，建立一个有时间约束，也即路程约束的最佳调度方案，即从20个服务平台选出13个使各平台到其所要到达的路口节点的路程之和最小。 对于增加交巡警服务平台的情况，需要从现有各平台的出警时间和工作量入手，对于出警时间我们定义为各个服务平台到其所管辖区域内各道路的时间；而对于工作量我们将其定义为一个和发案率及道路长度有关的量，再由工作量定义一个工作量均衡度，工作量均衡度愈小，交巡警服务平台的设置情况愈好。则可以通过对出警时间、工作量及工作量均衡度的分析来确定增加平台的具体位置和个数。3.2 问题分析对于分析研究全市交巡警服务平台的设置方案的合理性问题，我们可以建立一个包含发案率、交通流量、人流量的评
10、价指标体系，并分别给其赋权重，再运用综合评价的方法来评价的方法来评价其合理性。四 符号说明：A区标号为的路口节点：A区标号为的交巡警服务平台：相连通的两节点、之间的距离：标号为的交巡警服务平台到标号为的路口节点的最短路径值：标号为的警务平台到标号为的路口节点的出警时间：由标号为、的两个路口节点构成的道路上的工作量：标号为的路口节点的发案率：与标号为、的路口节点相关联的所有道路的路径总和：表号为的服务平台的工作量：工作量均衡度五 模型建立及求解5.1.1.1模型建立首先知道A区共有92个路口节点，根据附表所给路口节点的横纵坐标，可以在图中标出各路口节点的标号和平台的标号。设为标号为的路口节点，、
11、为其所处位置的横、纵坐标；为标号为的路口节点，、同样为它所处位置的横、纵坐标；为A区的各交巡警服务平台。若标号为的节点和标号为的节点相连通，则这两点之间的距离可表示为，即=若标号为的节点和标号为的节点不连通，先将其之间的距离定义为=。然后运用Dijkstra算法求出交通网络中任何一路口节点到其它节点的最短路径：设A区中所有的路口节点组成一个集合，称为节点集，记为；而点与点的连线集合称为边集，记为；由集合和集合所组成的集合对称为图，也即A区的交通网络图，用来表示。把交通网络中任何一个节点看作一个顶点，记为，设为具有永久标号的顶点集，对每个顶点定义两个标记，其中：表示从顶点到的一条路的权，即路径长
12、度；表示的父亲点，用以确定最短路的路线。现在要求出从顶点到其余节点的最短路，算法的过程就是在每一步改进以上两个标记，使最终为从顶点到的最短路的权，输入为带权邻接矩阵。具体算法如下：（1）赋初值：令，令=，将更新，。（2）更新、：，若,则令=（3）设是使取最小值的中的顶点，则令。（4）若，转（2）；否则，停止。这时用上述算法求出的就是到的最短路的权，从的父亲标记追溯到就得到到的最短路的路线。又由于每条道路有两个路口节点，所以对于每条道路我们可以得到两个路口节点分别到20个平台的距离，可以将它表示为一个9220的矩阵，那么可以分别选出距离两个节点路径最短的平台，分别记为、 ，使得、km/min3m
13、in=3km,再将所选出的两种路径进行比较，取两者之中较小的一个，记为，则=那么此条道路由所选路径对应的平台负责管辖。5.1.1.2模型求解根据上述模型，运用MATLAB编程，可以得到各个路口节点到各交巡警服务平台的最短路径，由此可以得出各路口节点到各交巡警服务平台的最短时间,也就是各路口节点到各交巡警服务平台的最短路经值。以此来划分各交巡警服务平台的管辖范围，具体划分情况如下：图1 A区各平台的管辖范围划分图5.1.2.1 模型建立对于有重大突发事件时，封锁13条交通要道也就是封锁各交通要道所对应的13个路口节点，我们假设每个路口节点只调动一个服务平台的警力资源来封锁，这就要求从20个服务平台中来选择13个平台进行调度，合理的调度服务平台就要求所选的13个平台中任何一个平台到达其所要到达的节点的时间尽可能短，那么13个服务平台到达13个路口节点的时间总和最短，也即路程总和最短，这就需要建立一个有时间约束，也就是路程约束的调度方案。我们知道A区的20个平台为，出入A区的13条要道所
