警车配置及巡逻方案设计

1、警车配置及巡逻方案设计摘要:本文就某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110 警车的配置和巡逻方案的设计建立了适当的模型，以确定警车的配置及巡逻方案 设计。对于问题一，首先利用Floyd算法求出了各个节点之间的最短距离，得到 了一个307x307阶的最短距离矩阵。对该矩阵进行处理后便得到我们需要的0-1 变量矩阵D。针对警车数量的配置问题，我们利用线性规划建立模型。其目标函 数为：minZ =弩气,再根据题目中给定的要求确立约束条件，最终通过编程 i=1对模型进行求解得到警车数量为17辆。再通过Matlab编程得到这17辆车 的分布图，加入重点部位的考虑后最终可确定所需配置

2、的警车数量为 18辆。对于问题二，先定义一个0-1变量七来表示该区域的点是否被覆盖。则才b根据公式门=x 100%可求出各个区域的有效巡逻率，这就是评价巡逻效果显 n著程度的指标。对于问题三，首先将这18辆警车的区域分布在18个图上，通过算法设计实 现了对每个图上的警车进行巡逻安排。通过计算得到的18辆警车的路径顺序在 文中均一一列出。最后由问题二中确立的评价巡逻效果显著程度的指标计算各个 区域的有效巡逻率。由计算结果发现有效巡逻率均在75%以上，甚至有的达到了 100%。由此可说明建立的模型及警车的巡逻方案都是比较合理的。对于问题四，为了达到巡逻规律的隐蔽性，我们可交换各辆车的巡逻顺序， 同

3、时也可根据已给出的巡逻路线选择不同的路径进行巡逻，这样在时间上和空间 上都形成差异，让人难以寻摸其中的规律，并且使得原本没有巡逻到的位置在进 行交换巡逻时被巡逻到了，因此使得巡逻效果更显著。对于问题六，其过程的求解思路是问题一与问题三的综合，编程后我们得到， 改变接警后的平均行驶速度后所需配置的警车数量为14辆。具体巡逻方案的给 出与问题三是一致的。关键词：Floyd算法0-1变量有效巡逻率一、问题重述110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率， 又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件） 时间，提高了反应时效，为社会和谐提供了有力的保障

4、。考虑某城市内一区域，区域图见附录二。为简化问题，假定所有事发现场均 在图中的道路上。该区域内三个重点部位的坐标分别为：（5112, 4806），（9126, 4266），（7434，1332）（见图中红点部位，蓝色部分为水域，道路数据见附件， 相邻两个交叉路口之间的道路近似认为是直线）。某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设 110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配 置及巡逻方案要尽量满足以下要求：D1.警车在接警后三分钟内赶到现场的比例不低于90%；而赶到重点部位 的时间必须在两分钟之内。D2.使巡逻效果更显著；D3

5、.警车巡逻规律应有一定的隐蔽性。请回答以下问题：若要求满足D1,该区最少需要配置多少辆警车巡逻？请给出评价巡逻效果显著程度的有关指标。请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评 价指标值。如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得 到满足？若警车接警后的平均行驶速度提高到50km/h，回答问题三。你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方 案。二、模型假设假设警车在初始状态是静止不动的且均匀分布在各个区域；假设警车在巡逻过程中，到达路口对相邻街道起到一定的震慑作用；假设各

6、辆警车的各类参数值是一样的，即警车本身对巡逻效果没有什么影响。三、符号说明七：警车接警后的平均行驶速度：警车的平均巡逻速度，：警车距离案发地点的最大距离d,： 0-1矩阵中的元素:每一个区域的有效覆盖率：每一个区域所覆盖的点数四、问题分析对于问题一，考虑到实际情况中，单辆警车的巡逻只是在小区域内进行而不 可能在短时间内巡逻整个城市，故可将整个城市的区域分成多个小区域，每个区 域派一辆车循环巡逻。首先用Floyd算法算出各个点之间的最短距离，得到一 个307 307的矩阵。为满足D1条件中警车在接警后三分钟须赶到现场的概率为 90%，也就是说必须保证距案发现场2000m以内有警车巡逻。在这里我们

