2011全国数模竞赛A题交巡警平台设置论文

1交巡警服务平台的管理与评价摘要交巡警是交通警察巡警合一的警务模式，交巡警合一，并不是将交警、巡警部门简单合并，而是要实现‘1+12’的效能。本文是在针对交巡警平台实际应用中遇到的各种问题进行合理解决。问题1是一个关于解决最短路径的问题。本文利用Floyd算法计算出各个路口之间的最短路径。题目要求满足：尽量在案发后3分钟内到达事发地，并尽量避免分析管辖范围重叠问题，本文选择以路口为主体向外3分钟路径辐射，以最近服务平台对其进行管理，管辖范围见表格5（P6）。问题2是一个求解全局最优解的问题。本文通过已知数据的分析设定一个搜索时间上线9min，并从原始表格中剔除大于9min的数据，按照最大时间尽量小的原则，通过不断确定局部最优解得到全局最优解。封锁方案如下（封锁最大时间为8.02分钟）：平台24578910111213141516路口38624829301612222423212814问题3是解决工作量不均衡及出警时间过长问题。用方差来衡量工作量的均衡问题，定3分钟为出警时间不过长的上限。通过简单数据处理可以确定：5个平台由于工作量不均衡需要进行调整，其中有附图可知28或29之间需要安排一个服务平台解决出警时间过长问题。最后利用matlab编程可得：需要增加5个平台。平台数达到上限但仍有61号路口不能解决工作时间长问题。因此需对模型进行改进优化问题1模型，对服务平台安排新的管辖范围。以平台为主体进行3分钟距离向外辐射，出现管辖范围重叠时，按管理路口最少优先安排、同等数量按节点号小安排的原则，得到新的增加平台方案：增加平台数增加平台节点440、48、91、29问题4是一个综合评价模型问题。首先确定评价因子，本文选取发案次数和有效出警（接到报警后3分钟内能够赶到现场）覆盖率，作为评价全市平台安置是否合理的评价因子。然后通过数据分析得到F区和C区服务平台设置明显不合理，并得到了关于不合理区域的解决方案（具体方案见表格22P16），最后通过比较增设平台前后各项评价因子，验证解决方案的合理性。问题5是一个复杂的追击问题，本文首先标记出罪犯在6分钟内可以行动的所有路径，由于警察是从第三分钟才开始行动，所以警察对所有标记出的路径进行围堵。然后向包围住的罪犯不断逼近，最后最后实现快速搜捕。关键词：Floyd算法全局最优解方差评价因子快速封锁2一．问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文针对某市设置交巡警服务平台的相关情况，建立数学模型分析研究下列问题：1.要求为A区20个交巡警平台划分管辖范围，要求在突发事件发生时，交巡警能尽量在3分钟内赶到。这是一个含约束条件的最短路径问题。2.需要设计一个20个平台快速封锁13个路口的调度方案，其中每个平台最多只能封锁一个路口。这是一个寻求全局最优解的问题，为保证快速全封锁，必须满足封锁的路口中最大时间尽量小。3.由于现有交巡警平台存在工作量不均衡和出警时间过长问题，所以需要选择合适的位置增加服务平台解决上述两个问题。衡量工作量均衡主要可以考虑方差，出警时间问题可以通过设定出警上限时间来分析。4.针对全市交巡警服务平台的具体情况，进行合理性分析。需要通过交巡警服务平台的原则和任务，设定可量化的评价标准，属于一个综合评价模型。然后根据设定的评价标准，对评价出现不合理的进行相应改进。5.在点P发生重大刑事案件，需要交巡警进行快速搜捕。案发后3分钟接到报警，要求给出最佳的快速围堵方案。二．问题分析2．1问题1要解决为A区的交巡警服务平台分配管辖范围，根据要求可知交巡警接到突发事件报案后尽量在3分钟内赶到。首先用Floyd算法求解3分钟内每个交巡警平台能够到达的最远距离。在计算过程中会发现A区东北方路口节点过于密集，按3分钟可以到达这个约束条件求得的管辖范围有可能有诸多重叠。因此本文主要用Floyd算法计算：是否在3分钟这个约束条件内所有路口皆能覆盖到。如果不能完全覆盖到，且管辖范围重叠较多，则把各个路口作为主体，以3分钟车程距离向外辐射可以得到距离路口最近的平台。然后把这些路口都分配给相应的平台，这样就可以得到交巡警服务平台管辖范围。由于我们是把路口离散化，必定会存在相邻两个路口归不同交巡警平台管辖，而中间的道路就没有划分到任何的管辖范围内，本文假设把这种道路平均划分给相邻的平台管理。2．2问题2在有重大突发事件时20个交巡警平台的警力资源能够对13条交通要道进行快速封锁（每个交巡警平台警力最多能封锁一个路口），本文需要给出合理的调度方案，这属于寻求全局最优解问题。通过数据处理筛选出部分时间较大的值，按照最大时间尽量小的原则，逐步通过局部最优解寻求全局最优解。2．3问题33根据交巡警平台的工作量情况选择性的增加2-5个平台。本文需要给出具体的增加平台数和安置位置。题目要求通过增加服务平台来解决两个问题：①工作量不均衡问题②出警时间过长问题。针对以上两个问题分析题目后设定三个衡量标准：①各个服务平台工作量方差减小50%以上②出警时间小于3分钟③服务平台尽可能少。当模型给出的结果满足以上三个衡量标准则说明问题3增加平台合理。解决工作量不均衡问题，暂时不考虑出警时间过长，因为在解决工作量问题而增加的平台时可能会解决到部分出警时间过长的路口。然后在问题①解决后，观察是否还有出警时间过长的路口，如果有则单独对出警时间过长的路口进行平台增加，并且进行是否满足衡量标准的检验，如果不满足则适当调整模型约束条件。在约束条件调整到满足合理性的最大限度时，依然无法完全解决问题①、②，则需要对模型进行改进，重新给各个服务平台安排管辖区域。然后再按照原模型步骤进行求解。2．4问题4需要根据题目分析，全市六个区交巡警服务平台设置方案的合理性，主要评价标准按照设置交巡警服务平台的原则和任务制定。如果分析结果显示方案明显不合理，则需要给出解决方案。这是一个综合评价问题，制定有效出警时间覆盖率、每个平台的平均发案次数作为评价标准。在以上两个评价因子判断都不合理的情况下，就判定该区域平台设置不合理，并需要增设服务平台进行问题解决。最后通过比较增设前后的各项评价因子验证解决方案的合理性。2．5问题5若在P点（第32个节点处）发生重大刑事案件，案发3分钟后接到报警，本文需要给出利用全市交巡警资源进行围堵的最佳方案。此问题属于追击问题，由于报警时间是案发3分钟后接到了，所以警察比罪犯的时间晚了3分钟，本文编程标记处逃犯6分钟内逃跑的所有路径，警察以此为依据进行快速搜捕。三．模型假设1．出警时道路恒畅通（无交通事故．交通堵塞等发生），警车行驶正常；2．警车和罪犯行驶速度恒定，均为60km/h；3．交巡警接警后到达报警地点所走的路线均为最短路线，且到达报警地点后一定可以解决问题；4．交巡警服务平台管辖范围是计算平台管理的各个路口数。5．所有道路都是双向通行；6、题目给定数据真实可靠。四．符号说明符号描述ija表示各个路口之间的权重maxt表示选取作为约束的一个最大时间2S表示方差nX表示每个交巡警平台的发案次数4X表示总平均发案次数n表示交巡警平台的个数(,)kAij表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度五．交巡警服务平台模型5．1管辖范围的分配5.1.1模型的准备首先把A区的整个交通网络进行路口节点离散化，即各服务平台的管辖范围只针对路口节点进行管理。查看附件1中的附图1可知，A区内有92个路口节点，而且每个节点的坐标是已知的，如下表：表格1各个路口坐标全市路口节点标号路口的横坐标X/mm路口的纵坐标Y/mm141335924033433383.5351·········90440.5381.59144538092444360所以通过matlab数据处理可以得到路口之间的相互距离，部分距离见下表：表格2部分路口之间距离(单位：百米)节点序号495051525349010.440316.7082045010.4403103.807887513.80788704.3011635204.30116308.544004536.7082048.5440040注：每个路口距自身的距离为0，路口之间相互没有直接连通的道路距离为。5．1.2Floyd算法于是可以把A区的92个路口看成是一个有权值图的各个顶点。管辖范围的划分本文定义的标准是：管辖区域内有突发事件发生可以在较短时间内到达。因此这就可以简化为一个最短路径问题。根据题目要求：各交巡警服务平台分配管辖范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。本文在计算过程中把3分钟作为约束条件，根据5*svt可知，在每个服务平台向外辐射3km（在数据处理过程中按照附图1的坐标进行计算）范围内都可以作为管辖范围。于是通过分析题目特点本文选用Floyd算法对各个路口节点进行最短路径求解。首先建立A区各个路口节点图G的权值邻接矩阵0A，1112112222012nnnnnnaaaaaaAaaa来存放各路口节点之间距离，其中：0ijji012;,=,12iiijijijijainaijawwijijnAaa，，，之间没有边，在程序中以各边都不可能达到的充分大的数代替是之间边的长度，，，，，。对于无向图，是对称矩阵，。Floyd算法的基本思想是：递推产生一个矩阵序列01,,,,,,knAAAA其中(,)kAij表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：111(,)min((,),(,)(,))kkkkAijAijAikAkjk是迭代次数，,,1,2,,ijkn。最后，当k=n时，nA即是各顶点之间的最短通路值。矩阵建立完毕，带入表格2中的数据，通过matlab编程（程序见T1_1.m）得到任意两口之间的最短路径，见下表：表格3各个路口节点之间距离节点序号12····91921018.98749····49.9147569.93974218.987490····68.1166380.72796338.8388421.11654····83.21813101.8445························9045.1713463.37321····4.74341624.76849149.9147568.11663····020.024989269.9397480.72796····20.024980因为1-20号节点是交巡警服务平台，所以根据表格3进行筛选可以得到，每个服务平台向外辐射3km范围内能够到达的路口情况，结果如下表（完整表格见附录T1_1.m）：表格4各平台3分钟辐射范围平台节点各平台可以在三分钟之内到达的所有路口611218194243···2123174042···32343445455···························1811819207172···1911819646566···20182081828384···通过以上表格数据可以看出，在A区东北方向上由于路口过于密集，导致以服务平台为主体向外辐射的筛选方法得到的管辖范围出现大量范围重叠，显然是不合理的。而且在3km辐射范围内还有6.5%的路口不能被管辖到，这样的结果也是不够理想的。因此本文在原有模型的基础上进行改进。5.1.3路口辐射筛选上述Floyd算法中我们是以交巡警服务平台作为主体进行筛选，以3km的管辖范围向外辐射，所以导致在路口密集处出现大量的管辖范围重叠的情况。现在本文把各个路口作为主体，同样是基于Floyd算法，任意一个路口以自己为中心向外辐射，最先到达哪个交巡警服务平台即属于哪个交巡警服务平台管理。以上筛选方法通过matlab编程（程序见附录Htu_1）可以实现，最