1、题 目 110 警车配置及巡逻方案摘 要：本题主要讨论的是社会安全系统中警车的优化配置及巡逻方案的合理安排问题。该问题可以采取静态优化和动态优化相结合的方法，利用模拟退火算法和动态仿真，给出满足不同条件下的相对最优巡逻路线。模型建立的主要过程是：首先对道路和重点区域进行合理离散化，使得二维的道路转化为一维的点来考虑；再根据离散化后得到的新地图计算出各个离散道路点的邻域；然后对静态过程使用模拟退火算法得到静态优化值；最后根据不同的目标和需求，通过对动态过程进行仿真，从而得到最后满足要求的动态优化值，并按照问题要求给出所需的评价值和合理的警车巡逻方案。问题一只考虑覆盖率和重点区域保护的条件，我们利
2、用上面的模型可以算出动态情况下最少只需 18 辆车即可。在问题二中，我们定义了多种巡逻效果指标，包括覆盖率、巡逻到达率、平均巡逻强度及其均方差，并详细地分析了它们对巡逻效果的影响。在问题三中，我们同时要求考虑覆盖率和巡逻效果指标要求，得到警车数量为 30 辆。问题四是在问题三的基础上，加入了隐蔽性的要求，我们引入了随机因素，并从单步规律性和整体规律性两个方面分别进行了解释，利用单步概率转移矩阵和分形维数两种衡量标准，并对其进行了分析。第五问是给定警车数量，寻找尽量满足覆盖率和巡逻指标的巡逻方案。第六问在警车速度提高的前提下，利用仿真模型得到 26 辆警车的巡逻方案是较为优化的解。最后一问属于开
3、放性题目，我们讨论了多处同时报警、0-1 规划等问题。该模型原理清晰易懂，采用启发式算法，计算比较简单，通用性强，优化性能显著，稳定性也较好。关键词：模拟退火算法 动态仿真 分形维数 平均巡逻强度 多目标规划 评价：1、考虑人口 密度与巡逻强度关系，反映思考深度。2、基本算法是模拟退火算法，对方法的理解有较充分的表现，算法描述清晰。3、优化算法是贪心算法，偏简单。结果表达完整。4、指标考虑较全面，包括覆盖率、巡逻到达率、平均巡逻强度及其均方差，体现了对问题有较深刻的理解。5、第三问结果完整，可信度高。6、用分形维数度量巡逻路线的隐蔽性，似乎不必要。7、总体来看，对问题及所用方法理解较深刻，指标
4、考虑全面，算法应用较熟练，效果较好，反映作者有较强的建模能力。结果表达清晰，有说服力。文章表达清晰，流畅，是一篇优秀的竞赛论文。一 问题的重述与分析211 问题的重述110 警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806） ， （9126， 4266） ， （7434 ，1332） （见下图红点部位，蓝色部分为水域，道路数据见附件,相邻两个交叉路口之间的道路近似认为是
5、直线） 。图 1： 区域道路和路口信息地图某城市拟增加一批配备有 GPS 卫星定位系统及先进通讯设备的 110 警车。设 110 警车的平均巡逻速度为 20km/h，接警后的平均行驶速度为 40km/h。警车配置及巡逻方案要尽量满足以下要求：D1. 警车在接警后三分钟内赶到现场的比例不低于 90；而赶到重点部位的时间必须在两分钟之内。D2. 使巡逻效果更显著； D3. 警车巡逻规律应有一定的隐蔽性。请回答以下问题：一若要求满足 D1,该区最少需要配置多少辆警车巡逻？二请给出评价巡逻效果显著程度的有关指标。三请给出满足 D1 且尽量满足 D2 条件的警车巡逻方案及其评价指标值。四在第三问的基础上
6、，再考虑 D3 条件，给出警车巡逻方案及其评价指标值五如果该区域仅配置 10 辆警车，如何制定巡逻方案，使 D1、D2 尽量得到满足？ 六若警车接警后的平均行驶速度提高到 50km/h，回答问题三。七你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。12 问题的分析本题主要讨论的是社会安全系统中警车的优化配置及巡逻方案的合理安排3问题。在确定需配置警车的数目和巡逻方案时，首先要考虑的问题应是怎样在满足接警时限要求的前提下，用尽可能少的警车最大限度地覆盖城市道路。同时，需要在使巡逻效果尽可能显著的目标下对巡逻道路进行具体规划及对警车进行合理调度。另外，该问题中的模糊概念有很多，需要
7、我们通过自己的理解和对资料的查询对其进行合理的假设和定义。第一，道路的合理离散化问题和重点部位的处理问题。题目中已经明确指出假定所有事发现场均在道路上，但是由于道路是连续的，且题目所给的数据均是交叉路口的坐标，使得我们处理问题时存在困难，所以为了方便处理，我们可以将道路合理离散化，把每条道路离散成若干个点，然后把这些新增加的点作为新的路口，由此得到一张新的道路地图。另外，题目中给出了三个重点部位的坐标，很明显的，这三个重点部分并不是都在交叉路口或者道路上，所以我们在处理时需要对其进行近似处理，把不在道路上的点近似到离该点最近的道路上，然后再对该条道路进行离散化处理。这样处理后的道路地图如下所示
8、：图 2：道路离散图第二，警车的巡逻模式问题。题目中并未明确说明在巡逻过程中警车是否必须始终处于运动状态，需要我们自己理解。如果假设警车在巡逻过程中不是始终处于运动状态，那么从耗费的角度来说也许会比较好，而且针对第一问计算出来的警车数目也许会比较少，但是从实际出发，我们认为这样的假设却是不可行的。题目中指出警车在道路上巡逻，既能够对犯罪分子起到震慑作用，又能够增加市民的安全感，同时也加快了接处警时间，提高了反应时效。并且我们通过查询实际生活中警察的巡逻路线发现，要求警车在巡逻过程中始终处于运动状态是更加合理更加贴近实际的，这样可以使巡逻效果更显著。第三，邻域和覆盖率概念的提出。为了处理方便，针
9、对此题目，我们提出了邻域和覆盖率的概念。其中，每个路口的邻域是指，以该路口为中心点，在接警后三分钟内能够到达的路口点的集合，也就是说该邻域内任一点到中心点的最短路小于警车以接警速度行驶 3 分钟的路程。对于道路离散化后得到的路口点也有相同的定义。另外，我们还提出了覆盖率的概念。覆盖率是指所有警车在接警后 3 分钟内可以到达的道路（线段）长度之和与图中所有道路总长度Comment W1: 有一定道理。体现思考深度。Comment W2: 是一种可行的处理方法4之比。那么把道路合理离散化后以点来考虑，则覆盖率又可定义为所有警车邻域的并集所包含的点数与总的点数之比。虽然覆盖率分别以线和点来定义有所不
10、同，但是当离散逐步细化后，以点定义的覆盖率也将逐渐逼近于以线定义的覆盖率。当离散细化到一定程度后，这种误差可以忽略不计。这种处理方法可以在满足精度的条件下，将问题的规模降维（由线降为点） ，进而难度大大降低。第四，巡逻效果指标的理解问题。题目中要求所设计的方案使巡逻效果更加显著，我们认为巡逻效果指标包括覆盖率、巡逻到达率、平均巡逻强度及其均方差等等，而平均巡逻强度及其均方差又与巡逻次数和相对人口密度值有关。其中，覆盖率上文已给出相关定义。如果在正常巡逻的路线中，至少有一辆警车到达过某个离散道路点，则称该点为到达点。对于整个系统，所有的到达点数占总离散点数的比例称为该方案的巡逻到达率。巡逻次数是
11、指在不影响接警后到达时间的基础上，警车正常巡逻时各个离散道路点点的被巡逻次数。另外，由于在实际情况下不同街道的人口密度（数量）不同，我们认为在讨论巡逻效果指标时还需要考虑人口密度，人口密度大的地方需要的巡逻强度高于人口密度低的地方。在本题中，我们假设某点的人口密度正比于该点附近一定距离内的街道密度，那么可以定义某点的相对人口密度值为：以该点为中心，以半径r的圆所覆盖的道路的总长度。当把道路合理离散化后，其相对人口密度值即为相应圆所覆盖的离散点的个数。例如下图所示的两点 A和 B：图 3：人口密度示意图按照上面的定义方法，它们的人口相对密度分别为 18和 43。平均巡逻强度及其均方差的定义与巡逻
12、次数和相对人口密度值有关，定义起来比较繁琐，具体方法见第四部分。综上所述，我们认为要想使巡逻效果越显著，就要相应地使覆盖率、巡逻到达率、平均巡逻强度及其均方差的加权函数越大，具体分析见第五部分。第五，巡逻规律隐蔽性的理解。题目要求警车巡逻的规律要有一定的隐蔽性，对于线路的隐蔽性，我们可以理解为线路的复杂性和无规律性。也就是说如果希望线路的隐蔽性好，我们就需要选择分岔路口相对较多的巡逻线路，并且同一警车每次的巡逻路线可以有些不同，主要体现在所走的交叉路口的先后顺序方面。比如图 4中的两条路线，假设它们都是属于同一点的邻域内，那么按照我们对隐蔽性的理解，警车会选择第二条路线，并且每次巡逻时可以选择
13、不同的走法，也就是说第一次巡逻可以选择 ABCDE 的走法，第二次可以选择 ACEDB 的走法。我们对单步规律性和整体规律性分别进行了讨论，具体分析见第六部分。5ABCDE图 4：隐蔽性解释第六，关于几个问题的理解。对于第一问，只需考虑满足条件一中关于出警时间的要求，从而确定最少需要配置的警车数量。对于第二问中评价巡逻效果显著的指标，上文中已进行了较详细地说明。对于第三问，需要考虑完全满足条件一和尽量满足条件二的警车巡逻方案，并且针对该方案，我们还需要给出在第二问中所提出的巡逻效果的具体指标值。对于第四问，是在第三问的基础上再加上条件三中隐蔽性的限制，从而给出警车巡逻方案及其具体指标值。第五问
14、中是确定警车数量为 10 辆的前提下，寻找尽量满足条件一和条件二的警车巡逻方案。第六问中是在警车接警后的平均行驶速度提高到 50km/h 的条件下，寻找完全满足条件一和尽量满足条件二的警车巡逻方案。第七问是一类开放性问题，考察我们考虑问题的全面性，具体分析见第九部分。通过上面的分析，我们认为该问题可以采取静态优化和动态优化相结合的方法，利用模拟退火算法和动态仿真，给出满足不同条件下的相对最优巡逻路线。主要的处理过程是：首先对道路和重点区域进行合理离散化，使得二维的道路转化为一维的点来考虑；再根据离散化后得到的新地图计算出各个离散道路点的邻域；然后对静态过程使用模拟退火算法得到静态优化值；最后根
15、据不同的目标和需求，通过对动态过程进行仿真，从而得到最后满足要求的动态优化值，并按照问题要求给出所需的评价值和合理的警车巡逻方案。二问题假设1 假设每辆警车在巡逻过程中始终处于运动状态，且以平均巡逻速度匀速行驶。2假设每辆警车只会在图中所示道路上行驶，且只会在路口处转弯，3假设事故只会出现在城市道路上，不会出现在区域里。4. 假设在同一时刻该城市道路上只会出现一次事故，且出现事故时一定会报警。4假设警车在巡逻过程中不会由于天气或路况等外部原因而影响其正常巡逻。5假设巡逻警车接警后到达报警地点所走的路线均为最短路线，且到达报警地点后一定可以解决问题。6. 假设每辆警车均有相同的处理事件能力，且每
16、次事故只需一台警车即可解决。7. 假设各辆警车之间可以通过卫星定位系统及通讯设备保证正常通讯。8. 假设道路越密集的区域，人口数量越大，反之越小。三符号说明表示离散道路点i的邻域；iA6表示经过离散化后的离散道路点的总数；N代表瞬时覆盖率，表示对于每一个时刻所定义的覆盖率；cp代表平均覆盖率，表示一段时间范围内的瞬时覆盖率对时间取平均值；c表示某个巡逻方案的离散道路点的到达率；vp表示某个巡逻方案中点 i 是否为到达点，若点 i 为到达点，则对isted其赋值为 1，反之为 0；表示第 i 个离散点处的到达次数；patroli表示第 i 个离散点处的人口密度；un表示第 i 个点的巡逻强度，它
17、定义为人口密度和到达次数的比值；streghi表示平均巡逻强度；表示平均巡逻强度的均方差；s表示分形维度，反映了图形的复杂性，其值越大，该图形的复杂性就越d大。四问题一的分析及结果4.1 模型建立的总体思想第一问只要求满足条件一中关于出警时间的要求，即只需要覆盖率达到一定要求，可与巡逻效果无关，从而确定最少需要配置的警车数量。因此可以先针对警车为静态的情况进行优化，得到静态时为达到覆盖率要求所需要的最少车数 n。此时得到的 n 是在一个接近最优的分布下满足覆盖率的最小要求。但处于实际情况和前文中的假设，警车必须始终以一定的速度进行巡逻，那么随着时间的演化，警车的分布是动态变化的，就有可能偏离这
18、个优化分布，进而在某些时段内不能满足覆盖率的要求。因此，考虑动态情况时所需的最小车辆数一定大于或等于静态情况时优化得到的车辆数。对本问的处理可以采取静态和动态相结合的方法：首先利用静态优化得到一个结果状态，包含了所需的最少车辆数以及这个优化状态的车辆位置分布。其次，以这个状态作为动态仿真的初始状态，对时间进行演化。演化的目标函数为：（1）覆盖率的增加；（2）三个重点部位必须被覆盖。如果演化时段内各个时刻的覆盖率都能够达到 90%的要求，且重点区域都能在两分钟内到达，那么这个车辆数就是可行的。反之，则应增加车辆数。再利用动态仿真，优化和检验增加车辆数后是否能满足相应条件。这个迭代过程一直到第一次
19、满足要求为止。总的过程如下图所示：Comment W3: 体现对方法的理解。7初始状态最终结果动态仿真优化静态优化结果模拟退火搜索图 5：问题一的优化流程4.2 静态优化中的模拟退火算法 1静态优化的情况，实际上是个优化组合的问题。优化组合的问题已经有多种不同的处理方案。但由于问题本身的 NP复杂性，当问题规模大到一定规模时，不一定能得到最优化的结果。尽管如此，优化组合方法中的模拟退火算法，具有渐近收敛性，在理论上已被证明是一种以概率 1收敛于全局最优解的全局优化算法。因而我们可以采用模拟退火方法，在可以承受的时间花费，得到静态优化解。模拟退火算法来源于固体退火原理，它由初始解 i 和控制参数
20、初值 t 开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减 t值，算法终止时的当前解即为所得近似最优解，这是基于 Metropolis迭代求解法的一种启发式随机搜索过程。模拟退火算法依据 Metropolis准则接受新解，除了接受优解外，还在一个限定范围内接受差解，这正是模拟退火算法与局部搜索算法的本质区别。模拟退火算法与初始值无关，算法求得的解与初始解状态 S(算法迭代的起点)无关。模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率 1收敛于全局最优解的全局优化算法，且它具有并行性。4.2.1 模拟退火算法描述首先按照问题分析中所提到的，在道路离散化后所得到的新
21、地图上考虑问题。设有 m辆警车和 N个交叉路口，对于每个路口有一个邻域，并记第 i个路口的邻域为 。我们的目标是要寻找 m个路口，使得当每个路口有一辆警车时，iAm个邻域的并集所含的点数最多。（1） 解空间：解空间 可表示为从 中选出 m个元素的所有可能组合的1,N集合，即 1,| , ,1, miijCccfori 初始解可以选为 。所有状态的转移都是在解空间里进行的。0（2） 目标函数：任一集合 中的元素个数计为 。此时目标函数为 m个ALENA邻域的并集的元素个数的极大值，即求 11ax(,)()imcnc （3） 新解的产生。当前解 。对于任一辆车，不妨设为第 i辆车，,C其现在处在路
22、口 。这时新解的产生有两种方法：（a）邻点法：在 的ic icComment W4: 算法描述清晰。8相邻点中任选一点 ，新解为 ;(b)邻域法：在 的邻ic1,imCc ic域内任选一点 ，新解为 。在算法中将上述两种方法ii 交替使用。（4） 目标函数差： ()n（5） 接受准则。由于为最大优化问题，所以接受准则为： 1, 0exp(/),PbTn即当 时以概率 1接受新解为当前解。当 时，则以概率0n接受新解为当前解。其中 为控制参数， 为冷却参数。4.2.2 模exp(/)bT拟退火算法搜索结果及分析下表列出了在不同警车数目下通过模拟退火算法搜索得到的优化覆盖率结果：表 1：模拟退火算
23、法搜索结果警车数目 优化覆盖率(%)12 81.0313 84.5214 86.6415 89.3716 90.89从表中的结果可以看出，当警车数目达到 16辆时，在优化分布下已经可以满足覆盖率大于 90%的要求。根据前面的分析，我们将以这个结果为初始状态进行动态仿真优化。4.3 动态优化中的仿真模型计算机仿真模型 2的建立一般可以分为两种方法：时间步长法和事件步长法。时间步长法就是按照时间流逝的顺序，一步一步地对系统的活动进行仿真。在整个仿真过程中，时间步长固定不变。事件步长法是以事件发生的时间为增量，按照事件发生的顺序，一步一步地对系统的行为进行仿真，直到预订的时间结束为止。本题要求的警车
24、随时间演化的巡逻方案，因此应采用时间步长法建立仿真模型。当采用时间步长法做计算机仿真时，其基本步骤为：首先选取系统的一个初始起点为仿真时钟的零点，然后根据实际问题的需要，选定一个时间步长。于是从仿真时钟的零点开始，每推进一个时间步长，就对系统的活动和状态按照预订的规则和目的的进行考察、分析、计算和记录，直到预定仿真结束时刻为止。4.3.1仿真模型的建立（1）选定时间步长。时间步长可通过下述方式确定。首先，对于输出结果的要求，仿真结果要求每个时间间隔 1分钟输出一次各警车的位置坐标，因此仿真时间间隔至少要9小于 1 分钟，并且最好为 1 分钟的因子，使得每个输出时刻同时也是仿真经历的离散时刻。其
25、次，由于警车巡逻时可能会在路口处转弯，那么在时间步长内警车巡逻的路程长度必须短于所有路段的最小长度。综合考虑上面两个因素，当警车巡逻速度为 20km/h 时，时间步长可以取为 10s.(2) 推进原则为了解决实际问题，我们将道路离散化成点，这相当于增加了交叉路口的数量。根据我们的假设，警车只有到实际的路口（即原有的交叉路口）才存在选择路径的问题。为了避免短距离的贪心算法导致的局部最优的情形，我们在为警车选择路线时，考虑的不是下一个点，而是下一个实际的路口。当警车位于某个实际的交叉路口时，计算如果警车位于与该路口直接相邻的各个路口整体的覆盖率，选择覆盖率最高的方向，而且我们允许车在路口进行掉头。
26、4.3.2 仿真运行结果及分析下面的两个表格给出了仿真结果（4 小时）的统计信息。表 1 为警车数量不同时不同覆盖率所占的百分比信息。可以看出，当有 16 辆警车巡逻时，覆盖率达到 90%以上的时段只有 6.1%。也就是说随着时间的演化，系统状态很大程度上偏离了静态优化的状态结果。由于假设警车始终是处在运动状态的，故静态优化的结果并不能满足题目要求，由此可以看出静态优化算法在处理此类问题时的局限性。当车数再增加一台为 17 辆时，情况得到很大的改善：90%以下的比例只占到 5.55%。当车数达到 18 时，则在所有仿真时段内，90%的覆盖率目标都可以得到满足。对于题目的不同理解会得到不同的最小
27、车数。如果是要求在所有仿真时段内平均覆盖率达到 90%，那么 17 辆警车既可满足要求（表 2） 。当理解为任一时刻覆盖率达到 90%，那么 18 辆警车为最少配置。表 2：仿真结果在不同覆盖率区间的分布覆盖率(%) 16 车 17 车 18 车8687 0.416378 0 08788 1.249133 0 08889 30.67314 0 08990 61.276 5.5517 09091 6.10 56.83553 1.4573219192 0 36.91881 30.117979293 0 0.485774 65.301879394 0 0 3.053435表 3：统计信息表百分比（）
28、 16 车 17 车 18 车平均覆盖率 89.2 90.8 92.290%以上时刻的比例 6.1 94.3 100图 6 中给出了当警车数量为 18 辆时，4 小时内各个警车的巡逻轨迹图。虽然这时满足了覆盖率和保护重点部位的要求，但警车巡逻的范围较小。如果将Comment W5: 表达完整。Comment W6: 问题理解较深刻10威慑作用理解为与巡逻到达范围的大小相关的话，那么此时的巡逻方案一定不是比较好的结果。这时就需要考虑除覆盖率以外的指标对巡逻方案进行优化。具体内容见下文。图 6：警车数量为 18时，各个警车的巡逻轨迹五问题二和问题三的分析及结果51 问题二的指标分析由问题一的结果可
29、以看出，如果仅仅以条件一作为优化目标，得到的巡逻轨迹并不理想，有些警车的巡逻路线太短，仅局限在比较狭小的区域内。这时就必须考虑其它评价巡逻效果的指标。在问题分析中，我们已经说明了巡逻效果指标包括覆盖率、巡逻到达率、平均巡逻强度及其均方差等等，并且给出了相应的定义。为了表述的连贯性，我们再次叙述其定义并分别对其进行分析：5.1.1覆盖率覆盖率是一个重要的指标。在问题一中仅仅考虑了这一个指标作为优化目标。覆盖率是指所有警车在接警后 3分钟内可以到达的道路（线段）长度之和与图中所有道路总长度之比。那么把道路合理离散化后以点来考虑，则覆盖率又可定义为所有警车邻域的并集所包含的点数与总的点数之比。虽然覆
30、盖率分别以线和点来定义有所不同，但是当离散逐步细化后，以点定义的覆盖率也将逐渐逼近于以线定义的覆盖率。当离散细化到一定程度后，这种误差可以忽略不计。这种处理方法可以在满足精度的条件下，将问题的规模降维（由线降为点） ，进而难度大大降低。简单来说，覆盖率就是警车在接受报警后规定时间内赶往现场处理事故的能力。覆盖率越大，警察能掌控的有效面积就越大，巡逻效果越好。覆盖率有瞬时和平均之分。对于每一个时刻，定义的覆盖率称为瞬时覆盖率，表示为 。cp若把一段时间范围内的瞬时覆盖率对时间取平均值，则称其为平均覆盖率，表示为 。cp5.1.2巡逻到达率如果在正常巡逻的路线中，至少有一辆警车到达过某个离散道路点，则称该点为到达点。对于整个系统，所有的到达点数占总离散点数的比例称为该巡