7、可假设 9警车是静止不动的，将一辆车想像成一个点，从每个点出发找到距这个点距离小 于或等于2000m的点，这些搜索到点的集合便可组成一个小区域。而中心点的9个数便是所需要的警车的最基本的数量。再进一步对图中给出的重点部位进行考 虑，便可得到最少需要配置的警车数量。这种算法类似于无线传感器网络中保证 覆盖的最少节点部署问题。即取适当的半径作圆，要求用尽量少的圆覆盖整个区 域。只是由于题目给出的实际情况不同，路与路之间存在着折点无法转化成圆的 问题，我们要考虑的覆盖不是圆，只是基本原理大致相同。在用Lingo对其进行 编程时，难免会有区域与其它区域产生交集部分。交集部分越大，所需的警车数 量也就越

8、多，因此得到的解并不是最优解，而是一个可行解，我们需进一步进行 处理。在对求得的结果不断地进行压缩后，便可得到最优解，即所需配置的最少 的警车的数量。对于问题二，要给出评价巡逻效果的显著程度的指标，即要先确立哪些指标 对衡量巡逻效果有影响。110警车在街道上巡弋，主要作用就是能够对违法犯罪 分子起到震慑作用，降低犯罪率，又能够增加市民的安全感。为达到这些效果， 警车的巡逻范围应尽量广，以保证所有的区域的人民都能够感觉到巡警的存在， 且犯罪份子不敢轻举妄动，这样就能够降低犯罪率。在相同的时间内，如果重复 巡逻的次数越多，则证明巡逻路径较优，巡逻效果越好。而由于公路的交叉，警 车在一次巡逻后不能够

9、走遍所有的点。因此，我们可求得警车在巡逻完后所遗漏 的节点。由此节点数即可判断巡逻的效果显著程度。在前面我们只是在满足D1条件下求得了所需配置的最少的警车的数量，在 实际生活中，巡逻方案一定要给出警车的巡视路线，即要对警车如何巡逻给出指 导。这就是问题三要我们做的工作。由于警车的巡逻范围是固定的，这就涉及到 一个最短路径问题，如何在最短的时间内走完最长的路，对于这样的问题我们可 以根据所设计的算法给出巡逻路线。给出巡逻方案后，我们可借助问题二中给出 的评价指标体系求出这一方案的指标值并判断方案的优劣。问题四是在问题三的基础上进一步考虑D3条件后要求我们重新给出巡逻方 案及其评价值。我们知道，如

10、果警车非常有规律地在一个范围内巡逻，时间一长， 犯罪分子就很容易发现他们的巡逻规律。这样他们便可以避开警车的视线大胆地 作案。如此一来，警车的巡逻则失去了意义。基于这一点，我们不能只单纯地考 虑巡逻路线的长短和巡逻和范围来安排巡逻方案。而应当使得巡逻真正发挥其作 用，为人民服务。为了不让犯罪分子的计划得逞，巡逻规律应当尽量的隐蔽。比 如说，我们可以在有些地方安排两辆车或三辆车为一个组，在一个稍大型点的区 域内交叉巡逻，这样犯罪分子就不容易发现警车的巡逻规律。问题六相对于问题三而言只是改变了一个量，即警车接警后的平均行驶速 度。求解方法跟问题三是一样的，只是由于警车的行驶速度的不同，求解结果自

11、然也不同。据常理我们知道，如果警车的速度越快，则警车处理事件的效率也越 高，因此，所需要的警车数量也应该越少才是。五、模型的建立与求解5.1问题一5.1.1Floyd算法原理Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权 图中顶点间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最 短路径矩阵。从图的带权邻接矩阵A = a(i,j)开始，递归地进行n次更新， . .,. nxn . ,.即由矩阵D(0)二A，按一个公式，构造出矩阵D(1)；又用同样地公式由D 构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵 D(n)的i行j列元素便是i号顶点到

12、j号顶点的最短路径长度，称D(n)为所 有点对的最短距离矩阵。5.1.2基本模型的建立与求解首先我们利用弗洛伊德算法算出各个点之间的最短距离，得到一个 307x307的上三角矩阵，由于路径具有双向性，所以原图的距离矩阵是对称 的，将所求得的矩阵对折得到原图的距离矩阵入。题目要求警车在接警后三分钟内赶到现场的比例不低于90%，警车在接警后的平均行驶速度为 七，所 以警车距离案发地点的最大距离为：13/5 20000 s = v 60 /90% = m对距离矩阵A做以下处理：矩阵A的对角线元素取值为1；矩阵A中大于0小于20000的点取值为1；9其余各点均取0； 得到处理后的0-1矩阵D = (d

13、)307x307其中：气=1表示警车从节点到j节点能在三分钟之内到达；d = 0表示警车从节点到j节点不能在三分钟之内到达。在这307个节点上，我们要通过算法选取其中合适的点作为警车出发点， 我们用0-1变量“.来表示该节点是否被选取，其中_J0, ”节点不作为警车出发点气=|1，”节点作为警车出发点i对问题的求解就可转化成线性规划问题，我们的目标函数就是要使得所配置 的警车数量最少，即0-1变量“ 的总和最小。而题目中的约束条件不仅要求 警车在接警后三分钟之内要赶到现场的概率为 90 %，而且要求重点部位是在 两分钟之内赶到。我们可以先假设巡逻车是静止不动的，每一辆车管辖一片 区域，这样的话

