数学建模：交巡警平台的设置与调度

1、-作者xxxx-日期xxxx数学建模：交巡警平台的设置与调度【精品文档】交巡警服务平台的设置与调度一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络

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

3、服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析（1）问要求为A区的20个交巡警服务平台划分管辖范围，使每个路口尽量在3分钟内能够由交巡警赶到。根据实际情况，每个交巡警服务平台的资源是基本均衡且有限的。我们规定xij=1, 路口i被平台j管辖0，路口i不被平台j管辖，则此问题可看作是一个多目标01规划问题。目标函数为：一：尽量多的路口能由交巡警在3

4、分钟内赶到；二：若某路口不能由交巡警在3分钟内到达，则交巡警到达此路口的时间应尽量短；三：各交巡警平台的工作量尽量均衡。求解此模型时，首先用matlab对数据进行初步整理，然后将目标一、二作为约束条件把多目标规划转化为单目标01规划问题，利用lingo软件求解。 （2）问中要求对进出A区的交通要道实现快速全封锁。可以将时间最小化问题转化为距离最短问题。建立以平台到封锁的交通要道中的最长距离最短为目标函数，以一个平台的警力最多封锁一条要道、每条要道必须被一个平台封锁为约束条件的规划模型。将此模型用lingo软件解出后，有多种调度方案，我们可以继续建立以封锁交通要道的总距离最短为目标函数，以解出的

5、最长距离的最小值为约束条件的规划模型进行进一步优化，用lingo解出最终的封锁调度方案。 （3）问要求增加平台，解决平台工作量不均衡和某些地方出警时间过长的问题。在（1）问中得到28,29,38,39,61,92这6个路口不能由交巡警在3分钟内到达。只要在离这6个路口距离不大于3km的路口处增加平台，就可以使得所有路口都能由交巡警在3分钟内到达，可以认为解决了出警时间过长的问题，并且可以求解出应增加的最少平台数。进而解决工作量不均衡的问题，可建立01变量fj=1, 在路口j处增加平台0, 不在路口j处增加平台，将平台工作量均衡度最大为目标函数，将解出的增加平台的可行数量作为约束条件建立规划模型

6、，用lingo可求解出增加平台的具体位置。最后综合分析出应增加的平台数量和具体位置。三、基本假设与符号说明1.假设每个巡警服务台的职能和警力配备基本相同； 2.假设每个路口只由一个巡警服务平台进行管辖； 3.假设每个巡警服务平台至少管辖一个路口； 4.假设巡警都按最短路径到达各案发路口； 5.假设每个路段道路畅通，可以双向行驶，没有堵车现象；6.假设犯罪案件都在路口上发生； 7.假设在重大案件发生时，每个平台只有封锁一个路口的能力； 8.工作量：每个巡警服务台所管辖范围内的所有路口案发率之和； 9.出警时间：巡警到达案发路口所需时间； 10.每个区的交巡警平台只可管辖本区内的路口，不可跨区管辖

7、。11.假设巡警车和犯罪嫌疑人的车行驶中速度保持匀速且车速均为60km/h；12.假设巡警在接到报案后并不知道逃犯的逃跑方向；3.2符号说明1. xij=1, 路口i被平台j管辖0，路口i不被平台j管辖；2. dij：路口i到j的最短距离；3. U0：交巡警能够在3分钟内到达的路口集合；4. Vi：能够在3分钟内到达路口i的交巡警平台的集合；5. U1：交巡警不可在3分钟内到达的路口集合；6. ri：第i个路口的发案率；7. r：交巡警服务平台的平均工作量；8. rrj：平台j的工作量；9. yij=1, 第i条交通要道由交巡警服务平台j封锁0，第i条交通要道不由交巡警服务平台j封锁；10.

8、sij：第i条交通要道到平台j的最短距离；11. fj=1, 在路口j处增加平台0, 不在路口j处增加平台；12.n：增加的交巡警服务平台的个数；四、模型的建立与求解4.1 问题一（1）：管辖区域的确定4.1.1 模型建立 此问要求在A区20个交巡警服务平台位置确定的情况下，分配管辖范围，使交巡警尽量能够在3分钟内到达事发地。本文考虑了三个分配原则即为三个目标。一：交巡警尽量能在3分钟内到达事发地。二：在不能满足3分钟内到达事发地的情况下，交巡警到达事发地的时间应尽量短。三：由于各交巡警平台的职能和警力配备基本相同，因此各交巡警平台的工作量应尽量均衡。由以上分析可知，此问为一个多目标规划问题。

