警车配置及巡逻方案设计

警车配置及巡逻方案设计摘要：本文就某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车的配置和巡逻方案的设计建立了适当的模型，以确定警车的配置及巡逻方案设计。对于问题一，首先利用Floyd算法求出了各个节点之间的最短距离，得到了一个307307阶的最短距离矩阵。对该矩阵进行处理后便得到我们需要的0-1变量矩阵D。针对警车数量的配置问题，我们利用线性规划建立模型。其目标函数为：3071miniiZa，再根据题目中给定的要求确立约束条件，最终通过编程对模型进行求解得到警车数量为17辆。再通过Matlab编程得到这17辆车的分布图，加入重点部位的考虑后最终可确定所需配置的警车数量为18辆。对于问题二，先定义一个0-1变量ib来表示该区域的点是否被覆盖。则根据公式1100%niibn＝可求出各个区域的有效巡逻率，这就是评价巡逻效果显著程度的指标。对于问题三，首先将这18辆警车的区域分布在18个图上，通过算法设计实现了对每个图上的警车进行巡逻安排。通过计算得到的18辆警车的路径顺序在文中均一一列出。最后由问题二中确立的评价巡逻效果显著程度的指标计算各个区域的有效巡逻率。由计算结果发现有效巡逻率均在75%以上，甚至有的达到了100%。由此可说明建立的模型及警车的巡逻方案都是比较合理的。对于问题四，为了达到巡逻规律的隐蔽性，我们可交换各辆车的巡逻顺序，同时也可根据已给出的巡逻路线选择不同的路径进行巡逻，这样在时间上和空间上都形成差异，让人难以寻摸其中的规律，并且使得原本没有巡逻到的位置在进行交换巡逻时被巡逻到了，因此使得巡逻效果更显著。对于问题六，其过程的求解思路是问题一与问题三的综合，编程后我们得到，改变接警后的平均行驶速度后所需配置的警车数量为14辆。具体巡逻方案的给出与问题三是一致的。关键词：Floyd算法0-1变量有效巡逻率2一、问题重述110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，区域图见附录二。为简化问题，假定所有事发现场均在图中的道路上。该区域内三个重点部位的坐标分别为：（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，回答问题三。七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。二、模型假设1．假设警车在初始状态是静止不动的且均匀分布在各个区域；2．假设警车在巡逻过程中，到达路口对相邻街道起到一定的震慑作用；3.假设各辆警车的各类参数值是一样的，即警车本身对巡逻效果没有什么影响。三、符号说明1v：警车接警后的平均行驶速度2v：警车的平均巡逻速度0s：警车距离案发地点的最大距离ijd：0-1矩阵中的元素：每一个区域的有效覆盖率n：每一个区域所覆盖的点数四、问题分析3对于问题一，考虑到实际情况中，单辆警车的巡逻只是在小区域内进行而不可能在短时间内巡逻整个城市，故可将整个城市的区域分成多个小区域，每个区域派一辆车循环巡逻。首先用Floyd算法算出各个点之间的最短距离，得到一个307307的矩阵。为满足D1条件中警车在接警后三分钟须赶到现场的概率为90%，也就是说必须保证距案发现场20009m以内有警车巡逻。在这里我们可假设警车是静止不动的，将一辆车想像成一个点，从每个点出发找到距这个点距离小于或等于20009m的点，这些搜索到点的集合便可组成一个小区域。而中心点的个数便是所需要的警车的最基本的数量。再进一步对图中给出的重点部位进行考虑，便可得到最少需要配置的警车数量。这种算法类似于无线传感器网络中保证覆盖的最少节点部署问题。即取适当的半径作圆，要求用尽量少的圆覆盖整个区域。只是由于题目给出的实际情况不同，路与路之间存在着折点无法转化成圆的问题，我们要考虑的覆盖不是圆，只是基本原理大致相同。在用Lingo对其进行编程时，难免会有区域与其它区域产生交集部分。交集部分越大，所需的警车数量也就越多，因此得到的解并不是最优解，而是一个可行解，我们需进一步进行处理。在对求得的结果不断地进行压缩后，便可得到最优解，即所需配置的最少的警车的数量。对于问题二，要给出评价巡逻效果的显著程度的指标，即要先确立哪些指标对衡量巡逻效果有影响。110警车在街道上巡弋，主要作用就是能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感。为达到这些效果，警车的巡逻范围应尽量广，以保证所有的区域的人民都能够感觉到巡警的存在，且犯罪份子不敢轻举妄动，这样就能够降低犯罪率。在相同的时间内，如果重复巡逻的次数越多，则证明巡逻路径较优，巡逻效果越好。而由于公路的交叉，警车在一次巡逻后不能够走遍所有的点。因此，我们可求得警车在巡逻完后所遗漏的节点。由此节点数即可判断巡逻的效果显著程度。在前面我们只是在满足D1条件下求得了所需配置的最少的警车的数量，在实际生活中，巡逻方案一定要给出警车的巡视路线，即要对警车如何巡逻给出指导。这就是问题三要我们做的工作。由于警车的巡逻范围是固定的，这就涉及到一个最短路径问题，如何在最短的时间内走完最长的路，对于这样的问题我们可以根据所设计的算法给出巡逻路线。给出巡逻方案后，我们可借助问题二中给出的评价指标体系求出这一方案的指标值并判断方案的优劣。问题四是在问题三的基础上进一步考虑D3条件后要求我们重新给出巡逻方案及其评价值。我们知道，如果警车非常有规律地在一个范围内巡逻，时间一长，犯罪分子就很容易发现他们的巡逻规律。这样他们便可以避开警车的视线大胆地作案。如此一来，警车的巡逻则失去了意义。基于这一点，我们不能只单纯地考虑巡逻路线的长短和巡逻和范围来安排巡逻方案。而应当使得巡逻真正发挥其作用，为人民服务。为了不让犯罪分子的计划得逞，巡逻规律应当尽量的隐蔽。比如说，我们可以在有些地方安排两辆车或三辆车为一个组，在一个稍大型点的区域内交叉巡逻，这样犯罪分子就不容易发现警车的巡逻规律。问题六相对于问题三而言只是改变了一个量，即警车接警后的平均行驶速度。求解方法跟问题三是一样的，只是由于警车的行驶速度的不同，求解结果自然也不同。据常理我们知道，如果警车的速度越快，则警车处理事件的效率也越高，因此，所需要的警车数量也应该越少才是。4五、模型的建立与求解5.1问题一5.1.1Floyd算法原理Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵nnAai,j开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为所有点对的最短距离矩阵。5.1.2基本模型的建立与求解首先我们利用弗洛伊德算法算出各个点之间的最短距离，得到一个307307的上三角矩阵，由于路径具有双向性，所以原图的距离矩阵是对称的，将所求得的矩阵对折得到原图的距离矩阵A。题目要求警车在接警后三分钟内赶到现场的比例不低于90%，警车在接警后的平均行驶速度为1v，所以警车距离案发地点的最大距离为：01320000/90%609svm对距离矩阵A做以下处理：（1）矩阵A的对角线元素取值为1；（2）矩阵A中大于0小于200009的点取值为1；（3）其余各点均取0；得到处理后的0-1矩阵307307()ijDd其中：1ijd表示警车从i节点到j节点能在三分钟之内到达；0ijd表示警车从i节点到j节点不能在三分钟之内到达。在这307个节点上，我们要通过算法选取其中合适的点作为警车出发点，我们用0-1变量ia来表示该节点是否被选取，其中0,1iiiaaa节点不作为警车出发点，节点作为警车出发点对问题的求解就可转化成线性规划问题，我们的目标函数就是要使得所配置的警车数量最少，即0-1变量ia的总和最小。而题目中的约束条件不仅要求警车在接警后三分钟之内要赶到现场的概率为90%，而且要求重点部位是在两分钟之内赶到。我们可以先假设巡逻车是静止不动的，每一辆车管辖一片区域，这样的话我们只要求出各个区域便可求得所要配置的警车数量。重点部位是图中给出的红点，由图中我们可以看到只有三个点。由于计算机的局限性，要同时满足这两个条件是比较困难的，甚至是无法实现的。为此我们先考虑全部的警车都是在三分钟之内赶到案发现场的情况。同时假设所有的点都能够满足这一条件，即警车三分钟之内能够赶到现场的概率为100%。在这种假设条件下,每一个节点都能够被覆盖。基于以上分析，我们建立如下的基本模型：5目标函数：3071miniiZa..st30711ijjjda（1,2,...307;1,2,...307ij）通过LINGO软件编程求解得到车辆的分布图如下（程序及数据见附件）：图1：静止状态下车辆的分布图图1中的每一个红点分别代表一辆警车，共有17个红点。即若只考虑三分钟的约束条件而暂不考虑重点部位的情况下，应配置17辆警车对该区域巡逻。相对来说，17辆车已经算是较优解了。观察图1还可发现，里面有三个红色的小叉代表重点部位，它们的坐标分别为A（5274，4806），B（9126，4266），C（7434，1332）。由于这些点都不是在交叉路口上，故先对它们近似取点，由附件中的数据我们可以分别取它们的近似点得到'A(5274，4788)，'B（9180，4086），'C（7452，1368）。在原来求得的17个点上选取距'A、'B、'C最近的点分别为D(5238，6210)，E（9162，2790），F（7416,1116），算得各个近似重点部位距最近中心点的距离分别为：'1691ADm'1296BEm'255CFm重点部位要求警车在接警后二分钟内赶到，警车接警后的平均行驶速度为1v，经过计算可得，警车可及时赶到现场的距离为：11240001333.3603svm将'AD、'BE、'CF与1s比较大小可得，只有'AD的距离大于1s，也就是说，6在之前的假设条件下求得的解中，B、C两点周围警车的安排都可以满足D1中的条件。而A则不行，因此需要在重点部位A处再安置一辆警车以满足需要。这样的话一共需要配置的警车数量则为18辆。经过编程处理后，我们还可以进一步得到各个区域的分区情况如下图2：图2：警车巡逻区域的分布图图2中的每一块区域都用不同的颜色进行标记，每一种颜色代表一辆车的巡逻区域。由图中我们可以看出，各个区域的分布都比较均匀和集中，这就避免了一辆车从一个点巡逻到另一个很远的点，每辆警车都能在自己的范围内恪尽职守。由于搜索的局限性，图中很多区域都出现了交集，即同一个点总有不同的车经过。这也是车辆数量不能达到最小的原因之一。综合以上分析及我们所建立的模型，我们求得一共需要配置的警车数量为18辆。5.2问题二由问题分析中我们已经