警车配置及巡逻方案.doc

全国第六届研究生数学建模竞赛题目110警车配置及巡逻方案摘要:针对110警车配置及巡逻方案问题,通过引入算法、贪心算法以及捕食者算法等相应知识,建立了警车优化配置的搜索模型,然后利用软件求解,得出满足相关要求的结论。首先将巡逻方案问题转化为图论中节点与边的覆盖问题,通过调整节点的覆盖率来调整道路的覆盖率,研究了在满足相关出警条件下,警车巡逻的道路覆盖率、巡逻方案的路线,以及提出了刻画巡逻效果显著程度的个指标:节点覆盖率、道路覆盖率、规定时间内单位车辆走过的不同节点数和规定时间内单位车辆走过的不同道路数,然后根据上述引入的相关算法,搜索出符合条件的结论,静态时最少需配置14辆警车,而动态时需17辆警车,具体巡逻路线及相关评价指标值参见正文。最后考虑了影响巡逻效果的各种因素及情况,提出了警车巡逻的增援模型,并给出了求解的算法与策略。关键词:警车优化配置贪心算法捕食者算法增援模型参赛密码(由组委会填写)参赛队号队员姓名仲伊刘文杰刘祥鹏目录摘要 队员姓名仲伊刘文杰刘祥鹏目录摘要 一、问题重述 3二、问题分析 : ..................................................................................................5三、问题假设 5四、符号说明 5五、模型建立与求解 19参考文献: 22附录1 23附录2 24附录3 26附录4 ,既能够对违法犯罪分子起到震慑作用,降低犯罪率,又能够增加市民的安全感,同时也加快了接处警(接受报警并赶往现场处理事件)时间,提高了反应时效,为社会和谐提供了有力的保障。考虑某城市内一区域,为简化问题,假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为:(5112,4806),(9126,4266),(7434,1332)(见下图红点部位,蓝色部分为水域,道路数据见附件,相邻两个交叉路口之间的道路近似认为是直线)。某城市拟增加一批配备有GPS***系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h,接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求:%;而赶到重点部位的时间必须在两分钟之内。;。请回答以下问题:,该区最少需要配置多少辆警车巡逻?。。四..在第三问的基础上,再考虑D3条件,给出的警车巡逻方案及其评价指标值。,应如何制定巡逻方案,使D1、D2尽量得到满足?,回答问题三。、哪些情况需要考虑?给出你们相应的解决方案。,在满足出警要求的相关要求的情况下,寻求所需要的最少警车数、每辆警车的巡逻路径以及评价指标值。,而赶到重点部分的时间必须在两分钟之内的条件下,求该区最少需要配置的警车数。首先把城区地图抽象化为一个无向赋权图,图中节点为交叉路口,边为城区街道,将警车巡逻问题转化为图论中图的节点、边等覆盖问题,利用算法处理相关数据。然后通过假定每条道路上案件发生的概率相同,将“警车在接警后三分钟内赶到现场的比例不低于”转化为图论中的数学约束条件,即警车接警后所能到达的道路条数占总道路条数的比例不低于,而“赶到重点部位的时间必须在两分钟之内”作为首先满足的条件,进而把研究道路条数的覆盖问题转化为研究交叉口节点的覆盖问题,利用节点覆盖率的调整来达到道路条数的覆盖范围不低于的要求。最后分析知在静态状态下,即定点巡逻时所需配置的警车数量最少,故通过引入贪心算法思想来求出所满足条件的最少警车数及其初始坐标位置。,而警车巡逻的目的是起到震慑作用,降低犯罪率,增加市民的安全感,因此衡量巡逻效果显著程度的指标应围绕这个目的而定,故依据警车在接警后三分钟内赶到现场百分比的要求,选取巡