课程设计交巡警服务平台的设置与调度

1、交巡警服务平台的设置与调度摘 要对提供的数据进行了预处理后，利用djist算法求出任意两个路口节点之间的最短路程，程序见附录2，结果见“a区节点间最小路的值.xls”。交巡警服务平台分配管辖范围的原则是（1）所管辖的节点到该交巡警服务平台的最近路程应尽量小于3000m,（2）各交巡警服务平台管辖范围内的所有节点发案率之和应尽量接近平均发案率6.225。由此建立多目标规划模型。对该模型利用matlab编程（见附录1）求出满意解如图1所示。对进出该区的13条交通要道快速封锁问题，我们把参与封堵各交巡警服务平台到各出口要道最短路程之和的最小化作为第一目标，把参与封堵各交巡警服务平台到各出口要道的最长

2、路程最小化作为第二目标，建立多目标规划模型，利用matlab编程（见附录4）求解，结果如表1和图2所示。根据a区各交巡警服务平台的出警时间方差和工作量方差，考虑在服务平台15附近的a区出口节点29增设一个服务平台，在服务平台7附近的路口节点48增设一个服务平台，在路口节点91增设一个服务平台。增设3个服务平台后的a区巡警服务平台分配管辖范围如图3所示，合理性有较大改善。对全市六区交巡警服务平台设置合理性评价如a区，主要要避免服务平台的出警时间过长，不能及时赶到突发事件地点，并且使各服务平台的工作量尽量均衡。我们计算了b区的出警时间方差和工作量方差如表3所示（程序见附录6）。建议在99、94、9

3、8处进行增设服务平台，另外也可以考虑在95处增加警力。其他各区的处理方法同b区。该市p点发生了重大刑事案件，快速围堵嫌疑犯的调度问题，是一个动态规划。我们给出了嫌疑犯逃跑各阶段的路口集合，可能的逃跑路线如图4所示。用matlab编程（程序见附录7），得到最佳围堵方案如表4。关键字：动态规划 多目标规划 最短路径算法 图论 0-1规划一、 问题的重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，

4、如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）根据给出的相关数据信息，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情

5、况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区a，b，c，d，e，f）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。如果该市地点某点处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、 问题的分析1、交巡警服务平台分配管辖范围的基本原则应该是（1）所管辖的范围内出现突发事件时，应尽量能在3分钟内有交巡警到达事发地，其实就是所管辖的节点到该交巡警服务平台的最近路程应尽量小于30

6、00m,（2）各交巡警服务平台的工作量应尽量均衡，就是各交巡警服务平台管辖范围内的所有节点发案率之和应尽量接近平均的发案率。由此可见该问题是一个多目标规划问题。为了求解问题，我们首先对提供的数据进行一些预处理，再利用djist算法求出任意两个路口节点之间的最短路程，程序见附录二，结果见“a区节点间最小路的值.xls”。由于题目提供的节点坐标单位为mm，因此我们将警车3分钟走过的路程根据比例化为30mm。如该区发生重大事件，交巡警对进出该区的13条交通要道要实现快速全封锁，即是求各交巡警服务平台到13条交通要道最小路径的总体最小化，以满足尽量实现快速封锁的目的。也是一个多目标规划问题。增设交巡警

7、服务平台的原则是：（1）对有些出警时间过长的地方，可以考虑增设交巡警服务平台，以期尽量能在3分钟内有交巡警到达事发地。（2）有些工作量过大的交巡警服务平台附近，可以考虑增设交巡警服务平台，以期工作量应尽量均衡。2、对该市现有交巡警服务平台设置方案合理性的分析，主要是看目前的方案中是否存在有些服务平台工作量过大和出警时间过长的情况，如果有明显不合理，应考虑增设服务平台或对工作量过大的服务平台增加警力。该市p点发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速围堵嫌疑犯，给出最佳调度方案，是一个动态规划问题。 三、 模型假设1、任意相邻两个路口之间的道路都是直线。2、增设服

8、务平台的时，其他服务平台地点不变。3、不考虑交通堵塞，犯罪嫌疑人的车速与交巡警的车速相同，均为常量。4、各交巡警服务平台的警力配备基本一致。四、 符号说明：表示从第i个服务平台到第j个路口节点的最短路程。：表示从第i个服务平台到第j个路口节点最短路程的正偏差。：表示第j个路口节点是否属于第i个服务平台，是为1否为0。：表示第i个服务平台是否负责围堵第j个交通要道，是为1否为0。：表示第j个路口节点的发案率。：a区平均每个服务平台的发案率 ：表示从第k个服务平台到第j个交通要道的最短路程。：表示第k个服务平台是否负责封堵第j个交通要道，是为1否为0。五、 模型的建立和求解5.1 a区交巡警服务平

