2011高教社杯全国大学生数学建模竞赛B题省一等奖.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： B甲00226 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：12交巡警服务平台的设置与调度摘要对于给各个交巡警服务平台分配管辖范围的问题，首先运用Dijkstra算法求出A区交通网络中的任一路口节点到其他路口节点的最短路经值，再从道路的两个节点出发，选出具离它最近的交巡警服务平台，那么此道路就由所选的服务平台来管辖，这样可以依次选出各条道路所对应的交巡警服务平台，那么各交巡警服务平台相对应的管辖范围就能划分出来。对于调度20各服务平台来封锁13条交通要道，也即13个路口节点的情况，假设每个路口节点只需一个服务平台的警力资源来封锁，建立一个有路程约束的最佳调度方案，得出进出城区的标号为12、14、16、21、22、23、24、28、29、30、38、48、62的路口节点分别由标号为12、9、16、14、10、13、11、15、7、8、2、5、4的交巡警服务平台的警力资源来封锁。对于在A区增设交巡警服务平台的情况，首先定义和路径有关的出警时间、和发案率及道路长度有关的工作量，进而根据出警时间和工作量来决定增设平台的具体个数和位置。得出需要在标号为30、53、90、74的路口节点各增设一个平台。对于分析研究该市全市交巡警服务平台设置方案合理性的问题，建立一个包含发案率、交通流量及人流量的评价指标值，根据各个指标的权重，运用综合评价的方法来评价服务平台设置是否合理。得到该市现有交巡警服务平台设置不合理。在一地点发生案件，犯罪嫌疑人由事发点驾车逃跑，设计一个调度全市交巡警服务平台警力资源的围堵方案，在警力资源一定的情况下，要尽量使此次行动所花时间短，同时能够尽量保证围堵成功。建立一个由事发点向外放射的放射性网状图，确定一番逃跑的所有路径，进行分析，得到一系列围堵点为：378，372，321，320，173，16，168，169，12，14，16，21，22，24，28，29，30，48，62。一 问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众的职能。市区的一些交通要道和重要部位都设有交巡警服务平台。而合理的设置交巡警服务平台、分配各平台的管辖范围及调度警务资源是警务部门面临的问题。现给出以下问题：（1）某市中心城区A区的交通网络和现有的20个交巡警服务平台的设置情况示意图已知，要求为各平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车时速为60km/h）到达事发地。已知一个平台的警力最多封锁一个路口，有重大突发事件时，需调度20个服务平台的警力资源来封锁进出城区的13条交通要道，要求给出合理的调度方案。现有交巡警服务平台的工作量不均衡和有些地方出警时间过长，所以拟在该区增加2到5个平台，确定增加平台的具体位置和个数。（2）按照设置交巡警服务平台的原则和任务，分析研究该市全市交巡警服务平台设置方案的合理性，如有不合理，给出解决方案。如果该市地点P发生了重大刑事案件，案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二 模型假设1. 由于事发地点可能发生在道路的任何一点，为简化起见，我们假设事发点聚集为道路中点。2. 假设应急警力到达事发点的车辆行驶速度恒定，与道路上的交通状况无关，即对于因交通事件引起的周围道路拥堵，因应急车辆选择应急车道而不影响应急警力到达事件现场的俗的。3. 一条道路只能归一个交巡警平台所管辖，而不存在两个或多个交巡警平台共同管理一条道路的情况。4. 假定各个划分区域在较短时间内最多发生一个案件，且警察接到报警后立刻出警，忽略其反应时间。三 问题分析3.1 问题分析此问题要求为各交巡警服务平台设置管辖范围，同时必须要考虑的因素是某一范围内交巡警服务平台到案发地点的总路线尽可能短。假设某条道路的任意一点案发概率相等，将道路从两边节点向中间无限缩短成一点，看为在道路的中点，由事发地点来选择距其最短的交巡警服务平台，也即由事发地点所属道路的两个节点来选择交巡警服务平台，根据节点到交巡警服务平台所用时间尽量在3分钟以内，即它们之间的距离尽量在3000米以内，且尽量短，那么事发地点所属的整条道路都由所选的平台来管理。我们可以根据以上分析来分配各服务平台的管辖范围。对于有重大突发事件封锁13条交通要到的情况来说，需要封锁的是进出城区的13各路口节点。我们假设只出动13个服务平台来封锁道路，所以每个路口节点有一个服务平台的警力资源，可以将它看作一个最优化问题，建立一个有时间约束，也即路程约束的最佳调度方案，即从20个服务平台选出13个使各平台到其所要到达的路口节点的路程之和最小。 对于增加交巡警服务平台的情况，需要从现有各平台的出警时间和工作量入手，对于出警时间我们定义为各个服务平台到其所管辖区域内各道路的时间；而对于工作量我们将其定义为一个和发案率及道路长度有关的量，再由工作量定义一个工作量均衡度，工作量均衡度愈小，交巡警服务平台的设置情况愈好。则可以通过对出警时间、工作量及工作量均衡度的分析来确定增加平台的具体位置和个数。3.2 问题分析对于分析研究全市交巡警服务平台的设置方案的合理性问题，我们可以建立一个包含发案率、交通流量、人流量的评价指标体系，并分别给其赋权重，再运用综合评价的方法来评价的方法来评价其合理性。四 符号说明：A区标号为的路口节点：A区标号为的交巡警服务平台：相连通的两节点、之间的距离：标号为的交巡警服务平台到标号为的路口节点的最短路径值：标号为的警务平台到标号为的路口节点的出警时间：由标号为、的两个路口节点构成的道路上的工作量：标号为的路口节点的发案率：与标号为、的路口节点相关联的所有道路的路径总和：表号为的服务平台的工作量：工作量均衡度五 模型建立及求解5.1.1.1模型建立首先知道A区共有92个路口节点，根据附表所给路口节点的横纵坐标，可以在图中标出各路口节点的标号和平台的标号。设为标号为的路口节点，、为其所处位置的横、纵坐标；为标号为的路口节点，、同样为它所处位置的横、纵坐标；为A区的各交巡警服务平台。若标号为的节点和标号为的节点相连通，则这两点之间的距离可表示为，即=若标号为的节点和标号为的节点不连通，先将其之间的距离定义为=。然后运用Dijkstra算法求出交通网络中任何一路口节点到其它节点的最短路径：设A区中所有的路口节点组成一个集合，称为节点集，记为；而点与点的连线集合称为边集，记为；由集合和集合所组成的集合对称为图，也即A区的交通网络图，用来表示。把交通网络中任何一个节点看作一个顶点，记为，设为具有永久标号的顶点集，对每个顶点定义两个标记，其中：表示从顶点到的一条路的权，即路径长度；表示的父亲点，用以确定最短路的路线。现在要求出从顶点到其余节点的最短路，算法的过程就是在每一步改进以上两个标记，使最终为从顶点到的最短路的权，输入为带权邻接矩阵。具体算法如下：（1）赋初值：令，令=，将更新，。（2）更新、：，若,则令=（3）设是使取最小值的中的顶点，则令。（4）若，转（2）；否则，停止。这时用上述算法求出的就是到的最短路的权，从的父亲标记追溯到就得到到的最短路的路线。又由于每条道路有两个路口节点，所以对于每条道路我们可以得到两个路口节点分别到20个平台的距离，可以将它表示为一个9220的矩阵，那么可以分别选出距离两个节点路径最短的平台，分别记为、 ，使得、km/min3min=3km,再将所选出的两种路径进行比较，取两者之中较小的一个，记为，则=那么此条道路由所选路径对应的平台负责管辖。5.1.1.2模型求解根据上述模型，运用MATLAB编程，可以得到各个路口节点到各交巡警服务平台的最短路径，由此可以得出各路口节点到各交巡警服务平台的最短时间,也就是各路口节点到各交巡警服务平台的最短路经值。以此来划分各交巡警服务平台的管辖范围，具体划分情况如下：图1 A区各平台的管辖范围划分图5.1.2.1 模型建立对于有重大突发事件时，封锁13条交通要道也就是封锁各交通要道所对应的13个路口节点，我们假设每个路口节点只调动一个服务平台的警力资源来封锁，这就要求从20个服务平台中来选择13个平台进行调度，合理的调度服务平台就要求所选的13个平台中任何一个平台到达其所要到达的节点的时间尽可能短，那么13个服务平台到达13个路口节点的时间总和最短，也即路程总和最短，这就需要建立一个有时间约束，也就是路程约束的调度方案。我们知道A区的20个平台为，出入A区的13条要道所对应的节点为，为了方便表述，将各节点重新定义为。和一一对应。运用01规划，建立优化模型，对任何一个平台来说，都存在两种情况，即被调度或不被调度。设，当=0时表示第个服务平台不被调度到第个路口节点；=1表示第个服务平台被调度到第个路口节点。为各平台到各路口节点的最短路径值。于是我们建立的模型为：s.t. 表示被调度的13个平台到其对应的路口节点的路径总和的最小值。5.1.2.2 模型求解对于上述优化模型,我们运用LINGO11进行编程,选择出距离各交通要道总路径之和最小的服务平台进行调度,所得的有时间约束，也即路程约束的调度方案如下表：表1 交巡警服务平台的调度方案路口节点12141621222324282930384862调度平台12916141013111578254最短路径值082740326577085003805475280153061398324763515.1.3.1 模型建立对于此问题，我们假设增加的平台只能位于路口节点处，而增加平台的具体位置和个数由交巡警服务平台的工作量和出警时间的长短来确定，所以我们需要求出各服务平台的出警时间和工作量。首先我们不考虑警察接到报案后的准备时间，将交巡警服务平台的出警时间定义为各服务平台沿最短路径到其所管辖范围内的各道路较远节点所用的时间，记为，最短路径值为，我们知道警车的速度恒定不变，为=60km/h=1km/min,则出警时间为：=而由问题一的结果我们可知，所有平台的出警时间基本都在3分钟以内，符合要求的出警时间，所以我们将只由工作量来确定增加平台的位置和个数。而对于工作量的定义，我们将其和发案次数及路长联系起来，若路口节点、相连通构成一条道路，这条道路上的工作量可定义为，节点、上的发案次数记为、，和节点相关联的所有道路其路径值总和记为，和节点相关联的所有道路其路径总和记为则由节点、构成道路上的工作量为对于交巡警服务平台来说，假设其管辖区域内有条道路，则此服务平台的工作量即为其管辖的所有道路的工作量总和，设为，则我们建立的各服务平台的工作量模型为：由上述模型可以求得各个交巡警服务平台的工作量，所以A区的所有交巡警服务平台的总工作量即为各交巡警服务平台的工作量之和，记为，则-而要衡量A区各个服务平台的工作量是否均衡，则需引入工作量均衡度的概念，工作量均衡即要求各个平台的工作量尽可能接近，由此定义工作量均衡度我们知道，均衡度越小，交巡警服务平台的设置情况越好。我们先选出工作量最大的平台，其工作量为，然后在其所管辖的区域内增设一个平台，再次计算工作量均衡度，这样一直循坏到增设完5个服务平台为止，所以我们可得到6个工作量均衡度，从中选出工作量均衡度最小的一个，此时其所对应的增设平台个数即为我们最后的增设平台方案。5.1.3.2 模型求解对于此问题的求解过程，我们可以运用MATLAB编程，得到没有增加交巡警服务平台时的工作量均衡度和分别增加1到5个服务平台的工作量均衡度，结果如下表：表2 平台增设和其对应的工作量均衡度关系表平台设置没有增加平台53节点增设平台30、53节点分别增设1个平台30、53、90节点分别增设1个平台30、53、90、74节点分别增设1个平台30、53、90、74、57节点分别增设1个平台工作量均衡度0.30.260.220.180.120.15 根据上表可以看出，当工作量均衡度最小时，共增设了4个交巡警服务平台，分别在标号为30、53、90、74的路口节点处。所以对于由工作量不均衡和出警时间过长而增设交巡警服务平台的情况来说，需要增加平台的具体个数为4个，位置分别位于标号为30、53、90、74的路口节点处。5.2.1.1 模型建立我们要根据设置交巡警服务平台的原则和任务，以及附录中给出的数据，判定该市现有交巡警服务平台设置方案是否合理。也就是对现有的服务平台设置方案进行评价。首先我们假设在全市的警力资源一定。由于每个交巡警服务平台的职能和警力配备基本相同，全市的警力资源一定则可表示为全市的交巡警平台个数一定。我们对该设置方案的评价原则是根据管区道路交通流量、拥堵状况、治安复杂情况、人流量、发案率高低，科学确定方案，并且出巡时间要尽量短。根据实际情况，我们对服务平台的设置方案进行评价，可以定义一组评价因子即发案量、交通流量、人流量。设任何一个区域的任一节点其发案率为，我们将各区域内的发案率定义为，它为各节点发案率的加和，则。再计算出每个区内的道路总长。而每个区域内的总人数已知，为，则将交通流量定义为公路上单位长度的人数，设为，。而各区域内的面积已知，记为，则可将各区域的人流量定义为，则。根据问题一中的模型，利用附件二所提供的数据，我们可以求出整个市区所有平台的工作量，并能评价出该设置是否合理，但考虑到计算量过大，为简化起见，我们分区进行考虑。为了对该设置方案进行评价，我们假设三个评价指标： 发案率，人流量，交通流量。然后将这三个指标分别进行归一化：发案率指标的归一化： 交通流量的归一化：人流量的归一化：然后对三个指标赋权分别为，由于交巡警服务平台的设置最先考虑的因素是发案率，其次为交通流量和人流量，所以将权重分别赋为，计算可得到六个区的评价结果为，则=对于评价结果定义其均衡度为：。5.2.1.2 模型求解表3区域发案率人口/道路总长人口/面积A124.50.1577548746910.909090909B66.51.69077497070.81553398058C187.2188687782805D67.84.08828912380.76240208877E119.41.92010154310.7037037037F109.21.04065893740.77372262774设=0.5，得到=0.2439051=0.1108336,=0.18461037,=0.182779,=0.1553941,0.12247735.2.2.1 模型建立在点出发生了重大刑事案件，在案发后3分钟后接到报警，犯罪嫌疑人驾车已逃跑，也就是说，犯罪嫌疑人从点出发3分钟后，交巡警服务平台开始行动，直到到达所负责封锁的路口。假设犯罪嫌疑人在出逃过程中驾车行驶的速度为一个定量设为，由于犯罪嫌疑人出逃时能选择的路径可任意，也就是选择的路径方式过多，而区内的警力有限，如果由其他区域向区调动警力进行围堵则不切实际，耽误的时间太长，因此，我们不过多考虑从区内部进行围堵。犯罪嫌疑人在出逃后逃出区，只能从进出的13个路口中选择一个，我们将区的大部分警力调去封锁进出A区的13个路口。犯罪嫌疑人出逃到达出入区的路口使得所用的时间最短，则必须选择最短路径。那么交巡警平台必须在出巡后壁犯罪嫌疑人要先到达所负责封锁的路口，才能确保能围堵犯罪嫌疑人。即犯罪嫌疑人出逃到达封锁路口的时间警察出巡到到封锁路口的时间。该市的交通网络图如下：图2 该市全市交通网络图犯罪嫌疑人从始发点点选择最短路径进出区的路口，而交巡警平台则采用问题一中的调度方案，由于这个调度方案不是特别合理，犯罪嫌疑人选择的路径等都不一定，犯罪嫌疑人有可能逃出区，则在逃出区后，从这13个节点向外做放射性网状图。例如犯罪嫌疑人从点的部分逃跑路线：5.2.2.2 模型求解通过查阅资料可得，在高速公路上行驶，汽车的最高行驶速度为120，则设犯罪嫌疑人的行车速度，根据问题一种的模型求解，起始点到13个路口节点的最短距离为：通过计算可求出从点到13个路口的时间，同样可计算得到从交巡警服务平台到各自负责的路口节点的时间，可以得出：犯罪嫌疑人出逃时选择的路口节点为，根据附录，能够求出每两个相邻点之间的的距离。能够确定一个最终围堵方案：先调动13个交巡警平台对犯罪嫌疑人进行围堵，为，为确保能专注犯罪嫌疑人，将出入市区的17个节点都围堵上。然后利用市中的平台在内部对其进行围捕，用到 六 模型评价6.1.1对于给各交巡警服务平台划分管辖范围的问题，我们建模的依据是每个节点到其所属平台的路径是它到所有平台路径中最小的，对各交巡警服务平台来说，在警车时速一定的情况下，基本都能在3分钟以内到达其管辖范围的各个路口节点，也基本能到达其管辖道路的任何一点。所以我们给各个平台划分的管辖范围是非常精确的。6.1.2对于交巡警服务平台的警力调度问题，我们的假设是一个服务平台可以封锁一个路口节点，而没有考虑到节点人口密集度、交通状况等对封锁路口的影响，所以我们的模型存在一定的局限性。调度全区个交巡警服务平台的警力资源对条交通要道进行快速全封锁，没有考虑所要封锁交通要道的人口密集程度及道路情况，如果有此情况所要安排的警力应该大于，可根据实际情况进行优化。例如：考虑个节点需要个警力资源，运用LINGO11编程得到如下表：表4 交巡警服务平台的调度方案路口节点12141621222324282930384862调度平台12916141013111587254,3最短路径值082740326577085003805475210490583398324763,514,3936.1.3按照设置交警服务平台的原则和任务，评价该市现有交巡警服务平台设置方案时，工作量模型是根据每个节点所对应道路的长度和两个端点的发案率建立的，考虑的比较好。但是模型建立时只是先取工作量最多的服务平台，对其所管辖的区域进行插点，不能得到最好的方案。应该将区个节点进行逐步插入平台点，再运用第一问的方法求出在最佳分配方案时，各个服务平台所管辖的范围及其工作量，计算出工作量均衡度，直到插入五个点，将五个均衡度进行比较，均衡度较小的即为最佳分配方案。6.2.1分析该市交巡警服务平台设置的合理性，我们运用综合方评价法，其中需要对各项指标进行赋权，赋权具有很大的主观性，并且我们考虑各区的发案率是节点发案率，所以所以我们的模型存在一定的不合理度。6.2.2对于调度全市警力围堵罪犯嫌疑人的设置方案，我们做出一个向外放射的网状图，能够考虑罪犯嫌疑人的所有逃跑路径，但由于全市的交通道路密集，没有考虑所有节点之间的最短路径，因此，调度方案可能不是最佳。附录11.1题中求最短路问题程序:w=0 inf inf inf inf inf inf inf inf inf inf inf inf . inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 2137.8 inf inf inf 2002.5 0; /90*92阶矩阵/n=size(w,1);w1=w(1,:);for i=1:n q(i)=w1(i); z(i)=1;ends=;s(1)=1;u=s(1);k=1;q;z;while kq(u)+w(u,i) q(i)=q(u)+w(u,i); z(i)=u; end end end end q; z;qq=q;for i=1:n for j=1:k if i=s(j) qq(i)=qq(i); else qq(i)=inf; end endendlv=inf;for i=1:n if qq(i)lv lv=qq(i); v=i; endendlv;v;s(k+1)=v;k=k+1;u=s(k);endq 21.2题中交警服务平台警力合理分配方案的程序：model:sets:a/1.20/;b/1.13/;c(a,b):D,m;ENDSETSdata:D=222.36 160.28 92.87 192.93 210.96 225.02 228.93 190.01 195.16 120.83 58.81 118.50 48.85 204.64 141.30 73.88 173.95 191.97 206.03 211.21 172.29 177.44 103.11 39.82 103.10 60.35 .183.52 127.67 60.26 160.32 132.15 151.00 113.08 121.75 47.43 34.06 54.50 86.17 218.92 149.03 81.62 181.68 199.71 213.77 225.49 186.57 195.24 120.92 47.56 127.99 78.21 242.47 185.14 117.73 217.79 235.82 249.88 249.04 210.12 215.27 140.94 83.6