校园电动巡逻车配备方案

郑玙

（湖北大学计算机与信息工程学院，湖北 武汉 430062）

1 模型的建立与求解

给定：在后台接听到校内有报警电话打出后的四分钟内，有不低于90%的校园巡逻车能及时赶到报警现场，即在一天当中任意一个时刻当校内有不低于90%的区域发生案件后，均有巡逻车可以在报警电话打出的四分钟内赶到现场。

1.1 数据预处理

1.1.1 地理信息离散化

为了方便我们建模过程中的计算与数据处理，可先将此道路抽象化，在分块后的每一段道路中分别采样，将道路运用线性插值的方法离散成一个一个的端点，设每250 米取一个点。整个校园区域就可以看作是由若干个结点和边构造成的无向图，从而建立了校园区域网拓扑关系。

则校园巡逻车的时间信息就可以用模型经过的离散点的数量来抽象，而巡逻车行驶过程则是模拟成从一个离散点到下一个离散点，便于清晰地观察与分析。

1.1.2 建立巡逻仿真系统

采用计算机仿真的方法，建立校园巡逻车巡逻仿真系统，要模拟出任意时刻的校园巡逻车的行驶状态。该计算机仿真系统会在每一个时刻计算出巡逻车当前的行驶参数是否符合给定的要求，若不符合则根据给定的要求进行调整，直至检测到行驶参数在符合要求的范围内达到动态平衡，输出此时校园巡逻车的行驶方案，如图1。

图1 巡逻仿真系统工作流程

1.2 模型建立与求解

1.2.1 模型建立的基本思想

1.2.1.1 按照一般思路，求解如何使区域内的校园巡逻车数目最少，可将问题转化为求解如何使每一辆校园巡逻车所能管辖的道路范围最大。假设一辆校园巡逻车停靠在A（0，0）。

设当后台接收到报警电话后巡逻车的平均行驶速度是20km/h，而它正常巡逻时平均行驶速度是10km/h，当校园巡逻车收到警报后，在四分钟内能从接警位置赶到事发现场的最大距离是1km。

如上图2，假设校园巡逻车最开始停靠于道路1，2，3，4 交叉的位置A，A 点即4 条道路的中心点。我们对校园巡逻车在y 轴正半轴的道路1 上行驶的这个例子来进行分析，车辆以7km/h 的平均速度在道路1 上0 到2 之间行驶，设0 到2 之间的距离为xkm。如果报警电话从2，3，4 其他三条道路上的任意一点呼出，当校园巡逻车行驶到A 点之后便以平均速度15km/h 行驶到案发现场，在收到报警电话后的四分钟内，校园巡逻车从道路1 赶到案发现场的最大距离是(1-x)km。但是另一种情况，如果在后台接到报警电话之前校园巡逻车继续在y 轴正半轴上朝向正无穷方向行驶，那么校园巡逻车按原15km/h 行驶赶往案发现场则会超过4 分钟，也就是说这种情况下巡逻车要在收到报警电话后的4 分钟内赶往报警现场需要用更快的行驶速度，此时可计算出校园巡逻车的最大巡逻覆盖区域比车辆到达A′点时的最大巡逻覆盖区域大，就是说在巡逻车从初始点向区域的中心点行驶但未达到x=2 这个点时，校园巡逻车巡逻的区域范围越小，它的巡逻覆盖区域面积范围越大。当x=0 时，校园巡逻车的管辖范围达到最大值1km，即校园巡逻车在初始停靠点静止不动时达到最大值。

图2 一辆校园巡逻车管辖范围效果示意图

以上是对特例进行分析，道路之间互相垂直、分布对称。以下简单分析一下一般的普遍情况。