9、对于第一个目标，可以转化为交巡警能在3分钟内到达管辖路口的路口数应尽量多。建立01变量：xij=1, 路口i被平台j管辖0，路口i不被平台j管辖。假设 dij为路口i到交巡警平台j的最短距离。U0为交巡警可在3分钟内到达的路口集合，即若j1,220, 使得dij3km，则iU0。Vi为能够在3分钟内到达路口i的交巡警平台的集合。此目标可表示为：maxf1=iU0jVixij； 对于第二个目标，假设U1为交巡警不可再3分钟内到达的路口集合，此目标可表示为：minf2=j=120xij*dij, iU1;对于第三个目标，本文用每个平台所管辖路口发案率的和表示平台的工作量，用工作量的变异系数来度量各

10、平台工作量的均衡度，各平台工作量越均衡，变异系数越小。假设ri为第i个路口的发案率，r为所有平台的平均工作量，rrj为第j个平台的工作量，此目标可表示为：minf3=119j=120(rrj-r)2r; r=i=192ri20;满足条件为：1.每个路口由一个交巡警服务平台管辖：j=120xij=1, i=1,292;：i=192xij1, j=1,220;3.每个交巡警服务平台必须管辖本路口：xij=1, i=j;i,j=120; 4.1.2 模型求解 对于模型中的多目标规划问题，本文将之转化为单目标规划问题。首先将目标一和目标二解出，然后将这两个目标作为约束条件，以目标三作为最终的单目标用l

11、ingo软件求出最终解。1.各路口间最短距离的确定。首先用公式算出两两之间的距离（如果有路），得出582*582的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用一个较大的数代替,在matlab环境下利用floyd算法求出最短路程矩阵D，矩阵D中两两之间的距离即为dij。程序见附录一。 Floyd算法的基本步骤如下： 令dij是顶点vi到顶点vj 的最短距离, wij是顶点vi到vj的权。STEP1:输入临界矩阵W。对所有i, j, 有dij=wij, k=1。STEP2: 更新dij。对所有i, j, 若dik+dkjdij, 则令dij=dik+dkj。STEP3: 若dii

12、0, 则存在一条含有顶点vj 的负回路, 停止; 或者k=n停止, 否则转到STEP2。 用MATLAB编程从上述得到的各路口的最短距离中抽出92个路口分别到20个服务平台的最短距离。筛选出dij3km的点，求出交巡警可在3分钟内到达的所有路口（集合U0），剩下的路口则为交巡警不可能在3分钟内到达的路口（集合U1）。程序见附录二。 为满足目标一，只需要满足：j=120xij*dij3, iU0; 为满足目标二，将集合U1=28,29,38,39,61,92中的路口直接分配给距离此路口最近的交巡警服务平台。结果如下：交巡警平台15162720管辖路口28、2938396192 将目标一、二作为约

13、束条件，目标三作为最终单目标，可得如下最终模型：minf3=119j=120(rrj-r)2rs.t.r=i=192ri20;j=120xij*dij3, iU0;xij=1, iU1, j=vi;j=120xij=1, i=1,292;i=192xij1, j=1,220;xij=1, i=j;i,j=120;xij0,1其中vi表示交巡警不能在3分钟内赶到的路口i被平台vi管辖。用lingo求解得最小变异系数为1.934，,最终分配方案如下（程序见附录三）：交巡警服务平台管辖路口工作量（次）11、67、69、76、77、79、8022、40、43、73、7533、44、54、55、66、6

14、844、57、60、62、63、64、6555、49、53、56、5966、50、51、52、5877、30、4888、34、37、4799、32、33、451010、29、391111、26、271212、251313、21、22、23、241414、38、611515、28、311616、35、36、461717、41、42、70、721818、74、84、85、87、881919、71、78、81、82、832020、86、89、90、91、92 问题一（2）：封锁方案的确定.1模型建立 本问要求调度20个交巡警服务平台对A区的13条交通要道实现快速封锁，且每个平台最多封锁一个路口。实现