14、我们只要求出各个区域便可求得所要配置的警车数量。重点 部位是图中给出的红点，由图中我们可以看到只有三个点。由于计算机的局 限性，要同时满足这两个条件是比较困难的，甚至是无法实现的。为此我们 先考虑全部的警车都是在三分钟之内赶到案发现场的情况。同时假设所有的 点都能够满足这一条件，即警车三分钟之内能够赶到现场的概率为100%。在这种假设条件下，每一个节点都能够被覆盖。基于以上分析，我们建立如下 的基本模型：目标函数：minZ =郊ai i=1s.t 弩 d a = 1(i = 1,2,.307; j = 1,2,.307 )=1通过LINGO软件编程求解得到车辆的分布图如下(程序及数据见附 件)

15、：900080007000600060004000300020001000005000W00015000图1：静止状态下车辆的分布图图1中的每一个红点分别代表一辆警车，共有17个红点。即若只考虑 三分钟的约束条件而暂不考虑重点部位的情况下，应配置17辆警车对该区域巡逻。相对来说，17辆车已经算是较优解了。观察图1还可发现，里面有 三个红色的小叉代表重点部位，它们的坐标分别为A(5274, 4806)，B (9126, 4266)，C(7434，1332)。由于这些点都不是在交叉路口上，故先对它们近似取 点，由附件中的数据我们可以分别取它们的近似点得到川(5274，4788)，B(9180，40

16、86)，C(7452, 1368)。在原来求得的17个点上选取距A、B、C 最近的点分别为 D(5238, 6210)，E(9162, 2790)，F(7416,1116)，算得各个近 似重点部位距最近中心点的距离分别为：AD = 1691mBE = 1296 m C F = 255m重点部位要求警车在接警后二分钟内赶到，警车接警后的平均行驶速度为七， 经过计算可得，警车可及时赶到现场的距离为：124000s = 60 v =3 1333.3m将A，D、BE、CF与*比较大小可得，只有AD的距离大于*，也就是说，在之前的假设条件下求得的解中，B、C两点周围警车的安排都可以满足D1 中的条件。而

17、A则不行，因此需要在重点部位A处再安置一辆警车以满足需要。这样的话一共需要配置的警车数量则为18辆。经过编程处理后，我们还可以进一步得到各个区域的分区情况如下图2：9000800070006000500040003000200010000050001000015000图2：警车巡逻区域的分布图图2中的每一块区域都用不同的颜色进行标记，每一种颜色代表一辆车的巡 逻区域。由图中我们可以看出，各个区域的分布都比较均匀和集中，这就避免了 一辆车从一个点巡逻到另一个很远的点，每辆警车都能在自己的范围内恪尽职 守。由于搜索的局限性，图中很多区域都出现了交集，即同一个点总有不同的车 经过。这也是车辆数量不能

18、达到最小的原因之一。综合以上分析及我们所建立的模型，我们求得一共需要配置的警车数量为18辆。5.2问题二由问题分析中我们已经提到，可用警车巡逻完后所经过的点作为评价巡逻效 果显著程度的重要指标。下面我们给出这项指标的求解方法。对于警车是否覆盖节点，我们可定义一个0-1变量b来表示，其中I1 f0,表示警车巡逻所覆盖到的点b =i 1，表示警车巡逻所未覆盖到的点则每一个区域的有效覆盖率门可表示为：乎bi门=-i=n其中n为每一个区域内所覆盖的节点数。这项指标的值越大，说明警车的巡逻所 覆盖的地方越多，巡逻效果也就越好。5.3问题三在问题一中我们已经求出需要配置的巡逻警车至少为18辆，如果按照一般