图3 所示为一般情况，道路呈不对称分布。和上图情形比起来会更为复杂，道路角度和方向都在灵活变化，建立的模型也会更加复杂。对图3 进行分析，道路1 与道路6 之间的转弯点是点D，道路1 更靠近区域中心位置，道路1，2，3，4，5 相交于区域的中心点点C。由于校园巡逻车在道路上巡逻时，行走的路线是分段直线，并不影响路径的长度，所以当校园巡逻车巡逻到D 点处（距离初始停靠的C 点xkm 远处）要求该校园巡逻车在四分钟内赶到现场处理刚刚发生的案件，最大行驶距离在(1-x)km 之内；若校园巡逻车在道路1 上继续向前行驶，则该校园巡逻车能在三分钟内赶到现场的距离继续缩小，当校园巡逻车没有行驶到D 点时，此时该校园巡逻车的最大管辖范围比(1-x)km 大，故校园巡逻车的巡逻范围越小，它的管辖范围尽量大。当x=0 时，即校园巡逻车静止不动时，一辆校园巡逻车的管辖范围能达到最大值。

图3 一辆校园巡逻车最大管辖范围分析示意图

1.2.1.2 由以上可知，当校园巡逻车的覆盖区域达到一定的大小时，即只要校园巡逻车能够符合条件（1）中的接收警报后的发车时间，就可以证明和校园巡逻车的巡逻效果对巡逻车的覆盖率没有影响，以此来确定需要配置的校园巡逻车数量的最小值。进行优化可知，模型静态状态下要想达到要求的覆盖率最少需要的巡逻车车辆数为n。此时计算出的n 是在一个几乎最优的配置方案下符合要求覆盖率90%的最少数量要求。但校园巡逻车在校内的分布情况会随着时间的变化而变化，这种动态的改变很可能导致配置的巡逻车偏离这个最优分布，从而导致巡逻车在某一些时间段内不能满足达到不低于90%覆盖率的要求。因此，我们计算动态的情况下所需要的最小车辆数一定要大于或等于在静态情形下静态优化所得到的车辆数。

这个问题我们用到动静态相结合的方法：我们用静态下的情形模拟出情况，其中的状态结果包含有静态优化过后的校园巡逻车位置图及在这种模型下所需最小的巡逻车车辆数目。然后用这个静态优化后的状态作为动态模型最开始的状态，来模拟时间的变化。时间演化的目标函数是覆盖率的增加，覆盖区域包含三个重点部位。

若在模拟过程中任何一个时间都可以达到90%及以上的覆盖率，并且能在120 秒内到达所有重点区域，则该模拟时间演化的车辆数是可行的。若不是，就应该继续增大车辆数，然后重新模拟动态优化、动态仿真，检验车辆数增加后是否符合所给出的条件，以此类推，直到符合条件要求。

1.2.2 模拟退火算法运用

根据以上内容分析，我们将该道路离散化，然后在新的地图上思考。不妨设道路交叉路口数量为N，校园巡逻车的数量为n，且任何路口都有一个对应的邻域，记Ai为第i 个路口的邻域。问题可看作是，求m 个路口，使得新地图上所有路口都各有一辆校园巡逻车时，m 个邻域的并集所含的点数最多。

△n 指的是邻域法和临点法两种算法算出解得误差值；n（C′）指的数值大的一方：n（C）指的数值小的一方。

（5）接受准则。由于为最大优化问题，所以接受准则为：

即当∆n≤0 时，则以概率exp（∆n/bT）（其中b 为控制参数，T 为冷却参数）接受新解为当前解。当∆n＞0 时，以概率1 接受新解为当前解。

1.2.3 模拟退火算法搜索结果及分析

表1 列出了在不同校园巡逻车数目下通过模拟退火算法搜索得到的优化覆盖率结果：

表1 16-20 辆校园巡逻车的优化覆盖率参数对比

分析上表数据可知，满足条件（在动态优化后的分布中校园巡逻车的覆盖率等于或大于90%）的校园巡逻车数量为20 辆。

1.2.4 运动中的环形区域切割法

