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

1、2012年数学建模大赛全国一等奖论文 交巡警服务平台的设置与调度摘要本文结合某城市实际情况对交巡警服务平台的设置和调度进行了深入研究，解决了以下问题：借助于Warshall-Floyd算法得出了区任意两点间的最短路，并按照距离最近原则将各路口分派给相应的平台，得到各平台的管辖范围（见表1），其中，除6个节点外，其余86个节点的出警时间均小于3分钟。建立二部图的最大匹配模型解决了13条要道快速全封锁问题，得最短封锁时间约8分1秒，各平台警力调度方案如下：服务台号4571011封锁路口4830291221以出警时间不超过3分钟为首要准则分析得出需增加4个服务平台，通过计算机搜索比较了所有可能的72

2、种方案后，按照工作量均方差最小原则确定出新增平台位置分别为28、39、48、87号路口，此时，工作量均方差取得最小值2.3703。在引入影响巡警服务平台设置合理性的3个指标基础上，建立熵权模糊评判模型，对平台设置合理性进行判决，得出现有平台设置不合理，其中区和区尤为明显，针对其工作量大且3km内平台覆盖率低的情况提出了解决方案。证明了关于围堵的一个结论，提出了一端围堵法，确定出了为实现围堵所需要封锁的随时间变化而变化的路口集合，并将其与全城所有服务平台构成动态二部图，根据匈牙利算法得出了在此方法下的最短围堵时间为10.79分钟，需调用37个平台警力，具体围堵方案如下：服务平台171661671

3、68169170171172封锁路口92248252175254178182213关键词 Warshall-Floyd算法 二部图 匈牙利算法 模糊评判 1一 问题的重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中

4、心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情

5、况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二 模型的分析本题主要研究交巡警管辖范围分配、设置与调度问题。能否及时响应一个或者多个路口的服务请求，是此问题所迫切的要求。由于交巡警平台设置及服务要求都在路口，自然可将问题抽象成图论模型。管辖范围的确立首先依赖于各节点间的最短路，这可借助于图论中的最短路算法Warshall-Floyd得以解决

6、，进而以最快出警时间为原则进行分配。对于多个路口的同时请求服务，需要尽快的分配各个不同平台警力到相应路口，由于要求每个平台至多服务一个路口，将问题转化为由平台和路口所构成的二部图的匹配问题。当需要围堵犯罪嫌疑人时，首要问题是确定需要封锁的依时间变化的路口集合，进而可将其转化为动态二部图的匹配问题。在考虑已有交巡警设置方案合理性时，先结合全市的具体情况寻找决定六区各交巡警服务平台设置合理性的一些指标，采用熵权的模糊评判方法，对平台设置合理性进行判决，并针对判决结果对设置方案进行合理的调控。三 模型假设1. 犯罪嫌疑人和警车速度均为60km/h；2. 服务平台接警后即可立即出警；3. 一个服务平台

7、的警力最多封锁一个路口；4. 交巡警服务平台均设在路口；5. 相邻节点间的道路为直线段。四 符号说明：初始距离矩阵（表示路线的距离，若路口之间无直达路线，取）：最短距离矩阵：（=1,2,3，20）表示区的20个交巡警服务平台：以为顶点划分为边集的二部图：二部图的匹配：嫌疑人或者警车的移动速度五 模型的建立与求解5.1 基于Warshall-Floyd算法的最短距离分配5.1.1 基本思想运用Floyd算法计算城区中任意两点间的最短路程，并将每个路口交给距离最近的交巡警服务平台管辖。5.1.2 最近距离分配算法Step1：由全市交通路口的路线及路口节点坐标数据，由假设5根据勾股定理计算出初始距离

8、矩阵（程序见附录1）。Step2：然后依据Warshall-Floyd算法得出任意两个路口之间的最短距离矩阵（程序见附录2），记其中的前20行为。Step3：对的每一列取最小值，并记录最小值大于3km的数值，设第列的最小值由第行取得，则将路口交由第个服务平台管辖（若有两行均取得最小值则任取其一即可）（程序见附录3）。5.1.3 分配结果及分析表1 A区交巡警平台管辖范围表巡警平台 12345管辖的路口1、67、68、69、71、73、74、75、76、782、39、40、43、44、70、723、54、55、65、66 4、57、60、62、63、645、49、50、 51、52、53、56、

