2011全国数学数学建模竞赛B题
- 格式：doc
- 大小：1.03 MB
- 文档页数：31
承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期： 2011年9月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度一摘要本文主要讨论某市的交巡警服务平台的合理设置与调度问题。
首先，参照主城区A的交巡警服务平台设置情况，利用图论中的Dijkstra算法计算交巡警服务平台到各路口节点的最短路程，再以尽量多的路口节点能有交巡警在3分钟内赶到为首要目标，各交巡警平台每天的处理案件次数相差尽量小为次要目标，建立一个规划模型，利用遗传算法，解出了具体的辖区划分方案。
并且考虑到某路口所在辖区的服务平台由于其他突发事件不能立即处理该路口的情况时，给出了备用方案。
其次，对于重大突发事件发生时全区交巡警服务平台封锁道路的警力资源调度问题，我们建立一个以交巡警服务平台是否封锁进出该城区交通要道为决策变量，负责封锁的交巡警服务平台到达指定地点所需时间中的最长时间最小为第一目标，所有负责封锁道路的交巡警到达各指定地点的时间总和最小为第二目标的多层规划模型，运用lingo编程求解，发现调用第2,4,5,7,8,9,10,11,12,13, 14,15,16个交巡警平台进行封锁工作，在经过8.0155分钟后，完全封锁A城区。
再次，考虑到快速出警作为交巡警平台设置的首要原则，我们首先确保在A 城区所有路口的突发事件均必定能由所辖交巡警在3分钟内赶到处理，此时参照模型1的结论可以得出需要新建4个平台，且能够给出相应的取址范围。
再以各交巡警平台的工作任务尽量均衡为目标，建立一个规划模型，并用遗传算法解得新建的服务平台分别取址在第28,40,48,89个路口，得到重新划分的辖区范围。
然后，针对全市6区所有交巡警服务平台的具体情况，制定了平均出警时间指标及覆盖密度指标来评价现行方案的合理性。
第一，我们对每个平台的单件突发事件的出警时间期望进行聚类分析，认为编号为B8、C13、E8、E9、E11的交巡警平台出警时间过长，设置不合理，于是在编号为388、206、420、439、408的路口各增设一个交巡警平台，降低其出警时间期望；第二，对每个交巡警平台每天的处理案件数量进行聚类分析，认为编号为C6、C14、C15、E11、F1、F3、F4的平台处理案件数量过多，设置不合理，于是在编号为230、277、314、408、550、520、514的路口各增设一个平台，降低其工作量。
之后，将地点P发生重大刑事案件的犯罪嫌疑人驾车逃跑作为实例，首先经过计算得到一段时间后犯罪嫌疑人可能到达的路口集合，然后将与该集合所有路口相邻且不属于该集合的路口节点作为交巡警封锁路口，一旦交巡警到达封锁路口的时间小于罪犯的到达时间，则围堵成功。
利用计算机搜索确定了接到报警后最短经过6分钟，可以将犯罪嫌疑人成功围堵。
最后，模型改进与推广部分我们引进时间满意度作为标准，并将市民满意度与交巡警工作人员满意度加权综合，作为我们考察的最终标准。
关键词：dijkstra算法多层规划遗传算法聚类分析计算机搜索二问题重述警察是与市民日常生活息息相关的一个重要职业。
一些城市为了有效地贯彻实施警察刑事执法、治安管理、交通管理和服务群众的四大职能，在一些交通要道设置了交巡警服务平台，每个平台警力配备和职能配备基本相同。
这里给出某城市交巡警服务平台的具体位置，然后针对该城市中各个区域的实际情况与需求合理的分配各交巡警管辖范围、调度警务资源。
1.针对附录1中中心城区A的交巡警服务平台设置情况，合理划分每个服务平台的管辖区域，使得绝大多数突发情况发生时交巡警能在3分钟内赶到事发地点。
2.重大突发事件发生时一个平台的警力最多封锁一个路口，需要合理调度20个服务平台警力至进出城区A的13个交通枢纽点，实现快速封锁道路以搜捕嫌疑犯。
3.分析考虑现行方案下不同交巡警服务平台工作量不均衡和某些地方出警时间太长，考虑在该区内合适的地方增加2-5个服务平台。
4.考虑全市6个城区，参照交巡警的服务原则和任务，分析该市所有交巡警服务平台设置方案的合理性，并对不合理的地方提出改进。
5.以第32个节点P发生重大刑事案件，在案发后3分钟接到报警作为实例，调度全市交巡警警力资源快速搜捕嫌疑犯，确定最佳围堵方案。
三问题分析对于问题1，即合理的划分各交巡警服务平台的管辖范围。
首先需要算出各路口节点到每个交巡警服务平台的最小距离，然后建立一个规划模型即可解决管辖范围的划分问题。
对于问题2，即在最短时间内封锁进出A城区的交通要道。
由于一个服务平台的警力只能封锁一个路口，故容易发现此问题为20个服务平台到13个进出城区的交通路口的简单指派问题，运用0-1规划即可得到指派方案。
对于问题3，即在服务平台工作量集中和较大的地点增加平台。
我们首先考虑将所有路口的出警时间均限制在3分钟以内，然后考虑均衡化每个平台的工作量大小。
运用与第一问类似的方法确定新增平台的位置以及管辖区域即可。
对于问题4，分析全市交巡警服务平台的设置合理情况及改进。
适当建立指标，将少数与其他平台差别较大的平台最为设置不合理的平台，并给出改进方案即可。
对于问题5，在最短时间内围堵P点重大刑事案件且已逃窜的犯罪嫌疑人。
我们考虑在尽量短的时间内由交巡警封锁某些路口，使得犯罪嫌疑人的逃跑范围无法继续扩大，即成功完成围堵。
四模型假设及符号系统4.1模型假设1)每个交巡警服务平台的警力与设施配置基本相同2)每次案件的出警时间仅受路线长短影响3)交巡警平台工作量仅受其处理案件数量的影响4)已有的交巡警服务平台不撤销，且新增平台不考虑建设成本5)所有道路均为双向车道6)犯罪嫌疑人车速为60km/h7)附录中所有数据均真实有效4.2符号系统五模型建立及求解5.1模型1——交巡警辖区划分模型5.1.1模型1的准备首先制定两个划分辖区规则如下：规则①：如果某路口已经设置了交巡警服务平台，则该路口直接由此路口交巡警所管辖。
规则②：如果所有交巡警服务平台均不能在3分钟内到达某个路口，则由到达该路口所需时间最短的交巡警所管辖。
由于需要保证尽可能地在路口节点有突发事件发生时交巡警能够在3分钟内赶到事发地点，所以首先必须算出各个路口节点到20个交巡警服务平台的最短距离，在这里我们运用图论中的Dijkstra 算法对其进行计算，而相邻两点间的距离则用同一平面内的两点间直线距离公式对其进行计算。
5.1.2模型1的建立根据附图1并参考文献[1]，我们针对问题一第一小问建立如下模型：1)建立目标函数1最大化应急事件发生时所属辖区交巡警可在3分钟以内到达事发路口的路口数量m ax n其中921i i n y ==∑，1,30,3i i y i ⎧=⎨⎩路口发生突发事件时最近的交巡警能在分钟内到达路口发生突发事件时最近的交巡警不能在分钟内到达2)建立目标函数2在满足目标1的条件下，使得各个交巡警服务平台所辖路口数方差最小2021()min 20j j mm =-∑ 其中9292111,,,1,2...20 200,i i j i ij ij i p i j m p x x j m i j ==⎧=⋅===⎨⎩∑∑第个路口由第个交巡警服务平台管辖且第个路口不由第个交巡警服务平台管辖3)构造约束条件1，每个路口均有交巡警服务平台管辖2011,1,2...92ij j xi ===∑构造约束条件2，ij x 和i y 的0-1约束0,10,1ij j x y ==4)模型综述如下：目标函数1m ax n目标函数22021()min 20j j mm =-∑2011,1,2 (92)..0,10,1ij j iji x i s t x y =⎧==⎪⎪⎪⎨⎪=⎪⎪=⎩∑ 5.1.3模型1的求解遗传算法说明如下：第一步：建立fun 函数，输入路口编号i ，根据距离矩阵罗列与其距离小于3的所有交巡警平台编号，记其个数为n ，以1/n 的等可能性产生其中的一个交巡警平台编号。
第二步：生成初始群体。
第一代u=zeros(10,92)，根据规则保持u （1:10,1:20）不变，其余位置根据路口编号利用fun 函数随机生成交巡警平台编号。
第三步；定义适应度函数。
S=zeros(1,20)，若u （i ）=j ，（i 为路口编号，j 为归属管辖的交巡警平台编号），则s(j)=s(j)+pl(i)。
适应度函数y=1/var(s)。
pl(i)为第i 个路口发生案件的频数，最终s(j)表示第j 个交巡警平台受理的案件的频数。
第四步：选择。
利用轮盘赌选择基因型良好的子代u （i ），淘汰基因型不好的子代u(j)，得到u1。
第五步：交叉。
在子代u1的第i 条染色体的第21列到92列中随机产生一个位置a ，生成随机数r （i ），若r （i ）小于0.25，子代u1的i 条染色体与第i+1条染色体在位置a 进行基因经行对调。
得到u2。
第六步：变异。
在子代u2的第i 条染色体的第21列到92列中随机产生一个位置a ，生成随机数r （i ），若r （i ）小于0.01，子代u2的第i 条染色体的位置a 根据fun 重新函数随机生成一个交巡警平台编号。
得到子代u3。
第七步：令u=u3，重复第四步到第六步。
生成10000代子代。
第八步：计算每一代的适应度函数。
上述结果解得86n =，方差为2.8960，仅有编号为28、29、38、39、61、92的六个路口交巡警不能在3分钟内赶到事发地点，效果良好，故模型可以使用。
5.1.4. 模型1的完善由于考虑到实际情况中当某路口有突发事件发生时，所辖交巡警有可能在当时已经在其他路口进行突发事件的处理工作，产生不能及时处理的情况。
于是我们考虑在这种情况发生时给出一个备用方案，即另外一个(或几个)次优的交巡警服务平台对该案件进行处理，使得依然能在尽可能不超过3分钟的情况下交巡警完整的备用方案见附录。
