交巡警服务平台的设置与调度(优秀论文)

1、承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛

2、队员（打印并签名）：1.2._3._指导教师或指导教师组负责人（打印并签名）：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：交巡警服务平台的设置与调度摘要本题主要讨论城市中的交巡警服务平台的设置和具体调度问题，在确定各平台管辖范围和增加平台的位置、数量等相关问题时，通过对已知条件中点的坐标，和相应道路信息，对已知条件进行合理的处理，得到我们需要的数据，然后进一步进行分析，获得合理的设置与调度方案。对于问题一：1.1是关于A区中20个交巡警服务平

3、台的分配管辖范围问题，首先求出相邻两路口节点之间的距离，建立92*92的邻接矩阵，然后在Matlab软件下采用Floyd算法求出任意两个点之间的最短距离，从中提取出92*20的矩阵，再引入0-1整型规划模型， 最后建立以总路程最小为目标函数， 以各个平台发案率均衡为约束条件，建立优化模型，最后使用Lingo编程实现区域的自动划分，最终求出A区各个服务台的管辖范围。1.2是关于如何封锁A区中13个交通要道口问题，本文以“一个平台的警力最多封锁一个路口”为约束条件，以“最后到达的警力所花时间的最小值（时间转化为路程）”为目标函数，建立相关模型，求出最优解，最终的结果见表2;1.3是要在原有平台数的

4、基础上增加25个平台，以发案均衡量和出警时间为约束条件，建立模型求出结果，再对结果进行分析适当的增减平台数使目标最优，最终的求解结果见表3。对于问题二：我们综合实际情况，把发案率，人口，路口节点数，管理面积作为交巡警服务平台的工作量的相关因子。依据各因子对工作量的影响程度，赋予一定权值，建立评判函数，判断该市各区现有设置方案的合理性，得出c、d、f为不合理区域。对不合理区域，需增加平台数，建立以增加平台数尽可能少，工作量尽可能均匀为目标建立了多目标非线性优化模型，进行合理分配。依据预处理距离，可以得到嫌疑犯在短时间内逃得最远距离，在保守的方案下可以确定一个相对全市较小，但又比较保守、可靠的围堵

5、范围，以围堵时间最快为目标函数，建立0-1规化模型，得出最佳围捕方案。关键词：邻接矩阵、Floyd算法、最优解、0-1规化模型一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。已知某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）由该市中心城区A的

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

7、务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析此题是研究交巡警的合理分配和调度的数学建模问题。需要我们通过建立合理的数学模型，进行多目标优化，对交巡警进行合理的分配。对于问题一：本问主要解决的是A区每个交巡警服务平台的管辖范围，也就是每个节点归哪个交巡警服务平台管辖的问题。因为每个交巡警服务平台的职能和警力配备基本相同，所以要考虑每个平台工作量的均衡下能在最短时间

8、内到达突发事件现场，主要考虑的方向是各个平台管辖范围内的总的时间最短（最短时间可转化为出警的最短路程）与均衡每个平台的发案率这两个因素，显然，这是个双目标问题，为了方便求解，把双目标函数单一化，将各个平台发案率的均衡转化为约束条件建立模型，进而划分出区域。其中，我们引入了0-1规划模型，采用了Floyd算法求出图中任意两个站点之间的最短距离，再根据所建立的模型划分出具体区本问主要解决的是在最短时间内封锁13个交通要道的问题， 也就要求从20个交巡警平台中找出13个平台用最短时间去封锁交通要道。由题目可以知道当A区重大突发事件时，需要调度全区20个交巡警服务平台的警力资源，现有20个交巡警服务平

