文档介绍：题目警车配置及巡逻方案摘要:为了更高效的利用警务资源,本文对警车配置及巡逻方案提出了四项评价指标,即单位时间内每条道路被巡查平均次数、单位时间内每条道路被巡查次数的标准差、事件发生后警车赶到现场所用的平均时间、单位时间内所有警车对全部道路巡逻的覆盖率。同时,针对问题1~7建立了三个模型解决相关问题或优化已有方案。针对问题1:要使覆盖一定范围的警车最少,本文将问题转化成集合覆盖模型,建立了模型Ⅰ(式1)。运用启发式SCHF算法(式2)求解,得出最少需要配置20辆警车。针对问题3~6:综合考虑评价巡逻方案优劣的四项指标,建立了基于结点优先级的巡逻方案模型(模型Ⅱ)。该模型通过降低被经过结点的优先级,实现对每条道路巡逻次数尽可能均等以及巡逻覆盖范围尽可能广。具体指标值见表8。针对问题4:针对要求警车巡逻具有隐蔽性这一目标,在相邻结点优先级相等的情况下,利用离散型随机变量模型(模型Ⅲ)来随机的选取一条道路进行巡逻,使得巡逻线路无规律可循,从而实现巡逻的隐蔽性。关键词:集合覆盖模型;启发式SCHF算法;结点优先;离散随机模型▲评价:第一问将问题归结为集合覆盖问题,有创意,利用启发式SCHF算法求解,算法描述清晰,但解释不够充分,结果较理想。评价指标体系比较合理。第三问基于结点优先级巡逻方案操作性好,但思想较简单,除道路通过次数以外,未考虑多辆车的协调问题。所有各问均未给出评价指标值,是一个不小的缺憾。例如,第三问巡逻方案的结果如何?总的评价:有想法,表达清晰,但结果表达不充分,计算能力似乎要加强。1问题重述某城市拟增加一批配备有GPS***系统及先进通讯设备的110警车。110警车的平均巡逻速度为20km/h,接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求:%;而赶到重点部位的时间必须在两分钟之内。;。结合题中给定的城市道路信息,如何配置警车以及设计合理的巡逻方案需要解决以下问题:(1)若要求满足D1,该区最少需要配置多少辆警车巡逻?(2)给出评价巡逻效果显著程度的有关指标。(3)在满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。(4)在第三问的基础上,考虑D3条件,给出警车巡逻方案及其评价指标值。(5)在仅配置10辆警车的情况下,如何制定巡逻方案,使D1、D2尽量得到满足?(6)若警车接警后的平均行驶速度提高到50km/h,回答问题三。(7)给出还需要考虑的情况因素以及相应的解决方案。2问题分析求解问题1时,可根据地图数据的分布对城区进行区域划分,对相应区域分配警车,这样可能得到比本文更优的解。但考虑到本题后续问题的求解,该方法在很大程度上不理想。首先,整个区域丢失了部分拓扑关系,在解决问题4、5时优化空间减少。其次,针对数据设计的解决方案,缺乏理论依据,不能解决一般性问题。考虑使用Floyd算法结合贪心算法求解问题1,由Floyd算法计算得到各路口两两间的最短路径,然后经过贪心计算得到第一辆警车的位置。为了不出现警车间管辖范围出现重叠,此时应删除已被覆盖的路口结点,更新剩下结点的拓扑关系,依次重复直到所有结点均被覆盖。由于Floyd算法的时间复杂度为,可知整个算法的时间复杂度为,显然在时间上不可取。而且该算法在数据特殊的情况下可能出现“岛屿”现象。所谓“岛屿”,即在某些结点周围的所有结点均优先被警车覆盖掉,剩下的稀散点间失去拓扑,形成部分孤点。鉴于此,本文采用启发式SCHF算法,较好地解决了上述存在的问题。巡逻方案直接影响巡逻的效应,设计一个合理有效的巡逻方案可以增强发现犯罪的能力,降低和减少可防性案件的发生。问题中除3个重点部位,其他结点发生事件的概率假设均相等,所以设计的巡逻方案应使警车尽量均匀分布在城区,而且尽量避免短时间内重复巡逻相同结点。据此,可提出、、和等评价指标来衡量巡逻方案的优良性。结合计算机操作系统中的进程调度策略,赋予城区路口优先级,为了避免OS中出现的“饿死”现象,在巡逻过程中动态改变结点的优先级,可以使巡逻效果达到最佳。为实现巡逻规律具有一定的隐蔽性,考虑让警车在其管辖范围内随机地进行道路的选择,使其巡逻路线不拘泥于常规。3基本假设(1)同一时间不发生两起以上的事件;(2)在每辆警车所管辖的区域范围内,事件发生的概率相等;(3)除去重点部位外,认为每条道路的重要性均相等;(4)所有道路均为双行道;(5)城区道路交通状况良好,警车以恒定的速度行驶。(6)假定所有事发现场均在道路上;(7)相邻两个交叉路口之间的道路近似为直线;4符号说明:该地区配置警车的数量;:该地区结点总数:该地区道路总数;:该地区所有道路的集合;:该地区所有结点的集合;:在第个结点上停放警车所能影响结点