9、台分配管辖范围的优化模型根据问题分析，交巡警服务平台分配管辖范围的原则主要是：（1）所管辖的节点到该交巡警服务平台的最近路程应尽量小于30mm，所以将总的正偏差最小化作为第一目标。即最小化 其中：=（2）各交巡警服务平台的工作量应尽量均衡，因此将服务平台所管辖的路口节点的总案发率的方差最小化作为第二目标。即最小化建立如下的多目标规划模型：对该模型利用matlab编程（见附录1）求出满意解：如图1所示：图1 a区交巡警服务平台分配管辖范围示意图5.2 交巡警服务平台警力合理的调度模型对于该区发生重大事件，交巡警对13个交通要道快速全封锁，根据问题分析，我们把参与封堵各交巡警服务平台到各出口要道最

10、短路程的总和最小化作为第一目标，把参与封堵各交巡警服务平台到各出口要道的最长路程最小化作为第二目标，建立多目标规划，模型如下： 其中 利用matlab编程（见附录4）求解，结果如表1：表1 a区交巡警服务平台对13条交通要道全封锁方案出口节点标号12222362483029281421241638服务平台标号12111345871514910162 图2为示意图，箭头起点为服务平台，终点为封锁的出口节点。图2 a区交巡警服务平台对13条交通要道全封锁方案示意图5.3 a区交巡警服务平台增设方案根据5.1交巡警管辖区域的划分，通过计算得出a区各交巡警服务平台的出警时间方差和工作量方差（见附录5）

11、，结果如下。表2 a区各交巡警服务平台的出警时间方差和工作量方差出警时间方差服务平台标号工作量方差服务平台标号010203060409050100601108012090140100160110190120.0380130.03150140.1440171.6310184.7330194.731816.47164.732036.15205.181346.5426.635141.66710.73171036.181522.807从表1中发现服务平台15出警时间过长，服务平台7出警时间过长且任务过重，服务平台20出警时间较长且任务较重，因此考虑在服务平台15附近的a区出口节点29增设一个服务平台，

12、在服务平台7附近的路口节点48增设一个服务平台，在18和20之间的路口节点91增设一个服务平台。增设三个服务平台后的a区巡警服务平台分配管辖范围如图3所示。图3 a区增设后的巡警服务平台分配管辖范围示意图5.4 全市交巡警服务平台设置合理性评价及改进方案对全市六区交巡警服务平台设置合理性评价的依据如5.1，主要要避免服务平台的出警时间过长，不能及时赶到突发事件地点，并且使各服务平台的工作量尽量均衡。我们计算了b区的出警时间方差和工作量方差（程序见附录6）。表3 b区交巡警服务平台设置评价指标出警时间方差服务平台标号工作量方差服务平台标号09309309509709709909801000100

13、0.25968.15964.419421.48945.2995229.569914.4498从表3中可以看出服务平台99的出警时间过长，服务平台94和96的出警时间较长，服务平台98的工作量很大，服务平台95和94的工作量也较大。因此可以采用5.3的方法在99、94、98处进行增设服务平台，另外也可以考虑在95处增加警力。其他各区的处理方法同b区。5.5 全市交巡警服务平台警力资源的最佳围堵嫌疑犯方案对于该市p点（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，调度全市交巡警服务平台警力资源的最佳围堵方案如下：案发点为，以为始点的道路之终点

14、为，所有点的集合为称之为状态，为第一步可能的围堵的路口集合，同理（集合元素的排序按距p的最短路程升序排列）称之为状态为第步可能的围堵路口集合状态转移规律：1、在第步可能围堵路口集合中，按升序依次判断犯罪嫌疑人若从此路口逃跑是否能够及时堵住（假设只要交巡警先到路口设卡，一定能够堵住，到达时立即可以实施围堵，设卡时间不计）。如果能堵住则继续判断下一个点，如果堵不住，则以该点为始点，向外扩展一步，即以该点为始点在逃逸方向上找终点，将若干个终点代替该点，得到状态的围堵点集合。2、如果某状态中所有路口都能堵住，则可输出最佳调度方案。通过编程计算第一状态的路口集合为7，31，33，第二状态的路口集合为8，

15、 34，37，47，15，30，第三状态的路口集合为5，6，9，10，28，29，36，46，48，237，第四状态的路口集合为16，26，35，39，49，45，49，50, 55，59，61，235，236，238，239，247，370，371，嫌疑犯从案发地点p可能逃跑的路线如图4所示，不同的线型对应着不同状态下可能逃跑的路线及到达的路口节点。按照上述思路利用matlab编程计算的结果如表4（程序见附录7）：表4 全市交巡警服务平台围堵嫌疑犯方案围堵节点标号569102829364648237服务平台标号56910151711687173p图4 嫌疑犯从案发地点p可能逃跑的路线图六、

