2011数学建模B题标准答案

交巡警服务平台的设置与调度姓名：谢云龙3120130911130刘星3120130911121段狄臻3120130911124指导老师：付晓舰1交巡警服务平台的设置与调度摘要本文通过建立整数规划模型，解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题；通过建立线性加权评价模型定量评价了某市现有交巡警服务平台设置方案的合理性，并根据各个区对服务平台需求量的不同，提出了重新分配全市警力资源的解决方案。在计算交巡警服务平台到各个路口节点的路程时，使用了图论里的floyd算法。针对问题一的第一个子问题，首先假设交巡警服务平台对某个路口节点的覆盖度是二元的，引入决策变量，建立了0-1整数规划模型。交巡警出警应体现时间的紧迫性，所以选择平均每个突发事件的出警时间最短作为目标函数，运用基于MATLAB的模拟退火算法进行求解，给出了中心城区A的20个服务平台的管辖范围，求得平均每个案件的出警时间为1.013分钟。针对问题一的第二个子问题，为了实现对中心城区A的13个交通要道的快速全封锁，以最短的封锁时间为目标，建立了0-1整数规划模型，利用lingo软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对13个交通要道实现全封锁最短需要8.02分钟。问题一的第三个子问题是交巡警服务平台的选址问题。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加最少的服务平台数和服务平台工作量方差最小为目标，采用集合覆盖理论，建立了双目标0-1整数规划模型，用基于MATLAB的模拟退火算法求解出增加的服务平台数为4个，新增的服务平台具体位置为A28,A40,A48,A88，并得到各个服务平台的工作强度方差为2.28。针对问题二的第一个子问题，通过建立线性加权评价模型定量评价了该市现有交巡警服务平台设置方案的合理性，结果发现全市服务平台覆盖率较低且各个区的工作量不均衡，得出全市服务平台的布局存在明显的不合理的结论。并确定各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为各区域对交巡警需求的指标，然后根据各个区对服务平台需求量的不同，提出了较为合理的分配全市警力资源的解决方案。对于问题二的第二个子问题，以围堵范围最小和调动警力最少的原则，通过分析案发后嫌疑犯可能到达的位置，给出了围堵方案。关键词：交巡警服务平台0-1整数规划模拟退火法2一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型假设（1）每个交巡警服务平台的职能和警力配备基本相同；（2）警车的行驶速度恒定，不考虑实际交通状况的影响；（3）交巡警服务平台接到报警后能立即出警，中间没有延误；（4）每个节点只能被一个服务平台管辖；（5）一个平台的警力最多封锁一个路口。3三、符号说明ijx服务平台iA管辖第j个路口节点的决策变量；ijt在中心城区A中，从第i个服务平台到第j个交叉路口节点的最短时间；jw中心城区A的第j个交叉路口节点的发案率；1T在中心城区A内平均每个案件的出警时间；2T在中心城区A内封锁13个出入城区的路口节点的最短时间；J中心城区A的13个出入城区的路口节点标号的集合；iq第i个服务平台的工作强度；k第k区分配的服务平台资源比率。四、问题分析在城市规划中，交巡警服务平台的布局是一项非常重要的内容。长期以来，由于种种原因，目前的城市建设大多对警务资源的规划缺乏科学性。交巡警服务平台的选址、管辖区域的划分多依据经验进行，大多数城市均不同程度地存在服务平台布局不合理、管辖范围分配不均、警务资源调度困难等问题。另外，警务资源常常是有限的，设置交巡警服务平台也需要大量成本。所以更有效地分配和调度警务资源对于城市的长治久安有着重要的意义。本文着力解决的是合理地确定交巡警服务平台的数量及其位置，合理分配各平台的管辖范围以及当重大突发事件发生时快速有效地调度警务资源这三方面的问题。（1）对于问题一：在问题一中又有三个子问题需要解决。第一是要对中心城区A的20个现有交巡警服务平台分配管辖范围。首先假设每个交叉路口节点要么被其中一个服务平台完全管辖，要么被完全不管辖，即覆盖度是二元的，所以考虑到用0-1整数规划模型。要使得案发后的损失减低到最小，就要求警方在接到报警后能在最短的时间内到达事故现场。这样就确定了平均每个突发事件警方出警时间的目标函数。第二是当重大突发事件发生后，要对中心城区A的20个交巡警服务平台的警力资源进行调度，从而对进出该区的13条交通要道实现快速全封锁。同样考虑使用0-1整数规划模型。因为要求对交通要道实现全封锁，所以问题的关键是合理调度警务资源使得封锁全部要道所需的总时间达到最小，也就是使得出警时间最长的服务平台所需的时间尽可能的小。第三是针对现有的中心城区A的20个交巡警服务平台进行分析后，需要新增加2~5个服务平台以解决工作量不平衡和部分路口节点出警时间过长的问题。这属于交巡警服务平台选址问题。一方面考虑采用集合覆盖模型[1]，目的是在满足所有节点3分钟内都有警方到达的条件下，使新增设的服务平台数目尽可能得小，从而降低了建设成本。另一方面也要考虑新增设服务平台后，能够解决服务平台工作量不平衡的问题，所以把尽可能均衡各个服务平台工作量作为第二个目标。因此考虑需要建立一个两目标的0-1整数规划模型。（2）对于问题二：问题二中有两个问题需要解决，一是根据已有的数据，评价全市六个区内现有的交巡警服务平台的数目和布局的合理性，如果不合理就给出解决方案；二是当该市P处发生重大刑事案件时，调度全市警力资源设计出最佳的围堵方案。4对于第一个小问题，要先按照设置交巡警服务平台的原则和任务，对全市的交巡警服务平台的数目和布局讨论其合理性。交巡警服务平台的选址应遵循尽量使每个交巡警服务平台的工作量基本均衡和每个节点突发事件发生时在3分钟内有警力到达的原则。所以选用各个服务平台平均每天的工作强度（平均每天处理的突发事件数）的方差和服务平台的覆盖率（区域内3分钟内有警方到达事发地的节点占区域内总结点的比率）为指标来进行评价。如果在全市范围内现有交巡警服务平台设置方案存在明显的不合理性，那么可能存在如下两种原因：第一，该市分配给各个区的交巡警服务平台比率不合理；第二，各个区内的交巡警服务平台选址方案不合理。对于第二种原因，在第一问第三个子问题中对A区交巡警服务平台设置方案已经做过详细讨论，可推广到其他几个区中。现在设法解决由第一种原因引起不合理性的问题。据此，我们提出了依据各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为三个评判指标，在全市范围内重新分配警力资源，也就是重新分配每个区服务平台数量的解决方案。对于第二个小问题，首先分析出，在案发后的3分钟内，警方还未接到报警，即使嫌疑人开车驶过服务平台，警方不能识别出嫌疑人；而3分钟后警方已接到报警，设此时警方掌握了足够证据，故可以假设3分钟后只要警方与嫌疑人相遇就能够将其抓获。警方在接到报警后，根据嫌疑人可能逃跑的路径，可以估计出嫌疑人逃跑的大致范围，所以问题就转化为，投入最少的警力以最快的速度形成包围圈，并确保嫌疑犯在这段时间内无法跑出包围圈，即可认为围堵方案成功。五、模型的建立5.1问题一：（1）对于第一个子问题，考虑使用0-1整数规划模型，下面确定目标函数和约束条件。观察每个路口节点平均每天的发案率，发现发案率不是很大，所以追加假设为每个服务平台有足够的时间去处理管辖范围内的突发事件，即当某个服务平台处理一起突发事件的同时，在它所管辖的区域内不会发生其他的突发事件。设问题的决策变量为ijx是0-1变量，即1,A0,iijjAx当中心城区的第个节点事发时，由服务平台管辖，否则1,2,,20;1,2,,92ij()为了及时高效地处理突发事件，警方到达事发地应争分夺秒，在满足时间紧迫性要求的前提下，使得平均每个案件的出警时间最短，所以确立了平均每个案件的出警时间最短作为唯一的目标。然后确定了两个约束条件，一是当每个路口节点有突发事件发生时，都至少有一个服务平台的交巡警到达现场处理事件；二是要求任一服务平台到达其所管辖的路口节点的时间都小于3分钟。于是问题就转化为求下面的0-1整数规划问题：2092111921min,jijijijjjwtxTw52011(1,2,,92);..3(1,2,,20;1,2,,92)ijiijijxjsttxij（2）对于第二个子问题，我们仍考虑使用0-1整数规划模型。用kijx表示决策变量，即1,0,kikijAjx服务平台到第个出入口节点封锁交通要道;否则其中1,2,,20ikjJ1,2,,13k根据对问题的分析，要实现对要道的快速全封锁，所以模型的目标是使封锁所有要道的总时间最短。所以关键在于控制封锁要道所需时间最长的服务平台的出警时间，使之达到最小值。确定了两个约束条件，其一是当每个路口节点有突发事件发生时，都至少有一个服务平台的交巡警到达现场处理事件；其二是一个平台的警力最多封锁一个路口。故，建立以下数学模型2minmax{},kijijTtx2011311,1,2,,13;..1,1,2,,20kkijiijkxkstxi（3）对于第三个子问题，首先分析现有的交巡警服务平台的分布，发现存在交巡警服务平台工作量不均衡和部分路口节点出警时间过长的问题。这时考虑新增加几个服务平台，使得各个交巡警服务平台的工作量尽可能相同以及使各个路口节点出警时间都被控制在3分钟内。新建服务平台需要成本，所以需要合理确定服务平台的选址，使需要建立的服务平台的数目最小。由此，我们参考集合覆盖模型，建立了一个两目标0-1整数规划模型。设增加交巡警服务平台后，平台总数为n。设平均每个交巡警服务平台的建设成本为1。对这一问题需要引入决策变量ija，设决策变量ija为1,0,ijijijtat3;31,2,,92;1,2,,92ij()定义服务平台的工作强度为平均每天处理的突发事件数，则记iq表示第i个服务平台的工作强度。集合覆盖模型中考虑了建立服务平台的成本，在给定3分钟到达事发地的条件下，其目标之一是建设成本最小。另一方面，考虑到要使得各个服务平台的工作量基本平衡，所以确定第二个目标为各个服务平台平均每天工作强度的方差最小。模型描述为69221minjjy2211min();niiSqqn