110警车配置及巡逻方案

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