交巡警服务平台的设置与调度.doc

交巡警服务平台的设置与调度摘要本文综合运用了算法、线性规划、指派模型、匈牙利法、递增包围圈等数学思想解决根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源、围堵犯罪分子等实际问题，主要是数学中的优化问题。针对问题一，划分管辖区域问题实质是寻找距各交巡警服务台最短路径小于特定值的问题，主要采用算法来解决，再加以Matlab进行辅助求解，因为服务台的设置不合理，最终结果并不是满意的，所以进行人工干预分组，同时针对服务台分布不合理现象进行了优化处理，增设了3个新服务台。另外第二小问的20个服务台封锁13个路口的问题实质上是“人多事少”指派问题，解决办法是增加虚拟的路口，建立线性规划模型，用匈牙利法求解，同时求解过程由计算机利用LINGO软件进行。针对问题二，首先是对全市的服务台设置进行评价，以A为比对对象，分别对B、C、D、E、F进行评价，最终得到全市的交巡警服务台设置不合理，并对其结构进行优化。关键字：服务台设置与调度、算法、指派模型、匈牙利法、围堵模型1、 问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文就是基于这个背景解决以下问题：（1）为附件1各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台作的工量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。另附有附件1、2。2、 模型假设1、题目中提供的路线为所有路线且均为直线；2、每个交巡警服务平台的职能和警力配备按相同处理；3、警车匀速直线运动，无反应时间，切无堵车现象；3、符号说明问题一A区第个服务台封锁第个路口A区第个服务台到第个路口最短路径4、 模型分析建立与求解4.1问题一模型分析建立与求解4.1.1问题一分析 问题一共分为三问，为附件1各交巡警服务平台分配适当的管辖范围；对于重大突发事件，设计调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁的方案；根据现有交巡警服务平台作的工量不均衡和有些地方出警时间过长的实际情况，为该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。管辖范围的条件是能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，即与交巡警服务平台相距小于30 （反映在图中）的节点在其监管范围内，也就是说交巡警服务平台与各节点的最短路径小于30 ，则可对该节点进行监管。解决最短路径问题的方法有很多，较为常用的有算法和算法，但前者只限于权为正值并且适用于少数的，对于大量的求最短路径还是选用算法。第三问是对第一问的完善优化，所以先于第二问讨论。根据第一问的结果看管辖区域的分布，对于管辖范围太大的且最短路径较长的地方，以及工作量很大的地方增加服务台。第二问是设计20个服务台来封锁13个路口的时间最短的方案，是运筹学中的指派问题，再假设7个虚拟的路口，而20个服务台到7个虚拟的路口的时间为0。再用LINGO进行求解。4.1.2问题一模型建立管辖范围：主要使用算法算法又称为插点法，是直接在图的邻接矩阵中用插入顶点的方法依次构造出个矩阵，使最后得到的矩阵成为图的距离矩阵，同时也求出插入点矩阵以便得到两点之间的最短路径。把带权邻接矩阵作为距离矩阵的初值，即（1），其中，是从到的只允许作为中间点的路径中最短路的长度。（2），其中，是从到的只允许、作为中间点的路径中最短路的长度。（），其中，是从到的只允许、作为中间点的路径中最短路的长度。即是从到中间可插入任何顶点的路径中最短路的长，因此即是距离矩阵。增加服务台：（1） 对各管辖区的总最短路径以及工作量进行数据处理；（2） 确定增加服务台。封锁路口:通过附件2得知其中在13个路口中有三个设有服务台（12、14、16），自然这3个路口的封锁有自己的服务台完成，也就是说问题变成了17个服务台封锁10个路口，另外假设出7个虚拟的路口，而17个服务台到达这7个虚拟路口的最短路径均为0。封锁时间反映出来就是距离问题。使用运筹中的指派问题模型。服务台为，路口为，1到10为原13个路口去掉那3个特殊路口后按顺序排出来的，11到17是虚拟出的7个路口，第个服务台去封锁第个路口为。第个服务台到封锁第个路口的最短路径长度为。根据题意得，每个服务台仅封锁一个路口，约束条件为：每个路口由一个服务台封锁，约束条件为：目标函数为 用LINGO进行匈牙利法求解，程序见附录。4.1.3问题一模型求解管辖区域：（1） 整理数据，建立一个的矩阵，表示20个服务台到该区的92个节点的直接距离，根据附件2的全市交通路口的路线工作表得出直接相连的两节点之间的直接距离，没有直接相连的距离则为无穷大，用表示；（2） 得到的矩阵带入算法，进行求解。最后会得到20个平台到个点的最短路径，对数据进行筛选找到小于30的。其中根据附件二得到的直接距离表格部分图如下图1：图1最终得到的20个服务平台到各节点的最短路径。对于最短路径其中有两个特例，一是同一节点到多个平台的最短路径均小于30，这种情况选择最短的路径；二是一节点到任何一个平台的最短路径都大于30，对于这种情况的处理办法是选取最短的路径进行管理，否则就不被管理，显然不这是不可能的。最终经过人工干预的结果如下表1：表1 管辖区域A1A2A3A4A5A6A7A8A9A10123456789106740545749303135684355605047324569446462514833717065635234723966615346735674587559A11A12A13A14A15A16A17A18A19A20111213141516171819202625212836417876812722293742797782233880832484 85 86878889909192增加服务台：对于上表做出对应的最短路径表以及工作量表格如下表2,3：表2 最短路径表A1A2A3A4A5A6A7A8A9A10000000000016.1919.1422.7118.6855.8323.15.0212.07812.6617.398.4912.8111.411.7359.4921.073.512.312.915.8511.48.615.2410.3116.68.2816.436.8218.452.111.719.310.2920.846.2623.0316.615.2294.2182.05120.2191.67113.19061.9567.9316.750A11A12A13A14A15A16A17A18A19A200000000000917.8927.0947.526.088.519.2414.3226.7816.439.0657.0111.189.8512.539.8521.76534.068.0621.623.8511.754.4722.8617.5513.529.4913.0317.0637.0825.4317.89650104.5340.1418.3539.8324.17216.95表3 工作量（发案率）表A1A2A3A4A5A6A7A8A9A0.91.71.6A11A12A13A14A15A16A17A18A19A0.84.614.9相对于表2、3，对应的更直观的条形图如下图2、3：图2 最短路路径条形图图3 工作量（发案率）条形图根据上面表2、3，图2、3，可以看出最短路径和发案率的分布，因为是要增加服务台，所以不考虑少的地方，仅考虑最短路径长和发案率大的地方，另外，根据表1知节点28、29、38、39、61、92到20个服务台的最短路径均大于30，所以也要考虑新增服务台来管辖这些点。（1）在20服务台处增加新设点，在原来他的管辖范围内挑选几个距它最短路径较小的，由第一小问的数据选取20、84、85、86、88、89、90节点，这几个距离20服务台很近，剩余的节点互相之间的最短路径如下表4：表4818283879091928105.0210.4325.3513.7518.4938.51825.0205.4120.338.7313.4733.498630.6625.6426.2211.0516.9112.3832.49013.758.7314.1411.604.7424.769118.4913.4718.887.574.74020.029238.5133.4938.921.3824.7620.020106.4386.35113.9897.2868.8969.1149.18首先92节点要包含进去，其他点之间互相之间最短路径也要小于30，所以从87、90、91中选择，选取最短路径小的即90节点为新的服务台21，另外考虑发案率，增加21后，20的发案率是8.4,21的发案率是6.5，都较整体均衡，所以在90节点（440.5,381.5）处增加新的服务台。（2）对于剩余的7个没有被包含的节点进行处理。28、29节点与其他所有节点的最短路径都大于30，所以只有在这两点之间选择一个。所以在28或29处增设新服务台。38、39与28、29的情况相同，但是这两个节点距40节点的最短路径均小于30，所以可以把40划到他们的管辖范围，这样还能给2服务台减小压力，考虑到40的话，就选取29节点为新设服务台，因28节点距40较远，所以在29节点（246,337）处新增服务台。最后一个是61节点，再此处设新服务台，同28、29一样，他可以监管48节点，所以在61节点（335,395）新增服务台。封锁路口：(1) 用LINGO的匈牙利发求解，首先整理出的原始最短路径矩阵，如下表5：表5 原始最短路径矩阵12345678910111213141516171180.25198.28212.34226.31179.82189.31116.4786.6999.2138.400000002173.95191.98206.04220.01173.52183.01110.1780.3992.9132.100000003160.32178.35192.41198.89152.4161.8989.0559.2771.78110.9800000004182.74200.77214.83207.44137.27127.7853.4689.9856.5952.0900000005150.75168.78182.84175.52113.07106.1531.8349.714.5653.7600000006151.06169.09183.15175.83113.38106.4632.1450.0114.8754.0700000007149142.8156.86148.1585.780.155.8347.9512.8141.900000008126.99142.15156.21147.5101.01110.549.6725.9432.471.600000009115.39133.42147.48159.1112.61112.3938.0714.3420.86000000001095.0877.0891.1482.43141.95151.44107.1783.4489.9129.100000001150.732.746.7638.05186.33195.82151.55127.82134.28173.4800000001227.069.06523.85228.09237.58174.55138.31164.03203.23000000013179.77172.78186.84178.1347.5257.0144.0178.7250.9980.08000000014181.69199.72213.78232.63199.43203.36129.0492.8118.52142.26000000015210.26228.29242.35256.32209.83206.82132.5116.7129.21131.13000000016209.47227.5241.56248.04201.55211.04138.2108.42120.93148.13000000017248.69263.08277.14268.43198.26188.77114.45150.97117.58113.080000000最终LINGO程序求解如下表6：（具体程序见附录）表6 指派结果21222324282930384862虚拟1虚拟2虚拟3虚拟4虚拟5虚拟6虚拟710000000000000001020000000000000000130000000000000100040000000001000000050000000010000000060000001000000000070000010000000000080000000100000000091000000000000000010000100000000000001101000000000000000130010000000000000015000010000000000001700000000000100000180000000000100000019000000000000100002000000000000000100所以最终结果如表7：表7最终封锁结果服务台所封锁路口1无2无3无462548630729838921102411221212132314141528161617无18无19无20无4.2问题二模型分析建立求解4.2.1问题二分析第一问同问题一的第三小问类似，同样是看服务台设置是否合理，从两部分入手，一是从附件中给出的发案率、地区面积、城区人口来看服务台的数量是否合理，二是像问题一的第一小问一样进行一定距离的区域划分，看服务台的分布是否合理。4.2.2问题二模型建立逃犯在经历一段时间后会经历n个节点，记为（i=1.n）由这n各节点组成的一个区域，该区域的边界就是包围圈，随着时间的递增，包围圈越来越大，成为递增包围圈。包围圈点集的确定：设经过t时间组成的最大区域为D，记D为D=， D为包围圈外部的节点，记为，D为包围圈边界上的点，应该满足的条件为，案发路口到包围圈的节点，大于等于经过t时间所走的最大距离。并且各包围圈上的节点与D的节点相邻接。交巡警府服务平台的确立，假设包围圈已经确定，调度警力，记表示警车从节点i到节点j所经历的时间，1表示服务平台i节点围堵了j节点，0表示服务平台没有调动警力围堵，设交警平台点集合为J，为保证平台快速及时的到达包围路口节点提高围堵成功率，建立模型： Min= 4.2.3问题二模型求解 服务台分布：（1） 从服务台数量来考虑，见下表8：表8ABCDEF发案率124.566.4187.267.8119.4109.2城区面积22103221383432274城区人口602149737653人口/面积2.790.180.19节点数927315452103108平台数2081791511由于问题一种已经求出A区的服务台数量上不合理，C、E、F的发案率很高，他们所需的服务平台应该也很多，但是都小于A的平台数，E、F少的还很多所以不合理。（2）从服务台的分布上来看，与A相比较，A的服务台分布一是不合理的，（原因见问题一求解），同样是C、E、F，节点数多，发案率高，面积还大，A的服务台的分布不能满足所有节点的需要，二后三者的服务台的分布应该更不能满足所有节点的需要，所以分布不合理。对于全市服务台设置的改进用问题一中的增加服务台的原理进行。首先依据某一标准对各服务台划分管辖范围。对于出警时间长的发案率大的服务台，在它的区域内增设新的服务台；在没有被监管的节点中选择合适的节点建立新服务台；对于某些服务台除了自己监管的节点数很少发案率很低的，可以选择撤销，使其区域的节点归其他服务台监管，或是重选新节点为服务台，即可监管原区的节点还可为其他服务台分担压力。由于全市数据庞大不一一列举。（1）求出递增包围圈包含的点，利用0-1整数规划求出平台警力调度方案，令t=0给出围堵成功率，递增时间段；（2）+，计算t时刻包围圈点集D；（3）利用0-1整数规划求出平台警力至包围圈调度方案；（4）有调度方案计算出在t-3分钟内警力到达的包围圈节点数目该时刻节点总数为m，则围堵成功率是n/m*100%，（5）如果成功率，则得到最佳围堵方案。5、 模型评价模型优点：1、 问题一中求最短路径数据庞大，使用算法简单方便；2、 问题一中指派问题模型是问题简单化，用匈牙利法求解简单；3、 4、 全文使用Matlab、LINGO进行求解简单精确快捷。5、 确定搜捕犯罪嫌疑人的最佳围堵方案中采用“递增包围圈”比较新颖有创意，模型缺点：1. 对问题二的假设犯罪嫌疑人车速60km/h,且只沿着交通网络不符合实际。2. 数据处理的不准确。3.文章语言不够专业凝练。6、参考文献1 实验8（Floyd 算法）/link?url=QeKnCwk8ot7o2GV_ntaSOkkLpWzKVfrWFEKdAtIcrQ9lDYaYVQbXM3sO6BPvHDQOXaEZTXvBJHlO1kRLIcs5fvMPyyf9vhcdWl3RGXR0Ve32 于春田，运筹学，河北人民出版社，2003-87、附录附录一：问题一算法的Matlab程序语言附录二：问题一匈牙利法的LINGO程序语言model:sets:ren/1.4/;renwu/1.4/;Assign(ren,renwu):C,X; endsetsdata:C=180.25198.28212.34226.31179.82189.31116.4786.6999.2 138.40000000173.95191.98206.04220.01173.52183.01110.1780.3992.9 132.10000000160.32178.35192.41198.89152.4161.8989.0559.2771.78110.980000000182.74200.77214.83207.44137.27127.7853.4689.9856.5952.090000000150.75168