9、58、59巡警平台678910管辖的路口67、30、32、34、47、48、61、8、33、469、31、34、35、4510巡警平台1112131415管辖的路口11、26、2712、2513、21 、22 、23、 241415、28、29巡警平台1617181920管辖的路口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

10、、3.60（单位：km），即无法在3min内到达。能在三分钟之内能到达的路口节点占总结点数的93.5%。5.2 基于二部图的快速全封锁方案由假设2可知，一个巡警平台的警力最多封锁一个路口，要实现快速全封锁，就是要使13条交通要道在最短时间内全部由20个巡警平台中的某13个平台一一封锁（封锁时间以最后一个路口被封锁的时间计）。5.2.1 基于二部图的快速全封锁方案的思想对于某个时间，建立一个二部图，其中分别表示13个要道与A区的20个服务平台。边表示平台可在时间内到达要道，即。使用匈牙利算法得到的最大匹配。如果饱和，表明可从得到一个全封锁。否则，就增大时间，重新循环上述操作。5.2.2 基于二部

11、图的快速全封锁方案的实现设20个巡警平台分别到达13个交通要道的时间从小到大依次是。设，由二部图边的构造知。故若可在时间内封锁（即找到饱和的匹配），则一定可在时间内封锁。即有下述结论：结论1：最短封锁时间一定是某个巡警平台到达某个交通要道的时间。基于上述结论，封堵时间依次取，直到对应的二部图存在饱和的匹配，即可找到最短全封锁时间。Step1：表示13个交通要道距离20个巡警平台的最短距离矩阵，记20个巡警平台分别到达13个交通要道的时间从小到大依次是.Step2：依次取,确定二部图，记其对应的邻接矩阵为，其中Step3：使用匈牙利算法得到（）的最大匹配，若饱和，则当前为最短全封锁时间，算法终止

12、，否则转Step2。5.2.3 最快封锁方案及其检验由附录程序4，得最小全封锁时间=8分1秒，此时对应的二部图具有一个饱和13个要道的匹配由此矩阵，得全封锁方案如下（矩阵的1-13行分别表示12、14、16、21、22、23、24、28、29、30、38、48、62号路口，1-20列分别表示1-20号巡警服务台）.表2 A区对13条要道的全封锁方案服务台号12345710封锁路口38166248302912距离5.887.394.397.403.188.027.59服务台号111213141516封锁路口212224232814距离5.076.882.396.474.756.74经检验（上表第

13、3行），服务台到各个对应封锁路口的距离均不超过8.02km（约合8分1秒）,表明所得结果是正确的。5.3 A区交巡警服务平台调整方案5.3.1 交巡警平台各指标定义服务平台工作量：指该服务平台管辖的各路口节点日均报案率之和；某地的出警时间：指管辖该地的巡警从交巡警平台到达该地的时间。5.3.2 总体调整思路交巡警服务平台增设原则：以对辖区所有节点的快速响应为首要考虑因素，统筹兼顾各服务平台工作量的均衡性。即平台设置的首要目标是增加尽可能少的服务平台（2-5个）以实现对该区所有节点3分钟以内的全覆盖，并且在新增平台后，全区所有路口节点的管辖权按就近原则重新分配后各平台工作量尽可能均衡。Step1

14、：新增平台数目确定筛选出出警时间长于3分钟（即距离管辖平台大于3千米）的路口节点，称其为偏远节点。表3 长于三分钟的偏远节点与巡警平台的距离偏远节点282938396192出警距离（km）4.75.73.43.64.13.6上述6个出警时间超过3分钟的节点可分为4组（如图1所示），从最短距离矩阵中可知，不同组类节点间距离均大于6km，故新增一个节点至多能使一类节点的出警时间降到3分钟以内，因此至少需要新增4个服务平台。图1 四组偏远路口另一方面，从4组中各取一个节点作为服务平台即可满足对这6个节点3分钟的全覆盖。初步方案可定为在28、 38、 61、92位置设立服务平台，从新分配管辖范围后工作