15、完全封锁的时间取决于13条交通要道中被封锁最长的时间。本文将时间问题转化为距离问题。对13条要道实现最快封锁，即是将平台到13条被封锁要道中的最长距离最小化。可建立01规划模型。 建立01变量：yij=1, 第i条交通要道由第j个交巡警服务平台封锁0，第i条交通要道不由第j个交巡警服务平台封锁。假设sij为第i条交通要道到第j个平台的距离。其中i=1,213;j=1,220。目标函数：平台到13条被封锁要道中的最长距离最小 ：mins=maxyij*sij i=1,213;j=1,220约束条件为：1.每条交通要道必须有一个交巡警服务平台进行封锁。j=120yij=1, i=1,213。 2.

16、每个交巡警平台最多封锁一条交通要道。i=113yij1, j=1,220。综上所述，此优化模型为：mins=max1i201j13yij*sijs.t.j=120yij=1, i=1,213;i=113yij1, j=1,220;yij0,1用smin表示上述模型解出的最小值。将上述模型解出后，依然存在多种封锁方案，我们做进一步优化。考虑到警力资源有限，以封锁距离总和最短为目标函数，上述模型解出的最小值smin为约束条件进一步做01规划求得最终封锁的调度方案。模型如下：minf4=i=113j=120yij*sijs.t.max1i201j13yij*sijsmin;j=120yij=1, i

17、=1,213;i=113yij1, j=1,220;yij0,1.2模型求解首先从最短路程矩阵D中，筛选出13条交通要道到各交巡警平台的最短距离，并且依照13条交通要道的顺序进行113编号，得到13*20的要道和平台间的距离矩阵。然后用lingo对上述两个模型分别进行编程求得最优解。程序分别见附录四与附录五。最终结果如下：smin=8.02km，最短封锁时间为8.02min。封锁方案为：路口标号12141621222324282930384862平台标号12169141013111578254时间（min）0 问题一（3）：确定增加平台的个数与位置4.3.1 模型建立本问要求在A区内增加2至5

18、个平台，解决现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况。本文认为只要增加平台能够使得A区全部路口可以由交巡警在3分钟内全部赶到，（A区所有路口到管辖平台间的距离不大于3km），即是解决了出警时间过长的问题。可以由问题一（1）中的结果中求得最小应增加的平台数，具体求解过程见模型求解部分。然后我们在所有路口都能够由交巡警3分钟内到达的前提下，考虑如何解决平台工作量不均衡的问题。 对于交巡警服务平台工作量不均衡的问题，利用问题一（1）中的方法，用工作量的变异系数衡量平台工作的均衡度，以工作量的变异系数取得最小值为目标函数建立01规划模型。建立01变量：fj=1, 在路口j处增加

19、平台0, 不在路口j处增加平台， xij=1, 路口i被平台j管辖0，路口i不被平台j管辖。n 为新增加交巡警平台的个数。目标函数可表示为：minf5=119+n j=192(i=192xij*ri-r)2rr=i=192ri（20+n）;其中ri为路口i的发案率，r为所有平台的平均工作量。约束条件为：1.交巡警平台个数为20+n：j=192fj=20+n; 2.所有路口到管辖平台间的距离不大于3km：j=192xij*dij3, i=1,292； 其中dij为路口i和路口j之间的距离。 3.每个路口都要被一个平台进行管辖：j=192xij=1, i=1,292；4.每个交巡警服务平台必须管辖

20、本路口：xij=1, fj=1;i=j;i,j=192; 5.只有当路口j处增加了平台j时，才可以管辖其他的路口:xijfj, j=1,292; 6.第1,220个路口处原本就设有平台：fj=1, j=1,220;综上所述，此模型为：minf5=119+n j=192(i=192xij*ri-r)2rs.t.r=i=192ri（20+n）;j=192fj=20+n;j=192xij*dij3, i=1,292；j=192xij=1, i=1,292；xij=1, fj=1;i=j;i,j=192;xijfj, i=1,2,20, j=1,292；fj=1, j=1,220；xij、fj0,1;

