研究生数学建模--110警车巡逻方案讲解

12009年全国研究生数学建模竞赛D题110警车配置及巡逻方案110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332）（见下图红点部位，蓝色部分为水域，道路数据见附件,相邻两个交叉路口之间的道路近似认为是直线）。某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：D1.警车在接警后三分钟内赶到现场的比例不低于90％；而赶到重2点部位的时间必须在两分钟之内。D2.使巡逻效果更显著；D3.警车巡逻规律应有一定的隐蔽性。请回答以下问题：一.若要求满足D1,该区最少需要配置多少辆警车巡逻？二.请给出评价巡逻效果显著程度的有关指标。三．请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四..在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。五．如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。第三、五、六问的巡逻方案结果请按规定格式分别存入文件“队号-Result3.txt”、“队号-Result5.txt”及“队号-Result6.txt”中。[[[[注]]]]必须严格按照以下格式保存结果数据，评阅论文时将用计算机验证你们的结果，作为评分参考依据。在电子文档中（纸质版中仅需要提供警车巡逻方案及其评价指标值）以附录形式提供第三、第五、第六问中白天任意连续4小时内的各警车的正常巡逻位置数据，巡逻位置数据请按规定格式分别保存为文本文件，文件名分别为：队号-Result3.txt、队号-Result5.txt和队号-Result6.txt，时间间隔为1分钟，即每隔1分钟记录下各警车位置，每辆警车的位置数据用(xxx,yyy)表示，不同警车间的位置数据用“，”隔开，第1辆警车位置与时间之间用“，”隔开，各个时刻的最后一辆警车位置数据后不加“，”，每一时刻的数据另起一行，文件以End结尾，数据格式为：警车数目，评价指标值时间1111，警车1111位置，警车2222位置，……警车nnnn位置时间2222，警车1111位置，警车2222位置，……警车nnnn位置3……EndEndEndEnd例如：假设有警车4辆，评价指标值为m1，m2，…，在0s时都位于各自起点(xi,yi)，1分钟时，位置分别为(a1,b1),(a2,b2),(a3,b3),(a4,b4),2分钟时，位置分别为(c1,d1),(c2,d2),(c3,d3),(c4,d4),则此时文件记录为：4444，m1m1m1m1，m2m2m2m2，…0,0,0,0,(x1,y1),(x2,y2),(x3,y3),(x4,y4)(x1,y1),(x2,y2),(x3,y3),(x4,y4)(x1,y1),(x2,y2),(x3,y3),(x4,y4)(x1,y1),(x2,y2),(x3,y3),(x4,y4)1,(a1,b1),(a2,b2),(a3,b3),1,(a1,b1),(a2,b2),(a3,b3),1,(a1,b1),(a2,b2),(a3,b3),1,(a1,b1),(a2,b2),(a3,b3),(a4,b4)(a4,b4)(a4,b4)(a4,b4)2,(c1,d1),(c2,d2),(c3,d3),(c4,d4)2,(c1,d1),(c2,d2),(c3,d3),(c4,d4)2,(c1,d1),(c2,d2),(c3,d3),(c4,d4)2,(c1,d1),(c2,d2),(c3,d3),(c4,d4)……EndEndEndEnd4全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛全国第六届研究生数学建模竞赛题目110110110110警车配置及巡逻方案警车配置及巡逻方案警车配置及巡逻方案警车配置及巡逻方案摘摘摘摘要：要：要：要：巡逻勤务是对社会治安进行动态管理的一种勤务方式,要求对社会面做到全时空控制。110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警时间，提高了反应时效，为社会和谐提供了有力的保障。本文根据某一区域的数据地图，在满足所给要求D1、D2、D3的情况下，给出求解警车配置及巡逻方案。由于交叉点众多，导致线性方程组复杂难解，因此采用离散化策略，将地图细分为相邻点距离不超过200米图集。对于问题一我们考虑它的静态状况，将此问题转化问P-中心问题，应用遗传算法求解。我们得到满足D1条件时该区最少需要配置16辆警车巡逻。对于问题二我们给出了评价巡逻效果显著程度的有关指标。而对于之后的问题，均牵扯巡逻问题，警车均为动态，我们采用贪婪策略来处理，得到了四种不同要求下的警车巡逻方案及其评价指标值。最后根据我们的模型和我们的理解，对当前警车巡逻等方面提出了一些具有实际意义的建议。关键词：关键词：关键词：关键词：巡逻方案；P-中心问题；遗传算法；贪婪策略参赛队号1190319队员姓名龚云路、周立刚、张家健参赛密码（由组委会填写）（由组委会填写）（由组委会填写）（由组委会填写）5110110110110警车配置及巡逻方案警车配置及巡逻方案警车配置及巡逻方案警车配置及巡逻方案一、一、一、一、问题重述问题重述问题重述问题重述110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332）。某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：D1.警车在接警后三分钟内赶到现场的比例不低于90％；而赶到重点部位的时间必须在两分钟之内。D2.使巡逻效果更显著；D3.警车巡逻规律应有一定的隐蔽性。请回答以下问题：一.若要求满足D1,该区最少需要配置多少辆警车巡逻？二.请给出评价巡逻效果显著程度的有关指标。三．请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。五．如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。二、背景与分析二、背景与分析二、背景与分析二、背景与分析警察勤务[1]是指警察机关完成警察任务，以最有效的方法，组织和运用警力，履行警察职责的一切有计划有规律的活动。纵观世界各国，警察勤务可分为五种：巡逻、临检、守望、值班、备勤。其中巡逻为最基本的勤务方式。警察巡逻勤务是6警察部门为完成自身任务的需要，运用巡逻工作方法，对社会面进行动态控制的一种勤务方式。当前，由于街面管理和防范工作相对滞后于社会经济的发展，各种隐藏的不安定因素增多，街面治安问题日趋复杂。一方面是不法分子在街面的违法犯罪活动越来越猖獗。街面的宽阔空间给不法分子以作案快、逃逸快的有利条件，所以一些不法分子越来越多地将作案地点选择在街面，严重威胁着老百姓的安全感。另一方面是街面刑事治安案件不断上升。这样就更显得进行街面巡逻的重要性及必要性。要使巡逻勤务达到对社会治安进行良好动态管理的目的，就要求对社会面做到全时空控制。这样对巡区的设计与规划，就要根据城市的实际情况和需要，以及巡警的实际勤务能力来划分巡逻区域和各组巡逻范围、规定巡区的安全保卫等级、确定巡逻警力及编组、选择合适的巡逻执勤方式，最终形成适合的巡逻工作方案。警察巡逻活动的目的有两个:一是即时打击犯罪；二是即时服务群众。其出发点都是追求“第一时间的有效快速反应”，即警情反应速度。警情反应速度，是指从接警到警察赶赴现场的时间。警情反应速度越快，制止和抓获犯罪的效率就越高。正是警情反应速度对犯罪的重要控制作用，使得世界第三次警务革命的立足点将警力重点摆在街面上，以缩短警察赶赴现场的时间。从城市治安安全角度而言，警情反应速度是考察城市治安控制力状况的重要指标。随着我国三十年的改革开放，经济和社会状态都发生了很大的变化，各地社会治安形势日益动态化、复杂化，以往那种在计划经济体制下形成的，以静态管理为主的治安管理方式、方法和手段，己越来越不适应新形势的发展和治安状况的需求。因此，在目前新形势下急需治安管理方式、方法进行转变。另外，根据西方警界的研究结果，公众的公共安全感和满意度，很大程度上并非源于警察的破案数、破案率或其它业务行动的结果，因为大多数情况下，公众对这些结果没有直接的感受，他们的安全感和满意率往往来源于身边的巡逻警察[2]。因此，构建巡逻格局就是要扩大警察时空的覆盖面，使警察无处不在，无时不在。通过街面巡逻，加强社会面控制和威慑，维护公共安全和公共秩序；通过街面巡逻，及时发现和调节群众纠纷，开展社会救援活动，为群众排忧解难，树立人民警察的良好形象；通过街面巡逻，充分宣传、发动和组织群众参与社会治安管理，及时掌握治安动向，把专门工作与群众工作有机的结合起来，变有限警力为无限警力。由于科技的发展，现代巡逻方式和巡逻所需配备设置都有了很大的改变。现在很多城市都用上了GPS巡逻车系统[3]。GPS巡逻车系统是公安部门指挥调度系统的一个重要组成部分，是一个功能完善、技术先进、设备可靠的系统，他的建立对车辆的指挥调度、实时监控、防盗反劫等方面起到积极的促进作用。通过警用GPS管理系统，可以实现对警车的统一监控、管理、指挥，提高警务工作的效率。实现了对警车的精确指挥调度、实时监控。保障了人民警察能够安全、迅速、准确地执行治安巡逻、治安防范的任务。因此，该城市警方在增加一批配备有GPS卫星定位系统及先进通讯设备的110警车后，通过配置合理的巡逻路线，对于接报、处理治安、刑事案件的效率将会有很大的提高。7在对模型的建模和求解过程中，由于交叉点众多，导致线性方程组复杂难解，我们采用离散化策略，将地图划分为相邻距离不超过200米的点集。另外，对于三个重点部位，由于都不在道路上，我们假设这三个点和它们附近的交叉点都有直接通路可以到达。对于问题一中的警车配置问题，由于D1条件中不牵扯警车的巡逻，所以我们可以在问题一中假设警车是处于静止的状态，进而可将此问题转化问P-中心问题求解。而对于之后的问题，均牵扯巡逻问题，警车均为动态，我们采用贪婪策略来处理。二、问题假设二、问题假设二、问题假设二、问题假设1.警车出行路线的路面状况应是通畅、良好的，每条道路都是可双向行驶的。2.相邻两个交叉路口之间的道路是直线。3.警车巡逻时应是正常的，如不因警车抛锚而耽搁正常巡逻，而且不考虑路面情况和天气状况对正常巡逻的影响。4.警车配备有的GPS卫星定位系统及先进的通讯设备都是良好的、正常运行的。警车可通过这些设备随时获得整个城市的治安状况。5.社会治安处于一个正常状态，如在每辆警车巡逻区域内不会同时有多起事件发生，即每次在警车接处警时，该巡逻区域内再有其它事件发生的概率很小。6.本文中除了考虑3个重点部位外，其