15、量的均方差为3.1005。Step2：平台位置的确定总体思想：新增四个平台，在满足所有节点出警时间均不超过3分钟的前提下，使得调整后的工作量具有尽可能小的均方差。记为这6个节点（28、29;38、39;61;92）的3km以内邻域节点，因为一个服务平台最多只能覆盖一个组类，故新增的4个节点应分别取自以及。由最短距离矩阵得，故共有种新增方案。用计算机对这些方案进行比较，选出使各服务平台工作量方差最小的新增位置，分别为28、39、 48、87号，按5.1重新分配后工作量均方差为2.3703。图2 两种方案下不同平台的工作量图注释：方案一为根据28,38,61,92共4个点选择的分配方案结果 方案二

16、为根据28，39，48，87共4个点选择的分配方案结果由图可知方案二的各平台工作量较方案一有明显收敛，即各平台工作量较均衡，工作负荷很大（9以上）和很小（2以下）的平台数量都明显减少，但图中大部分平台的工作量并未改变，这是由以下两方面原因造成的：一是由于问题节点的位置原本就比较偏远，其周边的节点有限，因此新增服务点后，能产生的影响有限；二是由于要优先满足3分钟覆盖这一限制条件，因此新增服务台的位置被限定在一定的区域内，无法全局安排，因此，只能产生局部影响。5.4基于熵权的交巡警服务平台设置的模糊综合评价模型5.4.1基本思想 先确定影响主城六区各交巡警服务平台设置合理性的3个影响指标（各区服务

17、平台平均的工作量、各区服务平台节点平均覆盖率、各区服务平台服务人口密度），再采用熵权的模糊评判方法，对平台设置合理性进行判决，并针对判决结果对设置方案进行合理的调控。5.4.2确定影响合理性因素 根据设置交巡警服务平台的原则和任务，结合现有服务平台工作量的不均衡和部分地方出警时间过长情况，可以确定出影响交巡警服务平台设置合理性的3项指标：服务平台的工作量、服务平台节点覆盖率、平台服务人口密度。 针对全市各区的具体情况，基于全局的考虑，先将各指标具体阐述如下： 1）各区服务平台的平均工作量2）各区服务平台节点覆盖率 基于第一问Warshall- Floyd算法计算出区中各路口与最近的巡警平台的距

18、离均大于3km的服务平台个数为6个的方法，求出全城582个节点间的最短路矩阵，通过Matlab编程依次可以算出剩余五区（）各个路口与最近的巡警平台的距离均大于3km的服务平台个数，记为平台覆盖不到的路口数，那么各区服务平台节点覆盖率为： 3）区服务平台服务人口密度5.4.3 模型算法 Step1：建立影响交巡警服务平台设置合理性的因素域 Step2：建立评判集 Step3：在影响交巡警服务平台设置合理性的因素域与评判集之间进行隶属度分析，建立模糊关系矩阵 矩阵中表示因素域中第个因素对于等级域中第个等级的隶属度。 Step4：确定，其为3个因素对交巡警服务平台合理性指标的权重，并满足 Step5

19、：求出，评价结果属于中最大值对应的合理性等级。5.4.4 建立评价集 服务平台设置合理性大小是相对且模糊的，不可能定性描述，是属于模糊集理论。那么根据模糊数学理论，可以将3个指标分为6个等级，分别为非常合理，较合理，合理，不是很合理，不合理，明显不合理。 熵权法权重向量的确定 1）判断矩阵权值 要比较3个指标、对于服务平台设置的影响，根据上述指标计算公式，通过Excel和Matlab编程求解得各区服务平台平均的工作量、各区服务平台节点平均覆盖率以及各区服务平台服务人口密度（万人/服务平台）如下表：表4 6城区3项指标的统计结果区域各服务平台平均工作量各服务平台节点平均覆盖率各服务平台服务人密度

20、A6.22593.75%3B8.391.78%2.625C11.01169.48%2.882D7.53376.92%8.111E7.9668.93%5.067F9.92767.59%4.818将上述6城区3项指标归一化为判断矩阵： 2）3个评价指标的熵值 根据熵权法的公式中熵的定义公式计算出3个评价指标的熵值为： 5.4.5 模型的求解 交巡警服务平台合理性模糊综合评价等于与两个矩阵的乘积， 即 Matlab编程（见附录5）求解得： 结合评价指标的熵值： 根据最大隶属度原则,0.195最大，所对应的是明显不合理，故全市六区的巡交警服务平台设置不合理。5.4.6解决方案 结合表4，发现区服务平台

