2012年数学建模大赛
全
国
一
等
奖
论
文
摘要
本文结合某城市实际情况对交巡警服务平台的设置和调度进行了深入研究，解决了以下问题： 借助于Warshall-Floyd四川卫视真情人生
算法得出了区任意两点间的最短路，并按照距离最近原则将各路口分派给相应的平台，得到各平台的管辖范围（见表1），其中，除6个节点外，其余86个节点的出警时间均小于3分钟。 建立二部图的最大匹配模型解决了13条要道快速全封锁问题，得最短封锁时间约8分1秒，各平台警力调度方案如下：
服务台号 | … | 4 | 节流阀体 5 | 7 | 10 | 11 | … |
封锁路口 | … | 48 | 30 | 29 | 12 | 21 | … |
| | | | | | | |
以出警时间不超过3分钟为首要准则分析得出需增加4个服务平台，通过计算机搜索比较了所有可能的72种方案后，按照工作量均方差最小原则确定出新增平台位置分别为28、39、48、87号路口，此时，工作量均方差取得最小值2.3703。
在引入影响巡警服务平台设置合理性的3个指标基础上，建立熵权模糊评判模型，对平台设置合理性进行判决，得出现有平台设置不合理，其中区和区尤为明显，针对其工作量大且3km内平台覆盖率低的情况提出了解决方案。
证明了关于围堵的一个结论，提出了一端围堵法，确定出了为实现围堵所需要封锁的随时间变化而变化的路口集合，并将其与全城所有服务平台构成动态二部图，根据匈牙利算法得出了在此方法下的最短围堵时间为10.79分钟，需调用37个平台警力，具体围堵方案如下：
服务平台 | … | 17 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | … |
封锁路口 | … | 92 | 248 | 252 | 175 | 254 | 178 | 182 | 213 | … |
| | 呼和浩特教育公共服务平台 | | | | | | | | |
关键词 Warshall-Floyd算法 二部图 匈牙利算法 模糊评判
一 问题的重述
警察肩负着刑事执法、治安管理、交通管理、服务众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
（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得以解决，进而以最快出警时间为原则进行分配。
对于多个路口的同时请求服务，需要尽快的分配各个不同平台警力到相应路口，由于要求每个平台至多服务一个路口，将问题转化为由平台和路口所构成的二部图的匹配问题。
当需要围堵犯罪嫌疑人时，首要问题是确定需要封锁的依时间变化的路口集合，进而可将其转化为动态二部图的匹配问题。
在考虑已有交巡警设置方案合理性时，先结合全市的具体情况寻决定六区各交巡警服务平台设置合理性的一些指标，采用熵权的模糊评判方法，对平台设置合理性进行判决，并针对判决结果对设置方案进行合理的调控。
三 模型假设
1.犯罪嫌疑人和警车速度均为60km/h；
2.服务平台接警后即可立即出警；
3.一个服务平台的警力最多封锁一个路口；
4.交巡警服务平台均设在路口；
5.相邻节点间的道路为直线段。
四 符号说明
：初始距离矩阵（表示路线的距离，若路口之间无直达路线，取）
：最短距离矩阵
：（=1,2,3，…，20）表示区的20个交巡警服务平台
：以为顶点划分为边集的二部图
：二部图的匹配
：嫌疑人或者警车的移动速度
骷髅党五 模型的建立与求解
5.1 基于Warshall-Floyd算法的最短距离分配
5.1.1 基本思想
一名退休人员返聘后因工死亡待遇的争议运用Floyd算法计算城区中任意两点间的最短路程，并将每个路口交给距离最近的交巡警服务平台管辖。
5.1.2 最近距离分配算法
Step1：由全市交通路口的路线及路口节点坐标数据，由假设5根据勾股定理计算出初始距离矩阵（程序见附录1）。
Step2：然后依据Warshall-Floyd算法得出任意两个路口之间的最短距离矩阵（程序见附录2），记其中的前20行为。
Step3：对的每一列取最小值，并记录最小值大于3km的数值，设第列的最小值由第行取得，则将路口交由第个服务平台管辖（若有两行均取得最小值则任取其一即可）（程序见附录3）。
5.1.3 分配结果及分析
表1 A区交巡警平台管辖范围表
巡警平台 | 尤卓尔1 | 2 | 3 | 4 | 5 |
管辖的路口 | 1、67、68、69、71、73、74、75、76、78 | 2、39、40、43、44、70、72 | 3、54、55、65、66 | 4、57、60、62、63、64 | 5、49、50、 51、52、53、56、58、59 |
| | | | | |
巡警平台 | 6 | 7 | 8 | 9 | 10 |
管辖的路口 | 6 | 7、30、32、34、47、48、61、 | 8、33、46 | 9、31、34、35、45 | 10 |
| | | | | |
巡警平台 | 11 | 12 | 13 | 14 | 15 |
管辖的路口 | 11、26、27 | 12、25 | 13、21 、22 、23、 24 | 14 | 15、28、29 |
| | | | | |
巡警平台 | 16 | 17 | 18 | 19 | 20 |
管辖的路口 | 16、36、37、38 | 17、41、42 | 18、80、81、82、83 | 19、77、79 | 20、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%。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议