之所以采用非传统的环形区域切割法，是因为传统区域分割无法将车辆间相互交换检查巡逻的灵活关系考虑在内，这会导致我们计算出的巡逻车数量偏大。出于对数据的谨慎，我们将同时兼顾切割方法和考虑到正在运动的车辆。在一指定区域内，设有若干条环形路线和若干辆校园巡逻车，每一条环线上的巡逻车都以相同的环绕方向行驶，这样一来每一辆巡逻车的覆盖区域也会随之改变，可以很好地降低覆盖区重叠率，同时也避免了巡逻车行驶导致的原覆盖区被忽略没有覆盖的情形。这样便于我们更好更加明显地得出结论，校园巡逻车的行驶方案完全可以在车辆数很少的情形之下符合要求。我们要计算出任何一个时刻巡逻车的道路覆盖率为多少，当覆盖率高于90%时就减少车辆数，反之覆盖率高于90%时就增加车辆数，直至达到一个在任一时刻下巡逻车的环绕行驶均符合上述要求的动态平衡。由上可知，分配校园巡逻车数量的关键之处在于，环形线路如何规定以及校园巡逻车如何在给定的环形线路上运动。

环形线路的确定方法：

（1）按照从外环至内环的顺序确定环线；

（2）计算给定区域边界距离环形路线最外环大概为2km 左右，即校园巡逻车在环形路线的最外环运动时的4 分钟内，覆盖区几乎到达该区域的边界；

（3）计算给定区域边界距离环形路线次外环大概为4km左右，即校园巡逻车在最外环和次外环运动时的4 分钟内，覆盖区几乎相接或者少部分重叠，依照此情形我们可以确定相邻的内环；

（4）计算给定区域边界距离最内环离环中心大概为2km左右，即校园巡逻车在环形路线的最内环运动时的4 分钟内，覆盖区域几乎将所有内环里面的道路覆盖。

校园巡逻车放置方案：

（1）将校园巡逻车均匀分配到各个环形道路上，保证放置后前后两车之间的距离大约是4km左右，已达到相邻两辆车行驶的4 分钟内运动的覆盖范围几乎相接或者有少部分重叠的效果；

（2）依照上述（1）情形放置好后，计算校园巡逻车静态条件下的道路覆盖率，如果覆盖率小于90%，则遍历道路上的点，在其中选择一点增加一辆校园巡逻车，来保证该辆校园巡逻车放置后，能使得道路覆盖率的增加值最大；

（3）重复步骤（2）直至静态条件下的巡逻车道路覆盖率能达到90%以上，且三个关键部位全都被覆盖到为止；

（4）此时得到静止条件下满足要求的情况，此时的校园巡逻车数为第一问要求的校园巡逻车数目的下限，因为一旦校园巡逻车运动，就会出现覆盖区重叠增加，从而不能满足要求的现象，校园巡逻车数目就需要增加。

动态条件下满足要求：

（1）规定所有的校园巡逻车都朝向同一环绕方向行驶（全部顺时针行驶或者全部逆时针行驶），计算所有时刻校园巡逻车的覆盖率，若有某一时刻不符合要求的情况，则校园巡逻车数量加一，直至使得该时刻符合要求情况，以此类推；

（2）定义校园巡逻车的运动步数上限为T，我们继续模拟车辆的行驶，当达到T 时，就认为本次模拟结束，如果在T 步内的任何一个时刻，都能满足题设要求，则视为目标达成。在设计的程序中不妨取T=4000 步，此时车辆在最外环至少行驶一圈以上，不难看出这是车辆运动基本达到一个动态平衡，且此时车辆继续行驶的任一时刻也都能满足题设的要求；

（3）按（1）（2）步骤处理后的校园巡逻车总数量即为符合要求的最少数量。

综上所述，校园巡逻车的行驶路线应用运动中的环形区域分割法定义，且依据以上步骤从符合要求的静止状态到最后符合要求的动态相对稳定状态。通过计算得到该问题的结果为：要想符合题设要求，则最少需要配置20 辆校园巡逻车。

2 现实因素

2.1 实际因素

因素一：事发现场并不是都在道路上。

这是很现实的问题，要想解决这一问题，要对该区域的地形有进一步深入的了解，并对整个区域进行离散化，而不是仅仅对道路离散化。并且还要考虑从道路上到事发现场（如公园或者小区内部）所花费的时间。

因素二：道路并非都是双行道