21、的平均工作量为11.011（发案率），是六个区中工作量最大的，而区服务平台对道路节点的平均覆盖率为69.48%，又是六个区中非常低的，服务人口还较少，说明区平台设置很不合理，而区服务平台平均工作量也很大，节点平均覆盖率最低，区平台设置也不合理。即： 1）从服务节点的覆盖率出发 根据前面求得六区各路口与最近的巡警平台的距离均大于3km的服务平台个数和对应的节点，得出、区交巡警平台覆盖不到3km部分路口如下：表5 C、F交巡警平台未覆盖路口城区 该城区覆盖不到的节点名称覆盖不到总节点数 183，199，200，201，202，203，205，206，20747 486，487，505，506，50

22、7，508，509，510，51235故建议在上述孤立节点附近增设服务平台，以增大服务节点的覆盖率。 2）从服务平台的工作量出发 从全市六区交通网络与平台设置的示意图看出、区是在郊区，同时、两区的工作量又很大，故建议在原有服务平台上增加值班巡警人数基础上，在所辖城区边上安排机动巡逻车，进行机动巡逻。5.5基于全动态二部图的围堵方案要实现对犯罪嫌疑人的围堵，最完美的设想是将犯罪嫌疑人刚刚经过的节点和正在前往的节点分别封锁，从而将犯罪嫌疑人限定在两个有连线且已经封锁的节点间。5.5.1 一种尝试的封堵方案：两端封堵法由最短距离矩阵可以确定从32节点出城所需的最短时间，确定封堵时间上限设，记表示距离

23、32号节点车程不超过的所有路口，表示所有与中任一节点相邻的路口集合，易知，若能在时刻封锁，则是一个可行的围堵时间。Step1：依次此取 ，Step2：建立二部图,其中表示全城所有的服务平台集合，其中的边表示平台可在时间内到达路口，即与的车程不超过Step3：求的最大匹配，若饱和，算法结束，否则转Step1。结果：执行此算法未找到饱和匹配，表明此方案下不能完成围堵任务。5.5.2 改进的封堵方案：一端封堵法与两端封堵法相对应，一端封堵法在于封锁，相应于两端封锁法，此方法只需封锁更少的节点。结论二： 若交巡警可在时间内全封锁，则嫌疑人无法逃离本市。证明：反证法。假设嫌疑人可以逃离本市，设其逃离本市

24、经过的路口序列为：，其中表示本城17个出城口之一。因，显然有。记，注意到，故。由的最小性，知。因相邻路口，故，从而有. 另一方面，因包含了从32节点车程不超过的所有路口以及，故嫌疑人到达的时间大于. 这是一个矛盾，因为在时刻已被某巡警封锁，证毕。算法实现：将两端封锁法中的改为即可（程序见附录6）。结果分析：当时，算法找到一组围堵方案如下表所示：表6 交巡警平台要封锁的路口号及其之间的距离服务平台123451011121314封锁路口8485901861932224471459487平台与路口的距离（km）4.096.647.857.2210.27.713.816.45.059.64服务平台16

25、17166167168169170171172173封锁路口52192248252175254178182213221平台与路口的距离（km）10.75.488.713.814.982.226.1784.899.7服务平台174175178179320321372475476477封锁路口274212275277370371491568530535平台与路口的距离（km）6.996.493.17.818.9810.18.014.655.63服务平台478480481482483484485封锁路口544554555563528565567平台与路口的距离（km）2.138.145.638.26

26、10.69.065.1检验：由表中的平台与路口的距离均不超过10.8km，结果合理。六 模型的评价与改进6.1 模型的评价1.模型的优点1）在设置新的交巡警平台时，在优先考虑到出警时间的同时也统筹兼顾到各平台工作量的平衡性；2）运用到了模糊评判模型，将模糊的且不易定性描述的合理性大小进行量化评判。3）将封锁固定路口及围堵嫌疑人的问题统一转化为依时间变化的二部图的匹配问题，借助于匈牙利算法，得以简单高效解决。2.模型的缺点过于强调出警时间（3km覆盖），使得交巡警服务平台的工作量不太均衡。6.2 模型的改进放松对出警时间的要求，建立工作量和出警时间的多目标规划，以使得管辖方案的配置更为合理。参考