19、 的巡逻规则，警车是在一定的范围内循环巡逻。这样有利于巡警熟悉周边环境， 提高办事效率，同时，也避免了安排巡逻方案的复杂性。现在我们要做的是在问 题一的基础上再增加条件D2，给出一套警车的巡逻方案，使得巡逻效果更加明显。 按照这样的原则，我们通过如下步骤给出巡逻方案。Step1:首先将图2分解，得到每一辆警车的巡逻区域及警车的初始位置。再对每 一张区域图一一进行分析。Step2 :观察各个区域图，将周围的支点去掉，得到相对较没有棱角的区域。Step3 :从中心点出发，依次寻遍各个点，再返回原点。每一次巡逻可不遍历各 点，但应尽量多地走完大部分点。返回原点后，在进行第二次巡逻的过 程中应尽量把上

20、一次巡逻没有走过的点走完，及保证巡逻效果的显著性。 这样直到走完所有的点后，警车巡逻的路线也就确定了。在一定时间内， 警车都可按照此路线对该区域进行巡逻。Step4： 一张区域图巡逻完后，便继续对下一张区域图按以上步骤进行分析，直 至得到这18辆警车的巡逻路线，则结束任务。首先我们根据整个图形区域以及18辆警车的初始位置，主观的将原图形分 为四个区，并且把初始位置分别为40（14418, 6840），24（10300，7182），13 （8118，7668），85（9972，5256）的4辆警车作为第一区，如图3所示：图3第一区警车分布及其所辖区域根据上述巡逻方案，我们可以给出第一辖区内每辆车

21、的巡逻路线，下面我们 给出第一辆警车初始位置为40（14418, 6840）的巡逻路线。30D0则第一辆警车的巡逻路线为：第一条：40 r 79 T 77 T 81T 2 T1T 35 T 40第二条：40 r 39 r 77 r 79 r 40且我们发现，上述所给的巡逻路线没有经过37和237两个位置，即第一辆 车在巡逻过程中遗漏了两个位置，则第一辆车的有效巡逻率为：10 - 2、=x 100% = 80%。我们给出第二辆警车初始位置为24（10300，7182）的巡逻路线。图5第二辆警车分布及其所辖区域则第二辆警车的巡逻路线为：第一条：24 r 49 r 45 r 21 r 2 r 5 r

22、 4 r 15 r 25 r 44 r 84 r 78 r 61 r 63 r 49 r 24第二条：24 r 17 r 16 r 15 r 25 r 44 r 49 r 24第二辆车的有效巡逻率为：L =100%。同理，我们给出第三辆和第四两警车初始位置为分别为13 (8118, 7668)和 85(9972，5256)的巡逻路线。图5第三辆和第四两警车分布及其所辖区域则第三辆警车的巡逻路线为: 第一条：第二条:第三条:13 T 3 T 6 T 8 T 22 r 50 T 51T 52 T 47 T 44 T 25 T15 T4 3 1313 r 18 r 29 r 51 r 83 r 88

23、 r 52 r 47 r 41 r 42 r 23 r 1313 r 3 r 4 r 5 r 16 r 15 r 25 r 23 r 29 r 22 r 28 r 19 r 20r 11 r 8 r 6 r 3 r 1319第二辆车的有效巡逻率为：L = 20 x 100% = 95%。第四辆警车的巡逻路线为：第一条：85 r 78 r 61 r 63 r 49 r 48 r 44 r 84 r 88 r 115 r 116 r 123r 141 r 148 r 136 r 137 r 86 r 85第二条：85 r 122 r 123 r 116 r 84 r 78 r 8517第四辆警车的

24、有效巡逻率为：L = x100% = 94.4%。由此我们可以给出第二、三、四区中剩余14辆警车的巡逻路线。且剩余每 辆警车分布及其所辖区域见附录。我们把初始位置分别为 12 (2502, 7902), 55 (5238, 6210), 94 (1548, 5184), 110 (5274, 4788)的4辆警车作为第二区。8000图6第二区警车分布及其所辖区域第五辆警车初始位置为12 (2502, 7902)的巡逻路线为：第一条：12 r 9 T14 r 33 T 38 T 46 T 62 T 60 T 30 T 27 T 7 T10 T12第二条：12 r 26 r 33 r 32 r 3

