交巡警服务平台的设置及调度 11年B题

-.z.全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开场后参赛队员不能以任何方式〔包括、电子、网上咨询等〕与队外的任何人〔包括指导教师〕研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料〔包括网上查到的资料〕，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕：B 我们的参赛报名号为〔如果赛区设置报名号的话〕：所属学校〔请填写完整的全名〕：西北大学参赛队员(打印并签名)：1.舒岱2.羽3.成悟指导教师或指导教师组负责人(打印并签名)：日期：2014年8月10日全国大学生数学建模竞赛编号专用页赛区评阅编号〔由赛区组委会评阅前进展编号〕：赛区评阅记录〔可供赛区评阅时使用〕：评阅人评分备注全国统一编号〔由赛区组委会送交全国前编号〕：全国评阅编号〔由全国组委会评阅前进展编号〕：-.z.交巡警效劳平台的设置与调度摘要交巡警效劳平台位置的选取以及划分交巡警效劳平台的管辖围对于处理突发事件有非常大的影响。现阶段，一般依据经历选取效劳平台位置及划分管辖区域。所以如何科学合理处理的交巡警效劳平台的设置与调度问题具有十分重要的现实意义。本文研究了交巡警效劳平台的设置与调度问题。具体讨论了在给定的区域A，如何合理的设置交巡警效劳平台的管辖区域；发生特殊事件时应如何调动效劳平台警力以快速封锁区域A；应该增加多少数量交巡警效劳平台以及在哪个位置增加。本文建立最短路模型、0-1整数规划模型，利用软件解决了分配各平台管辖围、调度警务资源以及合理设置交巡警效劳平台这三个方面的问题。在解决分配各平台管辖围问题时，本文建立了最短路模型。通过求解各个路口到交巡警平台的距离是否满足最低时间限制，解决交巡警效劳平台分配管辖围的问题。本文在软件上运用算法进展求解，给出了中心城区A的20个效劳平台的管辖围，并求得到达最近的交巡警效劳平台的时间超过3分钟的6个路口。在解决调度警务资源快速封锁城区的问题时，本文建立了0-1整数规划模型。以封锁城区所用时间最少为限制条件，利用lingo软件编程求解，给出了该区交巡警效劳平台警力合理的调度方案，并求得对13个交通要道实现全封锁最短需要8.01分钟。在解决交巡警效劳平台的选址问题时，本文建立了双目标0-1整数规划模型。考虑到建立新的效劳平台需要投入更多的本钱和警务资源，还需平衡各个效劳平台的工作量。因此，以增加效劳平台数最小和效劳平台工作量方差最小为目标，建立了双目标0-1整数规划模型。解出增加的效劳平台数为4个，新增的效劳平台具体位置为A29,A39,A48,A88。本文所提供的模型考虑到均衡各个交巡警效劳平台的工作量和新建效劳台的本钱，使结果更加合理符合需求，可以推广到任何一个市区甚至更广围的交巡警效劳平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会效劳部门的选址问题，对实际有指导意义。关键词：Dijkstra算法双目标0-1整数规划模型Lingo编程

