《110警车配置与巡逻方案》由会员分享，可在线阅读，更多相关《110警车配置与巡逻方案（42页珍藏版）》请在金锄头文库上搜索。
1、. . . .全国第六届研究生数学建模竞赛题 目 110警车配置及巡逻方案摘 要：针对110警车配置及巡逻方案问题，通过引入算法、贪心算法以及捕食者算法等相应知识，建立了警车优化配置的搜索模型，然后利用软件求解，得出满足相关要求的结论。首先将巡逻方案问题转化为图论中节点与边的覆盖问题，通过调整节点的覆盖率来调整道路的覆盖率，研究了在满足相关出警条件下，警车巡逻的道路覆盖率、巡逻方案的路线，以及提出了刻画巡逻效果显著程度的个指标：节点覆盖率、道路覆盖率、规定时间内单位车辆走过的不同节点数和规定时间内单位车辆走过的不同道路数，然后根据上述引入的相关算法，搜索出符合条件的结论，静态时最少需配置14辆
2、警车，而动态时需17辆警车，具体巡逻路线及相关评价指标值参见正文。最后考虑了影响巡逻效果的各种因素及情况，提出了警车巡逻的增援模型，并给出了求解的算法与策略。关键词：警车优化配置 贪心算法 捕食者算法 增援模型参赛密码 （由组委会填写） 参赛队号 1042610 .下载可编辑.队员姓名 仲伊 刘文杰 刘祥鹏 目录摘要一、问题重述3二、问题分析42.1问题一的分析：42.2问题二的分析42.3问题三的分析42.4问题四的分析42.5问题五的分析42.6问题六的分析.42.7问题七的分析.5三、问题假设5四、符号说明5五、模型建立与求解55.1问题一的模型建立与求解55.2问题二的解答95.3问题
3、三的模型建立与求解95.4问题四的模型建立与求解145.5问题五的模型建立与求解165.6问题六的模型建立与求解175.7问题七的解答19参考文献：22附录123附录224附录326附录429一问题重述110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126， 4266），（7434 ，1332）（见下图红点部位，蓝色部分为水域
4、，道路数据见附件,相邻两个交叉路口之间的道路近似认为是直线）。某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：D1. 警车在接警后三分钟内赶到现场的比例不低于90；而赶到重点部位的时间必须在两分钟之内。D2. 使巡逻效果更显著； D3. 警车巡逻规律应有一定的隐蔽性。请回答以下问题：一. 若要求满足D1,该区最少需要配置多少辆警车巡逻？二. 请给出评价巡逻效果显著程度的有关指标。三请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四. 在第三问的基
5、础上，再考虑D3条件，给出的警车巡逻方案及其评价指标值。五如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？ 六. 若警车接警后的平均行驶速度提高到50km/h，回答问题三。七. 你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。二.问题分析 整个问题是依据题目给定的城区地图的详细数据，在满足出警要求的相关要求的情况下，寻求所需要的最少警车数、每辆警车的巡逻路径以及评价指标值。2.1问题一的分析 问题一是在满足警车在接警后三分钟内赶到现场的比例不低于,而赶到重点部分的时间必须在两分钟之内的条件下，求该区最少需要配置的警车数。首先把城区地图抽象化为一个无向赋
6、权图，图中节点为交叉路口，边为城区街道，将警车巡逻问题转化为图论中图的节点、边等覆盖问题，利用算法处理相关数据。然后通过假定每条道路上案件发生的概率相同，将“警车在接警后三分钟内赶到现场的比例不低于”转化为图论中的数学约束条件，即警车接警后所能到达的道路条数占总道路条数的比例不低于，而“赶到重点部位的时间必须在两分钟之内”作为首先满足的条件，进而把研究道路条数的覆盖问题转化为研究交叉口节点的覆盖问题，利用节点覆盖率的调整来达到道路条数的覆盖范围不低于的要求。最后分析知在静态状态下，即定点巡逻时所需配置的警车数量最少，故通过引入贪心算法思想来求出所满足条件的最少警车数及其初始坐标位置。2.2 问
7、题二的分析问题二要求给出评价巡逻效果显著程度的指标，而警车巡逻的目的是起到震慑作用，降低犯罪率，增加市民的安全感，因此衡量巡逻效果显著程度的指标应围绕这个目的而定，故依据警车在接警后三分钟内赶到现场百分比的要求，选取巡逻方案的节点覆盖率、道路覆盖率、规定时间内单位车辆走过的不同节点数和规定时间内单位车辆走过的不同道路数等4个指标来刻画巡逻效果显著程度。2.3问题三的分析基于问题一和问题二的分析，欲求在满足条件且尽量满足情况下的警车巡逻方案，在引入贪心算法思想的基础上，依据题目特点，再引入捕食者算法，即运用贪心算法找到初始点(满意解)，然后运用捕食搜索迭代运算实现警车移动，达到动态分组的目的，进
8、而求出满足问题所设条件下的警车的巡逻方案及其评价指标值。2.4问题四的分析问题四是在问题三的基础上，考虑巡逻的隐蔽性问题，因本文采用的贪心算法和捕食者算法本身在搜索时具有极强的随机性，而警车均配有卫星定位系统和先进的通讯设备，故警车在选路时可有很强的动态随机性，每一辆警车在相应的时间间隔后有多种不同巡逻道路选择。所以警车巡逻时的隐蔽性的问题会同时得到很好的改善。2.5问题五的分析 在问题三分析的基础上，将巡逻车辆减少至10辆，在尽量满足和条件下，同样利用贪心算法和捕食者算法来求得相关的结论。2.6问题六的分析 基于问题三的分析，将接警后的速度提升为，按照问题三的分析求解过程求得警车的巡逻方案及
9、其评价指标值。2.7问题七的分析 在原问题的基础上，适当排除理想的假定，考虑现实生活中影响巡逻效率的相关因素和情况，从众多因素的解决方案中归纳出增援问题模型，并加以详细讨论。三.问题假设1.假设道路全是双行道；2.假定所有事发现场均在原图的道路上；3.假定警车在某个连续4个小时内巡逻过程中不休息；4.假定在各个警车初始位置设定在各交叉路口;5.假定警车在巡逻过程中不发生汽车故障；6.假定警车在巡逻过程中不受道路阻塞的限制；7.假定警车处理完案件后回到原巡逻路线；8.假定警车在巡逻过程变速行驶，但保持平均速度。四.符号说明表示第个评价指标值表示城市巡逻图中所有的交叉路口数表示街道的长度表示第个交
10、叉口到第个交叉口的距离表示最少需要配置的警车数量表示第辆警车所在位置的向量表示第个案发点五.模型建立与求解5.1问题一的模型建立与求解5.1.1模型准备 模型说明1) 把整个城市的街区抽象化为一个图： 据题意和附录数据知，城区只有街道存在，警车可以沿着街道的两个方向行走，为方便讨论，将这个城市的街区图抽象化为一个无向图。街区中的每条街道可以看作是无向图的边，而街区中的路口可以看作是无向图的节点。那么所提出的巡逻问题就可以理解为若干个警车在这个无向图中行走巡逻。2) 图形符号标注： 城市的街区图用图论中的符号表示为无向图：为图中的有限非空顶点数，即巡逻图中的路口，表示这个巡逻图中所有的交叉路口数
11、；为图中的有限边集合，即街区巡逻图中的街道，表示这个巡逻图中所有街道数，边的权值表示街道长度，即街道的长度为；利用题中给定的数据生成图，将交叉路口的编号添加上，图形参见图一：图一. 交叉路口的编号图3) 建模原则：原则一：假定每条道路上案件发生的概率相同；原则二：为了能够方便快速出警，将各个警车初始位置设定在各交叉路口；原则三：警车巡逻过程中的变速行驶是为了使得同时到达各个交叉路口。 数据处理：1) 数学原理：计算赋权无向图中各对顶点之间最短路径，利用算法，其基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后
12、，当时，即是各顶点之间的最短通路值。即图权的邻接矩阵为来存放各边长度： 变量说明：；之间没边，在程序中以各边都不可能达到的充分大的数代替；是之间边的长度，；对于无向图，是对称阵，。2) 每对顶点之间的最短路径： 根据题中地图数据中各个交叉路口的坐标数据，利用算法，程序参见附录1，将每对顶点之间的最短路径求出，得到各个交叉路口的邻接距离矩阵，部分数据结果如下(单位：米，结果保留整数)： 5.1.2模型建立： 引入贪心策略： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体
13、最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的一般步骤如下：1) 将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2) 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择 的安全；3) 说明在做出贪心选择后，剩余的子问题具有这样的一个性质。即如果将子问题的最优解和所作的贪心选择联合起来，可以得出原问题的一个最优解。 目标分析：1) 将警车在事件发生后赶到重点部位的时间必须在两分钟之内作为优先考虑的对象，必须首先满足；2) 基于上述建模思想原则一的说明(假定每条道路上案件发生的概率相同)，将警车在接警后三分钟内赶到现场的比
14、例不低于理解为警车接警后所能到达的道路条数占总道路条数的比例不低于；3) 将研究道路条数的覆盖问题转化为研究交叉口节点的覆盖问题，利用节点覆盖率的调整来达到道路条数的覆盖范围不低于的要求；4) 对于在满足的条件下需要最少配置多少辆警车巡逻问题，经分析可知，在静态状态下，即定点巡逻所需的车辆是最少的，故研究在静态状况下所需的最少车辆即可。 初始化警车位置交叉路口分组原则： 对307个交叉点进行分组，首先对三个重点部位进行分组，使得每个分组中警车可在两分钟内到达案件现场；然后对剩余交叉点进行分组，使得每辆警车都可在三分钟之内到达其分组中的所有节点，且被覆盖的交叉点数占总数的90%以上，进而通过调节交叉点的覆盖率来满足道路条数的覆盖率不低于的要求；最后所得的交叉路口分组数即为最少所需的警车数。分组方法：因问题一是最优问题，具有最优子结构，依据上述引进的贪心策略的思想，故构造“贪心算法”对交叉点进行分组。贪心算法是使所做的选择都是当前最佳的，期望通过所做的局部最优选择来产生一个全局最优解。1) 最大分组的定义：用表示个待分组点，的一个子集，满足，。则为