27、文献1王文波，数学建模及其基础知识详解M，武汉：武汉大学出版社.2刘振航，数学建模，M北京：中国人民大学出版社，2004.3李明哲，金俊，石端银，图论及其算法M, 北京：机械工业出版社，2010.4刘卫国，MATLAB程序设计教程M，北京：中国水利水电出版社，2005.5姜启源，谢金星，数学建模案例选集M，北京：高等教育出版社，2006.19附录1. A区初始距离矩阵MalLab程序function M=initdisM()load JDLX % 载入节点和路线的数据M=inf(92,92);for i=1:92 M(i,i)=0;endm,n=size(LX);for i=1:m start

28、=LX(i,1); endd=LX(i,2); if(start<=92&&endd<=92) M(start,endd)=sqrt(JD(start,1)-JD(endd,1)2+(JD(start,2)-JD(endd,2)2); M(endd,start)=M(start,endd); endend2最短距离矩阵functionD,R=floydwarshall()D=initdisM();n=length(D);for(i=1:n) for(j=1:n) R(i,j)=j; endendfor(k=1:n) for(i=1:n) for(j=1:n) if(

29、D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=k; end; end; endend3.管辖范围的分配load JDLXD,R=floydwarshall()D20_92=D(1:20,1:92);Min=min(D20_92)a=zeros(92,1);for i=1:92 a(i)=find(D20_92(:,i)=Min(i);enda %分配方案b=zeros(20,1);for i=1:20 ctrlby_i=find(a=i); fananlv=JD(:,3); b(i)=sum(fananlv(ctrlby_i);end

30、b %每个平台的工作量4.1匈牙利最大匹配算法%二部图的最大匹配算法匈牙利算法%A为二部图的矩阵表示%返回值M为最大匹配function M=maxmatch(A)m n=size(A);M=zeros(m,n);y=zeros(1,n);%求一个极大初始分配for i=1:m for j=1:n if(A(i,j)&y(j) M(i,j)=1; y(j)=1; break; end endendwhile(1) x=zeros(1,m); %0表示未标记 y=zeros(1,n); for i=1:m if(any(M(i,:) %xi是非饱和的 x(i)=-(n+1); %标记，-

31、表示未扫描, y共有n个 end end while(1) %尝试寻找M增广链 flag=0; for i=1:m if(x(i)<0) %标记但未扫描 x(i)=-x(i); %正号表已扫描 for j=1:n if(A(i,j)&y(j)=0&M(i,j)=0) y(j)=-i; flag=1;%出现新标记的y end end end end if(flag=0) break;end flag=0; for j=1:n if(y(j)<0) y(j)=-y(j); for i=1:m if(A(i,j)&x(i)=0&M(i,j)=1) x(i)

32、=-j; flag=1;%出现新标记的x end end end end if(flag=0) break;end end flag=0; for j=1:n if(y(j)>0&any(M(:,j) %Breakthrough:找到增广链。存在一个标记且非饱和的yj flag=1; k=y(j); M(k,j)=1; while(x(k)=n+1) %倒退求M增广链，修改M M(k,x(k)=0; M(y(x(k),x(k)=1; k=y(x(k); end break; end end if(flag=0) break;end %Non-Breakthrough end 4.

33、2基于二部图匹配的13条交通要道的封锁方案m=13;n=20;FF=1:20;%20个服务平台YD=12 14 16 21 22 23 24 28 29 30 38 48 62;%13个要道D=floydwarshall();L=D(YD,FF);l=sort(L(:);for i=1:length(l) a=l(i); A=(L<=l(i)+eps) %建立二部图，其中边表示在了平台与要道距离不超过了l(i) Q=maxmatch(A)if (sum(Q(:)=length(YD) % 饱和13个路口 break; %找到最小的距离（时间） endenda 5.模糊评判程序functi

34、on Example8_6A=1/12,1/6,1/3,2/3,1/6,1/12;R=0.12 0.16 0.22 0.15 0.16 0.19; 0.20 0.20 0.15 0.16 0.15 0.14; 0.11 0.10 0.11 0.31 0.19 0.18 'fuzzy_zhpj(3,A,R) %调用综合评判函数end%functionB=fuzzy_zhpj(model,A,R) %模糊综合评判B=;m,s1=size(A);s2,n=size(R);if(s1=s2) disp('A的列不等于R的行');else if(model=1) %主因素决定型 for(i=1:m) for(j=1:n) B(i,j)=0; for(k=1:s1) x=0; if(A(i,k)<R(