一、问题重述“有困难找警察〞，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、效劳群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警效劳平台。每个交巡警效劳平台的职能和警力配备根本一样。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警效劳平台、分配各平台的管辖围、调度警务资源是警务部门面临的一个实际课题。试就*市设置交巡警效劳平台的相关情况，建立数学模型分析研究下面的问题：1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警效劳平台的设置情况示意图，相关的数据信息见2。请为各交巡警效劳平台分配管辖围，使其在所管辖的围出现突发事件时，尽量能在3分钟有交巡警〔警车的时速为60km/h〕到达事发地。对于重大突发事件，需要调度全区20个交巡警效劳平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警效劳平台警力合理的调度方案。根据现有交巡警效劳平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区再增加2至5个平台，请确定需要增加平台的具体个数和位置。模型假设〔1〕每个交巡警效劳平台的职能和警力配备根本一样；〔2〕警车的行驶速度恒定，不考虑实际交通状况的影响；〔3〕交巡警效劳平台接到报警后能立即出警，中间没有延误；〔4〕每个节点只能被一个效劳平台管辖；〔5〕一个平台的警力最多封锁一个路口。三、符号说明赋权连通图顶点i到顶点j的距离顶点i到顶点j的距离0-1整型变量第i个交巡警效劳平台调度到第j个交通路口的情况；封锁要道所需时间最长的效劳平台的出警时间中心城区A的第个穿插路口节点的发案率；第i个交巡警效劳平台到第j个交通路口的最短距离距离的偏差限四、问题分析交巡警效劳平台位置的选取以及划分交巡警效劳平台的管辖围是一件非常重要的事情。由于种种原因，现在交巡警效劳平台的选址及管辖区域划分大多根据经历进展。缺乏科学系统的位置选取与管辖区划分，造成了警务资源浪费、突发事件处理不及时等多种问题。另外，警务资源是有限的，设置交巡警效劳平台也要消耗大量的资源。所以如何科学的规划管辖区，合理的设立新的交巡警效劳平台具有重大的意义。本文意在根据现有的城区道路图与交巡警效劳平台位置，根据到达突发事件地点使用时间最少原则进展交巡警效劳平台管辖围划分，根据使用资金尽量少及各交巡警效劳平台的工作量尽量一致的原则设立新的交巡警效劳平台。在问题一中有三个子问题需要解决。要对20个交巡警效劳平台分配管辖围，使其在所管辖的围出现突发事件时，尽量能在3分钟有交巡警〔警车的时速为60km/h〕到达事发地。即计算各交巡警效劳平台与各个地点的距离。将巡警在3分钟到达事发地转化为交巡警效劳平台距离事发地距离不超过3km。这是典型的最短路模型。对于这个问题，我们采用算法。当重大突发事件发生后，要对中心城区A的20个交巡警效劳平台的警力资源进展调度，对进出该区的13条交通要道实现快速全封锁，其关键在于合理调度警务资源使得封锁全部要道所需的总时间到达最小，也就是使得出警时间最长的效劳平台所需的时间尽可能的小。实际中一个平台的警力最多封锁一个路口，给出该区交巡警效劳平台警力合理的调度方案，我们采用0-1模型进展求解，给出该区交巡警效劳平台警力合理的调度方案。针对现有的中心城区A的20个交巡警效劳平台进展分析后，需要新增加2~5个效劳平台以解决工作量不平衡和局部路口节点出警时间过长的问题。这属于交巡警效劳平台选址问题。一方面考虑采用集合覆盖模型，目的是在满足所有节点3分钟都有警方到达的条件下，使新增设的效劳平台数目尽可能得小，从而降低了建立本钱。另一方面也要考虑新增设效劳平台后，能够解决效劳平台工作量不平衡的问题，所以把尽可能均衡各个效劳平台工作量作为第二个目标。因此考虑需要建立一个两目标的0-1整数规划模型。五、模型的建立和求解问题1.1——A区交巡警效劳平台管辖围的分配为各交巡警效劳平台分配管辖围，使其在所管辖的围出现突发事件时，尽量能在3分钟有交巡警〔警车的时速为60km/h〕到达事发地。即计算各交巡警效劳平台与各个地点的距离。将巡警在3分钟到达事发地转化为交巡警效劳平台距离事发地距离不超过3km。我们建立最短路模型：，，即求出离每个地点距离最短的交巡警效劳平台，将这个地点分配给距离最短的交巡警平台管辖。如何求每个地点之间的距离，我们运用了软件中的最短路函数——“〔〕〞函数。将题目中各节点坐标转化为矩阵，进而建立稀疏矩阵，然后利用最短路函数提取出符合3分钟路程要求的矩阵，最后进展整理，即可得所求。模型的求解：先用算法求解出各交巡警效劳平台到各个路口节点的最短距离，利用软件进展运算〔运算程序见一〕，代入数据,求得管辖围如下：表一A区各效劳平台的管辖围效劳平台节点编号管辖的节点11、42、44、79、8022、66、74、75、76、7833、43、54、55、68、7044、57、58、60、62、6355、49、5366、48、50、51、52、56、5977、30、3488、35、36、37、47、99、3210101111、25、26、2712121313、21、22、23、2414141515、311616、33、45、461717、40、411818、71、72、77、84、85、87、88、89、911919、64、65、67、69、73、82、832020、81、86〔原始表格见二〕把出警时间不超过3分钟，转化为效劳平台距离所管辖的路口距离不超过3千米。由此检验得六个路口〔28，29，38，39，61，92〕不满足出警时间要求。到达最近的交巡警效劳平台的时间超过3分钟的6个路口如下表：路口标号282938396192归属标号1515162720距离47.58150.00534.05936.82241.90236.013问题1.2——A区交巡警效劳平台警力调度方案对于重大突发事件，需要调度全区20个交巡警效劳平台的警力资源，对进出该区的13条交通要道实现快速全封锁。要求得该如何分配警力资源封锁路口我们使用0-1整数规划模型。设表示第个交巡警效劳平台调度到第j个交通路口的情况，即：其中根据对问题的分析，要实现对要道的快速全封锁，所以模型的目标是使封锁所有要道的总时间最短，其关键在于控制封锁要道所需时间最长的效劳平台的出警时间，使之到达最小值。设表示封锁要道所需时间最长的效劳平台的出警时间Aij表示20个交警平台到13个交通路口的距离封锁要道所需时间最长的效劳平台的出警时间最短：min；在13个交通路口上，每个路口都必须有一个交巡警：；每个交巡警效劳平台至多只能去一个路口：；每个交巡警到达路口的距离均小于最后一个到达路口的交警平台与该路口的距离：。建立模型如下：目标函数：min;：模型的求解：我们利用lingo软件进展目标函数的求解。主程序如下：〔具体程序见三〕由程序结果可得如下表格：封锁方案表格距离〔km〕节点走向时间〔m〕距离〔km〕节点走向时间〔m〕①2.476→482.47⑦2.608→162.60②3.105→303.10⑧5.409→105.40③8.01.7→298.01⑨7.7010→227.70④4.7015→284.70⑩3.8011→243.80⑤3.982→383.98⑾6.7416→146.74⑥0.354→620.35⑿3.2614→213.26=13\*GB2⒀012→120下列图是所求得各巡逻点到个路口的时间表：取其中的最大值为8.01546.故控制封锁要道所需时间最短约为8.01分钟。问题1.3——拟增A区交巡警效劳平台对于拟增A区交巡警效劳平台，首先分析现有的交巡警效劳平台的分布，发现存在交巡警效劳平台工作量不均衡和局部交通路口出警时间过长的问题。这就要求新增加几个效劳平台后，使得各个交巡警效劳平台的工作量尽可能一样以及使各个交通路口出警时间都被控制在3分钟。新建效劳平台需要本钱，所以需要合理确定效劳平台的选址，使需要建立的效劳平台的数目最小。由此，我们参考集合覆盖模型〔在一定的区域，设置最小数量的设施来覆盖其中所有的点〕，建立了一个两目标0-1整数规划模型。〔见四〕目标函数：约束条件：(i=1,2,…,92=1,2,…,92)且每个交通路口都有一个平台管辖：所有平台到其所管辖的交通路口最短距离中的最大值不超过距离偏差,即各个交通路口出警时间都被控制在3分钟：(i=1,2,…,92j=1,2,…,92)模型的求解：第三个子问题所建立的是双目标的0-1整数规划模型，第一目标为增加的效劳平台最少，第二目标为各个效劳平台每天的效劳强度方差最小。为了求解模型，先只考虑第一目标，然后再在第一目标最优的情况下给出第二目标最优的解。在lingo软件中运行程序，从24至30围取出假设干个偏差限与所对应的目标函数值。由结果，增加5个平台，标号与坐标分别为：29〔246,337〕;39〔371,333〕;48〔315,374〕;51〔348.5,380.5〕;88〔444.5,383〕由于该模型发案率的均衡性不是很好，增加的5个平台不一定是划分A区的最优解。因此要进展进一步的分析处理。将25个平台代入1.1的模型中，与原A区的划分结果相比拟〔以dij>30的节点个数的多少为标准〕，逐个去掉平台个数，再重复以上操作，最终得出结果。使用和求A区偏差限一样的方法分别确定增加5个平台、4个平台、3个平台时的偏差限，即最好均衡性分别为1.9、1.85、1.85，并设计表格进展比照，表格如下：增加的点数均衡性最优解时间超过3分钟的路口数增加的平台51.9886.25545293948518841.85954.690942939488831.851170.1714293948权衡均衡性、最优解及增加点个数所需花费的资源，增加四个点数是最节省资源且效果最好的。故：交巡警效劳平台增加四个，它们分别为：A29A39A48A88六、模型的评价6.1模型的优点：对于问题一的第一个子问题：题目规定以最短时间为目标，可转化为最短距离不超过3km。可是对于有一些节点，无论怎样安排都不能到达警方到达事故现场为3分钟之。我们对于这些节点单独处理，并根据条件计算出这几个节点应该属于哪个交巡警效劳平台。对于问题一的第三个子问题：该问题要求确定增加2-5个交巡警效劳平台的方案。一方面，根据限制条件，巡警到达其管辖节点应在3分钟之。另一方面，应平均合理安排各个交巡警效劳平台的工作量，不至于出现*个效劳平台工作量过大而*个平台工作量过小的情况。6.2模型的缺点：对于问题一的第一个子问题，建立的模型目标单一，并没有考虑到各个效劳平台交巡警工作梁的不均衡性。在分配结果中可以看到，局部交巡警的工作量很小而局部交巡警的工作量很大。这显然是不合理的。事实上，可以建立一个多目标规划问题，以交巡警到达事故现场和工作量的方差为目标，使得分配管辖围的方案更加合理。七、模型的推广本文所提供的模型可以推广到任何一个市区甚至更广围的交巡警效劳平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会效劳部门的选址问题。在实际运用中有很高的实用性及通用性。八、参考文献[1]殷代君，广义最大覆盖模型在应急设施选址中的应用研究，中外企业家，2010年第3期：169-170,2010。[2]卓金武，MATLAB在数学建模中的应用，：航空航天大学，2011。[3]中庚，数学建模方法及其应用，：高等教育，2009。[4]金星，薛毅，优化建模与lingo软件，：清华大学，2005。一：function[list,AdjMatri*,distance]=getList()edge=csvread('edge.csv');range=size(edge);%删除非A区的边fori=range:-1:1if(edge(i,1)>92)||(edge(i,2)>92)edge(i,:)=[];endendnode=csvread('node.csv');S=edge(:,1);%起点向量E=edge(:,2);%终点向量range=size(S);W=zeros(range,1);%权向量fori=1:1:rangea=[node(S(i,1),1),node(S(i,1),2)];b=[node(E(i,1),1),node(E(i,1),2)];distance=norm(a-b);W(i,1)=distance;end%建立稀疏矩阵AdjMatri*=sparse([S;E],[E;S],[W;W],92,92);%求最短路径矩阵distance=graphallshortestpaths(AdjMatri*,'directed',false);%提取出符合3分钟路程要求的矩阵A=distance(1:20,21:92);[rangeI,rangeJ]=size(A);fori=1:1:rangeIforj=1:1:rangeJifA(i,j)>30A(i,j)=NaN;endendend%整理list=zeros(72,1);fori=1:1:72Ma*=0;R=NaN;forj=1:1:20ifA(j,i)>Ma*Ma*=A(j,i);R=j;endendlist(i,1)=R;endT=linspace(1,20,20)';list=[T;list];end三：title0--1;sets:p/1..13/:a;l/1..20/:b;link(l,p):c,d;endsetsdata:d=222.36,160.28,92.87,192.93,210.96,225.02,228.93,190.01,195.16,120.83,58.81,118.50,48.85,204.64,141.30,73.88,173.95,191.97,206.03,211.21,172.29,177.44,103.11,39.82,103.10,60.35,183.52,127.67,60.26,160.32,178.35,192.41,190.09,151.17,156.32,82.00,60.94,81.98,43.93,219.97,150.09,82.67,182.73,200.76,214.82,226.54,162.27,155.35,81.03,48.61,73.96,3.50,176.28,129.70,62.28,162.35,177.50,191.55,182.85,113.07,106.15,31.83,94.21,24.76,52.55,176.59,130.00,62.59,162.65,177.80,191.86,183.16,113.37,106.46,32.14,94.52,25.06,53.37,149.15,109.01,41.60,141.66,150.36,164.42,155.72,85.70,80.15,5.83,73.53,12.90,79.92,140.93,94.34,26.92,126.99,142.14,156.19,147.50,102.28,104.93,30.61,58.85,30.99,86.77,130.11,82.74,15.33,115.39,131.32,145.38,136.68,97.76,107.24,34.92,47.26,41.99,93.37,75.87,127.76,69.57,95.11,77.08,91.13,82.44,141.95,151.44,79.11,101.50,86.19,147.61,37.91,83.37,113.95,50.72,32.70,46.75,38.05,186.33,195.82,123.50,145.88,130.57,191.99,0.00,119.50,145.43,86.85,68.83,64.77,35.92,217.81,227.30,154.98,177.36,162.05,223.47,59.77,59.73,127.15,27.08,9.06,5.00,23.85,228.08,237.57,165.25,161.21,172.32,213.32,119.50,0.00,67.42,32.65,50.68,64.73,83.59,180.50,189.17,114.84,101.48,121.91,153.59,170.30,132.98,65.56,165.63,171.51,185.56,176.87,47.52,57.01,44.01,97.50,51.09,118.10,145.43,67.42,0.00,100