16、模型的评价与推广总的来说，模型与算法的思路清晰，其结果可帮助交巡警的调度和最佳行进路径的选择，减少了出警时间，可操作性强，有一定的实际应用价值，模型与算法也有一定的局限性和不足，如个别地区的出警时间超过3分钟，也没有考虑道路的畅通性等不定因素对出警时间的影响等.本模型与算法较好的解决了交巡警平台的最优选址问题，当事故发生时，交巡警可以第一时间到达事发地点，有效的改善了交巡警在执行任务中的效率，并且该模型与算法也可运用到其他应急问题中，比如关于消防救援问题、重大生产安全事故应急救援问题等.七、 参考文献【1】 赵静,但琦等编著，数学建模与数学实验（第3版）， 北京，高等教育出版社，2008。【2

17、】 云舟工作室编著，matlab6数学建模基础教程，北京，人民邮电出版社，2001。【3】 吴翊，吴孟达，成礼智编著，数学建模的理论与实践，长沙，国防科技大学出版社，1999。【4】 谭永基，俞文吡编著，数学模型，上海，复旦大学出版社，1997。【5】 王海英等编著 图论算法及其matlab实现 北京航空航天大学出版社 2010【6】 王桂平，王衍，任嘉辰编著 图论算法理论、实现及应用 北京大学出版社 2011附件附录1%a区交巡警服务平台分配管辖范围求解clear all;mln = xlsread(d:b,2,a2:b138); %matrix of line between nodesm