25、6 r 43 r 46 r 38 r 33 r 26 r 30 r 10 r 12第五辆车的有效巡逻率为：L = 12x100% = 91.7%。第六辆警车初始位置为55(5238，6210)的巡逻路线为：第一条：55 r 53 r 67 r 58 r 59 r 65 r 70 r 76 r 90 r 99 r 101 r 10 r 106 r 107 r 91 r 56 r 54 r 55第二条：55 r 53 r 31 r 27 r 57 r 58 r 59 r 60 r 69 r 74 r 76 r 98 r 103 r 110 r 125 r 133 r 121 r 112 r 104

26、 r 96 r 80 r 100 r 93 r 69 r 65r 58 r 57 r 53 r 55第六辆车的有效巡逻率为：L = 48x100% = 75%。第七辆警车初始位置为94(1548, 5184)的巡逻路线为：第一条：94 r 109 r 111 r 128 r 130 r 158 r 157 r 193 r 211 r 167 r131 r 93 r 82 r 89 r 95 r 102 r 97 r 94第二条：94 r 92 r 67 r 66 r 71 r 73 r 89 r 95 r 97 r 9418第七辆车的有效巡逻率为：L = 20 x100% = 90%。第八辆警

27、车初始位置为110(5274，4788)的巡逻路线为：第一条：110 r 118 r 106 r 87 r 54 r 64 r 72 r 75 r 90 r 99 r 105 r 106r 118 r 110第二条：110 r 101 r 99 r 90 r 75 r 70 r 68 r 57 r 58 r 59 r 65 r 70 r 75 r 90 r 99 r 101 r 110第三条：110 r 101 r 98 r 76 r 74 r 69 r 60 r 82 r 93 r 80 r 96 r 104 r103 r 112 r 110第四条：110 T112 T121T129 T12

28、4 r 135 T132 T160 T161T162 T179 T 189 r 205 r 196 r 156 r 143 r 142第五条：110 r 118 r 125 r 143 r 144 r 153 r 163 r 164 r 172 r 171 r 155 r 152 r 146 r 126 r 120 r 106 r 118 r 110第六条：147 r 154 r 150 r 152 r 146 r 144 r 143 r 142 r 133 r 12770第八辆车的有效巡逻率为： = x100% = 98.6%。至于余下十辆车的巡逻路径及有效巡逻率也可依上述方法依次求得，由于

29、数 量过于繁杂和庞大，在这里我们就不一一进行列举了，有关数据见附录一。图7第三区和第四区警车分布及其所辖域12D0D综合上述所得到的数据，我们可以给出各巡逻警车的相关数据信息，如下表 所示：表1各巡逻警车的相关数据车辆初始位置所辖区域坐标数巡逻坐标数有效巡逻率第一辆警车4010880.00%第二辆警车241515100.00%第三辆警车13201995.00%第四辆警车85282485.71%第五辆警车12121191.70%第六辆警车55483675.00%第七辆警车94201890.00%第八辆警车110717098.60%第九辆警车29577100.00%第十辆警车2513333100.

30、00%第十一辆警车1683232100.00%第十二辆警车171715577.46%第十三辆警车215252288.00%第十四辆警车178645789.10%第十五辆警车25599100.00%第十六辆警车291171376.47%第十七辆警车271322990.63%第十八辆警车285302480.00%由以上结果发现，我们建立的模型及给出的巡逻方案效果还是不错的，其有 效巡逻率至少达到了 75%，还有些达到了 90%多甚至于100%。5.4问题四根据问题三的解答，我们清楚的知道了每一辆警车在各自辖区内的巡逻路 线，然而为了达到D3:警车巡逻规律应有一定的隐蔽性的条件，则警车不应该 只按照

31、自己的路线进行巡逻，或者不要老是按所给路线一一巡逻，而应该打乱选 择巡逻路线的规律，最好能够与同区的警车进行交换巡逻，从而在巡逻路线不变 的情况下达到同一巡逻路线时间的差异性。下面给出两辆警车进行进行交换巡逻 的方法。图8第一辆和第二辆警车警车分布及其所辖区域如图8所示，我们用第一辆和第二辆警车为例来说明两辆警车之间进行交换 巡逻。根据问题三的巡逻路线安排法，我们知道位置37并没有被巡逻，因此， 第一辆和第二辆警车可以通过这个点进行换区巡逻。当两辆警车要交换巡逻时， 因为各自的巡逻路线不同，导致彼此不能同时进入对方的巡逻区域，从而在巡逻 路线不变的情况下达到同一巡逻路线时间的差异性，达到了巡逻

