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