9、台的警务资源可供调度，且一个平台的警力最多只能封锁一个路口。为此我们采用以到达路口时最长的为标准（时间可以转内化为路程），建立目标函数为该标准最小，即最大距离最小化问题，以一个平台的警力最多封锁一个路口为约束条件的模型。 利用Lingo编程从而得出该去交巡警服务平台警力合理的调度方案。本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。这是一个典型的优化问题，由题目以及第一问可以知道A区交巡警服务平台分布不均匀以及有没能在题目要求下受到管辖的节点，因此，我们考虑到发案率、距离、与其它平台的覆盖率、人口密度，按照重要的程度不同，经过调研后假设它们各自的权值，然后将各自发案率、距离、与

10、其它平台的覆盖率、人口密度分别乘以相应的权值，综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域，即各个交巡警服务平台所管辖的节点，最后可以得到交巡警服务平台以及相应添加的平台。对于问题二：2.1在这个问题中，我们基于统计基理分析，对全市进行分区分析，统计出与工作相关的一些因素，建立了以各个交巡警平台管辖的面积、人口、节点数以及各个区的总发案率为变量的评判函数，判断出各个区域的合理性，对不合理的区域进行优化，并给出合理的解决方案。2.2我们基于保守方案的分析，当警方接到报案后，不考虑反应时间，立即对逃犯进行封堵。基于floyd的数理统计，计算出p

11、点距全市各个路口的最小距离，确定一个保守的可靠相对较小的围堵范围，类似于问题1.2建立的优化模型用lingo软件编程得到最好的围堵方案。三、模型假设1、假设警车在出警时的速度包为60km/h,且不会出现故障问题；2、假设在接到报案后，准备时间为0,即直接出发。；3、假设在发生案件时交巡警都是从平台处出发的，不考虑在远离案发点的节点或路段出发；4、假设犯罪嫌疑人的逃逸速度不大于60km/h;5、所有交巡警服务平台的配置是基本相同的；6、假设两个节点之间的路径为两点间的直线距离；7、假设每个路段道路畅通，可以双向行驶，没有堵车现象。四、符号说明i:全市第i个路口节点j:第j个交巡警服务平台k:第k

12、个出入市区的路口节点Ci:表示第i个路口的发案率6：第i个路口节点到第j个交巡警服务平台的最短距离v：犯罪嫌疑人的车速tj：第j个城区所需的平台个数(j=1,2,3,4,5,6)r：每个区的路口总数五、模型的建立及求解问题一1.1、Floyd算法原理与步骤1、邻接矩阵根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，及相关的数据信息，将路口节点看为图中的顶点M(i=1,2,92),构造图形的邻接矩阵A=(q),其中aj是连接图中顶点M与看边的数目。用MATLAB?(代码见附录一)运算得图形的邻接矩阵A=(aj)2、边权矩阵对图中连接相邻顶点W与Vj的每一条边， 用欧氏距

