2011年数学建模大赛优秀论文.pdf
交巡警服务平台的设置与调度的数学模型摘摘要要针对交巡警服务平台的设置与调度问题， 本文主要考虑出警速度和各服务平台的工作量来建立合理方案。对于 A 区的 20 个交巡警服务平台分配管辖范围的问题，我们采用Dijkstra 算法，分别求得在 3 分钟内从服务台可以到达的路口。根据就近原则，每个路口归它最近的服务台管辖。对进出 A 区的 13 个交通要道进行快速全封锁，我们采用目标规划进行建模，运用 MATLAB 软件编程，先找出 13 个交通要道到 20 个服务台的所有路径。然后在保证全封锁时间最短的前提下，再考虑局部区域的封锁效率，即总封锁时间最短，封锁过程中总路程最小，从而得到一个较优的封锁方案。为解决前面问题中3 分钟内交巡警不能到达的路口问题，并减少工作量大的地区的负担，这里工作量以第一小问中20 个服务台覆盖的路口发案率之和以及区域内的距离的和来衡量。对此我们计划增加四个交巡警服务台。避免有些地方出警时间过长和服务台工作量不均衡的情况。对全市六个区交警平台设计是否合理，主要以单位服务台所管节点数，单位服务台所覆盖面积，以及单位服务台处理案件频率这些因素进行研究分析。以A区的指标作为参考，来检验交警服务平台设置是否合理。对于发生在 P 点的刑事案件， 采用改进的深度搜索和树的生成相结合的方法，对逃亡的犯罪嫌疑人进行可能的逃逸路径搜索。 由于警方是在案发后 3 分钟才接到报警，因此需知道疑犯在这 3 分钟内可能的路线。要想围堵嫌疑犯，服务台必须要在嫌疑犯到达某节点之前到达。用 MATLAB 编程，搜索出嫌疑犯可能逃跑的路线，然后调度附近的服务台对满足条件的节点进行封锁，从而实现对疑犯的围堵。关键词：Dijkstra 算法；目标规划；搜索；1一、问题重述一、问题重述近十年来，我国科技带动生产力不断发展，我国的经济实力不断增强，而另一方面安全生产形式却相当严峻。每年因各类生产事故造成大量的人员伤亡、经济损失。尤其是一些大目标点，作为人类经济、政治、文化、科技信息的中心，由于其“人口集中、建筑集中、生产集中、财富集中”的特点，一旦发生重大事故，将会引起惨重的损失。为保障生产安全、预防各类事故。我国正在各省市目标点逐步建立交巡警服务平台。由于警力资源有限，则需要根据城市的具体情况合理地设置交巡警服务台、分配各平台的管辖范围、调度警力资源。就某市中心城区 A 的交通网络和现有的交巡警服务台分布的实际情况， 为各交巡警服务平台分配管辖范围，使其在所管辖范围内出现突发事件时，尽量在3分钟内有交巡警到达事发地点（警车的时速为 60Km/h） 。如果发生重大突发事件，要调用全区 20 个交巡警服务台的警力资源，对进出该区的 13 个要道进行全速封锁，以防罪犯逃走。其中一个交巡警服务台的警力资源只能封锁一个路口，建立数学模型， 给出一套合理调度交巡警服务台警力资源的方案！在现有的交巡警服务台中出现了个服务台的工作量不均衡和有的地方出警时间过长等情况，警务部门计划在该区增加 2 至 5 个服务平台， 避免出现服务台工作量不均衡和有的地方出警时间过长等情况！ 就此为警务部门确定要增加平台的个数及位置！根据全市六个城区的具体情况， 按设置服务台任务和原则，分析现已设置的交巡警服务台的合理性。如不合理，给出合理的方案！若在该市的 P 点发生重大刑事案件， 案发 3 分钟后警方才接到报警， 犯罪嫌疑人已经驾车逃亡。为了快速收铺疑犯，建立数学模型，利用现有的警力资源，给出一套最优的围堵方案！二、模型的假设二、模型的假设1）警车在赶往事发地点途中，交通无阻塞。2）在各个平台的管辖范围内，在较短时间内最多发生一起突发案件。3）交巡警在赶往案发地点途中，道路转弯处不影响警车速度。4）如果案发地点不在道路上，假设该案发地点在离它最近的道路上。5）在整个路途中，通过各种通讯设备，走的路径都是最短路径。6）犯罪嫌疑人驾车逃跑时速和警车时速相同。7）服务台一接到报警就出警，中间没有时间耽搁。三、符号说明三、符号说明G(V,E,W)：该市的道路网络赋权图，其中，V：图的顶点集合；E：图的边集合；W：图的邻接矩阵。Vi(i1,2,.,n)：赋权图的第i个节点标号。(xi, yi)：Vi点的坐标。2Ei(i 1,2,.,m)：赋权图的第i条边ei(vj,vk)：赋权图中第i条边的向量坐标dij：第i个节点到第j个节点的长度（i节点和j节点相邻）Pathi, j：i节点到j节点的路径v：警车行驶时速（Km/h）四、模型的建立与分析四、模型的建立与分析4.1.14.1.1 管辖范围确定管辖范围确定本问题要求根据中心城区 A 的交通网络和 20 个交巡警服务台的位置，对这20 个交巡警的管辖范围进行配置，寻找满足条件的路口节点。将道路网图中，每个路口看作节点，将道路看作图中对应节点的边，各条道路的长度看作对应边的权， 所给的城市道路网就转化成了图论中的加权网络图，问题就转化为一个图论问题， 即在给定的加权网络图中寻找各服务台在指定时间内能到达的节点，这些节点及以内的区域就是该服务台的管辖范围。Dijkstra (迪杰斯特拉 )算法是典型的单源最短算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。本问题就是运用Dijkstra 算法，从交巡警服务台节点出发，收索满足条件的节点。Dijkstra 基本思想 :若使(u0,u1,.,un)最短，就要使(u0,u1,.,un1)最短，即保证从u0开始到以后各点的路都是最短的。由图G(V,E,W), 设集合SiV，SiV Si令|V | n，Siu|从u0到u的最短路已求出 Siu|从u0到u最短路未求出 基本步骤如下：第一步：根据附录表中所给的各个服务台与节点的坐标数据，在示意图中标示出来，如图 1 所示：3第二步：考虑到服务台可以管理该服务台自身所在节点，故而1 到 20 号节点就由相应位置所在的服务台管理.第 三 步 ： 以 下 计 算 均 以 题 目 所 给 的 表 格 数 据 计 算 ， 由 公 式d (xi xj) (yi yj)求出i、j两点间的距离。根据已知条件，可以求出满足条件的管辖范围为：在保证出警时道路畅通， 警车行驶正常的情况下， 由题意可知， 车速恒为v千米/小时， 出警时间不超过t分钟， 则从交巡警平台到出事地所行使的最大路程为：L(0) vt/60由题目所给的数据t 3分钟，v 60千米/小时。可得：L(0) 3Km所以，要使事故发生后3 分钟内达到事发地点，则交巡警服务台的管辖范围不应超过 3Km，对于任何一个服务台在 3 分钟以内都无法到达的节点，稍后另作讨论。运用MATLAB 求出除自身以外在 3 分钟以内只有一个服务台可以赶到的节点。第四步：在 3 分钟之内有多个服务台可以赶到的节点，取离节点最近的服务台管理该节点，结果如表一所示：4表一 服务平台覆盖范围服务平台1234567891011121314151617181920覆盖的范围1234567891011121314151617181920673954574930333126252128364180778468405560503246342722293742817985694365625147352338828671446663524845248387737064536188747256897558907659917892第五步：在 3 分钟没有任何服务台可以赶到的节点，取离节点最近的服务台管理该节点。具体情况如表二所示：5表二 3 分钟不能到达的路口三分钟不能到达的路口282938396192取最近的服务台1515162（16）4、6、718、204.1.24.1.2 要道全封锁方案要道全封锁方案针对本问题我们在设置方案时， 首先考虑时间问题，即要使服务平台尽可能快地封锁 13 条交通要道。 在分配任务时， 充分调动全区 20 个交巡警服务平台的警力资源，首先考虑全局总体效率最高，封锁总时间最短，即在所有的封锁路线中的最大距离尽可能的短。再考虑局部效率较高，则必须使服务平台到各自封锁节点的长度和最短。 为此， 我们采用目标规划的基本建模思想对此问题进行求解。第一步：通过 MATLAB 编程找出 13 个路口到 20 个服务平台的映射路径，具体内容见表三。 从中筛选出路程最短的 4 个服务平台。 为下一步任务分配做准备。表三 距离要道最短的四个服务台交通要道服务台服务台服务台服务台备注备注129873本身有服务台141316911本身有服务台169873本身有服务台211314111222131114122313111412241312111028157982915785307856381629174875686243119第二步：因要对进出该区的 13 条交通要道实现快速全封锁，故我们必须先保证出警时间最短，然后再保证总路程最短， 同时还要使各个服务平台的工作量均衡。经过对表十表数据的分析比较可以得出：28、29 号路口较为偏远。具体情况如表四所示：6表四 距 28,29 要道最近的服务台及距离交通要道标号28282929服务台标号157157距离 d4751.8418570.2185700.5258015.456由于一个服务台的警力只能封锁一个路口， 从上表可以看出，调度 15 号服务台封锁 28 号路口，7 号服务台封锁 29 号路口，为较优的封锁方案，可以保证总封锁时间最短，总的封锁时间为：t d /v由以上数据可知d 8015.456m可得时间为：t 8.015min。其次考虑到局部封锁效率，使服务平台到各自封锁要道的长度和最短。这就是第三步考虑的问题。第三步： 在前两步的基础上， 要想得到服务台到各自封锁要道的路程和最短，就要使服务台到各自封锁要道的路程最短。 但由于一个服务台的警力资源只能封锁一个交通要道，故而服务台标号不能重复。通过对表三和表十的分析比较，得出一个较优的调度方案，如表五所示：表五 调度方案服务平台标号交通要道标号路程（m）路径10127586.58510-26-27-1216146741.66116-149161532.5409-35-36-1614213264.96514-2111223269.55611-22132350013-2312243591.63012-25-2415284751.841715-287298015.4567-30-298303060.8198-33-32-7-302383982.1852-40-39-385482475.8255-47-484623504-62总长 49123.074.1.34.1.3 平台增加个数及位置确定平台增加个数及位置确定从问题一的第四步我们可以看出 A 区现有交巡警服务平台设置方案的不合理性， 针对现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，我们确定需要增加 4 个服务平台，具体方案如表六所示：7表六 平台设置设置平台位置28 或 29396191原因28 和 29 出警时间长38 和 39 出警时间长，由 39 点出警比从 2 号出警时间短，可以帮 2 号服务台减少工作量出警时间长既可以使第 92 点的出警时间在 3 分钟内，又可以有效的减少 20 号服务平台的工作量4.2.14.2.1 全区服务台合理性分析全区服务台合理性分析交巡警服务台设置的原则主要有警情主导警务原则、快速处警原则、方便与安全原则。 在遵循上述三大原则的基础上， 还应当结合辖区地域特征、 人口分布、交通状况、 治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置。图二给出了六区交通网络与平台示意图。针对全市的具体情况，我们对题目附件一的表格作了分析整理，并判断服务8台设置的合理性。整理结果如表七、表八所示：表七 六个区的基本情况六个区城区面积城区人口A2260B10321C22149D38373E43276F27453服务台个数案发率总量道路节点数20124.592866.47317187.2154967.85215119.410311109.2108表八 服务台分布情况全市六个每个服务台平每个服务台平每个服务台平城区均所管节点数均覆盖面积均处理案件次数A4.601.106.23B9.1312.888.30C9.0613.0011.01D5.7842.567.53E6.8728.807.96F9.8224.919.93由表七、表八可以看出该市现有的服务平台设置有明显的不合理： B、C、F 三个城区每个服务台平均所管节点数过多，导致该区服务台的工作量过大； D、E、F 三个城区每个服务台平均覆盖面积过大，导致该区服务台出警时间过长。由于在六个区的交界处，有很多地方没有设置服务台，这将导致无法快速处理案件和突发事件。要解决此问题，就要在相应的城区，适当的位置多设立些服务台，避免出现服务台间工作量不均衡和某些服务台出警时间过长。4.2.24.2.2 最佳围堵方案确定最佳围堵方案确定由于疑犯逃跑 3 分钟之后才接到报警，所以要先确定这 3 分钟疑犯可能到达或即将到达的节点。在假设 6 和 7 的前提条件下，为了快速有效的的围堵在逃疑犯，不给疑犯任何可逃的路线，本方案同时考虑两点作为选择最佳方案的条件：条件 1：布置的围堵网最小条件 2：警力调动总距离短选择改进的搜索方法和树的生长方式来确定方案。步骤如下：Step1:确定与 P(标号 32)直接相连的顶点，并计算出它到这些点的距离。Step2:以 Step1 中确定的顶点为起点，搜索与它直接相连的顶点，并计算距离。9Step3:重复 Step1,当 P 点到某个点的距离等于或大于 3000m 时，停止搜索。该点就是疑犯下一个可能出现的节点。Step4:如果警力能赶在疑犯之前到达疑犯可能出现的节点，则在该节点设置封锁，如若不能，则寻找下一个最近的围堵点。基本思想如图三：图三 基本思想3273037471515313434338通过 Matlab 编程，和结果整理后，得到疑犯下一个可能到达的节点的标号，以及所要到达的最短距离，如表九所示。表九 疑犯下一个可能到达的路口3 分钟后罪犯即所需最还需行行驶将到的下一个路口短距离驶距离路径615330233032-7-30-48-612354128112832-7-30-48-235374181118132-7-3748344044032-47-485387687632-47-56390790732-47-6154139113932-31-159322722732-31-34-9107647464732-31-34-1037111411132-33-34-9-35-45-316330130132-33-34-9-35-36-16396194319432-33-34-9-35-36-3947341841832-33-8-4745359359332-33-9-35-4536342242232-33-9-35-36237359159132-7-30-237555211221132-33-8-46-5535353953932-33-8-46-45-35根据表九结果，可以大致确定欲围堵范围，如图四所示10所得的围堵方案如表十所示。表十 围堵方案设置的交巡警平台位置标号34569101516415561234235246561调入的交巡警标号2195691015161734168173171480六、模型的评价与改进本文主要运用 Dijkstra 算法，构建了全市六个区的邻接矩阵，能够较好的解决已知点间的最短路问题。由于数据量较多，和一些循环的原因，程序运行有一点慢，但不影响所求的结果。在解决快速围堵疑犯的问题时，本文结合深度搜索算法和树的生成方法，找到了一个较优的围堵方案。11参考文献参考文献1赵静、但琦，数学建模与数学实验，北京：高等教育出版社，2003.6。2范逢曦，图论方法及应用，太原：山西科学教育出版社，1987.4。3姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2003.8。4黄国瑜、叶乃菁，数据结构，北京：清华大学出版社，2001.8。5李春葆，数据结构教程，北京：清华大学出版社，2005. 16卢开澄,卢华明,图论及其应用（第二版），北京:清华大学出版,19977严蔚敏,吴伟民，数据结构，北京：清华大学出版社，19978百度文库，交巡警平台的设置，http:/ BticlcA=xlsread(cB.xls,全市交通路口节点数据,A2:C93);mA,nA=size(A);plot(A(:,2),A(:,3),.)hold onplot(A(1:20,2),A(1:20,3),o)B=xlsread(cB.xls,全市交通路口的路线,A2:B144);mB,nB=size(B);C=xlsread(cB.xls,全市区出入口的位置,C2:C14);mC,nC=size(C);for i=1:mC plot(A(C(i),2),A(C(i),3),*)endcount1=0;count2=0;for i=1:mBif B(i,1)B(i,2)&B(i,2)93 j1=B(i,2); j2=B(i,1); x=A(j1,2),A(j2,2); y=A(j1,3),A(j2,3); count1=1+count1; Z1(count1,1:2)=j1,j2; plot(x,y) hold onendif B(i,1)B(i,2)&B(i,2)Z(i,2) t=Z(i,2); Z(i,2)=Z(t,1); Z(i,1)=t; endendZ=sortrows(Z);for i=1:mZA1(i)=100*sqrt(A(Z(i,1),2)-A(Z(i,2),2)*(A(Z(i,1),2)-A(Z(i,2),2)+(A(Z(i,1),3)-A(Z(i,2),3)*(A(Z(i,1),3)-A(Z(i,2),3);endfor i=1:mA for j=1:mA if i=j W(i,j)=0; end W(i,j)=inf; endend for i=1:mZ W(Z(i,1),Z(i,2)=A1(i); W(Z(i,2),Z(i,1)=A1(i); end title(图 1 A 区交通网络与平台设置示意图) for k=1:mA text(A(k,2),A(k,3),sprintf(%d,k);end for i=21:mA for j=1:2022 d,path=dijkstra(W,i,j); if (d/1000)=3 d; path; end end endD=;numPath=0; mC,nC=size(C); for i=1:mC for j=1:20 if C(i,1)=j d,path=dijkstra(W,C(i,1),j); numPath=numPath+1; D=D;d;xlswrite(test1.xls,path,sheet1,strcat(B,num2str(numPath),:,setstr(B+(length(path)-1),num2str(numPath); end end endxlswrite(test1.xls,D,sheet1,A);%W 是关联矩阵，s 和 t 分别是起始点和终止节点的序号。返回的 d 为最短的加权路径长度,p 为最优路径节点的序号向量。注意，这里 W 矩阵为 0 的点权值已经自动设为无穷大了function d,path=dijkstra(W,s,t)n,m=size(W);ix=(W=0);W(ix)=inf;if n=m,error(Square W required);endvisited(1:n)=0; dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;for i=1:(n-1),%求出每个节点与起始点的关系 ix=(visited=0);vec(1:n)=inf;vec(ix)=dist(ix); a,u=min(vec);visited(u)=1; for v=1:n, if (W(u,v)+dist(u)dist(v), dist(v)=dist(u)+W(u,v);parent(v)=u;23 end; end;endif parent(t)=0,path=t;d=dist(t);%回溯最短路径 while t=s,p=parent(t);path=p path;t=p; end;end;24
