文档介绍：警车配置及巡逻方案设计
摘要：本文就某城市拟增加一批配备有GPS***系统及先进通讯设备的110警车的配置和巡逻方案的设计建立了适当的模型，以确定警车的配置及巡逻方案设计。
对于问题一，首先利用Floyd算法求出了各个节点之间的最短距离，得到了一个阶的最短距离矩阵。对该矩阵进行处理后便得到我们需要的0-1变量矩阵D。针对警车数量的配置问题，我们利用线性规划建立模型。其目标函数为：，再根据题目中给定的要求确立约束条件，最终通过编程对模型进行求解得到警车数量为17辆。再通过Matlab编程得到这17辆车的分布图，加入重点部位的考虑后最终可确定所需配置的警车数量为18辆。
对于问题二，先定义一个0-1变量来表示该区域的点是否被覆盖。则根据公式可求出各个区域的有效巡逻率，这就是评价巡逻效果显著程度的指标。
对于问题三，首先将这18辆警车的区域分布在18个图上，通过算法设计实现了对每个图上的警车进行巡逻安排。通过计算得到的18辆警车的路径顺序在文中均一一列出。最后由问题二中确立的评价巡逻效果显著程度的指标计算各个区域的有效巡逻率。由计算结果发现有效巡逻率均在75%以上，甚至有的达到了100%。由此可说明建立的模型及警车的巡逻方案都是比较合理的。
对于问题四，为了达到巡逻规律的隐蔽性，我们可交换各辆车的巡逻顺序，同时也可根据已给出的巡逻路线选择不同的路径进行巡逻，这样在时间上和空间上都形成差异，让人难以寻摸其中的规律，并且使得原本没有巡逻到的位置在进行交换巡逻时被巡逻到了，因此使得巡逻效果更显著。
对于问题六，其过程的求解思路是问题一与问题三的综合，编程后我们得到，改变接警后的平均行驶速度后所需配置的警车数量为14辆。具体巡逻方案的给出与问题三是一致的。
关键词：Floyd算法 0-1变量有效巡逻率
一、问题重述
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. 假设各辆警车的各类参数值是一样的，即警车本身对巡逻效果没有什么影响。
三、符号说明
：警车接警后的平均行驶速度
：警车的平均巡逻速度
：警车距离案发地点的最大距离
：0-1矩阵中的元素
：每一个区域的有效覆盖率
：每一个区域所覆盖的点数
四、问题分析
对于问题一，考虑到实际情况中，单辆警车的巡逻只是在小区域内进行而不可能在短时间内巡逻整个城市，故可将整个城市的区域分成多个小区域，每个区域派一辆车循环巡逻。首先用Floyd算法算出各个点之间的最短距离，得到一个的矩阵。为满足D1条件中警车在接警后三分钟须赶到现场的概率为90%，也就是说必须保证距案发现场以内有警车巡逻。在这里我们可假设警车是静止不动的，将一辆车想像成一个点，从每个点出发找到距这个点距离小于或等于的点，这些搜索到点的集合便可组成一个小区域。而中心点的个数便是所需要的警车的最基本的数量。再进一步对图中给出的重点部位进行考虑，便可得到最少需要配置的警车数量。这种算法类似于无线传感器网络中保证覆盖的最少节点部署