21、4.3.2 模型求解 由问题一（1）的求解可知，在A区现有20个平台的设置下，集合U1=28，29，38，39，61，92中的路口不能由交巡警在3分钟内及时赶到。从最短路程矩阵D中搜索出A区距离U1中各路口距离小于等于3km的路口，结果如下：U1路口标号282938396192符合条件的路口28,2928,2938,39,4038,39,4048,6187,88,89,90,91,92 从上面结果可知，最少增加4个平台才可以使得这6个路口可以由交巡警在3分钟内赶到，这样就满足了所有路口都可以由交巡警在3分钟内赶到。因此为解决有些地方出警时间过长的问题，需要增加4或5个平台。 将n=4和n=5分

22、别代入上述0-1规划模型，用lingo求解，程序见附录六，得到如下结果：增加平台数平台增加位置均衡度（变异系数）428、40、48、90528、39、48、87、88758 从表格可以看出增加5个平台要比4个平台均衡度高，但是由于两者均衡度相差并不大，都可以解决出警时间过长的问题，且实际问题中增加一个平台所需花费很多，因此最终选择为： 增加4个平台，位置为路口28、40、48和87。4.4 问题二（1）交巡警平台设置的评价与改进现有交巡警平台设置的合理性的评价本文对现有交巡警平台的设置定义了两个评价原则： 1.交巡警能在3分钟内到达案发路口 2.各平台的工作量均衡度尽量高 依据这两个评价原则，

23、分别对6个区现有的平台设置进行评价。 首先将6个区的平台依据问题一（1）的方式进行管辖区域的划分，得到结果如下：区域不能由交巡警3分钟内到达的路口个数（U1）U1路口所占总路口的比重平台工作量均衡度（变异系数）A区66.5%1934B区68.2% 1925C区 47 30.5% 4083D区 1223.1% 2253E区 32 31.1% 3798F区 35 32.4% 4562 对于原则一：A区和B区不能由交巡警在3分钟内到达的路口个数即U1路口个数比较少，较符合原则一的要求。C、E、F三个区U1路口所占比重过高，明显不合理。对于原则二，在问题一（1）中，我们已经分析到对于变异系数为1.93

24、4的A区，工作量的均衡度是比较好的，因此我们可以推测B区的均衡度也是比价好的。而C、E、F三个区的变异系数过高，因此均衡度较差。 综上所述，A区和B区的设置较合理，D区稍不合理，而C、E、F区严重不合理4.4.2 交巡警服务平台设置的优化4.4.2.1 模型建立 由上面分析可知，很多区不能由交巡警在3分钟赶到的路口过多，出警时间过长，因此我们首要选择增加交巡警服务平台对每个区进行优化，优化方式按照问题一（3）中的模型，对每个区有：1.集合U1中的路口表示不能由交巡警在3分钟内及时赶到的该区路口，从最短路程矩阵D中搜索出该区距离U1中各路口距离小于等于3km的路口，解出初步增加的平台个数，使得该

25、区每个路口都可由交巡警在3分钟内到达，解决了某些地方出警时间过长的问题。2解决平台工作量不均衡的问题，建立如问题一（3）的模型：min f6=1Xm+n j=ZmYm(i=ZmYmxij*ri-r)2rs.t.r=i=ZmYmri（Xm+n）;j=ZmYmfj=Xm+n;j=ZmYmxij*dij3, i=ZmYm；j=ZmYmxij=1, i=ZmYm；xij=1, fj=1;i=j;i,j=ZmYm;xijfj, i=ZmYm, j=Zmzm；fj=1, j=Zmzm；xij、fj0,1;其中Xm表示第m个区现有的平台数量； Ym 表示第m个区起始的路口编号；Zm 表示第m个区终止的路口编

26、号；zm表示第m个区现有最后一个平台所在的路口编号。将上述模型用lingo求解，得到最终结果如下：区域增加平台个数增加平台位置平台工作量均衡度（变异系数）A428、40、48、90B2104、147C20183、208、201、203、206、214、238、240、246、248、251、256、260、263、267、287、297、299、313、315D8329、332、333、338、344、362、369、370E15387、388、390、393、404、408、419、420、421、438、451、459、462、472、474F11486、505、510、503、515、5