模型假设中把所有道路当作双行道来处理，其实并不是不能处理单行道的情况，而是没有实际数据，无法得知哪条道路是单行道。如果可以得到道路单双行的信息，我们建立的系统也是可以使用的，只是需要对道路多加上一个标记。原本得到的巡逻路线可能由于某条道路不能反向通行而改变。但是模型中基本的规则、做法还是可行的。

因素三：用平均速度计算与实际情况有差别

警车的巡逻速度实际上是位置与时间的函数，比如某些地段，某些时间段车流量大，交通拥挤。这些因素会影响警车巡逻的速度。如果可以大致得到这些统计数据，可以不认为警车的速度是恒定的，而是根据不同地点，不同时间有所变化的，则可以得到更切合实际的结果。

因素四：巡逻路线隐匿性

电动巡逻车的路线应具有一定的隐匿性和随机性，不可具体的预测路线，以对有作案心理的人员造成心理压力。

2.2 实际情况讨论

情况一：有多个地点同时发生案件

虽然多个地点同时发生案件的概率相当小，但是万一发生这样的事件，系统需要对这种情况进行有效的处理。比如，若一辆车的覆盖范围内同时发生两起案件，而这两个地点又都是仅仅在这一辆警车的覆盖范围内，那么，该警车处理哪起案件，如何调度其他警车到另一案件的事发现场处理案件，其他警车到该地方的接处警时间会不会过大，就是需要解决的问题。解决的办法一般是，首先根据案件性质，选择最重要的案件，由该案件反覆盖区内的警车处理；若两起案件重要性相当，则根据最短路原则，选择事发地点最接近警车的案件。再根据周围警车巡逻状态，选择另外一辆距离较近的警车，尽量减小接处警时间。

情况二：天气环境

天气相对于来说是一种不可测的条件，但它又应该纳入考虑。常见天气变化，雨、雪等也会对巡逻产生一定影响（个别的确甚至有台风、沙尘暴等恶劣天气）。在比较恶劣的天气情况下，可以将巡逻车静止守候，如同问题一。在常见天气变化时，应该根据情况改良巡逻车，减小恶劣环境对巡逻车速度的减益。或者重新获取在雨、雪天气时巡逻车的速度，再根据问题二可算出此时所需配备巡逻车的数目。

情况三：上下课人流高峰

上下课时，人流量较大，巡逻车的速度也会受到减益，但考虑到上下课时间会比较集中在课前、课后半小时内，在这短期时间内。远离人群稠密地区的巡逻车可以按正常情形来行驶。在人群稠密区内，考虑到此段时间并不会太长，且人多时间段作案的概率会大幅降低，人流量大的区域巡逻车可以暂时静止。

3 模型评价与推广

模型优点：

（1）本模型分析得比较深入，模型结构也比较清晰，其中定义的假设与引入的新概念都清晰明了且易懂，很符合我们生活中的实际情况，有利于我们对模型的理解。（2）建立模型的方法简单且容易实行，本模型应用了静态优化与动态优化相互结合的方法，其中利用了动态仿真及模拟退火算法，给出了符合不同条件下的相对而言最佳的巡逻路线。本模型的原理也十分清晰易懂，采取了启发式算法，计算原理也比较简单，模型的实用性强，故该模型具有极高的创新性和应用价值，并且应用在实际生活中它的稳定性也很好。

模型缺点：

（1）本模型在对于道路的处理过程是将道路离散化成若干个点，然后将道路当作若干个点来处理，目的是更加形象便于观察，且将道路离散成无数个点，把道路看作点的集合，这样的处理方法可以将误差忽略不计，但是在实际计算的时候，细化的点数越多我们的计算量就越大，这又有与“将误差忽略不计”的多点数离散相悖。除此之外，本模型针对不同的目标制定出的路线只是相对而言较好一点的结果，并不是所有情况下的最优路线，此处要注意。（2）由于模型中将连续的道路以250m 为一个单位进行离散化，每一条道路上并不能得到整数个节点，因此计算得到的坐标值会有一定的误差。（3）由于不依赖于该区域的地图，所以针对性不强。