18、n = xlsread(d:b,1,a2:e93); %matrix of nodes% create 0-1 matrix of line beteen nodesmln01=zeros(92,92);mlnsize=size(mln);mlnr=mlnsize(1); %row number of mlnfor i=1:mlnr if mln(i,1)=92 & mln(i,2)=92 % only deal with the data in the part a mln01(mln(i,1),mln(i,2)=1; endend% solve the path between the n

19、odesmlnpath=zeros(92,92);m=10000; %set m with a big numberfor i=1:92 for j=1:92 if mln01(i,j)=1 mlnpath(i,j)=sqrt(mn(i,2)-mn(j,2)2+(mn(i,3)-mn(j,3)2); end % set infinite number to the nodes with not connection endendsp=shortpath(mlnpath);for h=1:1000 randservicenode=randperm(20); handlenode=zeros(92

20、,1); %storage the depart result,0 note not servicenode=1:20; for i=1:20 startsn=servicenode(randservicenode(i); handlenode(startsn)=startsn; totalwork=0; clear totalpath startnodea totalpath(1)=0; startnodea(1,:)=startsn,0; startnodecount=1; while totalwork=10 startnode=startnodea(startnodecount,1);

21、 for j=1:mlnr if mln(j,1)=startnode & handlenode(mln(j,2)=0 tempm=startnodea(:,1); tempc=find(tempm=startnode); tempp=mlnpath(startnode,mln(j,2)+totalpath(tempc); if tempp30 totalpath(length(totalpath)+1)=mlnpath(startnode,mln(j,2)+totalpath(tempc); startnodea(size(startnodea,1)+1,:)=mln(j,2),startn

22、ode; handlenode(mln(j,2)=startsn; totalwork=totalwork+mn(mln(j,2),5); end end end startnodecount=startnodecount+1; if size(startnodea,1)sp(uanode,j) minservice=j; mindistance=sp(uanode,j); end end handlenode(uanode)=minservice; uam(i,2)=minservice; uam(i,3)=mindistance; end totalwork=0; largem=0; fo

23、r i=1:20 fservices=find(handlenode=i); work=0; for j=1:length(fservices) work=work+mn(fservices(j),5); end if work6.225 totalwork=totalwork+(work-6.225)2; largem=largem+1; end end finaltotalwork(h)=totalwork; finalhandlenodeh=handlenode; finallargem(h)=largem;enda,v=min(finaltotalwork)finallargem(v)

24、附录2%求最短路径函数function sp=shortpath(a)m=10000;a=a+a;for i=1:length(a) for j=1:length(a) if a(i,j)=0 a(i,j)=m; end endendfor i=1:length(a) pb(1:length(a)=0; pb(i)=1; d(1:length(a)=m; d(i)=0; temp=i; while sum(pb)length(a) tb=find(pb=0); d(tb)=min(d(tb),d(temp)+a(temp,tb); tmpb=find(d(tb)=min(d(tb); temp

25、=tb(tmpb(1); pb(temp)=1; end sp(i,:)=d;end附录3%寻找a区出口节点clear all;mln = xlsread(d:b,2,a2:b928); %matrix of line between nodesmn = xlsread(d:b,1,a2:e93); %matrix of nodes% create 0-1 matrix of line beteen nodesmln01=zeros(92,92);mlnsize=size(mln);mlnr=mlnsize(1); %row number of mlnfor i=1:mlnr if mln(i

26、,1)=92 & mln(i,2)=92 % only deal with the data in the part a mln01(mln(i,1),mln(i,2)=1; endend% solve the path between the nodesmlnpath=zeros(92,92);m=10000; %set m with a big numberfor i=1:92 for j=1:92 if mln01(i,j)=1 mlnpath(i,j)=sqrt(mn(i,2)-mn(j,2)2+(mn(i,3)-mn(j,3)2); end % set infinite number

27、 to the nodes with not connection endendsp=shortpath(mlnpath);j=1;crossnode=zeros(13,1);for i=1:mlnr if (mln(i,1)92) | (mln(i,1)92 & mln(i,2)=92) if mln(i,1)=92 if isempty(find(crossnode=mln(i,1) crossnode(j)=mln(i,1); j=j+1; end else if isempty(find(crossnode=mln(i,2) crossnode(j)=mln(i,2); j=j+1;

28、end end end end附录4%寻找封锁交通要道的程序clear all;mln = xlsread(d:b,2,a2:b143); %matrix of line between nodesmn = xlsread(d:b,1,a2:e93); %matrix of nodes% create 0-1 matrix of line beteen nodesmln01=zeros(92,92);mlnsize=size(mln);mlnr=mlnsize(1); %row number of mlnfor i=1:mlnr if mln(i,1)=92 & mln(i,2)=92 % o

29、nly deal with the data in the part a mln01(mln(i,1),mln(i,2)=1; endend% solve the path between the nodesmlnpath=zeros(92,92);m=10000; %set m with a big numberfor i=1:92 for j=1:92 if mln01(i,j)=1 mlnpath(i,j)=sqrt(mn(i,2)-mn(j,2)2+(mn(i,3)-mn(j,3)2); end % set infinite number to the nodes with not c

30、onnection endendsp=shortpath(mlnpath);load out13.matsp13=zeros(13,20);for i=1:length(crossnode) tempsp13(i,:)=sp(crossnode(i),1:20); endsave shortpath.mat sp sp13for i=1:13 for j=1:20 if tempsp13(i,j)=0 tempsp13(i,j)=m; end endendfor h=1:1000 randoutnode=randperm(13); sp13=tempsp13; clear serviceton

31、ode servicetonode=zeros(13,3); % the first column store the out node,second store service node,third store distance servicetonode(:,1)=crossnode; % for i=1:13% if crossnode(randoutnode(i)=20% servicetonode(randoutnode(i),2)=crossnode(randoutnode(i);% servicetonode(randoutnode(i),3)=0; % end% end for

32、 i=1:13 if servicetonode(randoutnode(i),2)=0 a,b=min(sp13(randoutnode(i),:),2); tempm=servicetonode(:,2); while isempty(find(tempm=b) sp13(randoutnode(i),b)=m; a,b=min(sp13(randoutnode(i),:),2); end servicetonode(randoutnode(i),2)=b; servicetonode(randoutnode(i),3)=a; end end sumd=sum(servicetonode(

33、:,3); finalstnh=servicetonode; finalsd(h)=sumd;enda,v=min(finalsd)附录5%a区交巡警服务平台设置合理性指标计算clear all;mln = xlsread(d:b,2,a2:b141); %matrix of line between nodesmn = xlsread(d:b,1,a2:e93); %matrix of nodes% create 0-1 matrix of line beteen nodesmln01=zeros(92,92);mlnsize=size(mln);mlnr=mlnsize(1); %row

34、number of mlnfor i=1:mlnr if mln(i,1)=92 & mln(i,2)30 path=path+(sp(fservices(j),i)-30)2; end end totalpath(i)=path; if work6.225 totalwork(i)=(work-6.225)2; largem=largem+1; endendsorttw,positionw=sort(totalwork)sorttp,positionp=sort(totalpath)附录6%b区交巡警服务平台设置合理性指标计算clear all;load partb.mat % partb.

35、mat sp mn mln sn b131handlenode=minhn;len=length(mn);lensn=length(sn);avework=sum(mn(:,5)/lensn;totalwork=zeros(lensn,1);totalpath=zeros(lensn,1);largem=0;for i=1:lensn fservices=find(handlenode=sn(i); work=0; path=0; for j=1:length(fservices) work=work+mn(fservices(j),5); if sp(fservices(j),i)30 path=path+(sp(fservices(j),i)-30)2; end end totalpath(i)=path; if workavework totalwork(i)=(work-avework)2; largem=largem+