32、规律应有一定的 隐蔽性的目的。每辆警车的具体巡逻路线同样可以参照问题三的解决方法给出， 并且使得原本没有巡逻到的位置37在进行交换巡逻时被巡逻到了，因此使得巡 逻效果更显著。5.5问题六在问题三的基础上，若警车接警后的平均行驶速度由40km/h增加到50km/h。由于只是其中的一个量改变了，整个解题思路还是一样的。我们先改 变的值，依照问题一的步骤重新编程，得到所需配置的警车分布图如下：8000700Uenoo50004000300020001000图8： V 50km/ h时车辆的分布图图8是提高接警后的平均行驶速度后，所需要的配置的警车的分布图， 一共为14辆车。也就是说警车办事的效率增加

33、了，用来巡逻的车辆也减少 了。因此为了节省开支，警车接警后可以适当地提高速度，这样就能够减少 所派去巡逻车辆的数量。同样的，我们对各辆车的管辖区域给出分布图如下：800070006000500040003000200010000图9：各车辆管辖区域的分布图依据问题三的步骤，可将整个区域图划分成各区域的小图，再在小图上对车 辆巡逻的路径进行搜索。由问题三的求解我们可以看出其过程是复杂的，但基本 思路是完全一致的。具体过程和结果在此就不做一一的叙述了。六、模型的评价与推广优点：该模型很好地解决了警车数量的配置问题，有助于警方在对车辆的 部署上作出参考。同时，我们用自己设计的方法对警车的巡逻给出了一

34、套方 案，该方案基本上能够实现所有的条件，使巡逻的效果显著程度能够达到较 大值。另外，该模型的建立对于其他相似的配置问题具有很好的借鉴作用。缺点：由于算法的局限性和作者能力有限，没有给出巡逻时每一分钟警车 的位置，所求得的对警车的配置数量并不是理想的最优解，该模型的改进空 间还很大。许多问题还有待比赛后进一步思考和完善。推广：该模型不仅适用于警车的配置及巡逻方案，对社会治安防控、国庆 治安巡逻方案甚至小到商场的保安巡逻都有同样的借鉴价值。参考文献温俊，窦强，蒋杰，宋磊，窦文华，无线传感器网络中保证覆盖的最少节点 部署，国防科技大学学报，第31卷第3期：唐振民，赵春霞，杨静宇，张进，基于动态规划

35、思想的多机器人路径规划， 南京理工大学学报，第27卷第5期：2003.10顾平，试论我国警察巡逻体制的建立与建设，江苏公安专科学校学报，第4 期:1994林祝亮，冯远静，俞立，无线传感网络覆盖的粒子进化优化策略研究，传感技术学报，第22卷第6期:2009.06运怀立，刘兴，王贵强，不确定车数的随机车辆路径问题模型及算法，工业 工程，第10卷第3期:2007.05附录一：第九辆警车初始位置为295(11880，7021)的巡逻路线为：第一条：295 T 306 T 305 T 251T 253 T 295第二条：295 306 307 296 257 253 295第九辆车的有效巡逻率为：L =

36、 100%。第十辆警车初始位置为251(911304, 2160)的巡逻路线为：第一条：251T 236 T 235 T 237 T 257 T 296 T 295 T 306 T 305 T 251第二条：251 253 295 296 257 253 251第十辆车的有效巡逻率为：、=100%。第十一辆警车初始位置为168(8802, 3618)的巡逻路线为：第一条：168 192 169 165 173 165 169 149 139 147154 149 169 192 168第二条：168 170 168第十一辆车的有效巡逻率为：L11 = 100%。第十二辆警车初始位置为171(7

37、110，3582)的巡逻路线为：第一条：171 154 147 139 138 141 116 115 117 108 83 91 107 106 118 119 127 133 142 143 144 153 201 207 222 216 224 244 238 265 266 261 241 242 226 215 197 203 220 227 225 210 194 214 184 172 171第二条：171 172 164 163 153 144 134 118 106 120 126 146 152 140 145 150 154 149 151 166 173 166 169 194 185 171第十二辆车的有效巡逻率为：L12= 71X100% = 77.46%。第十三辆警车初始位置为215（9162，2790）的巡逻路线为：第一条：215 141 123 116 123 141 148 136 137 136 148141 215第二条：215 197 203 210 194 238 265 266 261 241 242 226 215第三条：215 226 220 227 225 210 194 238 240 241 242 226 21522第