27、20、525、540、541、558、560 在做如上优化后，6个区的所有路口都可由交巡警在3分钟内到达，解决了某些地方出警时间过长的问题，而且6个区的工作量均衡度均在1.62.1之间，相比之前得到了很大的提高。4.5问题二（2）围堵方案的确定根据题意，为了快速搜捕嫌疑犯，也就是说，各个平台到封锁路口的时间要最短，即最大搜索距离最短，首先求出需要封锁的路口，具体做法为：先计算出嫌疑犯3分钟走的路程为30，再以P32点为圆心，以30为半径形成一个包围圈，在这个包围圈的邻域内选出若干个路口，再以这些路口为圆心，10t为半径形成若干个包围圈，从而建立模型如下： 目标函数： 约束条件： 即 将上述模型

28、用lingo求解，（程序见附录七）结果如下：路口平台151731519396382153951771772021752031802351623615264182317178181325324328327332380362323387100418375483478541476572484578485479此时最短时间为：。附录附录一（matlab）data=xlsread(cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls,1);x=data(:,2); %每个路口的横坐标y=data(:,3); %路口的纵坐标rate=data(:,5); %路口的发案率boolean=z

29、eros(582,582); route=xlsread(cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls,2);route=route(2:929,1:2);for i=1:928 %直接连接的两路口，矩阵元素为1，否则为0 boolean(route(i,1),route(i,2)=1; boolean(route(i,2),route(i,1)=1;endfor i=1:582 boolean(i,i)=1;endw=zeros(582,582); %求出邻接矩阵 for i=1:582 for j=1:582 if boolean(i,j)=1 w(i,j)=sq

30、rt(x(i)-x(j)2+(y(i)-y(j)2); else w(i,j)=9999; end endendD,R=floyd(w);functionD,R=floyd(a) %弗洛伊德算法n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endend for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end endend附录二（matlab）d=D(1:20,1:92);U0=;U1=;for i=1:92 su

31、m=0; for j=1:20 if d(j,i)=1 U0=U0,i; else U1=U1,i; endend附录三（lingo）sets:lukou/1.92/:r;pingtai/1.20/:rr;link(lukou,pingtai):x,d;endsetsdata:r=ole(G:/数学建模/国赛/2011/B/cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls,rate);d=ole(G:/数学建模/国赛/2011/B/shortdistance.xlsx,distance);enddatamin=(z/19)0.5;for(pingtai(j):rr(j)=

32、sum(lukou(i):x(i,j)*r(i);rp=sum(lukou:r)/20;z=sum(pingtai:(rr-rp)2);for(link(i,j)|i#ne#28 #and# i#ne#29 #and# i#ne#38 #and# i#ne#39 #and# i#ne#61 #and# i#ne#92:x(i,j)*d(i,j)=1);for(link:bin(x);附录四（lingo）sets:yaodao/1.13/;pingtai/1.20/;link(yaodao,pingtai):s,y;endsetsdata:s=ole(G:/数学建模/国赛/2011/B/交通要道

33、与交巡警平台的距离.xlsx);enddatamin=max(link:y*s);for(yaodao(i):sum(pingtai(j):y(i,j)=1);for(pingtai(j):sum(yaodao(i):y(i,j)=1);for(link:bin(y);附录五（lingo）sets:yaodao/1.13/;pingtai/1.20/;link(yaodao,pingtai):s,y;endsetsdata:s=ole(G:/数学建模/国赛/2011/B/交通要道与交巡警平台的距离.xlsx,s);enddatamin=sum(link:y*s);max(link:y*s)80

34、.155;for(yaodao(i):sum(pingtai(j):y(i,j)=1);for(pingtai(j):sum(yaodao(i):y(i,j)=1);for(link:bin(y);附录六（lingo）sets:lukou/1.92/:r,f;link(lukou,lukou):x,d;endsetsdata:r=ole(cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls,rate);d=ole(shortdistance.xlsx,d);enddatamin=(z/23)0.5/rp;z=sum(lukou(j):(sum(lukou(i):x(i,j)*r(i)-rp)2);rp=sum(lukou:r)/24;sum(lukou:f)=24;for(lukou(i)|i#le#20:f(i)=1);for(lukou(i)