交巡警服务平台的设置与调度-全国一等奖论文

2012年数学建模大赛全国一等奖论文1交巡警服务平台的设置与调度摘要本文结合某城市实际情况对交巡警服务平台的设置和调度进行了深入研究，解决了以下问题：借助于Warshall-Floyd算法得出了A区任意两点间的最短路，并按照距离最近原则将各路口分派给相应的平台，得到各平台的管辖范围（见表1），其中，除6个节点外，其余86个节点的出警时间均小于3分钟。建立二部图的最大匹配模型解决了13条要道快速全封锁问题，得最短封锁时间约8分1秒，各平台警力调度方案如下：服务台号…4571011…封锁路口…4830291221…以出警时间不超过3分钟为首要准则分析得出需增加4个服务平台，通过计算机搜索比较了所有可能的72种方案后，按照工作量均方差最小原则确定出新增平台位置分别为28、39、48、87号路口，此时，工作量均方差取得最小值2.3703。在引入影响巡警服务平台设置合理性的3个指标基础上，建立熵权模糊评判模型，对平台设置合理性进行判决，得出现有平台设置不合理，其中C区和F区尤为明显，针对其工作量大且3km内平台覆盖率低的情况提出了解决方案。证明了关于围堵的一个结论，提出了一端围堵法，确定出了为实现围堵所需要封锁的随时间T变化而变化的路口集合，并将其与全城所有服务平台构成动态二部图，根据匈牙利算法得出了在此方法下的最短围堵时间为10.79分钟，需调用37个平台警力，具体围堵方案如下：服务平台…17166167168169170171172…封锁路口…92248252175254178182213…关键词Warshall-Floyd算法二部图匈牙利算法模糊评判2一问题的重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二模型的分析本题主要研究交巡警管辖范围分配、设置与调度问题。能否及时响应一个或者多个路口的服务请求，是此问题所迫切的要求。由于交巡警平台设置及服务要求都在路口，自然可将问题抽象成图论模型。管辖范围的确立首先依赖于各节点间的最短路，这可借助于图论中的最短路算法Warshall-Floyd得以解决，进而以最快出警时间为原则进行分配。对于多个路口的同时请求服务，需要尽快的分配各个不同平台警力到相应路3口，由于要求每个平台至多服务一个路口，将问题转化为由平台和路口所构成的二部图的匹配问题。当需要围堵犯罪嫌疑人时，首要问题是确定需要封锁的依时间变化的路口集合，进而可将其转化为动态二部图的匹配问题。在考虑已有交巡警设置方案合理性时，先结合全市的具体情况寻找决定六区各交巡警服务平台设置合理性的一些指标，采用熵权的模糊评判方法，对平台设置合理性进行判决，并针对判决结果对设置方案进行合理的调控。三模型假设1.犯罪嫌疑人和警车速度均为60km/h；2.服务平台接警后即可立即出警；3.一个服务平台的警力最多封锁一个路口；4.交巡警服务平台均设在路口；5.相邻节点间的道路为直线段。四符号说明0D：初始距离矩阵（ijd表示路线ij的距离，若路口,ij之间无直达路线，取ijd）D：最短距离矩阵iA：（i=1,2,3，…，20）表示A区的20个交巡警服务平台(,,)GXYE：以,XY为顶点划分E为边集的二部图M：二部图的匹配V：嫌疑人或者警车的移动速度五模型的建立与求解5.1基于Warshall-Floyd算法的最短距离分配5.1.1基本思想运用Floyd算法计算A城区中任意两点间的最短路程，并将每个路口交给距离最近的交巡警服务平台管辖。5.1.2最近距离分配算法Step1：由全市交通路口的路线及路口节点坐标数据，由假设5根据勾股定理计算出初始距离矩阵09292D（程序见附录1）。4Step2：然后依据Warshall-Floyd算法得出任意两个路口之间的最短距离矩阵9292D（程序见附录2），记其中的前20行为2092D。Step3：对2092D的每一列取最小值，并记录最小值大于3km的数值，设第j列的最小值由第i行取得，则将路口j交由第i个服务平台管辖（若有两行均取得最小值则任取其一即可）（程序见附录3）。5.1.3分配结果及分析表1A区交巡警平台管辖范围表巡警平台A1A2A3A4A5管辖的路口1、67、68、69、71、73、74、75、76、782、39、40、43、44、70、723、54、55、65、664、57、60、62、63、645、49、50、51、52、53、56、58、59巡警平台A6A7A8A9A10管辖的路口67、30、32、34、47、48、61、8、33、469、31、34、35、4510巡警平台A11A12A13A14A15管辖的路口11、26、2712、2513、21、22、23、24A1415、28、29巡警平台A16A17A18A19A20管辖的路口16、36、37、3817、41、4218、80、81、82、8319、77、7920、84、85、86、87、88、89、90、91、92由于1-20号设置了巡警平台，因此由自己管辖，28、29、38、39、61、92号路口与最近的巡警平台的距离均大于3km，分别为4.75、5.70、3.41、3.68、4.19、3.60（单位：km），即无法在3min内到达。能在三分钟之内能到达的路口节点占总结点数的93.5%。5.2基于二部图的快速全封锁方案5由假设2可知，一个巡警平台的警力最多封锁一个路口，要实现快速全封锁，就是要使13条交通要道在最短时间内全部由20个巡警平台中的某13个平台一一封锁（封锁时间以最后一个路口被封锁的时间计）。5.2.1基于二部图的快速全封锁方案的思想对于某个时间T，建立一个二部图(,,)TGXYE，其中,XY分别表示13个要道与A区的20个服务平台。边xyE表示平台y可在时间T内到达要道x，即xydVT。使用匈牙利算法得到TG的最大匹配M。如果M饱和X，表明可从M得到一个全封锁。否则，就增大时间T，重新循环上述操作。5.2.2基于二部图的快速全封锁方案的实现设20个巡警平台分别到达13个交通要道的时间从小到大依次是12,,,nttt。设1iittt，由二部图边的构造知ittGG。故若可在t时间内封锁（即找到饱和X的匹配），则一定可在it时间内封锁。即有下述结论：结论1：最短封锁时间一定是某个巡警平台到达某个交通要道的时间。基于上述结论，封堵时间T依次取12,,,nttt，直到对应的二部图TG存在饱和X的匹配，即可找到最短全封锁时间。Step1：1320D表示13个交通要道距离20个巡警平台的最短距离矩阵，记20个巡警平台分别到达13个交通要道的时间从小到大依次是12,,,nttt.Step2：依次取iTt(1,2,...)in，,确定二部图(,,)TGXYE，记其对应的邻接矩阵为1320=ijAa，其中113;1,2,200ijijdTVaij若（=1,2,，，）否则Step3：使用匈牙利算法得到TG（1320A）的最大匹配M，若M饱和X，则当前T为最短全封锁时间，算法终止，否则转Step2。5.2.3最快封锁方案及其检验由附录程序4，得最小全封锁时间T=8分1秒，此时对应的二部图具有一个饱和13个要道的匹配M6000000000100000000000000000000000001000001000000000M00000000000000000001000000000000000000001000000000000000000000100000000000000000010000000000000000000001000000000001000000000000000001000000000000000100000000000000000000001000000000000000000100000000000000000由此矩阵，得全封锁方案如下（矩阵的1-13行分别表示12、14、16、21、22、23、24、28、29、30、38、48、62号路口，1-20列分别表示1-20号巡警服务台）.表2A区对13条要道的全封锁方案服务台号12345710封锁路口38166248302912距离5.887.394.397.403.188.027.59服务台号111213141516封锁路口212224232814距离5.076.882.396.474.756.74经检验（上表第3行），服务台到各个对应封锁路口的距离均不超过8.02km（约合8分1秒）,表明所得结果是正确的。5.3A区交巡警服务平台调整方案5.3.1交巡警平台各指标定义服务平台工作量：指该服务平台管辖的各路口节点日均报案率之和；某地的出警时间：指管辖该地的巡警从交巡警平台到达该地的时间。5.3.2总体调整思路交巡警服务平台增设原则：以对辖区所有节点的快速响应为首要考虑因素，统筹兼顾各服务平台工作量的均衡性。即平台设置的首要目标是增加尽可能少的服务平台（2-5个）以实现对该区所有节点3分钟以内的全覆盖，并且在新增平台后，全区所有路口节点的管辖权按就近原则重新分配后各平台工作量尽可能均衡。Step1：新增平台数目确定筛选出出警时间长于3分钟（即距离管辖平台大于3千米）的路口节点，称7其为偏远节点。表3长于三分钟的偏远节点与巡警平台的距离偏远节点282938396192出警距离（km）4.75.73.43.64.13.6上述6个出警时间超过3分钟的节点可分为4组（如图1所示），从最短距离矩阵D中可知，不同组类节点间距离均大于6km，故新增一个节点至多能使一类节点的出警时间降到3分钟以内，因此至少需要新增4个服务平台。图1四组偏远路口另一方面，从4组中各取一个节点作为服务平台即可满足对这6个节点3分钟的全覆盖。初步方案可定为在28、38、61、92位置设立服务平台，从新分配管辖范围后工作量的均方差为3.1005。Step2：平台位置的确定总体思想：新增四个平台，在满足所有节点出警时间均不超过3分钟的前提下，使得调整后的工作量具有尽可能小的均方差。记(1,2,,6)iNi为这6个节点（28、29;38、39;61;92）的3km以内邻域节点，因为一个服务平台最多只能覆盖一个组类，故新增的4个节点应分别取自12345,,NNNNN以及6N。由最短距离矩阵D得1228,29NN，3438,39,40NN548,61N，687,88,89,90,91,