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

全国大学生数学建模竞赛全国大学生数学建模竞赛承承 诺诺 书书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西北大学参赛队员(打印并签名)：1.张舒岱 2.刘羽 3.张成悟指导教师或指导教师组负责人 (打印并签名)：日期：2014年8 月10 日全国大学生数学建模竞赛全国大学生数学建模竞赛编编 号号 专专 用用 页页评阅人评分备注赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要交巡警服务平台位置的选取以及划分交巡警服务平台的管辖范围对于处理突发事件有非常大的影响。现阶段，一般依据经验选取服务平台位置及划分管辖区域。所以如何科学合理处理的交巡警服务平台的设置与调度问题具有十分重要的现实意义。本文研究了交巡警服务平台的设置与调度问题。具体讨论了在给定的区域A 内，如何合理的设置交巡警服务平台的管辖区域；发生特殊事件时应如何调动服务平台警力以快速封锁区域 A；应该增加多少数量交巡警服务平台以及在哪个位置增加。本文建立最短路模型、0-1 整数规划模型，利用MATLAB软件解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题。在解决分配各平台管辖范围问题时，本文建立了最短路模型。通过求解各个路口到交巡警平台的距离是否满足最低时间限制，解决交巡警服务平台分配管辖范围的问题。本文在MATLAB软件上运用Dijkstra算法进行求解，给出了中心城区 A 的 20 个服务平台的管辖范围，并求得到达最近的交巡警服务平台的时间超过 3 分钟的 6 个路口。在解决调度警务资源快速封锁城区的问题时，本文建立了 0-1 整数规划模型。以封锁城区所用时间最少为限制条件，利用 lingo 软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对 13 个交通要道实现全封锁最短需要 8.01 分钟。在解决交巡警服务平台的选址问题时，本文建立了双目标 0-1 整数规划模型。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加服务平台数最小和服务平台工作量方差最小为目标，建立了双目标 0-1 整数规划模型。解出增加的服务平台数为 4 个，新增的服务平台具体位置为 A29,A39,A48,A88。本文所提供的模型考虑到均衡各个交巡警服务平台的工作量和新建服务台的成本，使结果更加合理符合需求，可以推广到任何一个市区甚至更广范围内的交巡警服务平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会服务部门的选址问题，对实际有指导意义。关键词：关键词：DijkstraDijkstra算法算法双目标双目标 0-10-1 整数规划模型整数规划模型 Lingo Lingo 编程编程一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。二、模型假设（1）每个交巡警服务平台的职能和警力配备基本相同；（2）警车的行驶速度恒定，不考虑实际交通状况的影响；（3）交巡警服务平台接到报警后能立即出警，中间没有延误；（4）每个节点只能被一个服务平台管辖；（5）一个平台的警力最多封锁一个路口。三、符号说明GV,E赋权连通图Di,j顶点 i 到顶点 j 的距离D顶点 i 到顶点 j 的距离0-1 整型变量第 i 个交巡警服务平台调度到第 j 个交通路口的情况；表示20个交警平台到13个交通路口的距离jxijAijcjdija封锁要道所需时间最长的服务平台的出警时间中心城区 A的第j个交叉路口节点的发案率；第 i 个交巡警服务平台到第 j 个交通路口的最短距离距离的偏差限四、问题分析交巡警服务平台位置的选取以及划分交巡警服务平台的管辖范围是一件非常重要的事情。由于种种原因，现在交巡警服务平台的选址及管辖区域划分大多根据经验进行。缺乏科学系统的位置选取与管辖区划分，造成了警务资源浪费、突发事件处理不及时等多种问题。另外，警务资源是有限的，设置交巡警服务平台也要耗费大量的资源。所以如何科学的规划管辖区，合理的设立新的交巡警服务平台具有重大的意义。本文意在根据现有的城区道路图与交巡警服务平台位置，根据到达突发事件地点使用时间最少原则进行交巡警服务平台管辖范围划分，根据使用资金尽量少及各交巡警服务平台的工作量尽量一致的原则设立新的交巡警服务平台。在问题一中有三个子问题需要解决。（1）要对 20 个交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。即计算各交巡警服务平台与各个地点的距离。将巡警在 3 分钟内到达事发地转化为交巡警服务平台距离事发地距离不超过3km。这是典型的最短路模型。对于这个问题，我们采用Dijkstra算法。（2）当重大突发事件发生后，要对中心城区 A 的 20 个交巡警服务平台的警力资源进行调度，对进出该区的 13 条交通要道实现快速全封锁，其关键在于合理调度警务资源使得封锁全部要道所需的总时间达到最小，也就是使得出警时间最长的服务平台所需的时间尽可能的小。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案，我们采用0-1 模型进行求解，给出该区交巡警服务平台警力合理的调度方案。（3）针对现有的中心城区 A 的 20 个交巡警服务平台进行分析后，需要新增加 25 个服务平台以解决工作量不平衡和部分路口节点出警时间过长的问题。这属于交巡警服务平台选址问题。一方面考虑采用集合覆盖模型，目的是在满足所有节点 3 分钟内都有警方到达的条件下，使新增设的服务平台数目尽可能得小，从而降低了建设成本。另一方面也要考虑新增设服务平台后，能够解决服务平台工作量不平衡的问题，所以把尽可能均衡各个服务平台工作量作为第二个目标。因此考虑需要建立一个两目标的 0-1 整数规划模型。五、模型的建立和求解问题问题 1.11.1A A 区交巡警服务平台管辖范围的分配区交巡警服务平台管辖范围的分配为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。即计算各交巡警服务平台与各个地点的距离。将巡警在 3 分钟内到达事发地转化为交巡警服务平台距离事发地距离不超过 3km。我们建立最短路模型：t 3min，s vt，v 60km/h即s 3000m求出离每个地点距离最短的交巡警服务平台，将这个地点分配给距离最短的交巡警平台管辖。如何求每个地点之间的距离，我们运用了MATLAB软件中的最短路函数“graphallshortestpaths（）”函数。将题目附件中各节点坐标转化为矩阵，进而建立稀疏矩阵，然后利用最短路函数提取出符合3分钟路程要求的矩阵，最后进行整理，即可得所求。模型的求解：模型的求解：先用Dijkstra算法求解出各交巡警服务平台到各个路口节点的最短距离，利用MATLAB软件进行运算（运算程序见附件一），代入数据,求得管辖范围如下：表一 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.21.2A A 区交巡警服务平台警力调度方案区交巡警服务平台警力调度方案对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。要求得该如何分配警力资源封锁路口我们使用 0-1 整数规划模型。设xij表示第i个交巡警服务平台调度到第 j 个交通路口的情况，即：j个交通路口0,第i个平台没有调度到第xijj个交通路口1，第i个平台调度到第其中i 1,2,20j 1,2,92根据对问题的分析，要实现对要道的快速全封锁，所以模型的目标是使封锁所有要道的总时间最短，其关键在于控制封锁要道所需时间最长的服务平台的出警时间，使之达到最小值。设表示封锁要道所需时间最长的服务平台的出警时间Aij表示 20 个交警平台到 13 个交通路口的距离封锁要道所需时间最长的服务平台的出警时间最短：min；在 13 个交通路口上，每个路口都必须有一个交巡警：xi120ij1j1.13；每个交巡警服务平台至多只能去一个路口：xj113ij1i 1.20；每个交巡警到达路口的距离均小于最后一个到达路口的交警平台与该路口的距离：xij Aiji 1.20j 1.13。建立模型如下：目标函数：min;20j 1.13xij1i113s.t：xij1i 1.20j1x A i 1.20ijijj 1.13模型的求解：模型的求解：我们利用 lingo 软件进行目标函数的求解。主程序如下：（具体程序见附件三）由程序结果可得如下表格：距离节点走向（km）2.476483.105308.01.7294.7015283.982380.35462下图是所求得各巡逻点到个路口的时间表：封锁方案表格时间距离（m）（km）2.472.603.105.408.017.704.703.803.986.740.353.260节点走向时间（m）2.605.407.703.806.743.26081691010221124161414211212取其中的最大值为8.01546.故控制封锁要道所需时间最短约为8.01 分钟。问题问题 1.31.3拟增拟增 A A 区交巡警服务平台区交巡警服务平台对于拟增 A 区交巡警服务平台，首先分析现有的交巡警服务平台的分布，发现存在交巡警服务平台工作量不均衡和部分交通路口出警时间过长的问题。这就要求新增加几个服务平台后，使得各个交巡警服务平台的工作量尽可能相同以及使各个交通路口出警时间都被控制在 3 分钟内。新建服务平台需要成本，所以需要合理确定服务平台的选址，使需要建立的服务平台的数目最小。由此，我们参考集合覆盖模型（在一定的区域内，设置最小数量的设施来覆盖其中所有的点），建立了一个两目标 0-1 整数规划模型。（见附件四）目标函数：约束条件：min cjdijxiji1j19292j个交通路口0,第i个平台没有调度到第xij1，第i个平台调度到第j个交通路口(i=1,2,92j=1,2,92)且xjj122xjj 25j192每个交通路口都有一个平台管辖：xi192ij1所有平台到其所管辖的交通路口最短距离中的最大值不超过距离偏差a,即各个交通路口出警时间都被控制在 3 分钟内：max(模型的求解：模型的求解：第三个子问题所建立的是双目标的 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 区的划分结果相比较（以 dij30 的节点个数的多少为标准），逐个去掉平台个数，再重复以上操作，最终得出结果。使用和求 A 区偏差限相同的方法分别确定增加 5 个平台、4 个平台、3 个平台时的偏差限，即最好均衡性分别为1.9、1.85、1.85，并设计表格进行对比，表格如下：d*x)aijij (i=1,2,92 j=1,2,92)增加的点数均衡性最优解时间超过 3 分钟的路口数增加的平台51.9886.2554529 39 48 51 8841.85954.6909429 39 48 8831.851170.171429 39 48权衡均衡性、最优解及增加点个数所需花费的资源，增加四个点数是最节省资源且效果最好的。故：交巡警服务平台增加四个，它们分别为：A29 A39 A48 A88六、模型的评价6.1 模型的优点：（1）对于问题一的第一个子问题：题目规定以最短时间为目标，可转化为最短距离不超过 3km。可是对于有一些节点，无论怎样安排都不能达到警方到达事故现场为 3 分钟之内。我们对于这些节点单独处理，并根据已知条件计算出这几个节点应该属于哪个交巡警服务平台。（2）对于问题一的第三个子问题：该问题要求确定增加 2-5 个交巡警服务平台的方案。一方面，根据限制条件，巡警到达其管辖节点应在 3 分钟之内。另一方面，应平均合理安排各个交巡警服务平台的工作量，不至于出现某个服务平台工作量过大而某个平台工作量过小的情况。6.2 模型的缺点：对于问题一的第一个子问题，建立的模型目标单一，并没有考虑到各个服务平台交巡警工作梁的不均衡性。在分配结果中可以看到，部分交巡警的工作量很小而部分交巡警的工作量很大。这显然是不合理的。事实上，可以建立一个多目标规划问题，以交巡警到达事故现场和工作量的方差为目标，使得分配管辖范围的方案更加合理。七、模型的推广本文所提供的模型可以推广到任何一个市区甚至更广范围内的交巡警服务平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会服务部门的选址问题。在实际运用中有很高的实用性及通用性。八、参考文献1殷代君，广义最大覆盖模型在应急设施选址中的应用研究，中外企业家，2010 年第 3 期：169-170,2010。2卓金武，MATLAB 在数学建模中的应用，北京：北京航空航天大学出版社，2011。3韩中庚，数学建模方法及其应用，北京：高等教育出版社，2009。4谢金星，薛毅，优化建模与 lingo 软件，北京：清华大学出版社，2005。附件一：function list,AdjMatrix,distance=getList()edge=csvread(edge.csv);range=size(edge);%删除非A区的边for i=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);%权向量for i=1:1:range a=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%建立稀疏矩阵AdjMatrix=sparse(S;E,E;S,W;W,92,92);%求最短路径矩阵distance=graphallshortestpaths(AdjMatrix,directed,false);%提取出符合3分钟路程要求的矩阵A=distance(1:20,21:92);rangeI,rangeJ=size(A);for i=1:1:rangeIfor j=1:1:rangeJif A(i,j)30 A(i,j)=NaN;endendend%整理list=zeros(72,1);for i=1:1:72 Max=0;R=NaN;for j=1:1:20if A(j,i)Max Max=A(j,i);R=j;endend list(i,1)=R;endT=linspace(1,20,20);list=T;list;end附件三：附件三：title 0-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.07,118.09,132.15,151.00,113.08,121.75,47.43,34.06,54.50,86.17,218.92,149.03,81.62,181.68,199.71,213.77,225.49,186.57,195.24,120.92,47.56,127.99,78.21,242.47,185.14,117.73,217.79,235.82,249.88,249.04,210.12,215.27,140.94,83.67,136.99,67.34,225.47,169.61,102.20,202.26,220.29,234.35,232.04,193.12,198.26,123.94,76.39,119.99,50.34,269.46,212.13,144.71,244.78,262.81,276.86,276.03,230.11,223.19,148.87,110.66,141.80,64.49;enddatamin=max(link(i,j):c(i,j)*d(i,j);for(link(i,j):bin(c(i,j);for(p(j):sum(l(i):c(i,j)=1);for(l(j):sum(p(i):c(j,i)=22;sum(a(i):x(i,i)=25;for(a(i):sum(a(j):x(i,j)=1);for(a(i):for(a(j):(x(i,j)*d(i,j)29);for(a(j):sum(a(i):x(i,j)=if(x(j,j)#eq#0,0,sum(a(i):x(i,j);for(type(i):x(i,i)=1);data:d=ole(G:/short.xls,data1);c=ole(G:/short.xls,data2);enddataenddata1为92*92的两两节点的最短距离，data2为92个节点的发案率。