13、离%=，&-Xj)2+(yi-yj)2作为边权值,用MATLAE程(代码见附录二)运算得边权矩阵D=dij。3、Floyd算法取图的边权矩阵D=dj,进行n(n=92)次更新， 按递推公式， 构造出矩阵 D； 又用同样地公式由 D构造出 D；最后用同样的公式由 D(n,)构造出矩阵 D。矩阵 D(n)=(djn)=(dj)的i行j列元素便是顶点Vi与Vj的最短路径长度，称 D为图的距离矩阵，具体算法如下：步骤1:令k=0,输入边权矩阵 D(0)步骤2:令k=k+1,计算D(k)=。k),k=1,2,3,()式中(n)k(1Ak(1)匕：(dij尸 midnijd,ikdkj步骤3:如果

14、k=n,终止算法；否则，返回步骤2,上述算法的最终结果D=(dj)中元素dj就是从顶点Vi与Vj的最短路程， 计算结果运用MATLAB(代码见附录三)可求得最短路矩阵%*92。优化后的92个节点到20个交巡警服务平台的最短距离列表如下：表1最短距离矩阵节点距离平台节点距离平台节点距离平台1012517.88912495520226911508.485353032716.433115112.29354042847.518155216.59455052957.005155311.7085606305.83175422.70937073120.55795512.65938083211.4027562

15、0.8375909338.276585718.682410010345.024995823.019511011354.242695915.209512012366.0828166017.3924130133711.182166141.9027140143834.05916623.54150153936.82226310.3084160164019.14426419.363417017418.5176515.24318018429.8489176618.40231901943826716.194120020449.486826812.07112127.083134510.95196951229.

16、055413469.30058708.60232235134712.80677111.40312423.854134812.90277216.0622节点距离平台7310.2961746.2651759.300517612.8361779.848919786.40311794.472119808.06328816.708188210.7918835.385188411.7520854.47220863.606208714.65208812.9520899.487209013.02209115.99209236.01204、管辖范围的确定本文的覆盖半径用距离来表示，因为应急限制期限定在3min之

17、内，结合警车的速度及地图的比例尺转化为图上距离30mm目标是使各服务平台在服务时间最短的前提下， 覆盖所有可能的事发地点， 并且每个可能事发地点都要求有且只有一个服务平台对其服务。建立模型如下：9220目标函数：minFj=dj为i3j3Xij=1;i=1,2,3，20;20约束条件：Xj%=1；j=1,2,92;jLdjXjM30;i,j=1,292上式中Xj表示第j个节点是否属于第i个交巡警服务平台的管辖范围，如20果属于则xj=1,否则Xj=0;约束条件Xj=1表示第j个节点必须属于某一j1交巡警平台管辖范围。通过模型白建立及lingo编程（代码见附录四）求解可知，A区每个交巡警服务平台

18、的管辖范围划分结果最优如下表：表2各服务台管辖范围交巡警服务口编力管辖区域116869717374752240437072334454556567445760626364554950515253566658597730474861883233469935451010313411112627121224251313231414212215152829161636373839171741429218188182838490911919767778798020208586878889在路程已知的基础上，可以求得28、29、38、39、61、92号节点到各自最近的巡警服务台的时间是超过3分钟的。本问要

19、求调度20个交巡警服务平台的警力资源，对进出的13条交通要道实现快速全封锁，且一个平台的警力最多封锁一个路口， 所以要求最后一个到达的应该最小， 因此， 建立模型如下 （程序见附录五） ：目标函数：minS=max(djkxjk)13、XjkMl;j=1,2,20;k120XjkXjk1;k 之 1;k=1,2，20；j1Xjk=1代表第j个服务平台到第k个出入市区的路口节点；Xjk=0代表第j个服务平台不到第k个出入市区的路口节点；其中j=1,2,20;k=1,2,13。由lingo编程可得，计算结果经整理如下表所示：表3调度方案交通要道路口1214162122232428233038486

20、2需要调动的平台13163141012111575、6、81、2 4、9 17、18、19该题是要求在原有平台的基础上增加2至5个，使得改变现有的平台工作量不均衡，时间过长的实际情况，该模型可描述为：在一个有N个节点的道路网络中，从M个备选的节点中选取p个节点建立设施，在一定约束条件下使得目标函数最大或者最小，因此我们既要考虑时间（路程），又要考虑发案率，从而建立模型如下：9292目标函数：minF=Gd。%i=1jmXxj=1(i=1,2，20)92约束条彳 Zxj=1(i=1,2,92)，凸92:22D(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=p

21、ath(i,k);endendendendP=sp；mp=sp;fork=1:nifmp-=epd=path(mp,ep);p=p,d;mp=d;endendd=D(sp,ep);path=p;附录四(用lingo划分A区域)：model:sets:dept/1.92/;type/1.20/;a/1.92/:c;time(dept,type):d,x;endsetsmin=sum(time(i,j):d(i,j)*x(i,j);for(time:bin(x);for(dept(i):sum(type(j):x(i,j)=1);for(type(j):(6.225-sum(a(i):x(i,j)*c(i)-1.9);for(type(i):x(i,i)=1);data:d=ole(D:/1a.xls,distance);c=ole(D:/1a.xls,rate);endd